Exploiting Orbits in Symmetric ILP
Contents
1. with gi E U B for i 1 k and h Gk Generators of stab 6 1 k G can be thus obtained by selecting a all permutations g g gk 1 gk With gi E U B for i 1 k such that g 6 1 k 6 1 k b all the entries in U 8 fori k 1 n Listing all permutations described in a can be done easily with a backtracking procedure Observe that go g all stabilize point 6 1 and thus we must choose g U 8 1 such that gi G 1 G 1 k Once gi is chosen as g3 9k all stabilize point 6 2 we must choose gz U 2 such that gi g2 G 2 B 1 k gi BIBI ie g2 2 gf G 1 k gi G 1 The same reasoning applies for selecting g3 9x The backtracking procedure given below outputs generators of the stabilizer of the points in G 1 k It consists of an initializing procedure stabilizer_gen that calls a recursive procedure stab_gen Exploiting Orbits in Symmetric ILP 15 stabilizer_gen a k Outputs generators of stab G 1 k G where G is the group repre sented by T with base 8 Output U G for i k 1 n ident identity permutation remain p 1 k stab_gen a k ident remain 1 The parameters of the call to stab_gen have the following interpretation ind refers to the point G ind being treated during the current call perm is a per mutation in G sending 6 1 ind 1 on a subset B C pf 1 k and remain is the set perm 1 12. F 4 Moreover as a ranked branching rule is used and as i is fixed at d R4 i lt min R4 j j FP Ff As g 1 g Ff Ug i FfUi and R4 F Ui lt R4 F F is not a representative with respect to R Lemma 1 i and Lemma 3 ii then show that b T a contradiction Exploiting Orbits in Symmetric ILP 9 In situations were the strict setting algorithm is an expensive operation it might be faster to use it only at a subset of the nodes of the enumeration tree At other nodes it is possible to use the following result to draw on the knowledge of fixed and set variables at other nodes in the tree Note also that in certain cases the strict setting algorithm works with an outside hint and that different conclusions might be obtained with different hints For example for the reduced cost fixing procedure with degenerate LPs two different optimal LP bases might yield different groups of variables to set to 0 or 1 Lemma 5 Let z be the value of the best known feasible solution of ILP 1 while processing node a E T and let d be a node of T Let g G such that g F8 C FS U Se and g F2 C FU S2 Then no optimal solution x in T with value better than z has zg 1 fori S or Tgi O fori Se Proof Assume that the indices in S U S i1 ip are ordered according to the order in which the setting algorithm proved that these variables could be set Let b iz be the ancestor of d in T at which
3. N ii Otherwise choose freely any index f N It follows that if each variable has been used at least once as a branching variable the resulting rank vector R is a permutation of I The branching rule of 23 is obtained by always choosing the minimum index in N in step ii above Note that a variable 7 S for k 0 or k 1 might be the chosen branching variable Then the rank vector is updated a unique son b is created since the other son could be pruned by infeasibility and variable becomes one of the fixed variables In the remainder of the paper we consider a branch and cut using a ranked branching rule The rank vector R at the start of the processing of node a is denoted by R R depends on the enumeration strategy but the results given below are valid for any enumeration strategy Let J j1 jp be an unordered multiset of I t Let J be the ordered mul tiset obtained from J by ordering its elements in non decreasing order Given two multisets J J2 in I we write J lt Jz resp Jy lt Jz if J is lexico graphically smaller or equal to Jz resp lexicographically strictly smaller than J2 Exploiting Orbits in Symmetric ILP 5 For a given rank vector R a set J is a representative of the sets in its orbit under G if its rank R J R y j J is lexicographically minimum among the sets in its orbit under G i e R J 3 R g J Vg EG Notice that for any rank vecto
4. Sphere Packings Lattices and Groups Springer 1993 7 Feo T A Resende G C A Probabilistic Heuristic for a Computationally Difficult Set Covering Problem Operations Research Letters 8 1989 67 71 8 Fulkerson D R Nemhauser G L Trotter L E Two Computationally difficult Set Cover ing Problems That Arise in Computing the 1 width of Incidence Matrices of Steiner Triple Systems Mathematical Programming Study 2 1974 72 81 9 Hall M Combinatorial Theory Wiley 1986 10 Jiinger M Naddef D eds Computational Combinatorial Optimization Lecture Notes in Computer Science 2241 Springer 2001 11 ILOG CPLEX 7 1 User s Manual 2001 12 Elf M Gutwenger C Jiinger M Rinaldi G Branch and Cut Algorithms for Combina torial Optimization and their Implementation in ABACUS in 10 155 222 13 Etzion T Wei V Zhang Z Bounds on the Sizes of Constant Weight Covering Codes Designs Codes and Cryptography 5 1995 217 239 14 Hoffman C M Group Theoretic Algorithms and Graph Isomorphism Lecture Notes in Computer Science 136 Springer 1982 15 J nger M Thienel S Introduction to ABACUS A Branch And CUt System Oper ations Research Letters 22 1998 83 95 16 Kreher D L Stinson D R Combinatorial Algorithms Generation Enumeration and Search CRC Press 1999 17 Leon J S On an Algorithm for Finding a Base and a Strong Generating Set for a Group Given by
5. The rank vector and the fact that variables fixed and set to zero are moved to the end of the base instead of only the variables fixed to 0 as in 23 require only a small modification of first_in_orbit line marked below The justification of this comes directly from the relation 2 The proof of correctness of the procedure is identical to the one in 23 as the ordering of the variables in the base and the test take into account that the lexicographic ordering is done with respect to R The complexity of the procedure is O n k where k is the cardinality of the set first_in_orbit a k Returns true if and only if R G 1 k is lexicographically minimum among all sets in orb 1 k G ident identity permutation remain p 1 k islermin true f_in_orb a k ident remain 1 islexmin return islexmin The parameter islexmin is passed by reference and is used to stop the procedure as soon as it is known that R G 1 k is not lexicographically minimum among all sets in orb G 1 k G f_in_orb a k perm remain ind islexmin If islexmin false then return For each 7 remain do If 87 1 i gt part_zerolind and R i lt R buf then islexmin false return h T G6 ind i If h A then loc remain remain i loc_remain h 1 loc remain loc_perm perm h If ind lt k then f_in_orb a k loc_perm loc_remain ind 1 islexmin Exploit
6. however this is not true anymore as the node corresponding to might be pruned by isomorphism and the representative of its orbit might have x 1 k To avoid this it is necessary to use a strict setting algorithm This is a procedure used to identify variables that must be 0 resp 1 in every optimal solution of ILP 1 having 8 Fran ois Margot value less than z that is feasible for J P The procedure then includes the variables in S resp S and sets them to 0 resp 1 If the algorithm wants to set a variable in Ff U Sf to the value 1 k for k 0 or k 1 ILP is infeasible and a is pruned For simplicity this observation is implicit in the remainder of the paper For what follows it is essential that the strict setting algorithm works under symmetry If the setting algorithm is able to set variable x in ILP then for any g G it is able to set variable x in the ILP obtained from JL P by permuting the variables according to g This essentially prevents the setting algorithm to work based on conditions linked to the isomorphism pruning but allows for traditional setting procedures In the remainder of the paper we only consider strict setting algorithms working under symmetry As an example of a strict setting algorithm consider the usual reduced cost fixing procedure Let gt 0 be the reduced costs of the optimal solution of the linear relaxation of ILP having value z If x is non basic at its low
7. Generating Permutations Mathematics of Computation 35 1980 941 974 18 Leon J S Computing Automorphism Groups of Combinatorial Objects in Computa tional Group Theory Atkinson M D ed Academic Press 1984 321 335 19 Luks E Permutation Groups and Polynomial Time Computation in DIMACS Series in Discrete Mathematics and Theoretical Computer Science 11 1993 Groups and Com putation L Finkelsein W Kantor eds 139 175 20 Mannino C Sassano A Solving Hard Set Covering Problems Operations Research Letters 18 1995 1 5 21 http www ms uky edu fmargot rec_pub html 22 Margot F Small Covering Designs by Branch and Cut Research report 2000 27 De partment of Mathematics University of Kentucky To appear in Mathematical Program ming 23 Margot F Pruning by Isomorphism in Branch and Cut Research report 2001 08 De partment of Mathematics University of Kentucky 24 S Lytsin An Updated Table of the Best Binary Codes Known in Handbook of Coding Theory V S Pless W C Huffmann eds North Holland Elsevier 1998 25 Martin A General Mixed Integer Programming Computational Issues for Branch and Cut Algorithms in 10 1 25 26 McKay B D Nauty User s Guide Version 1 5 Computer Science Department Aus tralian National University Canberra 27 Mills W H Mullin R C Coverings and Packings in Contemporary Design Theory A collecti
8. Lemma 3 Let R be the rank vector obtained at the end of the enumeration for B Then i IfaeT T then F is not a representative of its orbit with respect to R ii IfaeT then Ff is the unique representative of its orbit with respect to R iii B and B return the same optimal value Proof i If a T T then a node b on the path between the root of T and a is pruned by isomorphism Then F is not a representative with respect Exploiting Orbits in Symmetric ILP 7 to R and thus by Lemma 1 i it is not a representative with respect to R By definition of a ranked branching rule we have for all i F F that R i gt max R j j Fi Then by Lemma 2 F cannot be a representative with respect to R ii As a was not pruned by isomorphism Ff is a representative with respect to R According to the rule for updating the rank vector during the enumeration we have that R ii lt n 1 for all i Ff By Lemma 1 ii and iii Ff is the unique representative with respect to R iii Let a be a node of T for which F is the characteristic vector of an optimal solution to ILP 1 and such that Ff I Ff A representative of the orbit of F under G with respect to R is a set F and by i and ii there is a node bET with F F and Fe F As B processes node b at some point B yields the same optimal value as the one returned by B Lemma 3 shows the validity o
9. is a representative if and only if F 1 Since Ff and Ff are always disjoint a would be pruned by the isomorphism test working with both Ff and F and all nodes containing the optimal solution would be pruned One way to work with both Ff and F would be to say that node a is not pruned if Ff is a representative and that Ff is lexicographically minimal in its orbit under stab Ff G But this results in pruning exactly the same nodes as the proposed isomorphism pruning test as Fo is filling the gaps between elements in Ff and F UFS 1 2 k for some k showing that FY is always lexicographically minimal in the considered orbit Let 6 be a branch and cut using a ranked branching rule isomorphism pruning and a particular enumeration strategy Let 7 be the enumeration tree of B assuming that nodes are pruned only by isomorphism pruning or when the LP relaxation of the corresponding ILP is infeasible This implies that even in the case where the linear relaxation associated with node a has an integer optimal solution B continues to branch Pruned nodes are not included in T Let B be the branch and cut obtained from B by dropping isomorphism pruning but enumerating the nodes in the same order as B the remaining nodes being processed arbitrarily after that Let 7 be the enumeration tree of B assuming that nodes are pruned only by infeasibility Pruned nodes are not included in T Note that T CT
10. one variable from each orbit of stab Ff G Note that the situation is different for the setting algorithm based on reduced costs Since the calculations are done with respect to one particular optimal base it is possible that the algorithm is able to set i but not 7 A side result of the strong branching calculations is the occasional setting of some variables Let x be a candidate for strong branching If ILP with x k for k 0 or k 1 is infeasible or has an optimal value larger or equal to the value z of the best known feasible solution or strictly larger than z 1 if c is integer then x may be set to 1 k This is a strict setting algorithm and thus the orbit setting described in Section 4 is still valid In the computational tests given in the next section when strong branching is used it means that the strict setting algorithm described above is used 12 Francois Margot 6 Group Operations Following 23 the chosen group representation and algorithms are based on the Schreier Sims representation of G 2 5 14 16 18 Let Go G and G stab i Gi_1 for i 1 n Observe that Go Gi Gn are nested subgroups of G For k 1 n let orb k Gk 1 hi jp be the orbit of k under Gp_1 Then for each 1 lt i lt p let hg j be any permutation in Gz_ sending k on ji ie hp jilk ji Let Uk hej hej Note that Up is never empty as orb k Gy_1 always contains k Arrange the p
11. variable xi was set for k 1 p Note that pole C F and F C F 2 We prove by induction on k that rg satisfies the statement For k 1 observe that a problem isomorphic to JL P is obtained from ILP 1 by assigning the value 0 to all variables in g FO and the value 1 to those in g F G The choice of g implies that all these variables have the corresponding values in JEP It follows that the setting algorithm applied at node a can prove that r satisfies the statement The reasoning for k gt 1 is similar since a problem isomorphic to LP is obtained from ILP 1 by assigning the value 0 to all variables in g F ie and the value 1 to those in go Feo Moreover when the setting algorithm was used at b ip to prove that x could be set the other variables already set had indices in t1 1 Since all variables in Tyli for 1 lt q lt k 1 are set to the proper value in JL P and thus the strict setting algorithm on LZ P can prove that g ip can be set too Oo One difficulty in using Lemma 4 or Lemma 5 to set variables to 0 or 1 is com puting the set G of all g G satisfying the statement For given nodes a and d this set has no nice property and might not be a subgroup of G Note however that there is no need to compute the whole set G as the results remain valid even if setting is done only for a subset of G The following corollaries are easier to use albeit weaker than the Lemma
12. with R BlL lt lt R G fixed_one The vector part_zero is used to store information about variables fixed or set to 0 For i 1 fiwed_one 3 part_zero i n are the variables that have been fixed or set to 0 before Gi was fixed to 1 For i fixed_one 1 Blpart_zero i n FG U S i e all the variables currently fixed or set to 0 at a The remaining variables appear in in increasing order of their rank after variables in Ff and before variables in Ff US This structure of 2 is not difficult to maintain throughout the branch and cut using the procedure down of 23 and a more general base change algorithm when needed The procedure down has complexity O n for downing a point This is a compact way to store the sets Ff Ff and S with their history Note that the set Ff can be recovered as j Blpart_zero fixed_one 1 n R j lt R bvf 2 Another advantage is that if the branching variable at a is chosen as a variable in Sg there is no real need to actually generate the son This is becaus the data structure and ILP of the son would be identical to those of a except for buf which can be updated However when branching on a variable in j Sf we might need to modify the base by moving j at its appropriate place and updating the vector part_zero Although this could be done at node a we nevertheless create one son in this situation In this section we consider algorithms for solving que
13. Corollary 1 Let i F Then all the variables in orb i stab F G may be set to 0 in ILP 10 Fran ois Margot Proof This is Lemma 4 for d a and g stab F G i e g satisfying g F Fe o Corollary 2 Fori F US all the variables in orb i stab Ff G can be set to 0 in ILP Fori S all the variables in orb i stab F G can be set to 1 in ILP Proof For i F the result is Corollary 1 After setting these variables to 0 we have g Fy C FS US Then for i S U SF the result is Lemma 5 for d a and g stab Ff G o Consider the following operations at node a T with rank vector R called an orbit setting Let set_alg a be the strict setting algorithm used at node a with variables in Ff U Sg having value 0 and variables in Ff U S having value 1 i Compute all orbits in stab FY G ii For each i S set to 1 all variables in orb i stab F G and update S accordingly For each i Fi U S set to 0 all variables in orb i stab F G and update S accordingly iii If additional variables can be set by set_alg a update S and S accordingly and go to ii iv If N f then return n 1 and stop v Let xy be the variable that would be chosen as the branching variable ac cording to the ranked branching rule If Ff U f is not a representative with respect to R then set to 0 all variables in orb f stab F G update S accordin
14. Mathematical Programming manuscript No will be inserted by the editor Fran ois Margot Exploiting Orbits in Symmetric ILP February 2003 Abstract This paper describes components of a branch and cut algorithm for solving in teger linear programs having a large symmetry group It describes an isomorphism pruning algorithm and variable setting procedures using orbits of the symmetry group Pruning and orbit computations are performed by backtracking procedures using a Schreier Sims table for representing the symmetry group Applications to hard set covering problems generation of covering designs and error correcting codes are given Key words Branch and cut isomorphism pruning symmetry 1 Introduction An integer linear program ILP is symmetric if its variables can be permuted without changing the structure of the problem Symmetric ILPs frequently ap pear when formulating classical problems in combinatorics or optimization graph coloring problem scheduling of jobs on parallel identical machines covering de sign problems code construction see 31 for additional real world examples Even for relatively modestly sized problems ILPs with large symmetry groups are difficult to solve using traditional branch and bound or branch and cut al gorithms We assume that the reader is familiar with these procedures as ex cellent introductions can be found in 10 30 32 33 The trouble comes from the fact that many subproblems
15. Peoot053 85 oar 190 if ona ase ar a o Ccov1174 87 113 69 036 21 454 16 103 Table 2 Enumeration tree size A means that CPLEX7 1 did not finish after days of running A means that it ran out of memory Exploiting Orbits in Symmetric ILP 21 Table 3 gives the CPU times of the different algorithms Comparing BC1 with BC2 and BC3 with BC4 we see that the time spent on the orbit setting is usually more than offset by the time savings due to the reduction in the number of nodes in the enumeration tree The exception here is STS81 although the total CPU time for BC4 is not worse than the one for BC3 Variants BC2 and BC4 seem to dominate BC1 and BC3 respectively BC2 is faster than BC4 on all problems except ST S81 and cov7114 This is not exactly a surprise as it is well known that the time to perform strong branching is non negligible In addition all these problems are solved in a few hundred nodes at most by BC2 making it hard for BC4 to recover the cost of reoptimizing 20 problems at each node of the enumeration tree However for cov1174 where the enumeration tree of BC2 has close to 70 000 nodes BC4 is significantly faster despite spending about 2 3 of the CPU time in the strong branching setting algorithm eoar 870 a T E E ojl ojl N olo 75 e e 95 a 85 3 39 95 Peouto75 o oo o 193 1m 118 a o Table 3 CPU times rounded in seconds ordered as Total time strong branching time orbi
16. The following property is crucial for the validity of the pruning Lemma 2 Let J C I be a representative under G with respect to rank vector R Let J J j with j arg max Rii i J Then J is also a representative with respect to R Proof If J is not a representative then there exists g G such that R g J lt R J Then R g J lt R J a contradiction Consider the following isomorphism pruning to be applied at node a of the enumeration tree of a branch and cut using a ranked branching rule If Ff is not 6 Fran ois Margot a representative with respect to R then prune node a Node a is said to be pruned by isomorphism for short Remark 1 This isomorphism pruning introduces an asymmetry between vari ables fixed to 1 and those fixed to 0 It would be of course possible to define the representative using Fj instead of Ff with similar results Note however that pruning nodes where at least one of Ff and Ff is not a representative with respect to R would not work To simplify the following assume that the branching variable is chosen according to the minimum index rule implying that R is the identity permutation Consider the group generated by the permutation 2 3 1 7 and suppose that the optimal solution of the ILP 1 is obtained at node a when two of the variables have value 1 and the remaining one has value 0 Then F is a representative if and only if Ff 1 2 and F
17. ch by fixing the value of one variable x to 0 or 1 We make a difference between a variable fixed to 0 or 1 and a variable set to 0 or 1 A variable is fixed to a value if this is the result of a branching operation it is set to a value if for some reason other than a branching decision e g reduced cost fixing logical implications the variable must take that particular value Let a be a node of the branch and cut enumeration tree We denote by F resp F the set of indices of variables fixed to 0 resp to 1 at a and N for the set of indices of variables that are not fixed to 0 or 1 at a We use S resp S for the set of indices of variables set to 0 resp to 1 at a Note that S U S C N 3 Ranked Branching Rule Let a and b be two nodes of the enumeration tree of a branch and cut algo rithm The subproblems associated with nodes a and b of the branch and cut are isomorphic if there exists a permutation g G such that g F FP for k 0 1 Using this definition to prune nodes is difficult for two reasons First for a given pair of nodes a b deciding if a suitable permutation g G exists is not easy Second this decision problem would have to be solved for a large number of pairs of nodes The goal of this section is to present a practical isomorphism 4 Francois Margot pruning algorithm One advantage of the proposed algorithm is that it works with a single node a of the enumeration tree instead of a
18. e form min ca 1 s t Ax gt b x 0 1 where A is an m x n matrix Without loss of generality we also assume that the entries in A b and c are all integers For a permutation 7 of the n variables and a permutation o of the m rows of A let A z o be the matrix obtained from A by permuting its columns according to 7 and its rows according to Let G r r c c and there exists o s t o b b A t o A Exploiting Orbits in Symmetric ILP 3 Clearly G is a permutation group of I Moreover for 7 G a point Z is feasible resp optimal for the linear relaxation of ILP 1 if and only if a z is feasible resp optimal for that ILP Hence G is a symmetry group of the feasible and of the optimal set of the ILP Let S C I To simplify the notation we make no difference between a set S and its characteristic vector and sets containing a single element e are written simply e instead of e The orbit of S under G is orb S G S CI S g S for some g G The stabilizer of S in G is the subgroup of G given by stab S G gE G g S S For 1 lt a lt b lt n we write v a b for the entries v a vla 1 v b of v as an unordered set If g1 gk are k permutations of I the permutation g g1 gx is obtained by applying the permutations from right to left i e g v g g2 gk v for any n vector v The proposed branch and cut algorithm will bran
19. er bound and z gt z then x 0 in every feasible solution of ILP with value better than z A similar test can be used for a non basic variable at its upper bound Since we assume that c is integer it is valid to replace the condition by the stronger z gt z 1 We consider a branch and cut 6 using isomorphism pruning a ranked branching strategy and a strict setting algorithm Let 7 be the nodes in the enumeration tree of B that are not pruned by infeasibility or isomorphism For a T let TJ be the subtree of T rooted at a A feasible leaf of T is a leaf of 7 where all variables are fixed to 0 or 1 A solution in T is a solution x corresponding to a feasible leaf of T An optimal solution in T is a solution in T that is optimal for ILP 1 The next lemma shows that it is possible to set additional variables to 0 based on the variables fixed to 0 at ancestors nodes The idea is that if a variable was fixed to 0 at an ancestor d then either F U i is not a representative or the nodes f with F F U i are explored in the other subtree in the sons of d Coupling this observation with some permutations in G we get the following Lemma 4 Let a T and let d be an ancestor of a in T Let g G such that g FY C FE US and let i F Then no solution x in T has xi 1 Proof Assume that a feasible leaf b of 7 has g i F As g F C Feu Se c F we have that g F Ug i C F and thus F
20. ermutations in the sets Uk k 1 n in ann x n table T with T hej AJE orb k Gk 1 kj otherwise The table T is called the Schreier Sims representation of G This table is not uniquely defined as there is usually a choice for the permutations included in the sets Up However the non empty entries in the table are always the same in all representations It is possible to make a small generalization of the presentation by ordering the points of the ground set in an arbitrary order 8 called the base of the table In that case the subgroups G 3 for k 1 n are defined as the stabilizer of Blk in G 8 k 1 with G 3 o G The corresponding table is denoted by T Row k of T corresponds to the element k U 3 is the set of non empty entries in row k of T G and J denotes the corresponding set of indices j I T B k j 4 O also called the basic orbit of k in T following the terminology of 18 When the base is fixed we sometimes drop the qualifier 8 in these symbols but from now on each table T is defined with respect to a base Algorithms for creating the table T and for changing the base 8 of the rep resentation can be found in 2 4 5 14 16 18 The implemented algorithm for creating the table is closest to 16 and runs in O n n P where P is a given set of generators of the group The change of base algorithm is similar to one in 5 and runs in O n See 23 for details Although the alg
21. f the isomorphism pruning It should then be obvious that usual techniques such as cutting planes and pruning by bounds can be added to 6 keeping a branch and cut returning an optimal solution of the problem On the other hand setting variables to 0 or 1 requires some care as explained in the next section 4 Setting variables This section shows how to modify standard techniques for setting variables to 0 or 1 e g reduced cost fixing when coupled with isomorphism pruning This motivates the definition of a strict setting algorithm Then new results allowing for the setting of additional variables are presented A consequence of these results is that at node a all variables in the same orbit of stab F G can be set simultaneously to k as soon as it is known that one of them can be set to k by a strict setting algorithm working under symmetry for k 0 1 Let a be a node of the enumeration tree and let z be the value of the best known feasible solution to ILP 1 when processing node a Let LP denote the ILP at node a i e ILP 1 where variables in Ff U S take value k for k 0 1 It is sometimes possible to identify variables that may be set to 0 or 1 without affecting the optimal solution returned by a branch and cut Usually if it is possible to show that there exists an optimal solution z of ILP with Zi k for k 0 or k 1 then it is valid to set that variable to k at a When using a branch and cut with isomorphism pruning
22. fication of the algorithm allows for a more flexible rule to pick the branching variable called ranked branching rule It also introduces strict setting algorithms that can be used to set variables to 0 or 1 without conflicting with the isomorphism pruning Section 3 defines the ranked branching rule and describes its associ ated pruning algorithm Section 4 defines the strict setting algorithms and show how to use orbits of subgroups of G to set additional variables an operation called orbit setting Section 5 describes the strong branching procedure and the corresponding strict setting algorithm Section 6 briefly presents basic group al gorithms and data structures Finally Section 7 presents a comparison between several branch and cut algorithms to illustrate the effect of two strict setting al gorithms when coupled or not with orbit setting The test problems come from three types of applications set covering problems from Steiner triple systems covering designs and error correcting codes 2 Preliminaries Let JI be the set of all permutations of the ground set J 1 n II is known as the symmetric group of J A permutation in JT is represented by an n vector 7 with i being the image of i under r If v is an n vector and x I let w m v denote the vector w obtained by permuting the coordinates of v according to 7 i e wl rli vfi for allie I We consider an integer linear program ILP of th
23. gly and go to ii Otherwise update R return f and stop The output of the orbit setting is the value f in v for which Ff Uf is a representative or n 1 if no such f exists The validity of the orbit setting should be clear Step ii is an application of Corollary 2 and the correctness of Step v follows from Lemma 1 i and Corollary 2 It remains to show how to compute orbits in stab F G and how to test if a set is a representative or not This will be covered in Section 6 If orbit setting is used the operations performed at node a are f orbit setting at a Repeat until a criterion is met solve the LP relaxation of LP generate cuts If f lt n 1 then create two sons of a by fixing xp to 0 or 1 Exploiting Orbits in Symmetric ILP 11 It would of course be possible to apply the orbit setting a second time after cuts have been generated but the differences are likely to be minimal If orbit setting is not used the branching index f is obtained by repeated ap plication of step v of the orbit setting skipping the setting of variables in orb f stab F G when Ff U f is not a representative with respect to R 5 Strong Branching The selection of the branching variable is a crucial component of an efficient branch and cut While a rule of thumb can usually be devised for a particular problem a universal rule is more elusive For hard problems where reducing the size of the enumeration tree is particula
24. ied problems but numbers in Ta ble 1 relate to the original ILP We choose not to introduce new names for the modified problems as identical results could be obtained for the original ILP by running a similar branch and cut with the roles of 1 s and 0 s interchanged The symmetry groups were computed using the program nauty version 1 5 written by McKay 26 CPLEX7 1 is able to prove optimality of the optimal value of STS 45 in 52 seconds and solves ST S63 in a little bit more than 3 hours It fails to do so for ST S81 as it runs out of memory after 6 hours and having generated more than 9 million nodes 90 of them remaining in the tree Despite the fact Exploiting Orbits in Symmetric ILP 19 that ST S81 is solved easily by our branch and cut the solution of ST S135 still seems to be out of reach Its best known feasible solution has value 103 28 Covering designs Let V be a set of elements of cardinality v and let k and t be integers such that v gt k gt t gt 0 Let K be the set of all k subsets of V and T be the set of all t subsets of V A v k t covering design is a collection C of sets in K such that each t T is contained in at least one set of C A v k t covering design C is minimum if the cardinality of C is as small as possible Results and optimal values for these problems can be found in 27 Generators of the symmetry group are the v 1 permutations corresponding to swapping elements 1 and k for k 2
25. ifficult for standard branch and cut codes ST S45 was first solved by Ratliff in 1979 1 As an indication on the difficulty of these problems Avis 1 showed that any branch and bound algorithm using LP relaxations and dominance pruning will enumer ate at least 2V 3 nodes for an infinite family of problems STSn with n oo Feo and Resende 7 studied similar problems called ST S81 and ST S243 and found good heuristic solutions but only a few years ago Mannino and Sassano 20 were able to solve ST S81 to optimality Their branch and bound requires an enumeration tree with more than 900 million nodes They also introduced the problem STS135 for which they could only find an upper bound on the optimal value We report results for S7 S45 ST S81 and a problem generated according to the same method that we call ST S563 Since our branch and cut is asymmetric with respect to 0 s and 1 s in the solution from isomorphism prun ing working with Ff not with F and since any optimal solution for STS45 ST S63 or STS81 has more than 2 3 of the variables set to 1 it is much faster to solve the problems where all variables are complemented i e x is replaced by 1 2 fori 1 n The constraints of the resulting ILP become of the form Li a a lt 2 for the triples i j k generating an inequality x j p gt 1 of the corresponding ST S problem The objective is then to minimize ae y The statistics given below are for the modif
26. in the enumeration tree are isomorphic forcing a wasteful duplication of effort One way to deal with the symmetry is to try to remove or reduce it by fixing variables and adding inequalities cutting part of the feasible region while guar anteeing that an optimal solution of the original problem is still feasible 31 While this is sometimes an efficient approach it usually involves empirical ex perimentation each problem requiring a new study The approach followed in this paper along the lines of 23 is to deal with the symmetry by using the symmetry group of the problem to fix or set variables to generate cuts and to prune the enumeration tree The symmetry group is assumed to be part of the Fran ois Margot Department of Mathematics University of Kentucky Lexington KY 40506 0027 e mail fmargot ms uky edu Mathematics Subject Classification 1991 90C10 90C27 90C57 2 Francois Margot input If the symmetry group is not completely known any of its subgroups can be used Alternatively software computing the automorphism group of graphs for example nauty 26 can be used to generate the symmetry group from the ILP formulation In 23 an isomorphism pruning algorithm using the symmetry group for a branch and cut algorithm was described One of the main drawbacks of that algorithm is that the branching variable cannot be chosen freely but always has to be the non fixed variable with smallest index In this paper a modi
27. ing Orbits in Symmetric ILP 17 Remark 3 Assume that this algorithm is used to find the branching index f when no orbit setting is used i e the orbits of stab G 1 4k 1 G are not known It is then possible to compute the orbit or at least part of it of G k in stab 6 1 k 1 G at virtually no cost During a recursive call of fin_orb at depth k 1 if the permutation loc_perm stabilizes 6 1 k 1 then loc_perm 3 k is in the orbit of 6 k If the algorithm returns that R 6 1 k is lexicographically minimum in the orbit of 3 1 k it is easy to check that all the points in the orbit of G k have been found If R G 1 k is not lexicographically minimum in the orbit only a subset Q of the orbit might have been found but it is possible to set all variables in Q as well as G k to 0 similarly to what is done in step v of the orbit setting 7 Applications We use the software ABACUS version 2 3 originally developed by Thienel 12 15 32 now distributed by OREAS 29 as generic implementation of all branch and cut steps with the LP solver CPLEX7 1 11 The machine used is an HP B2000 running HP UX11 with a 500MHz PA 8600 CPU Results on three classical com binatorial problems are presented set covering problems generated by Steiner triple systems covering design problems and error correcting code construction All the branch and cut including the one in CPLEX7 1 are run in order to prove that no so
28. k B The variable i runs through all possible choice for gi E U B ina stab_gen a k perm remain ind For each i remain do h T Glind il If h Q then loc_remain remain i loc_remain h loc_remain loc_perm perm h If ind lt k then stab_gen a k loc_perm locremain ind 1 else output perm Remark 2 When using this algorithm in the first step of the orbit setting a slight modification may allow us to set more variables to 0 or 1 while computing the generators of the stabilizer Observe that during a recursive call at depth q Bll q F and B part_zero q 1 n FE U S for some ancestor d of a It is thus possible to use Lemma 5 and set to 0 all variables perm j for j Blpart_zero q 1 n This is implemented in the codes tested in Section 7 A stronger variant would be to initialize remain as Ff U S and then output perm only if it stabilizes Ff Moreover it would be possible to also set to 1 all variables perm j for j S but this would require additional bookkeeping to be able to retrieve the set S2 In most applications that we considered few variables are ever set to 1 making it likely that very little benefit would be obtained by implementing this oO 16 Fran ois Margot 6 2 Deciding if a set is a representative or not For deciding if a set is a representative of its orbit with respect to R we refer to 23 where procedure first_in_orbit is described
29. lution with value better than the optimal one exists i e the optimal value is used to prune the enumeration tree from the start This is done in order to remove the randomness of the time at which an optimal solution is found Since the optimal value is always an integer for the problems under consideration the value Z 0 95 is used as the upper cutoff value The branching variable order is the minimum index branching variable of 23 described in Section 3 Cutting is used in neither for our algorithms making them work as Branch and Bounds but the branch and cut of CPLEX7 1 is allowed to use cuts we use the default settings Since the goal is to get a better feel for the enumeration tree under different strategies for setting variables the comparisons are more reliable under these choices The three applications and the set of test problems are described briefly below Table 1 gives characteristics of the test problems Files of the test problems in LP format can be obtained from 21 Error correcting codes The Hamming distance between two binary n vectors v and v is the number of indices 1 lt i lt n such that v i 4 v i An error correcting binary code with distance d and word length w is a collection C of binary w vectors such that the Hamming distance between any pair of vectors in C is at least d 24 Chapter 9 in 6 The goal is to find such a collection C of maximal size This maximal size is denoted by A w d A si
30. mple set packing problem with one variable per binary w vector yields an ILP named codwd We 18 Fran ois Margot report results for cod83 cod93 and cod105 Those ILPs are difficult to solve for the branch and cut of CPLEX7 1 as it runs out of memory after more than two days of CPU time with roughly 80 of the generated nodes still in the tree Generators of the symmetry group are the w 1 permutations corresponding to swapping entry 1 and k in a word for k 2 w and the 2 permutations corresponding to complementing a subset of entries The order of the group is 2 w Related reduced problems are denoted by codwdr They are obtained from codwd by setting to 1 the variable corresponding to the zero word and deleting all other variables corresponding to words with at most d 1 ones CPLEX7 1 needs more than 6 hours to solve cod83r more than 4 hours to solve cod105r and is not done after more than 3 days and 2 25 million nodes almost none pruned for cod93r Generators of the symmetry group of the reduced problems are the w 1 permutations corresponding to swapping entry 1 and k in a word for k 2 w The order of the group is w Set covering from Steiner triple systems Fulkerson 8 introduced a class of difficult set covering problems obtained from the incidence matrix of Steiner triple systems 9 These problems named ST S9 STS15 STS27 and ST S45 have 9 15 27 and 45 variables respectively and are surprisingly d
31. on of Surveys Dinitz J H Stinson D R eds Wiley 1992 371 399 28 Odijk M A van Maaren H Improved Solutions to the Steiner Triple Covering Problem Information Processing Letters 65 1998 67 69 29 http www oreas de 30 M W Padberg G Rinaldi A Branch and Cut Algorithm for the Resolution of Large Scale Symmetric Travelling Salesman Problems SIAM Review 33 1991 60 100 Exploiting Orbits in Symmetric ILP 23 31 Sherali H D Smith J C Improving Discrete Model Representations via Symmetry Con siderations Management Science 47 2001 p1396 1407 32 Thienel S ABACUS A Branch And CUt System Ph D Thesis Universitat zu K ln 1995 33 L A Wolsey Integer Programming Wiley 1998
32. or BC2 and BC4 the orbit setting is based on Corollary 2 with the extension described in Remark 2 For BC4 the variables in the strong branching candidate list are selected based on the orbits of stab Ff G at most one variable per orbit The maximum size of the candidate list is 10 Table 2 gives the total number of nodes in the enumeration trees Comparing BC1 with BC2 and BC3 with BC4 the orbit setting reduces the size of the enumeration tree significantly BC2 has a tree on average 16 smaller than BC1 by using orbit setting The use of the orbit setting in BC4 and possibly a better choice of the variables in the strong branching candidate list reduces the tree by an additional factor of roughly 25 Exceptions are cod83r cod105 cod105r and ST S45 but this probably comes from the fact that cod105 cod105r are solved in a few nodes and the symmetry groups of the other two problems are rather small implying that only a few non trivial orbits are exploitable For ST 45 the fact that about 1 4 of the variables are in the candidate list for strong branching might also play a role It is interesting to note that although cod83r and cod93r have fewer variables and a symmetry group smaller than cod83 and cod93 the number of nodes for the reduced problems is larger than for the original problem for all four variants The opposite is true for cod105r and cod105 o o o s as i Cobs 1365 1301 295 a7 Peodio5r ia 9 s 14881 9
33. orithms are described for a 2 dimensional table T a more space efficient implementation uses a vector of ordered lists instead as most entries in the table are usually empty The actual implementation uses a vector of ordered lists but algorithms are simpler to describe and understand for the 2 dimensional table We use backtracking algorithms to decide if a set is a representative or to com pute the orbits in the stabilizer of a set in G These algorithms take advantage of the fact that we may assume that the base 8 of the group at node a of the enumeration tree has the following structure Variables fixed to 1 at a i e Ff Exploiting Orbits in Symmetric ILP 13 come first in then the variables not set to 0 and not fixed N S and then the variables fixed or set to 0 at a FG U S The data structure associated with group G at node a of the branch and cut is the following integer buf matrix of permutations T integer vector integer fixed_one integer vector part_zero In addition a single rank vector R is updated during the whole enumeration according to the rule of Section 3 When processing node a the current rank vector R corresponds to the vector R of the previous sections The integer buf is the index of the branching variable of the father of a The table T is just a Schreier Sims representation of the group with base 8 The variable fixed_one gives the number of variables in Ff and F b 1 fixed one
34. pair of nodes This is a very valuable property as storing nodes that have been already explored is then unnecessary However to achieve this we need to restrict the choice of the branching variable We then define one representative of each class of isomorphic subproblems guaranteeing that pruning all nodes that are not representatives is valid The proof of the later is the main result of this section In 23 a simple branching rule called minimum index branching was used Unfortunately this rule is very inflexible At node a the branching variable has to be x where f is the minimum index in N even if the value of xs in the current solution of the LP relaxation is 0 or 1 This section presents a relaxation of the rule leaving more latitude for picking the branching variable at the cost of maintaining a vector R of integers the rank vector indicating the order in which the variables have been used as branching variables At the beginning Rii n 1 for i 1 n and r 0 If variable xy is chosen for branching and R f n 1 then R f is set to r 1 and r is increased by one Note that both R and r are global variables i e the same R and r are in use at each node of the enumeration tree and that r is never decreased during the whole enumeration The rule to select the branching variable xf at a called ranked branching rule is then the following i If there exists j N with R j lt n 1 then f arg min R j j
35. r R there is at least one representative in the orbit of J and possibly more than one Lemma 1 Let R and Rz be two rank vectors obtained during a branch and cut using a ranked branching rule and assume that R is obtained after R Then i if J is not a representative with respect to R then J is not a representative with respect to R ii if J is a representative with respect to R and all the entries in R J are strictly smaller than n 1 then J is the unique representative of its orbit with respect to Ry iii if J is a representative with respect to R and all the entries in R J are strictly smaller than n 1 then J is also a representative with respect to R Proof i Let g G such that Ri g J lt Ri J and let p J Let Ri J be the ordered set a1 2 p R2 J be the ordered set a a5 a Ri g J be the ordered set b1 b2 b and Ro g J be the ordered set b 05 b Let k be the index such that a b for i 1 k 1 and bk lt ap Then by lt n 1 implying that a a for i 1 k 1 a gt bk and b b fori 1 k It follows that Ro g J lt Ro J ii Let J be a set in the orbit of J under G If Ri J Ri J then J J as R is a bijection between J and Ri J iii The orbit of J under G has at least one representative with respect to Ro Since by ii J is the unique representative with respect to R1 i implies the result oO
36. rly important the most successful procedure is probably strong branching A list of candidate branching variables is built and for each variable in the list the LP relaxation of the two sons that would be created if the variable was selected is solved The final choice of the variable is then based on the different values of the LP relaxations Usually the LP is not solved to optimality as only a fixed number of iterations of the dual simplex algorithms are performed The maximum size of the candidate list is typically small In the implemented algorithms the LP is solved to optimality and the size of the candidate list is at most 10 See 10 for more background on strong branching After performing an orbit setting at node a of the enumeration tree the orbits of stab F G partition N into equivalent variables If a variable is set to k then so are all variables in its orbit If a variable is not set then none of the variables in its orbit is set In the latter case let i and j be two variables in the same orbit As there exists g E stab F G such that g t j g F FT g S S and f FG US FS U S including both i and j in the candidate list for strong branching is useless as the resulting LPs for the potential sons will have exactly the same optimal values If i resp j can be set then the orbit setting will set 7 resp i too It follows that the strong branching candidate list needs to include not more than
37. stions related to a single node a of the branch and cut To avoid heavy notations the table associated with a is denoted by T instead of a more precise notation like T a or a gt T 14 Francois Margot The same remark applies to the other fields of the data structure associated with a We are interested in performing the following operations that were mentioned in Section 4 Computing all orbits in the stabilizer of a set and deciding if the rank of a set is lexicographically minimum in its orbit under G 6 1 Computing orbits in the stabilizer of a set If generators gi 9p of the stabilizer G are known a simple algorithm 3 works with the graph with node set I and edge set i j gk i j with 1 lt k lt p andi I The orbits are then the connected components of the graph Unfortunately finding generators of the stabilizer of a set under G is difficult as it is at least as hard as testing if two graphs are isomorphic 14 19 We resort to backtracking for finding generators of G The resulting algorithm has a complexity exponential in the size of the set to stabilize but is practical for small sizes One property of a Schreier Sims representation of G is that each g G can be uniquely written as g g g2 eee ee Jn 3 with gi U 8B for i 1 n Hence the permutations in the table form a set of generators of G As a consequence any g G can be written as 9 91 gt t Jk 1 Jk h
38. t setting time w O O ow mele O These results indicate that for problems requiring only an enumeration tree of a few hundred nodes BC2 is probably fastest However when BC2 has an enu meration tree much larger BC4 might be faster Note that if a problem has an efficient strict setting algorithm faster than the strong branching setting algo rithm the comparison would be more in favor of BC4 This could be simulated by calling the strong branching setting algorithm only at a fraction of the nodes of the enumeration tree Acknowledgements I wish to thank three anonymous referees whose numerous suggestions helped improve the paper substantially 22 Francois Margot References 1 Avis D A Note on Some Computationally Difficult Set Covering Problems Mathemat ical Programming 8 1980 138 145 2 Butler G Computing in Permutation and Matrix Groups II Backtrack Algorithm Mathematics of Computation 39 1982 671 680 3 Butler G Fundamental Algorithms for Permutation Groups Lecture Notes in Computer Science 559 Springer 1991 4 Butler G Cannon J J Computing in Permutation and Matrix Groups I Normal Closure Commutator Subgroups Series Mathematics of Computation 39 1982 663 670 5 Butler G Lam W H A General Backtrack Algorithm for the Isomorphism Problem of Combinatorial Objects Journal of Symbolic Computation 1 1985 363 381 6 Conway J H Sloane N J A
39. v and the order of the group is v The optimal value for the 10 5 4 covering design was found by Etzion et al 13 without optimality proof The branch and cut of 22 proved optimality and generated 40 non isomorphic optimal solutions Results for cov954 cov1053 cov1054 cov1075 cov1076 and cov1174 are reported CPLEX7 1 solves only cov954 196 seconds and cov1075 13 hours The other four problems are not solvable by CPLEX7 1 even after running for several days it runs out of memory after 2 days on cov1076 it does not make much progress on cov1053 cov1054 or cov1174 after several days and millions of enumerated nodes 19 T a o o 30 63 Table 1 Problem characteristics Opt is the optimal value and LP is the value of the LP relaxation of the initial formulation We consider four slightly different versions of a branch and cut depending on the choice of the strict setting algorithm and the use of orbit setting BC1 is a branch and cut using isomorphism pruning and the strict setting algorithm based on reduced costs cf Section 4 20 Francois Margot BC2 is BC1 plus the orbit setting described in Section 4 BC3 is BC1 plus the strict setting algorithm based on strong branching described in Section 5 BC3 thus uses two strict setting algorithms BC4 is BC3 plus the orbit setting described in Section 4 For BC1 and BC3 the additional setting of variables described in Remark 3 is used F
Download Pdf Manuals
Related Search