New Bounds in Linear Combinatorial Optimization

Abstract

The paper is dedicated to the important issue of developing new approaches to obtain bounds of the objective function in linear constrained combinatorial optimization problems. Two general schemes have been developed for finding these bounds, which are based on solving polyhedral and semidefinite relations of the original problem. These schemes are adapted for three classes of combinatorial optimization problems, known by numerous practical applications. These are linear Boolean, permutation-based and signed permutation-based problems. For these classes, the polynomiality of obtaining the bounds is justified, for which purpose analytical representations of admissible domains in the form of systems of nonlinear equations are constructed, and separating oracles for their convex hulls are found.

Keywords

• linear constrained combinatorial optimization
• polyhedral relaxation
• semi-definite relaxation
• Boolean set
• permutation matrix set
• multipermutation
• signed multipermutation

Introduction and literature review

A large number of real-world problems are modelled as linear combinatorial optimization problems [2],[11],[16],[17],[27],[30],[34].

The vast majority of these problems belong to a class of np-complete ones [3],[11],[14],[16], which attracts the interest of researches over the world in studying general features of the class and single outing special classes of these problems that can be solved in polynomial time. In particular, this concerns estimates of the objective function.

There is a wide class of practical problems that are effectively solved by heuristic methods [2], [10], [11], [12], [17],[32]. However, the question is still open about assessing the accuracy of heuristic solutions. It is especially difficult to solve this task for the discrete case [10],[17].

Therefore, this paper poses a goal to find new ways to assess the accuracy of solutions of linear combinatorial optimization problems. This task can be formulated as a problem of constructing a new upper bound for the objective function in a constrained linear minimization problem on a combinatorial set E embedded into Euclidean space: where A  R mn , c  R n , b  R m , and the number m of additional constraints ( 2 ) is fixed.

Let x*, z* = x*, cx*

be an exact solution to the problem ( 1 )-( 3 ), x**, z ** = x**, cx**

be its approximate solution, while z l , z u be a lower and an upper bounds of z , respectively. Then, as a lower bound, z l = z ** can be chosen.

Having solved the problem of finding the bound z u , it can estimated an absolute  and a relative error  of the approximate solution x** , namely:  | z * − z ** |  =| z u − z l |=| z u − z ** | ,  = | z ** | .

Building the upper bounds as accurate as possible is important in many aspects. First, it is an assessment of heuristic solutions' accuracy. Second, it is faster obtaining accurate solutions by Branch and Bound approaches or cutting-plane methods, since it allows reducing a search domain [11],[16],[17],[20],[27]. 2

Materials and Methods

This paper proposes a general method for constructing an upper bound for the objective function (from now on the estimate z u1 ) in problems of the type ( 1 )-( 3 ) on sets for which there exists a polynomial separating oracle for the polytope P of the form z = cx → max,

Ax  b, x  E  R n , ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) where

P = {x  P : Ax  b},

P = conv E is a combinatorial polytope corresponding to E . This oracle determines whether the given point x of the space belongs to the polytope P ' and if not, generates the correct clipping of the point x using the hyperface equation of the combinatorial polytope P . Given that the number of additional constraints is fixed, the condition Ax  b is checked in polynomial time. Accordingly, the existence of a polynomial separating oracle for P is equivalent to the existence of such an oracle for P . It is the latter that we will seek during the presentation. The estimate of the estimate z u1 is the value of the objective function obtained by solving the polyhedral relaxation of the original problem, which in this case is effectively solvable.

A method is also proposed for constructing another upper bound for the objective function (hereinafter the bound z u2 ) for three classes of the class of combinatorial sets:

Bn = {0, 1}n ; Enk (G) = {x  R n :{x} = G};

En+k (G) = Enk (G)  Bn , where ( 6 ) is a Boolean set embedded into Euclidean space (a Boolean Cb -set [23]); ( 7 ) is the set of multipermutations embedded into Euclidean space (a multipermutation Cb -set [24]); ( 8 ) is a set of signed multipermutations embedded into Euclidean space (a signed multi-permutation Cb -set [19],[21],[23],[25]). Hereinafter {x} = {x1, ..., xn} for x = (x1, ..., xn ) ,

