The Polyhedral-Surface Cutting-Plane Method for Linear Combinatorial Optimization

Abstract

For linear optimization on combinatorial sets inscribed into a convex surface, a Polyhedral-Surface Cutting-Plane Method (PSCM) is offered. It essentially 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 realworld tasks modelled as combinatorial optimization problems.

Keywords

• Linear Optimization
• Combinatorial Optimization
• vertex-located set
• surface-located set
• cutting-plane method
• polyhedral relaxation

-

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. Let us consider a linear optimization problem over a finite point configuration (FPC) ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 6 ) ( 7 ) Ax  b, x  E , E = P  S , dim P = n, 1 <| E |< , where convex hypersurface, E  is an FPC, i.e.,

A  R mn , b  R m , c, x  R n , P  is a full-dimensional polytope, S is a f : R n → R 1 − convex : S = {x  R n : f ( x) = 0} .

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 = conv E , ( 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 combinatorial space of permutations with repetitions [19,20]. It is a set R n of the Enk (G) = {x  R n : {x} = {x1, ..., xn} = G} ( 9 ) ( 10 ) ( 11 ) ( 12 ) induced by a multiset

G = {g i }iJ n ={1,...,n}  R 1 : g i  g i+1, i  J n−1, with a ground set S (G) = {ei }iJ k : ei < ei+1, i  J k −1 ;

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:

Enk (G) = {x  R n : {| x |} = {| x1 |, ...,| xn |} = G}.

Finally, these are the well-known Boolean set Bn and binary set Bn' , where Bn = {0, 1}n ;

B n' = {−1, 1}n , 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.

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 Enk (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 PBn' (x) = n ; 2. Despite the fact that the generalized permutohedron Pnk (G) , which is the convex hull of Enk (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 = Enk ( G ) : a) Pnk ( G ) = conv Enk ( G ) - is the generalized permutohedron; b) x  Enk ( G )

N Pnk ( G ) (x) = n1n2 + ... + nk −1nk ; c) an Hrepresentation is known and has up to 2 n −1 constraints. However, for Enk ( G ) , PR of Problem 1 is polynomially solvable based on the following fact: x  R n such that xi  xi+1, i  J n−1 ,

j j n n x  Pnk ( G )  xi  gi , j  J n−1; xi = gi .

i=1 i=1 i=1 i=1 ( 13 )

Here, N P[.] ( x j ) is a neighbourhood of x j in 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); P j

b) if x j  E ' , then terminate;

c) otherwise, form N P j intersecting at x j . The edges' endpoints are: P j ( x j ) , choose the shortest n edges  x j , x jil  , l  J n , of   X j =  x jil  lJ n  vert P j ; d) form a hyperplane through points ( 14 ):  j = x : a j m j +1 x − b j m j +1 = 0 : a j m j +1 x j − b j m j +1 > 0;

e) choose a subspace cutting off x j :

Step 2. Go to the next iteration:  j : a j m j +1 x − b j m j +1  0.

( 14 ) ( 15 ) ( 16 ) j = j +1, m j = m j−1 +1, P j = x  P j−1 : a j x − bmj j  0. m j 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: For fulfilling ( 17 ), it is sufficiently that x  N j (x j )

P

amj j +1x − bmj j +1  0. n j = N j (x j ) = n.

P ( 17 ) ( 18 )

If ( 17 ) is false, cut x j by a hyperplane  j is built passing through a point of N j (x j ) in one of the ways:

P

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 iJ 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).

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. 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 up to their intersection with a surface P getting extended edges  x j , x ji  , i  J n j ,    x j , y ji  , i  J n j ,   Endpoints of first n the shortest edges are used instead of ( 14 ):

X j → Y j =  y jil'   ( 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. ( 19 ) ( 20 ) ( 21 ) We operate with a bound of P , therefore ( 18 ) is replaced by: x  y ji   P amj j +1x − bmj j +1  0 . ( 22 ) Fig. 4. The Combinatorial Polytope

Cutting-Plane Method (CPCM)

Fig. 5. The Surface-Cutting 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 j , unless they intersect S and forming the plane  j through n of these intersection points z ji , i  J n j , the closest to x j . As a result, we utilize edges  x j , z ji  , i  J n j , endpoints of the shortest n of which:

Z j =  z jil'   are used for constructing a hyperplane ( 15 ), respectively, the condition ( 18 ) is replaced by:

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. 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 }, 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 }, ( 24 ) ( 25 ) ( 26 ) where

S j = D j , D j = {x  R n : A j x  b j } S j = D j , D j = {x  R n : A j x  b j } , S 'j = D 'j , D 'j = {x  R n : A'j x  b 'j } , A j x  b j and A'j x  b

'j 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): (27)  n j  Cone(x j ) =  x j +  l v jl :  l  R 1+ , v l V l , l  J n j  ,

 l=1  where v jl - is the direction vector of an edge  x j , x ji  , x ji  N P j (x j ) , i  J n j , a set V j = {v ji }iJ n j is found in such a way that V j  S j .

PSCM outline: On each iteration, choose a surface ( 26 ).

Find a cone ( 25 ) and its CCD (27). Form a cutting plane ( 15 ) through points V 'j = {v jil }lJ n  V j , which are the closest to x j .

Verify a condition: if x V j amj j +1x − bmj j +1  0 holds, for instance, if 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 j = v j − x 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. 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 Intelligent 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.) Polytopes – Combinatorics and Computation. pp. 1–41. Birkhuser Basel (2000). https://doi.org/10.1007/978-3-0348-8438-9_1.

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 University, 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 Applications . Cambridge University Press, Cambridge ( 2006 )

5. Cook , W.J. , Cunningham , W.H. , Pulleyblank , W.R. , Schrijver , A. : Combinatorial optimization . 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 Combinatorial 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. Prirodoznavstvo. 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 Combinatorial Theory. Series A 117 ( 8 ), 1037 - 1048 ( 2010 )

13. Korte , B. , Vygen , J. Combinatorial Optimization: Theory and Algorithms . Springer, Heidelberg ; 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 Complexity . 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 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 .

20. 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 . 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 . Documenta 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 Optimization . ISSE, Kyiv ( 1993 ) (in Ukrainian)

26. Taha , H.A. : Integer Programming: Theory, Applications , and Computations. Academic Press, New York ( 2014 )