=Paper=
{{Paper
|id=Vol-2711/paper35
|storemode=property
|title=The Polyhedral-Surface Cutting-Plane Method for Linear Combinatorial Optimization
|pdfUrl=https://ceur-ws.org/Vol-2711/paper35.pdf
|volume=Vol-2711
|authors=Oksana Pichugina,Nadezhda Muravyova
|dblpUrl=https://dblp.org/rec/conf/icst2/PichuginaM20
}}
==The Polyhedral-Surface Cutting-Plane Method for Linear Combinatorial Optimization==
https://ceur-ws.org/Vol-2711/paper35.pdf
The Polyhedral-Surface Cutting-Plane Method for Linear
Combinatorial Optimization
Oksana Pichugina1,2[0000-0002-7099-8967], Nadezhda Muravyova3[0000-0002-8307-2290]
1 National Aerospace University "Kharkiv Aviation Institute", 17 Chkalova Street, 61070
Kharkiv, Ukraine
2 University of Graz, 15 Universitatsstrasse, E3, 8010 Graz, Austria
o.pichugina@khai.edu
3 South Ural State University, 76 Lenin Av., 454080 Chelyabinsk, Russia
muravevanv@susu.ru
Abstract. For linear optimization on combinatorial sets inscribed into a convex
surface, a Polyhedral-Surface Cutting-Plane Method (PSCM) is offered. It es-
sentially uses representability of such sets as an intersection of a polytope with
a circum surface. Three versions of PSCM are formulated depending on the
choice of surface involved. A justification of applicability of PSCM for linear
permutation-based and Boolean optimization problems is given, which opens
perspectives to solve in a reasonable time a significantly wider class of real-
world tasks modelled as combinatorial optimization problems.
Keywords: Linear Optimization, Combinatorial Optimization, vertex-located
set, surface-located set, cutting-plane method, polyhedral relaxation.
1 Introduction
In Combinatorial Optimization and Convex Optimization, cutting-plane methods play
a special role in illustrating how discrete optimization problems can be solved by
continuous optimization methods [2, 14, 24, 26]. The effectiveness of cutting-plane
methods substantially depends on the depth of the cuts and the computational
complexity of their construction. In Combinatorial Optimization, when developing
optimization methods, the most important component is the study and utilizing of the
specifics of a feasible domain of optimization problems under consideration [5, 7, 13,
24]. The present paper is dedicated to developing a cutting-plane method for one class
of combinatorial problems.
2 Problem 1 Statement
Let us consider a linear optimization problem over a finite point configuration (FPC)
[11] E in R n :
cx → min , (1)
Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons
License Attribution 4.0 International (CC BY 4.0). ICST-2020
Ax b, (2)
x E , (3)
E = P S , (4)
where A R mn , b R m , c, x R n , P is a full-dimensional polytope, S is a
convex hypersurface, E is an FPC, i.e.,
dimP = n, (5)
1 <| E |< , (6)
f : R n → R 1 − convex : S = { x R n : f ( x) = 0} . (7)
A statement of this problem (further referred to as Problem 1) is as follows: it is
necessary to find a solution x * of the problem (1)-(4), which is the problem of
minimizing the linear function (1) with linear constraints (2) on a finite set of points
R n formed as an intersection of a convex surface S and the full-dimensional
polytope P expressed in the constraint (4).
This means that conditions (5)-(7) are also satisfied, in particular, there exists a
convex function f ( x) defining this surface.
Here, the condition (4) is present that distinguishes this problem from the generic
linear discrete optimization problem.
This allows offering specific methods for solving Problem 1 that use the specifics
of the admissible domain.
Let x * , z * = x * , cx * be a solution to Problem 1.
Among the features of E is that, without loss of generality, it can be assumed that
P is a convex hull of E . In other words, it is a combinatorial polytope corresponding
to this set. The set’s representation (4) is called polyhedral-surfaced [19, 20]. The
next important feature is that E is vertex-located set (VLS) [27], i.e., it coincides
with a vertex set of its convex hull.
Respectively, a feasible domain E of Problem 1 will also be VLS. Associating a
combinatorial polytope P to set E , this allows constructing a polyhedral-surface
representation involving P and S . This Problem 1 specifics can be summarized as
follows:
1. One can assume that P is a combinatorial polytope (CP) associated with E ,
i.e.,
P = convE , (8)
then (4) is a polyhedral-surfaced representation of E ( E .PSR) as an intersection of
a CP P with a circumsurface S .
2. From (4) , it follows that E is a vertex-located set (VLS), i.e., E = vert P .
3. Let E be a feasible region of Problem 1, and P be its convex hull:
E = {x E : Ax b},
P = convE ,
then E is a VLS, while P is a CP associated with E .
It is easy to see that an arbitrary VLS allows forming a polyhedral-surface
representation.
Its constructing it is a separate task, which includes finding an H-representation of
the polytope and equality of circumscribed surface S . Sets satisfying (4) are called
polyhedral-surface (PSSs), among which are polyhedral-spherical (PSSs),
polyhedral-ellipsoidal (PESs), and so on [19, 20, 29].
In this paper, special attention we will be paid to polyhedral-spherical sets (PSSs),
because their specificity in solving linear combinatorial optimization problems and a
variety of practical problems modelled as optimization problems on PSSs [17, 21, 29].
The class of such sets includes a set of n -multipermutations induced by a numerical
multiset G containing k different elements, which is an image in R n of the
combinatorial space of permutations with repetitions [19,20]. It is a set
E nk (G ) = {x R n :{x} = {x1 , ..., x n } = G} (9)
induced by a multiset
G = {g i }iJ ={1,..., n} R 1 : g i g i +1 , i J n −1 ,
n
with a ground set S (G ) = {ei }iJ : ei < ei +1 , i J k −1 ;
k
Also, this class includes a set of signed n -multipermutations [17, 23] that differs
from the previous one in that signs are added to the elements of the permutation:
E nk (G ) = {x R n :{| x |} = {| x1 |, ...,| x n |} = G}. (10)
Finally, these are the well-known Boolean set B n and binary set B n ' , where
B n = {0,1} n ; (11)
B n' = {− 1,1} n , (12)
on which Boolean optimization problems are modelled [5, 13, 15, 16, 32], as well as
their various subsets, such as the permutation matrices [4], even and odd permutation
sets [30], a vertex set of the half-cube [6, 12], etc.
Thus, Problem 1 covers all problems of linear Boolean optimization, linear
problems on permutations, allowing formulation on a set of multipermutations and
signed multipermutations, and many others.
3 Cutting-Plane Approaches to VLS-Optimization
A method we propose to solve Problem 1 generalizes a method of combinatorial cuts
(CCM) for solving linear programs on VLSs [8, 10]. CCM utilizes a standard idea to
solve linear combinatorial optimization problems with the help of their polyhedral
relaxations [5, 15]. This means that, for its effective utilization, there must be ways to
solve the corresponding polyhedral relaxation problems in polynomial time on their
dimension. Generally, this stage is complicated because combinatorial polytopes can
contain an exponential number of constraints [1, 9, 17, 22, 31]. CCM uses an original
idea of constructing deep cuts through adjacent vertices of the relaxation polytope P ,
since the feasible points are located at its vertices only. In this connection, one more
constraint arises on the number of adjacent vertices of a a vertex of combinatorial
polytopes. For example, the Birkhoff polytope is the convex hull of set n , which is
described by a polynomial number of constraints [4]. However, the number of
adjacent vertices is exponential on n . Thus, to solve conditional linear problems on
n , by a method that analyzes all adjacent vertices is problematic.
CCM is applicable to solving Problem1, if :
1. its polyhedral relaxation (PR) is polynomially solvable on n (Property 1);
2. any point of E has a number of adjacent vertices in P polynomial on n
(Property 2).
Among sets with Properties 1, 2 are the listed above sets (10)-(12). Let us illustrate
this by set E nk (G ) :
1. E = B n' : a) an H-representation of a hypercube PB n' = conv B n' is well-known
and has 2n constraints; b) x B n' N ( x) = n ;
PBn'
2. Despite the fact that the generalized permutohedron Pnk (G ) , which is the
convex hull of E nk (G ) , is generally defined by a non-polynomial number of
constraints [25,31], the polyhedral relaxation problem can be solved efficiently based
on the property (13), which allows using an insignificant part of the constraints of the
polytope [25]. So, for E = E nk ( G ) : a) Pnk ( G ) = conv E nk ( G ) - is the generalized
permutohedron; b) x E nk ( G ) NP
nk ( G ) ( x) = n1n 2 + ... + n k −1n k ; c) an H-
representation is known and has up to 2 n − 1 constraints. However, for E nk ( G ) , PR
of Problem 1 is polynomially solvable based on the following fact: x R n such
that x i x i +1 , i J n −1 ,
j j n n
x Pnk ( G ) xi g i , j J n −1; xi = g i . (13)
i =1 i =1 i =1 i =1
Here, N [.] ( x j ) is a neighbourhood of x j in P [.]
P
3.1 Modified CCM (MCCM)
In the original version of the CCM [8,10], cutting planes for a polyhedral relaxation
solution, which is not a point of E' , are constructed based on the analysis of the last
simplex table, from which information about adjacent vertices to this point is derived.
As a result, a cut of the unfeasible solution is formed through at least adjacent vertex
of P ' .
In this paper, we offer a modified CCM (MCCM), where geometric features of E'
and P ' are substantially used, resulting in a possibility of deeper cuts built on their
basis than CCM-ones. So, on the initial iteration, the usual polyhedral relaxation of
Problem 1 is solved. If its solution x 0 is a point of E' , this problem is solved.
Otherwise, we move to the construction of a cut. To do this, we construct a
neighbourhood of the point x 0 in the polytope P ' and draw a hyperplane 0
through the neighbourhood points.
MCCM outline:
Step 0. Initial iteration j = 0 , a search domain is P j = P ' , the number of
additional constraints is m j = m .
Step 1 (Main Stage)
a) solve a problem: find x j = arg min f ( x);
Pj
b) if x j E ' , then terminate;
c) otherwise, form N j ( x j ) , choose the shortest n edges x j , x l , l J n , of
ji
P
P j intersecting at x j . The edges' endpoints are:
ji
X j= x l
lJ n
vert P j ; (14)
d) form a hyperplane through points (14):
j j j
j
j = x : a j x − b j = 0 : a j x j − b j > 0;
m +1 m +1 m +1 m +1
(15)
e) choose a subspace cutting off x j :
j j
j : a j x − b j 0. (16)
m +1 m +1
Step 2. Go to the next iteration:
j
m
j
m
j = j + 1, m j = m j −1 + 1, P j = x P j −1 : a j x − b j 0 .
Repeat Steps 1-2 until a valid point of E' is obtained - x j E ' .
Output: x * = x j . (16) is a cut for x j , if the following condition holds:
j j
x N j ( x j ) a j x − b j 0. (17)
P m +1 m +1
For fulfilling (17), it is sufficiently that
nj = N ( x j ) = n. (18)
Pj
If (17) is false, cut x j by a hyperplane j is built passing through a point of
N ( x j ) in one of the ways:
Pj
According to Lemma 1, 0 will certainly be a cutting plane if the number of
adjacent vertices to x 0 equals the dimension of the polytope. Moreover, the plane is
uniquely determined. Condition (17) is a check that as a result of adding constraint
(16) no other vertex of P 0 than x 0 was cut off. Using it, one can verify that the cut
(16) is valid if the number of adjacent vertices exceeds n . If the condition (17) is not
satisfied, we propose using the standard cut of CCM [8, 10] (further referred to as
Way 1).
Note that, for polyhedral-spherical sets, one can use the following their feature: if
there are two different hyperspheres circumscribed about E' , then E' lies in an
intersection plane of these hyperspheres, which equation can be easily found from the
equations of these hyperspheres. So, for PSpS E ' S r ( a ) , we recommend forming
a hypersphere S j ( x j ) centred at x j with a radius r j = min x ji − x j and, if
r iJ n
j
S = S r ( a ) S j ( x j ) is n − 2 -sphere, take, as a cutting plane (15), a hyperplane
r
where S lies (further referred to as Way 2).
Fig. 1. (17) is true Fig. 2. (17) is false Fig. 3. Way 2 illustration
Figure 1 illustrates a case, where the hyperplane passing through the n nearest
vertices is cutting off, while Figure 2 shows a situation, where such a plane cannot be
selected because it is not valid, because the point x j is cut off. Finally, Figure 3
illustrates one more method of constructing a cut through the adjacent vertex closest
to x i .
At the next step, the valid cut is added to the constraints, and the procedure is
repeated in the same way until point of E' is found as a solution of a polyhedral
relaxation problem.
Figure 4 illustrates the MCCM for the case of polyhedral-spherical E' . First, x 0
is found on iteration 0. It does not belong to E' . Thus we build a cut for it. It is
formed through vertices x 01 and x 02 adjacent to it. Then repeat the procedure
similarly until we find the optimal solution x * to Problem 1.
3.2 Combinatorial Polytope Cutting-Plane Method (CPCM)
The second approach, a combinatorial polytope cutting-plane method (CPCM),
utilizing the fact that there are no feasible points of E' in the interior of the
combinatorial polytope P and all its faces of any dimension.
CPCM uses an observation that feasible points of a VLS E are absent in an
interior of a CP P ' and its faces of the dimension at least one. Let us represent the
method as a modification of MCCM.
The modification core: at the iteration j of the main stage of MCCM, extend the
edges
x j , x ji , i J n , (19)
j
up to their intersection with a surface P getting extended edges
x j , y ji , i J n , (20)
j
Endpoints of first n the shortest edges are used instead of (14):
ji '
X j → Y j = y l P (21)
lJ n
in constructing a cut (16).
As a result, a hyperplane (15) is built through points (21).
As a modification of the CCM, it looks like this: edges (19) of the polytope P j
are extended until they intersect a surface of polytope P ' resulting on forming set
(20). By a choose of the nearest n to x j among the set’s points, a set Y j is formed,
which is then used instead of X j to form the cut.
We operate with a bound of P , therefore (18) is replaced by:
iJ n P a mj j +1x − bmj j +1 0 .
x y ji (22)
j
Fig. 4. The Combinatorial Polytope Fig. 5. The Surface-Cutting Method
Cutting-Plane Method (CPCM) (SCM)
Fig. 5 shows how edges of the polytope P 0 , induced by x 0 , are extended to an
intersection with a surface of the combinatorial polytope and the cut is conducted
through the formed points. Then, the procedure is repeated.
3.3 Surface Cutting-Plane Method (SCM)
A third approach is a surface cutting-plane method (SCM), which offers a greater
extension of the edges forming x 0 . Namely, they go up to an intersection with
surface S resulting in forming a set Z j of intersection points. Then, the cut is formed
through all or a part of these points. Here we use a VLS-feature, that feasible points
can only be on a circumsurface S Not that, as a result of such a cut, not only an
unfeasible part of the combinatorial polytope is cut off, but also an unfeasible piece of
S.
Thus SCM exploits the fact that x * S and E P P C = conv S . This
inclusion suggests further prolongation of the edges x j , x ji , i J n , unless they
j
intersect S and forming the plane j through n of these intersection points
z ji , i J n , the closest to x j . As a result, we utilize edges x j , z ji , i J n ,
j j
endpoints of the shortest n of which:
ji '
Z j = z l S (23)
lJ n
are used for constructing a hyperplane (15), respectively, the condition (18) is
replaced by:
iJ n S a mj j +1x − bmj j +1 0.
x z ji (24)
j
An illustration of this method is given in Figures 6, 7. It shows a comparison of
cuts constructed by all listed methods. The figure illustrates that a SCM-cut is
deepest.
Fig. 6. SCM illustration Fig. 7. An SCM comparison
3.4 Polyhedral-Surface Cutting-Plane Method (PSCM)
Let us generalize CCM, CPCM, and SCM in a method called the Polyhedral-Surface
Cutting Plane Method (PSCM).
For that, we introduce a polyhedral cone with a vertex x j :
Cone( x j ) = {x R n : A j x b j }, (25)
where A j x b j is the collection of constraints of an H-representation of P j active
at x j .
Let S be a surface:
S {S , S j , S 'j }, (26)
j j
where S j = D j , D j = {x R n : A x b } ,
j j 'j 'j
S j = D j , D j = {x R n : A x b } , S 'j = D 'j , D 'j = { x R n : A x b } ,
j j 'j 'j
A xb and A x b are collections of constraints of P j and P respectively,
which are non-active at x j . The cone (25) allows the conical combination description
(CCD):
nj
j
Cone( x ) = x + l v jl : l R 1+ , v l V l , l J n ,
j
(27)
j
l =1
where v jl - is the direction vector of an edge x j , x ji , x ji N j ( x j ) , i J n , a
P j
set V j = {v ji }iJ is found in such a way that V j S j .
nj
PSCM outline: On each iteration, choose a surface (26).
Find a cone (25) and its CCD (27). Form a cutting plane (15) through points
jil
V 'j = {v }lJ V j , which are the closest to x j .
n
j j
Verify a condition: if x V j a x − b j 0 holds, for instance, if
m j +1 m +1
V 'j = V j , then the corresponding new constraint (16) is added to current constraints.
Otherwise, form a hyperplane through a point v j V j , which is the closest to x j
and cut it off. Then the corresponding cut is added to the current collection of
constraints.
For instance, if E S r ( a ) form a hypersphere S j ( x j ) centred at x j with a
r
radius r = v − x
j j j
, as (15) it can be taking a hyperplane, where n − 2 -sphere
S r ( a ) S j ( x j ) is situated.
r
In (26), if at step j S = S j is chosen, PSCM becomes MCCM; if S = S 'j -
CPCM; if S = S - SCM. Thus, PSCM covers all the above cutting-plane approaches.
Moreover, it allows choosing different surfaces from a family (26) at various stages of
implementing PSCM, thus combining MCCM, CPSM, SCM together.
4 Discussion
Problem 1 can be solved to optimality by another well-known approach – Branch and
Bound [5, 13, 24]. For sets (9)-(12), the corresponding methods can utilize partitions
of these sets into lower-dimensional ones of the same combinatoral type [19, 20].
Other original approaches to linear constrained permutation optimization are
described in [25, 29, 30]. Among cutting-plane methods attacking Problem 1 is the
one presented in [18], where another generalization of CCM is presented called a
Spherical Cutting-plane Method (SCPM). Along with polyhedral sphericity of
(9)-(12), it utilizes another important feature of these sets - the simplicity of solving
unconstrained linear problems. This results in a possibility to form cuts of unfeasible
solutions of polyhedral relaxations by cutting planes, which do not require a search of
their neighbourhood. In turn, an advantage of PSCM over SCPM is a depth of cuts.
The listed approaches can be combined with approximate and heuristics ones
[25,28,30], which expectedly will result in an expansion of a class of Boolean,
permutation-based, and other combinatorial problems having wide real-world
applications solvable in a reasonable time.
5 Conclusion
In this paper, we propose a new cutting plane method for solving linear optimization
problems on VLSs, using the ability to fit these sets into a convex hypersurface. The
scope of this method is not limited to such sets, since the optimization problem on an
arbitrary discrete set can be reduced to optimization on one or more VLSs. In the
future, we plan to develop PSCM into new classes of combinatorial sets, in particular,
we are working on the search for new cutting plane methods.
References
1. Balinski, M.L., Hoffman, A.J. (eds.): Polyhedral Combinatorics: Dedicated to the Memory
of D.R.Fulkerson. Elsevier Science Ltd, Amsterdam ; New York : New York (1978)
2. S. Boyd and L. Vandenberghe: Localization and Cutting-Plane Methods. Stanford Univer-
sity, Stanford (2003)
3. Brouwer, A.E., Cohen, A.M., Neumaier, A.: Distance-Regular Graphs. Springer-Verlag,
Berlin Heidelberg (1989).
4. Brualdi, R.A.: Combinatorial matrix classes. Encyclopedia of Mathematics and its Appli-
cations. Cambridge University Press, Cambridge (2006)
5. Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., Schrijver, A.: Combinatorial optimi-
zation. Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley
& Sons, Inc., New York (1998)
6. Coxeter, H.S.M.: Regular and semi-regular polytopes. III. Mathematische Zeitschrift
200(1), 3–45 (1988). https://doi.org/10.1007/BF01161745
7. Elf, M., Gutwenger, C., JГјnger, M., Rinaldi, G.: Branch-and-Cut Algorithms for Combi-
natorial Optimization and Their Implementation in ABACUS. In: JГјnger, M. and Naddef,
D. (eds.) Computational Combinatorial Optimization: Optimal or Provably Near-Optimal
Solutions. pp. 157–222. Springer Berlin Heidelberg, Berlin, Heidelberg (2001).
https://doi.org/10.1007/3-540-45586_5.
8. Emets, O.O., Emets, E.M.: Cut-off in linear partially combinatorial problems of Euclidean
combinatorial optimization. Dopovd Natsonal no Akadem Nauk Ukrani. Matematika. Pri-
rodoznavstvo. Tekhnchn Nauki (9), 105–109 (2000)
9. Emets, O.A., NedobachiД, S.I., Kolechkina, L.N.: An irreducible system of constraints of
a combinatorial polyhedron in a linear-fractional optimization problem on permutations.
Diskret. Mat. 13, 110–118 (2001). https://doi.org/10.1515/dma.2001.11.1.95.
10. Iemets, O.O., Yemets, E.M., Olhovskiy, D.M.: The Method of Cutting the Vertices of
Permutation Polyhedron Graph to Solve Linear Conditional Optimization Problems on
Permutations. Cybernetics and Systems Analysis. 50, 613–619 (2014).
https://doi.org/10.1007/s10559-014-9649-x.
11. Grande, F. On k-level matroids: geometry and combinatorics. Doctor of Natural Sciences
Dissertation, Institut fГјr Mathematik und Informatik (2015)
12. Green, R.M.: Homology representations arising from the half cube, II. Journal of Combi-
natorial Theory. Series A 117(8), 1037–1048 (2010)
13. Korte, B., Vygen, J. Combinatorial Optimization: Theory and Algorithms. Springer, Hei-
delberg ; New York (2018)
14. Marchand, H., Martin, A., Weismantel, R., Wolsey, L.: Cutting planes in integer and
mixed integer programming. Discrete Applied Mathematics 123(1), 397–446 (2002).
https://doi.org/10.1016/S0166-218X(01)00348-1
15. Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexi-
ty. Dover Publications (1998).
16. Pardalos, P. M., Du, D., Graham, R. L., Eds.: Handbook of combinatorial optimization.
Springer, New York (2013)
17. 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
18. 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).
19. Pichugina, O., Yakovlev, S.: Euclidean Combinatorial Configurations: Typology and Ap-
plications. In: 2019 IEEE 2nd Ukraine Conference on Electrical and Computer Engineer-
ing (UKRCON). pp. 1065–1070 (2019). https://doi.org/10.1109/UKRCON.2019.8879912.
20. Pichugina, O., Yakovlev, S.: Euclidean Combinatorial Configurations: Continuous Repre-
sentations and Convex Extensions. In: Lytvynenko, V., Babichev, S., WГіjcik, W., Vyno-
kurova, O., Vyshemyrskaya, S., and Radetskaya, S. (eds.) Lecture Notes in Computational
Intelligence and Decision Making. pp. 65–80. Cham : Springer, Zalizniy Port, Ukraine
(2019). https://doi.org/10.1007/978-3-030-26474-1_5.
21. 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/https://doi.org/10.1007/978-3-030-33695-0_17.
22. Pulleyblank, W.R.: Edmonds, matching and the birth of polyhedral combinatorics. Docu-
menta Mathematica. pp. 181–197 (2012)
23. Sanyal, R., Sottile, F., Sturmfels, B.: Orbitopes. Mathematika 57, pp. 275–314 (2011).
24. Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer Science &
Business Media (2002)
25. Stoyan, Y.G. Yemets, O.O.: Theory and Methods of Euclidean Combinatorial Optimiza-
tion. ISSE, Kyiv (1993) (in Ukrainian)
26. Taha, H.A.: Integer Programming: Theory, Applications, and Computations. Academic
Press, New York (2014)
27. Yakovlev, S. Convex extensions in combinatorial optimization and their applications. In:
Butenko, S. et al. (eds.) Optimization and its Applications 130, pp. 567–584. Springer,
Cham (2017)
28. Yakovlev, S., Pichugina, O.: On Constrained Optimization of Polynomials on Permutation
Set. In: Proceedings of the Second International Workshop on Computer Modeling and In-
telligent Systems (CMIS-2019). pp. 570–580. CEUR Vol-2353 urn:nbn:de:0074-2353-0,
Zaporizhzhia, Ukraine (2019).
29. Yakovlev, S.V., Valuiskaya, O.A. Optimization of linear functions at the vertices of a
permutation polyhedron with additional linear constraints. Ukr. Math. J. 53(9), pp. 1535–
1545 (2001)
30. Yemelichev, V.A., Kovalev, M.M., Kravtsov, M.K.: Polytopes, graphs and optimization.
Cambridge University Press, Cambridge (1984)
31. Ziegler, G.M.: Lectures on 0/1-Polytopes. In: Kalai, G. and Ziegler, G.M. (eds.) Poly-
topes – Combinatorics and Computation. pp. 1–41. Birkhuser Basel (2000).
https://doi.org/10.1007/978-3-0348-8438-9_1.