G = {g i }iJ n  R1, S (G) = {ei}iJ k is a base of G , J n = {1, .., n} , Bn = {−1, 1}n , A1 • A2 is the Hadamard product of sets A1 and A2 .

The method for obtaining the estimate z u2 is based on the use of continuous functional representations (f-representations) [24] of these sets or their images in the space of higher dimension.

It is justified that, for the sets ( 6 )-( 8 ), we apply both the first and second approaches to solving the problem.

Note that both proposed methods for obtaining estimates give a solution in polynomial time, which makes them practically applicable. We assume that in the problem ( 1 )-( 3 ) all the coefficients of the additional constraints of the objective function are integer, and our combinatorial set E is a subset of the integer lattice, i.e.

A  Z mn , b  Z m , S (G)  Z1. ( 6 ) ( 7 ) ( 8 ) ( 9 ) ( 10 ) ( 11 )

We also assume that all linear functions of the additional constraints ( 2 ) take a polynomial in n number of values within an admissible region, that is, ( 2 ) can be represented as: where A  Z mn , m < m , b  Z m , b −   Ax  b,

  Z +m , ki  Z + , ai'T x  {bij } jJ k , bi − i = bi1 < bi2 < ... < biki = bi, i  J m.

i

As noted earlier, another condition is the existence of a polynomial separation oracle for the polytope ( 4 ), i.e., one that determines whether a given point in space is a polytope of P .

Thus, we consider a problem of the form ( 1 ), ( 3 ), ( 11 ), ( 12 ). 2.1

The bound z u1

The first solution method involves the transition from the solution of the problem ( 1 ), ( 3 ), ( 11 ), ( 12 ) to consideration of its polyhedral relaxation, i.e. to a problem of the form ( 1 ), ( 11 ), ( 12 ), where P is the combinatorial polytope ( 5 ). Denote the solution to this problem by x 0 , z 0 . Note that this is a standard approach, which difficulty of the practical implementation is caused by the fact that an analytic form of most combinatorial polyhedra is unknown, and if it is known, it contains an exponential in n number of constraints [26],[27],[34]. The upper bound is:

x  P ,

In our case, this relaxation can be solved in real-time due to the existence of a separating oracle, by methods such as the ellipsoid method [27]. However, again, the practical implementation of this method is significantly difficult.

We propose another approach, which is based on solving a set of linear problems forming a sequence of points that converges to solving the x 0 relaxation problem. For that, we consider the linear problem ( 1 ) on the hypercube [e1, ek ]n with additional restrictions ( 11 ). This problem is solved by linear programming methods, and the resulting solution x 0 is checked for membership in the polytope P using the oracle.

In order to accomplish this, we consider the linear problem ( 1 ) on the hypercube [e1, ek ]n with additional restrictions ( 11 ). This problem is solved by linear programming methods, and the resulting solution x 0 is checked for membership of the polytope P using the oracle.

If the point is invalid, then this oracle generates a constraint P , which can be added to the system ( 11 ), e1e  x  ek e, ( 15 ) where e is a vector of units.

The resulting problem is solved by the linear programming method, and it is advisable to start from the point x 0' and take one or several steps of the dual simplex method.

This process continues iteratively until the vertex of the polytope is obtained, which is the desired point x 0 . This method was tested on the multipermutation Cb -sets and partial multipermutation Cb -sets showing high computational efficiency [18].

We consider three classes of Euclidean combinatorial optimization problems. The first is the classical problem, which is formulated as a linear conditional optimization problem on a Boolean Cb -set ( 6 ) (starting now Problem 1), the second is a linear conditional problem on the multipermutation Cb -set ( 7 ) (linear permutation-based problem) (further referred to as Problem 2), and a conditional linear problem on the signed multipermutation Cb -set ( 8 ) (a linear signed-permutation-based problem) (hereinafter Problem 3). The corresponding polyhedral relaxation problem has the form: ( 1 ), ( 11 ), ( 12 ), ( 13 ), where

P = Dn = convBn = [0, 1]n is a unit hypercube in Problem 1; is a generalized permutohedron [34] in Problem 2;

