The article discusses the formulation of an optimization problem with a quadratic target function and additional constraints on the permutation set, which can be a model of many applied problems. An algorithm for solving an optimization problem with a quadratic target function and additional constraints on permutations is proposed. During the implementation of the method the first reference plan is found and additional restrictions for it are checked at the first stage. Thus, in the beginning of the algorithm, the number of considered solutions decreases. This makes it possible at the first stage to reduce the number of possible solutions and narrow the area of the problem study. An example of solving a theoretical problem using this method, demonstrating its effectiveness, is proposed. Such task can be used to modeling various technological processes. The reason for this is the optimization of mathematical models and algorithms for the proposed models.
Computer simulation of technological processes consists in optimization of the study
object by a mathematical model, and further model study with the help of
implemented computational algorithms on personal computers. The computer simulation
process, as a single process of building and researching a model, is used for research,
analysis, design and optimization of technological objects and systems [
Computer modeling is the process of building a real study object's model and
setting up computational experiments on this model in order to understand and evaluate
various strategies based on the use of algorithms that ensure the functioning of this
study object. Thus, the process of computer simulation includes the model design, and
its application to solve the problem of optimization and design of technological
processes in production. All these problems are extremely complex and include numerous
elements, variables, parameters, constraints, etc. Such problems can be modeled by
combinatorial optimization tasks [
The combinatorial optimization problems study comprises a fairly wide range of
mathematical models associated with the need to solve various important practical
problems of optimal planning, management and design [
The paper presents a model of optimization problems on a combinatorial set of permutations, which is a model of many applied problems. It is proposed the algorithm for solving an optimization problem with a quadratic target function and additional restrictions on permutations.
During the method's implementation the first reference plan is located and additional restrictions are checked, which reduces the number of considered solutions at the beginning of the algorithm
It is offered an example of solving a theoretical problem by the given method and demonstrating its efficiency. 2
Computer models have become a common tool for mathematical modeling and are used in various areas of electronics, engineering, industry, and so on. Computer models are used to obtain new knowledge about the object or for an approximate assessment of the system’s behavior that are too complex for analytical research.
Computer modeling is one of the effective methods for studying complex systems.
The construction of a computer model is based on abstracting from the specific nature
of the phenomena or the original object under study and consists of two stages – first,
the creation of a qualitative, and then a quantitative model. The more significant
properties will be identified and transferred to the computer model – the more
approximate it will be to the real model, the greater the capabilities that the system
using this model will have. Today the works of many scientists are devoted to this
research area [
An important computer simulation area is analytical and simulation modeling. In
analytical modeling, mathematical (abstract) models of a real object are studied in the
algebraic equations form, as well as providing for the implementation of an
unambiguous computational procedure leading to their exact solution. In simulation,
mathematical models are studied in the algorithms form, which reproduce the
functioning of the system under study by sequentially performing numerous
elementary operations. Very relevant today for simulation and analytical modeling are
discrete models, in particular, combinatorial optimization, their study is the subject of
a great number of papers [
A significant contribution to the development of modern discrete optimization theory, the development and implementation of its methods in the study and solving of important applied problems have been made over the course of more than forty years under the scientific guidance of Academician I.V. Sergienko scientists of the Institute of Cybernetics named by V.M. Glushkov National Academy of Sciences of Ukraine. They obtained important results, which became the basis for the theory development and the creation of n lines in discrete optimization.
At present, intensive studies of the stability problems of vector discrete
optimization problems are carried out at the Institute of Cybernetics named by V.M.
Glushkov of the National Academy of Sciences of Ukraine (I.V. Sergienko, T.T.
Lebedev, N.V. Semenova, T.I. Sergienko) [
Belarusian scientists under the scientific guidance of Professor V.O. Yemelycheva successfully develops a constructive approach to the problem of the vector discrete optimization problems correctness associated with the reception of quantitative characteristics of the stability of specified problem statements, a mathematical apparatus for studying the stability of multicriteria discrete problems with different types, vector criteria functions, principles of optimality, as well as generalized and parameterized principles of optimality are developed.
It is important to study the relation between different classes of point
configurations triangulation (regular, weakly regular, deployed, symmetric, political,
etc.), in particular, the study of the structure of a partially ordered set constructed on
the family of triangulation classes considered in relation to the inclusion relation.
Recently, algorithms for solving convex polyhedral admissibility problems are
actively explored [
Applied problems simulated by extreme discrete tasks often have a high dimensionality, so they are quite complex from a computational point of view. The main task is to determine the value of an argument belonging to a certain combinatorial configuration for which the target function acquires the global optimum. So it is necessary to develop the most effective algorithm, which is based on the specific properties of the combinatorial configurations.
For the extreme problems of combinatorial optimization, polynomial algorithms for finding an optimal solution based on the properties of the input data structure have been developed, but there are few such work compared to methods based on partial overview of the options. One of the approaches to solving such problem is to carry out research and analysis of the combinatorial configurations properties, in which the target function, which reflects the combinatorial nature of the tasks, is determined. Analysis and study of combinatorial configurations as a target function argument, setting the change in the values of the target function, depending on the elements ordering of the selected combinatorial configuration and the structure of the input data specificity, does not pay sufficient attention in the literature. But it should be noted that the study of the certain tasks properties in order to identify their characteristic properties and their use for solving the problem, gives the possibility of constructing new approaches and the development of known methods.
Hence, one of the important problems in the discrete optimization area is the detection of the properties of combinatorial configurations in extreme problems, the use of which would allow to establish the regularity of the change in the values of the target functions, depending on the argument ordering and on the specificity and structure of the combinatorial configurations sets.
Today, significant results have been obtained in the area of research of
combinatorial models' various classes and the development of new methods for their
solution. The following foreign scientists made a fundamental contribution to the
development of discrete, in particular, combinatorial optimization: M. Gary, S. Berge,
D. Johnson, H. Papadimitriou, P. Pardalos, K. Staiglich, R. Stanley, F. Harari, V.A.
Emelichev, V.M. Sachkov [
In turn, the many Ukrainian scientists' works are devoted to the various classes of combinatorial optimization problems' study: L.F. Gulyanitsky, P.I. Stetsyuka, I.V. Sergienko, N.S. Shor, Yu.G. Stoyan, S.V. Yakovlev, A.O. Yemetsa, V.O. Perepelitsy and many others.
In particular, in [
Quadratic optimization on the permutation set is reflected in [
The permutation set's representation as the intersection of a permutation
polyhedron and a hypersphere is interesting, as well as optimization methods on
permutation configurations using the intersection described in [
The development of an integrated approach to the analysis of the properties of combinatorial optimization supplies covers a wide range of studies of combinatorial functions, combinatorial polyhedral, combinatorial configurations as an argument of the target function. The results give the opportunity to improve existing methods for solving such problems and develop new methods for optimal solutions searching. The problems based on the properties of combinatorial configurations are actual problems of combinatorial optimization. Of particular importance in this aspect is the consideration of extreme problems in combinatorial configurations using graph theory.
The research of tasks in graphs deals with such scientists as F. Harari, O. Ore, I.V. Sergienko, V. O. Yemelichev, A. O. Zikov, V. O. Perepelytsya, R. I. Tyshkevich and others. Despite quite large achievements in the area of discrete optimization, in the process of modeling, there are extreme problems classes for which a number of issues have not yet been investigated. Principal difficulties that arise during modeling are also related to various types of uncertainty. These include: the availability of many criteria for evaluating the quality of solutions, interval setting of task parameters, etc. In these conditions, classical methods are not sufficiently suitable for solving problems. As you know, most combinatorial optimization tasks can be reduced to integer programming tasks, but this is not always justified, since it eliminates the possibility of taking into account the combinatorial properties of task solutions.
This work is a continuation of research in the extreme discrete problem’s area, in particular, combinatorial optimization, as well as optimization problems under the conditions of multicriteria, which arise in the study of many theoretical and applied problems. 3
We consider the permutation as an ordered sample of elements a (ai1 , ai2 ,..., aik ) ,
where ai j A , i j Nn , j Nn is it if s t s Nn , t Nn from some
multi-set A {a1, a2 ,..., aq} , which is characterized by the base S ( A) {e1, e2 ,..., ek } ,
where
e j R1, j Nk
and the
multiplicity of the elements
k (e j ) rj ,
j Nk , r1 r2 ... rk q j Nk , according to [
A set of permutations with repetitions of n real numbers, among which k different, is called the general permutation set and is denoted as Pnk ( A) . This is the set of ordered n-samples from the multiset A under the condition n q k .
If we have n k q set of permutations without repetition, we denote it as P . n Obviously, Pn ( A) Pnn ( A) . In cases where the form of the set of permutations is not indicated, it will be possible to write down these sets as P( A) .
It is known [
Without loss of generality, we order the elements of the multiset A in nondescending order: a1 a2 ... aq and the elements of its foundation –in descending order: e1 e2 ... ek .
Then the convex hull of a common set of P( A) permutations is a generic polyhedron ( A) conv P( A) , that is described by a well-known system of linear inequalities: j Nn , j t , j t, j, t Ni , i Nn and P( A) vert ( A) .
Consider the optimization problem: n n x j a j , j1 j1 i i xj a j , j1 j1 Z (, P( A)) : max{(a) | a P( A)}
D {x R n | Gx ()b} where G R mn , b R m
n n n (a) c j x 2j aij xi x j
j1 i1 j1 on a set of permutations Pn ( A) .
Additional linear constraints form a multifaceted set D R n .
Then, to every point a Pn ( A) will match point x X , one that satisfies equality F (x) (a) :
Z (F , X ) : max{F (x) | x X }
n n n where, F (x) c j x 2j aij xi x j
j1 i1 j1 and additional constraints:
D {x R n | Gx ()b} (1) (2) (3) (4) (5) (6)
X - nonempty set in R n , which is defined as follows:
X vert ( A) , conv P( A) (8)
It is natural to assume that the maximum of a quadratic function will be one of the vertices of the permutation polyhedron, and the vertices of the graph G(Pn ) will match to all points of the set of permutations Pn ( A) .
The adjacency of the vertices of a permutation polyhedron is determined by a
onetime transposition of two vertex elements. The number of transpositions in the graph
is determined by the formula [
The algorithm for finding the problem optimal solution consists of four steps, which in a few steps make it possible to obtain an optimal solution.
STEP 1. Finding the first support solution.
Consider the first transposition of the target function: x1 x2 , (i 2,..., n) : f12 (x1 x2 )(a1x1 a1x2 ... an2 xn ) We form the necessary conditions for finding the first solution: x1 x2 , xi max, (max ai ).
Variants of transpositions: x1 x2 , (i 2,..., n) : f12 (x1 x2 )(a1x1 a1x2 ... an2 xn ) x1 x3 : f13 (x1 x3 )(a13 x1 a23 x2 ... an3 xn )
… … … x1 xn : f1n (x1 xn )(a1n x1 a2n x2 ... ann xn ) x2 xi , (i 3,..., n); (9) (10) (11) … … … … … … x2 x3 : f 23 (x2 x3 )(a12 x1 a22 x2 ... an2 xn ) x2 xn : f 2n (x2 xn )(a1n x1 a2n x2 ... ann xn ) xn1 xn : f n1n (xn1 xn )(a1n1 x1 a2n1 x2 ... ann1 xn )
The first solution will be: (x1, x2 ,..., xn ) . It should be noted that there may be several first solutions.
STEP 2. Check constraints: (g1, g 2 ,..., gn ) .
When checking constraints, the following options are possible: All constraints are satisfied, then go to step 3.
At least one of the restrictions is not satisfied, then the next solution found for the given transposition is considered. If there are none, then we consider the next point in ascending order and proceed to step 1.
In the case of consideration of all transpositions, it is necessary to consider the point in ascending order by three transpositions, four, etc.
STEP 3. Formation of conditions for finding the optimal solution.
Initial conditions for finding the optimal solution: f (x1, x2 ,..., xn ) b, g1 (x1, x2 ,..., xn ) ()b1, b1 b1 g1(x1, x2 ,..., xn ), g 2 (x1, x2 ,..., xn ) ()b2 , b2 b2 g 2 (x1, x2 ,..., xn ), ..............................................................................., g n (x1, x2 ,..., xn ) ()bn , bn bn g n (x1, x2 ,..., xn ).
STEP 4. Improved support solution.
Choose the next point from the set of permutations, which is better than the first support solution. Next, we transpose this point with respect to the first support solution and find the numerical value of the transposition of the target function: (12) ftr (x1, x2 ,..., xn ) b (13) Prerequisite:
ftr (x1, x2 ,..., xn ) b – growth. 4.1. If this condition is true, then it is necessary to check the growth of restrictions: 2 2 1 1 gi gi2 gi1 xigi * c j x gji * ci x gji * c j xigi * ci (14)
All increments satisfy conditions (12), then the found point is the optimal solution. Otherwise, we return to the beginning of the step 4.
4.2. If condition (13) is not fulfilled, we return to the beginning of step 4.
It should be noted that conditions (12) are sufficient for finding the optimal solution, and the fulfillment of inequality (13) is necessary for finding the optimal solution. 5
Find the maximum value of the target function: max F (x) on the permutations set A4 ,where A (1,2,3,4) , with the following restrictions: g1 5x1 2x2 3x3 4x4 15, g 2 3x1 6x2 8x3 x4 31.
Solving.
For formula (1), the number of possible transpositions is: С42 6 .
Consider the first transposition x1 x2 , presenting the target function as a product:
f12 (x1 x2 )(x1 x2 6x3 x4 ) , accordingly, when searching for the first solution, it is necessary to consider the following conditions: x1 x2 , x3 min . g1 (4,3,1,2) 25 15, g 2 (4,3,1,2) 12 31. max f1 (4,3,1,2) 40, Then the first solution may be the following points of the permutations set: (4,3,1,2), (4,2,1,3), (3,2,1,4).
Consider the first point (4,3,1,2): Additional restrictions are enforced. Then the initial conditions for improving the first support solution will be: g11 (4,3,1,2) 10, g12 (4,3,1,2) 19.
When considering point 2, it is necessary to fulfill the condition f i - increases: f 2 (4,2,1,3) (x2 x4 )(4x1 0.5x2 0.5x4 7x3 ) 6,5.
Consequently, the target function increases by 6.5 units, so there is a need to check the increment of additional restrictions: g11 (4,2,1,3) 6 10, g 12 (4,2,1,3) 7 19.
Constraints are met, so the support solution can be improved:
max f 2 (4,2,1,3) f1 (4,3,1,2) f 2 (4,2,1,3) 46,5. g11 (4,2,1,3) 16, g12 (4,2,1,3) 26. Consider the point (3,2,1,4) , then you need to transpose x1 x4 regarding point 2 (4,2,1,3) :
1 1 f14 (3,2,1,4) ( x1 x4 )(3x1 6x2 2x3 3x4 )
2 2 Since the target function decreases by 5.5 units, there is no point in considering this point of the set of permutations.
Consider ascending, point (4,2,3,1) , respectively, transposition, x3 x4 regarding point 2 (4,2,1,3) : (3 4)(9 12 2 12) 5,5. f 34 (3,2,1,4) (x3 x4 )(6x2 8x1 x3 x4 )
(3 1)(12 32 3 1) 16. The target function decreases by 16 units, respectively, this point is not considered.
Therefore, point 2 (4,2,1,3) is optimal and cannot be improved.
max f 2 (4,2,1,3) 46,5. 6
The article represents an optimization problem model with a quadratic target function and additional constraints on the combinatorial set of permutations as a model of many applied problems. An algorithm for solving the optimization problem is proposed and a numerical example is demonstrated. It should be noted that the problem are very complex from a computational point of view. Therefore, their solutions require a lot of time and resources. This method significantly simplifies the procedure for finding the optimal solution of an optimization problem with a quadratic target function and additional constraints on the combinatorial set of permutations, since the inequality of restrictions increments allows you to immediately determine whether the point of the permutation set is a support solution or not. There is not a necessity to do complex calculations of all constraints and the target function; it suffices to find the increment of constraint and functions in the case of an improvement the solution.
The further development of this study is going to be aimed at realizing and adapting the formulated method on other combinatorial constructions, as well as developing new methods for solving combinatorial optimization problems, taking into account the input data. 37. Kolechkina, L. M., Dvirna, O. A., Nagornaya, A. N.: Modified coordinate method to solve multicriteria optimization problems on combinatorial configurations. Cybernetics and Systems Analysis. 50(4): pp. 620-626 (2014) 38. Koliechkina, L., Pichugina, O.: Multiobjective Optimization on Permutations with Applications, In DEStech Transactions on Computer Science and Engineering, 2018 IX International Conference on Optimization and Applications (OPTIMA 2018) (Supplementary Volume), pp. 61-75 (2018)