Algorithm for the simplification of solution to discrete optimization problems
Journal Title: Восточно-Европейский журнал передовых технологий - Year 2018, Vol 3, Issue 4
Abstract
<p>Typically, the search for solutions in discrete optimization problems is associated with fundamental computational difficulties. The known methods of accurate or approximated solution of such problems are studied talking into consideration their belonging to so-called problems from <strong>P</strong> and <strong>NP</strong> class (algorithms for polynomial and exponential implementation of solution). Modern combinatorial methods for practical solution of discrete optimization problems are focused on the development of algorithms which allow obtaining an approximated solution with guaranteed evaluation of deviations from the optimum. Simplification algorithms are an effective technique of the search for solutions to an optimization problem. If we make a projection of a multi-dimensional process onto a two-dimensional plane, this technique will make it possible to clearly display a set of all solutions to the problem in graphical form. The method for simplification of the combinatorial solution to the discrete optimization problem was proposed in the framework of this research. It is based on performance of decomposition of a system that reflects the system of constraints of the original five-dimensional original problem on a two-dimensional plane. This method enables obtaining a simple system of graphic solutions to a complex problem of linear discrete optimization. From the practical point of view, the proposed method enables us to simplify computational complexity of optimization problems of such a class. The applied aspect of the proposed approach is the use of obtained scientific results in order to provide a possibility to improve the typical technological processes, described by systems of linear equations with existence of systems of linear constraints. This is a prerequisite for subsequent development and improvement of similar systems. In this study, the technique for decomposition of a discrete optimization system through projection of an original problem on two-dimensional coordinate planes was proposed. In this case, the original problem is transformed to a combinatorial family of subsystems, which makes it possible to obtain a system of graphic solutions to a complex problem of linear discrete optimization.</p>
Authors and Affiliations
Sergii Chernov, Sergiy Titov, Lyudmila Chernova, Viktor Gogunskii, Liubava Chernova, Kateryna Kolesnikova
Keywords
Related Articles
- EP ID EP527978
- DOI 10.15587/1729-4061.2018.133405
- Views 66
- Downloads 0
Development of adaptive fuzzy-logic device for control under conditions of parametric non-stationarity
<p>We studied an automatic control system with the fuzzy adaptive device for setting parameters of the PI-controller under conditions of non-stationarity of parameters of the control object’s model. The relevance of pres...
Investigation of the properties of Ni(OH)2 electrochrome films obtained in the presence of different types of polyvinyl alcohol
<p class="1">Electrochromic films were prepared by cathodic template synthesis in the presence of two types of polyvinyl alcohol: with the hydrolysis degree of 99 % and 85 %. The prepared films show differences in struct...
Development of test operations of different duration in terms of input for the verification of efficiency formula
<p>Determining an indicator for the estimation of effectiveness of system operations is an important stage for optimization of technological processes of any enterprise. This step predetermines the established mode of fu...
The model to optimize deliveries of perishable food products in supply chains
<p>The probabilistic-statistical analytical model of optimizing the supply of perishable food products (PFPs) has been improved. The demand for PFPs is effectively satisfied by introducing into supply chain systems a pos...
Iterative hard-decision decoding of combined cyclic codes
<p>We propose error correction iteratively decodable cyclic codes (IDCC) that consist of two cyclic Hamming codes with different generator polynomials. As a mathematical apparatus, we apply the theory of linear finite-st...