P = Pnk (G) = convEnk (G) P = Pnk (G) = convEnk (G). ( 16 ) ( 17 ) ( 18 ) ( 19 ) ( 20 )

Moreover, without loss of generality, it is assumed that the multiset G  R 1+ is preordered in such a way that is a generalized signed permutohedron [24], [31] in Problem 2;

The polynomial solvability of the polyhedral relaxation of Problem 1 by linear programming methods is not in doubt, since the number of constraints Dn is 2n , and the number of additional ones is fixed. As a result, the point x 0 = x 0 .

For Problems 2 and 3, the situation is much more complicated, since the corresponding polyhedra are defined, generally speaking, by a non-polynomial number of constraints, namely:

n n || Pnk (G) : xi = g i , xi  g i ,   J n ; i=1 i=1 i i=1

|| Pnk (G) :  | xn−i+1 | g n−i+1 ,   J n .

i i=1 wherefrom

( 20 ) is a compact H-representation of the polytope Pnk (G) , in which the signs in the modules are expanded in all possible ways, forming a system of linear constraints.

The cardinality of the irreducible subsystems singled out in ( 19 ), ( 20 ) reaches values 2 n −1 and 4 n − 2 n , respectively.

To justify the polynomial solvability of the polyhedral relaxation problem and the possibility of applying the indicated scheme for obtaining z u1 , we give oracles for each of these polyhedra.

Theorem 1 [21],[31]. 1. A point x  R n , such that satisfies a condition 2. A point x  R n , such that satisfies a condition

n n j j x  Pnk (G) iff xi = g i , xi  g i , j  J n−1.

i=1 i=1 i=1 i=1 x  Pnk (G) iff j j  | xn−i+1 | g n−i+1 , j  J n−1.

i=1 i=1

It is clear that ordering ( 23 ), ( 25 ) and checking ( 24 ), ( 26 ) can be done in polynomial time. Moreover, if the membership condition for the polytope is not fulfilled, a violated constraint is generated during this process, so a polynomial separating oracle is found. The scheme is based on the use of a concept of a multi-level finite point configuration (FPC, a finite discrete set mapped into Euclidean space) [7] and the Theta-rank [6],[8]. ( 22 ) ( 23 ) ( 24 ) ( 25 ) ( 26 )

Definition 1 [7]. A finite point configuration E is k -level if, for every facetdefining hyperplane H , there are k parallel hyperplanes H = {H1, H 2 , ..., H k } with E  H1  H 2  H k .

A levelness of E , denoted by Lev(E) , is the smallest k such that E is k -level.

A concept of the Theta rank Th(E) of an FPC E was introduced in [6] as a measure of the complexity of linear optimization over this set by polynomial optimization tools. Namely, if E is given as a solution set to a system of polynomial equations, a semi-definite relaxation of a linear program over E can be solved exactly in the time of order O(nTh(E) ) .

It is easy to see that Th(E)  Lev(E) −1 , and this inequality turns into equality for 2-level sets. This means that the time complexity of solving semi-definitete relaxation of the problem ( 1 ), ( 3 ), ( 11 ), ( 12 ) is bounded above by order O(n Lev(E)−1) for E with Lev(E) > 2 , and it is of order O(n Lev(E)−1) for a two-level set E . This means that, if Lev(E) does not depend on E , then the relaxation is polynomially solvable. The result of solving this relaxation will be denoted x* , z * = x* , cx* . This optimization problem is convex; thus z* is a new upper bound of z * is achievable. It will be used as a second upper bound z u2 :

z u2 = z *.

In order to apply this approach, a strict polynomial f-representation of E has to be found. Also, inequality constraints in ( 2 ) (equivalently, ( 11 )) has to be replaced by equalities, thus yielding a strict polynomial f-representation of E  .

To accomplish this, the following technique will be applied to each inequality aiT x  bi , i  J m in ( 2 ). First, assume that b  0 . Represent bi  Z n+ as follows: bi = y0 + 2 y1 + ... + 2ti yti , where ti = log 2bi , y j {0, 1} , j  J t0i , i  J m . By introducing y  J T0 such that T = max ti , the constraint ( 2 ) can be represented as a iJ m system of linear equations as follows:

Ax + Cy = 0, y  BT +1, ( 27 ) ( 28 ) where C = (cij )iJ m, jJT0  N m(T +1) , cij = (−1, −2, ..., −2ti , 0, ..., 0) , i  J m . If there exists i  J m such that bi < 0 then the corresponding constraint can be rewritten in the form of aiT x+ | ci |= 0 . Applying the same technique to expand | ci | , we get cij = (1, 2, ..., 2ti , 0, ..., 0) , i  J m , and the common result of the lifting into a higher dimension space given by ( 27 ), ( 28 ).

Denoting AC = ( A, −C) , Problem 1 is rewritten as a problem of finding a vector xy satisfying ( 1 ), ( 29 ), ( 1 ) For Problem 2, the extended reformulation is given by ( 1 ),( 7 ),( 28 )-( 30 ). Similarly, for Problem 3, it will be a problem ( 1 ),( 8 ),( 28 )-( 30 ). The two later extended formulations are ones on a Cartesian product of the Binary Cb -set and a multipermutation or a signed multipermutation Cb -set, respectively, whose levelness coincides with the one of Enk (G) and Enk (G) due to Lev(Bn ) = 2 and levelness properties [7]. 2.3

Matrix Cb -sets for evaluating z u2 Let us consider an issue of obtaining in a reasonable time the bound z u2 in Problems 1-3.

We start with the Boolean Problem 1. The Boolean set Bn is two-level [7], and our feasible set is Lev(E) -level, where Lev(E) is determined by the formula where ki , i  Jm are determined by the formula ( 12 ). The levelness of our feasible set is independent of n , hence the computational complexity of semi-definite relaxation is bounded from above by

Thus, the relaxation is polynomially solvable.

In order to apply this relaxation, a strict f-representation of the Boolean set needs to be found.

For instance, the well-known strict f-representation of a Boolean set by quadratic equations xy = (x, y), AC  xy = 0, xy  BnT +1. ( 29 ) ( 30 ) ( 31 ) ( 32 ) ( 33 ) ( 34 ) Lev(E) = imJamx ki  2 ,

O(n (Lev(E)−1) ).

xi2 − xi = 0, i  J n can be applied. Many other similar f-representation can be found in [21],[24].

For sets ( 7 ), ( 8 ), applying this technique does not give positive results, since these sets, generally, are not Lev -level, where Lev does not depend on n [21]. Therefore, for Problems 2,3, we offer a transition to considering an equivalent formulation in the space of higher dimension in the form of Problem 1.

Now, we consider the multipermutation set ( 7 ) along with a set

 nk = {X  Bkn : Xe = n, X T e' = e} of multi-permutation matrices [13], where e  R n , e'  R k are vectors of units, n = (ni ) iJ k is a vector of S (G) -multiplicities in G . Its special case is a multitude of permutation matrices [15],[22]:

 n = {X  R nn : Xe = X T e = e} corresponding to the case n = e in (35).

According to [13], between the sets ( 7 ), (35), there exists a bijective mapping where cij = eic j , i  J k , j  J n .

In the same way, constraints ( 1 ) are reformulated yielding

Ai • X  bi , i  J m , where Ai = (alij ) l, j , alij = ei alj , i  J m , l  J k , j  J n .

A new formulation of Problem 2 (further referred to as Problem 2.1) is: find a matrix X such that (40), (41), namely, or

Let us reformulate our problem in terms of new variables. So, for the objective function ( 1 ), we have:

 : x = X T e,  nk iff x = X T e  Enk (G). z = cT x = cT X T e = k nxi (eic j ) → max

i=1 j=1 k n z = C • X = cij xij → max, i=1 j=1 (35) (36) (37) (38) (39) (40) (41) hold.

It can be shown that the polytope Pnk = conv nk of multipermutation matrices is defined as follows

X   nk 0  xij  1, i  J k , j  J n ; n xij = ni , i  J k ; j=1 k xij = 1, j  J n.

i=1 Now, for obtaining the upper bound z u2 in Problem 2, Scheme 2 can be applied.

A similar procedure is applicable for Problem 3 and the signed multipermutation Cb -set. For that, we introduce a set of signed permutation matrices' set: (42) (43) (44) (45) (46) (47)

Hence, facets of Pnk are parallel to coordinate planes, while set  nk is two-level. Involving additional constraints (41) into consideration and taking into account an equivalence of Problem 2 and Problem 2.1, as well as ( 12 ), ( 32 ), we get that a levelness of a feasible domain of Problem 2.1 is given by ( 32 ). This implies that a semi-definite relaxation of Problem 2 in the extended space is polynomially solvable.

To apply it, a strict representation of Bkn needs to be utilized. It can be, for example,

xi2j − xij = 0, i  J k , j  J n.   = {X T kn :| X | e = n,| X |T e' = e},

nk where T = {−1, 0, 1} is a ternary set, | X | e = n implies that sum of absolute values of rows' coordinates equal to the corresponding multiplicity of S (G) -elements, while | X |T e' = e means that the columns are zero ones except for a single element, which is either one or minus one.

Next, we need to construct a strict f-representation of the set (47), more precisely, of its image in space R kn . The condition X  T kn will be formalized, likewise (46) yielding: xij (xij −1)(xij +1) = xi3j − xi2j = 0, i  J k , j  J n . (48)

The rest of the constraints in (47) let us represent in a quadratic form:

Set Bn ( 1 ) is an example of a ternary permutation Cb -set [23],[24]. It belongs to a Bn (i) = Bn • En2 ({0 n−i , 1i}), i  J n−1, n xi2j = ni , i  J k ; j=1 k xi2j = 1, j  J n. i=1 (50) (51) (52) (53) (54) (55) n PBn (i) = conv Bn (i) = {x [−1, 1]n :  | x | i}.

i=1

Examine a levelness of  nk based on (53)-(55). With respect to faces of Pnk parallel to coordinate planes, the sets is 3 -level. Toward normal vectors of facets k  | xij |= 1 , it is two-level, while for a hyperpalne i=1 n  | xij |= ni , it is 2ni -level. j=1 Overall   nk

is l -level set, where

Generalizing ( 32 ) for this case, we get that a levelness of the corresponding set E  is given by: l = Lev(  ) = max 3, 2n1, ..., 2nk .

nk Lev(E) =

max iJ m, jJ k {ki , 3, 2n j }  3 .

(56) (57) (57) implies, that the semi-definite relaxation of Problem 3 utilizing the above is polynomialy solvable if n1, ..., nk do not depend on strict f-representation of  

nk n . 3

Discussion

Thus, we justified z u2 is always achievable in polynomial time for Problem 1 an Problem 2 and indicted a condition when the same is true for Problem 3. The results on semi-definite and polyhedral relaxation bounds can be further combined [9] in order to obtain more accurate lower bounds in z . One more direction for tightening the bound z u2 is to use Lagrangian dual bounds by Shor's r algorithms [28], [29]. The algorithms deal with quadratic optimization problems. Hence they are directly applicable to Problem 1 and Problem 2 while requiring one more step of lifting in higher dimension space for Problem 3 represented as a cubic optimization problem. No less important in numerical algorithms are effective ways to get upper bounds. Their obtaining associating with a search of a feasible solution means a possibility to finish a process as soon as a required accuracy is achieved. With this regards, it highly helpful an approaches presented in [33] and other sources [1], solving the problem as a polynomial optimization or a feasibility problem. 4

Conclusion

In this paper, two innovative approaches of mathematical modeling general permutation-based and signed permutation-based optimization problems as problems of polynomial optimization with equality constraints are presented and applied to justify a polynomial solvability of getting semi-definite bounds. They can be generalized into other classes of optimization problems and utilized in many other problems arising in combinatorial and continuous nonlinear optimization.

References

1. Anjos , M.F. , Lasserre , J.B. eds: Handbook on Semidefinite, Conic and Polynomial Optimization . Springer ( 2011 ).

2. Butenko , S. , Pardalos , P.M. , Shylo , V. eds: Optimization Methods and Applications: In Honor of Ivan V. Sergienko's 80th Birthday . Springer International Publishing, Cham ( 2017 ).

3. Cook , W.J. , Cunningham , W.H. , Pulleyblank , W.R. , Schrijver , A. : Combinatorial optimization . John Wiley & Sons, Inc., New York ( 1998 ).

4. Ferreira , O.P. , Iusem , A.N. , NГ©meth, S.Z.: Concepts and techniques of optimization on the sphere . TOP . 22 , 1148 - 1170 ( 2014 ). https://doi.org/10.1007/s11750-014-0322-3.

5. Elte , E.L. : The semiregular polytopes of the hyperspaces . Groningen : Gebroeders Hoitsema ( 1912 ).

6. Gouveia , J. , Parrilo , P. , Thomas , R. : Theta Bodies for Polynomial Ideals . SIAM J. Optim. 20 , 2097 - 2118 ( 2010 ). https://doi.org/10.1137/090746525.

7. Grande , F. : On k-level matroids: geometry and combinatorics , http://www.diss.fuberlin.de/diss/receive/FUDISS_thesis_000000100434, ( 2015 ).

8. Grotschel , M. , Lovasz , L. , Schrijver , A. : Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, Berlin Heidelberg ( 1993 ).

9. Helmberg , C. , Poljak , S. , Rendl , F. , Wolkowicz , H.: Combininsemi-definitete and polyhedral relaxations for integer programs . In: Balas, E. and Clausen , J . (eds.) Integer Programming and Combinatorial Optimization . pp. 124 - 134 . Springer Berlin Heidelberg ( 1995 ). https://doi.org/10.1007/3-540-59408-6_ 46 .

10. Hulianytskyi , L. , Riasna , I. : Formalization and Classification of Combinatorial Optimization Problems . In: Optimization Methods and Applications . pp. 239 - 250 . Springer, Cham ( 2017 ). https://doi.org/10.1007/978-3- 319 -68640-0_ 11 .

11. Korte , B. , Vygen , J.: Combinatorial Optimization: Theory and Algorithms . Springer, New York, NY ( 2018 ).

12. Kozin , I.V. , Maksyshko , N.K. , Perepelitsa , V.A. : Fragmentary Structures in Discrete Optimization Problems . Cybern Syst Anal. 53 , 931 - 936 ( 2017 ). https://doi.org/10.1007/s10559-017-9995-6.

13. Liu , X. , Draper , S.C. : LP-Decodable Multipermutation Codes . IEEE Transactions on Information Theory . 62 , 1631 - 1648 ( 2016 ). https://doi.org/10.1109/TIT. 2016 . 2526655 .

14. Nocedal , J. , Wright , S. : Numerical Optimization. Springer-Verlag, New York ( 2006 ).

15. Onwubolu , G.C. , Davendra , D. eds: Differential Evolution: A Handbook for Global Permutation-Based Combinatorial Optimization . Springer-Verlag, Berlin Heidelberg ( 2009 ).

16. Papadimitriou , C.H. , Steiglitz , K. : Combinatorial Optimization: Algorithms and Complexity . Dover Publications ( 1998 ).

17. Pardalos , P.M. , Du , D. , Graham , R.L. : Handbook of combinatorial optimization . New York : Springer ( 2005 ).

18. Pichugina , O.S. : Methods and algorithms for solving some optimization problems on sets of combinations and arrangements , Ph.D. in Mathematics[Thesis] (speciality 01.05.02) , Kharkiv: Kharkiv State Technical University of Radio Electronics, 1996 (in Russian).

19. Pichugina , O. , Kartashov , O. : Signed Permutation Polytope Packing in VLSI Design . In: 2019 IEEE 15th International Conference on the Experience of Designing and Application of CAD Systems (CADSM) Conference Proceedings. 4/ 50-4/55, Lviv ( 2019 ). https://doi.org/10.1109/CADSM. 2019 . 8779353 .

20. Pichugina , O. , Muravyova , N.: A Spherical Cutting-plane Method With Applications In Multimedia Flow Management . In: Proceedings of the 1st International Workshop on Digital Content & Smart Multimedia (DCSMart 2019 ). pp. 82 - 93 . CEUR Vol- 2533 , Lviv, Ukraine ( 2019 ).

21. Pichugina , O.S. , Yakovlev , S.V. : Continuous functional representations in discrete optimization: a monograph . Gold Mile , Kharkiv ( 2018 ).

22. Pichugina , O. , Yakovlev , S. : Quadratic Optimization Models and Convex Extensions on Permutation Matrix Set . In: Shakhovska, N. and Medykovskyy , M.O. (eds.) Advances in Intelligent Systems and Computing IV . pp. 231 - 246 . Springer International Publishing ( 2019 ). https://doi.org/10.1007/978-3- 030 -33695-0_ 17 .

23. Pichugina , O. , Yakovlev , S. : Euclidean Combinatorial Configurations: Typology and Applications . In: 2019 IEEE 2nd Ukraine Conference on Electrical and Computer Engineering (UKRCON) . pp. 1065 - 1070 ( 2019 ). https://doi.org/10.1109/UKRCON. 2019 . 8879912 .

24. Pichugina , O. , Yakovlev , S. : Euclidean Combinatorial Configurations: Continuous Representations and Convex Extensions . In: Lytvynenko, V. , Babichev , S. , WГіjcik, W., Vynokurova , O. , Vyshemyrskaya , S. , and Radetskaya , S. (eds.) Lecture Notes in Computational Intelligence and Decision Making . pp. 65 - 80 . Springer, Cham, Zalizniy Port, Ukraine ( 2019 ). https://doi.org/10.1007/978-3- 030 -26474- 1 _ 5 .

25. Sanyal , R. , Sottile , F. , Sturmfels , B. : Orbitopes . Mathematika. 57 , 275 - 314 ( 2011 ). https://doi.org/10.1112/S002557931100132X.

26. Schrijver , A. : Polyhedral Combinatorics . In: Graham, R.L. , Grötschel, M., and Lovasz , L. (eds.) Handbook of Combinatorics (Vol. 2 ). pp. 1649 - 1704 . MIT Press, Cambridge, MA, USA ( 1995 ).

27. Schrijver , A. : Combinatorial Optimization: Polyhedra and Efficiency . Springer-Verlag, Berlin Heidelberg; New York ( 2003 ).

28. Shor , N.Z. , Stetsyuk , P.I.: The use of a modification of the r -algorithm for finding the global minimum of polynomial functions . Cybern Syst Anal . 28 - 49 ( 1997 ). https://doi.org/10.1007/BF02733104. https://doi.org/10.1007/BF02733104.

29. Shor , N.Z. : Nondifferentiable optimization and polynomial problems . Kluwer Academic Publishers, Dordrecht ( 1998 ).

30. Stoyan , Y.G. , Yakovlev , S.V. : Theory and Methods of Euclidian Combinatorial Optimization: Current Status and Prospects . Cybern Syst Anal . 56 , 366 - 379 ( 2020 ). https://doi.org/10.1007/s10559-020-00253-6.

31. Stoyan , Y.G. , Yemets’, O. : Theory and methods of Euclidean combinatorial optimization (in Ukrainian) . ISSE , Kiev ( 1993 ).

32. Yakovlev , S. , Kartashov , O. , Pichugina , O.: Optimization on Combinatorial Configurations Using Genetic Algorithms . In: Proceedings of the Second International Workshop on Computer Modeling and Intelligent Systems (CMIS-2019) . pp. 28 - 40 . CEUR Vol- 2353 urn:nbn:de: 0074 - 2353 -0, Zaporizhzhia, Ukraine ( 2019 ).

33. Yakovlev , S. , Pichugina , O. : On Constrained Optimization of Polynomials on Permutation Set . In: Proceedings of the Second International Workshop on Computer Modeling and Intelligent Systems (CMIS-2019) . pp. 570 - 580 . CEUR Vol- 2353 urn:nbn:de: 0074 - 2353 -0, Zaporizhzhia, Ukraine ( 2019 ).

34. Yemelichev , V.A. , Kovalev , M.M. , Kravtsov , M.K. : Polytopes, graphs and optimization . Cambridge University Press, Cambridge ( 1984 ).