BiqCrunch User's Guide
Contents
1. REAL where the first and second number means that we re defining the objective function matrix and we re defining the first block INT 1 and INT 2 are the row and the column of the element of the matrix and REAL is his value XINT 1 and INT 2 must be greater than 0 and less or equal to n 4 1 After the Qo matrix we have to describe all the constraints matrices and for each constraint k we have to write the values of the matrix Q in sparse format CONS MATRIX EL INDEX k 1 INT 1 INT 2 REAL where INDEX k must be equal to k If the constraint we re defining is an inequality j we have to define the value of the second block of the matrix lt INEQ_ MATRIX EL INDEX k 2 INT INT REAL where INT must be equal to j and real can be 1 0 if the inequality is in form of lt or 1 0 if it s a gt inequality 1 2 2 Examples We report now a couple of examples to understand how to formulate BC instances You can copy these examples and solve them using the from source option in the online solver at http www lipn univ parisi3 fr BiqCrunch solver Model 1 max 2103 2104 22333 Los 2 334 X435 subject to Li Lo T3 La T5 3 x 0 1 Example of an instance for BiqCrunch This instance contains only an equality constraint just equalities COWMEFFE S eo e e e Ww oo o o BiqCrunch User s Guide v1 0 6 BhRE BR BPRPRPP2. bound obtained during the bounding procedure 12 A user guide to the conversion tool is included in the archive available online BiqCrunch User s Guide v1 0 10 Bibliography 1 Alain Billionnet and Sourour Elloumi Using a mixed integer quadratic programming solver for the unconstrained quadratic 0 1 problem Mathematical Programming 109 55 68 2007 10 1007 s10107 005 0637 9 2 Richard H Byrd Peihuang Lu Jorge Nocedal and Ciyou Zhu A limited memory algorithm for bound constrained optimization SIAM J Sci Comput 16 5 1190 1208 September 1995 3 Michel X Goemans and David P Williamson Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming J ACM 42 6 1115 1145 November 1995 4 Nathan Krislock Jerome Malick and Fr d ric Roupin Improved semidefinite bounding procedure for solving Max Cut problems to optimality Available at http hal archives ouvertes fr hal 00665968 Submitted to Mathematical Program ming 5 Nathan Krislock J r me Malick and Fr d ric Roupin Improved semidefinite branch and bound algorithm for k cluster Available at http hal archives ouvertes fr hal 00717212 Submitted to Journal Of Combinatorial Optimization 6 Am lie Lambert A library of k cluster problems CNAM CEDRIC http cedric cnam fr lamberta Library k cluster html 7 Bertrand Le Cun Catherine Roucairol and The Pnn Team Bob a unified platfo
3. gt must be equal to 1 if the model contains also inequality constraints lt INT gt must be equal to 2 The third entry of the instance describes the size of the blocks of the matrices SIZE INT 1 lt INT_1 gt lt INT_1 gt lt INT_2 gt lt INT_1 gt lt INT_2 gt If we describe a problem without inequalities we have only to provide the size of the first block of the matrices lt INT_1 gt which is equal to n 1 If the problem contains inequalities we have to define also the size of the second block lt INT_2 gt which starts always with a minus before its size to explicit that the values of the blocks are only on the diagonal of the matrix since they correspond to slack variables and that must be equal to mzy In the next line we have to define the right hand side values of the constraints which is a sequence of values BiqCrunch User s Guide v1 0 5 lt RIGHT HAND SIDE REAL k gt REAL k gt RIGHT HAND SIDE The number of values must be equal to mg m and REAL k gt must be the right hand side value of constraint k At the end of the instance we define all the matrices that describe the objective function and the left hand side of the constraints The first matrix to describe is the objective function coefficient matrix Qo we describe the matrix in sparse format and we have to write a line for every non zero element of the matrix 0BJ MATRIX EL 0 1 INT 1 INT 2
4. BiqCrunch online Solver User s Guide Marco Casazza and Fr d ric Roupin July 27 2012 LIPN CNRS UMR7030 Universit Paris Nord Sorbonne Paris Cit Frederic Roupin lipn univ parisi3 fr Summary BiqCrunch is a semidefinite based solver for binary quadratic problems It uses a branch and bound method featuring an improved semidefinite bounding procedure 8 mixed with a polyhedral approach see 4 5 for details BigCrunch is written in C and Fortran and uses the library L BFGS B for quasi Newton bound constrained optimization 2 13 and the Branch and Bound framework BOB 7 People involved with the development of BiqCrunch are e Nathan Krislock nathan krislock inria fr e J r me Malick jerome malick inria fr e Fr d ric Roupin Frederic RoupinOlipn univ parisi3 fr BiqCrunch User s Guide v1 0 2 1 BiqCrunch For now BiqCrunch is available only as online solver You can try it at http www lipn univ parisi3 fr BiqCrunch solver 1 1 Usage The BiqCrunch online solver is very simple to use but you have to provide some informa tion to be able to solve your problem e mail address a valid e mail address where BiqCrunch online solver will send the results of the computation objective you can either choose to maximize or minimize the value of the objective function specific problem heuristic you can choose the heuristics used during the computation The online solver offers you a generic heuristic
5. Pe Bee oao amp NO HP NN N D OO OO OO OO O1 H O1 W OO OO OOo O O1 O1 O1 O1 O1 n U1 UT Model 2 max 202423 262124 2919223 8rox5 321324 132425 subject to Li Lo 3 La U5 3 122123 24x124 142223 161525 281324 122425 lt 30 x 0 1 Example of an instance for BiqCrunch This instance contains equalities and inequalities 2 constraint 2 equalities and inequalities 6 1 3 0 30 0 0 1 1 3 10 0 0 1 1 4 13 0 0123 11 5 01254 0 0134 16 0 0 1 4 5 6 5 11160 5 11260 5 11360 5 11460 5 11560 5 2113 6 0 2114 12 0 2123 7 0 2125 8 0 213 4 14 0 2145 6 0 2211 1 0 BiqCrunch User s Guide v1 0 2 Heuristics The BiqCrunch online solver uses some heuristics to improve the performance of the branch and bound by building feasible solutions generally from the SDP solution provided by the bounding procedure We have three types of heuristics root node heuristic called once before starting the Branch and Bound bound heuristic called a large number of times while computing the bound of the branch and bound nodes node heuristic called after the evaluation of eachnode of the branch and bound tree We provide different versions of BigCrunch which use also heuristics for specific problems 2 1 Generic problem For generic problems BiqCrunch provides some general heuristics that can improve the performance of the branch and bound by trying to build a feasible 0 1 vector fo
6. and some heuristics for specific problems verbosity level this flag allows the user to choose the level of details given with the output Right now you can choose between a low detailed output or a more completed output with informations about the bound computation at each node of the search tree upload method the instance of the problem can be provided uploading a file or coding the instance directly in the website Note that there are some limitations the online solver handles problems with no more than 100 variables and 5000 constraints The time limit of computation is one hour after that the user will receive the best solution found so far and the current gap The input file uploaded on the website must be in BC format and weigh less than 1MB Finally when submitting the problem the user agrees that the data will be stored and may be added with a credit to the BiqCrunch library of users instances 1 1 1 BiqCrunch Parameters The user can also modify the behaviour of BiqCrunch by changing the values of some parameters BiqCrunch User s Guide v1 0 3 root by default BiqCrunch solves the problem to optimality but checking this option you can ask to BiqCrunch to stop the branch and bound after the evaluation of the root node withCuts by default BigCrunch adds and removes dynamically cuts see 4 to improve the bound during the computation This option generally offers much better performance but you can also try BiqCrun
7. ch without this feature heur 1 this parameter asks to BigCrunch to use a heuristic before starting the Branch and Bound to get a feasible solution The heuristic used depends on the problem chosen by the usert heur 2 this parameter asks to DiqCrunch to use a heuristic to try to improve the best current feasible solution during the computation of the bound of each node of the branch and bound tree The heuristic used depends on the problem chosen by the 1 user heur 3 this parameter asks to BigCrunch to use a heuristic after the evaluation of a node of the branch and bound tree The heuristic used depends on the problem chosen by the usert gapCuts minimum value to consider a triangle inequality as violated The value must be between 1 and 0 By default BigCrunch uses a gap of 5e 2 1 2 Input format BiqCrunch allows to solve problems that can be stated as max g Aoz br Co subject to zT A x blr c Vie l mp zT Ajr bia c Yj E 1 mr x 0 1 The problem has to be converted in BC format very similar to standard SDPA format see Instance 1 1 In the BC format the problem is described in matrix form by considering cut x the matrix X zm and defining the inner product of two matrices X and Y by 1 X eY Trace XTY In particular the objective function is written as Qo e X where A db Qo E Similarly each constraint k 1 mj mg is associated to a 3 A BE matrix Q
8. cluster with exactly k nodes First for the initial feasible point before running the Branch and Bound we use the classical greedy heuristic since it gives very good feasible solutions we remove one by one vertices from the graph by choosing at each step the one with the smallest degree or sum of the weights over the adjacent vertices Second during the evaluation of the bound and after running the bounding procedure on a subproblem having k nodes added to the cluster we add the remaining k k nodes having the largest fractional values x in the SDP solution More detailed can be found in 5 2 3 2 K cluster instances and conversion An instance for the k cluster problem should be in a format like the example in Instance 2 2 defining the objective function coefficient matrix and the equality constraint 1 number of constraints 1 blocks of the matrices n 1 k 0 1 i j Wig j Wij 0 a 1 1 ntl 0 5 l 1 1 1n n l 0 5 Code 2 2 Structure of a BC instance for k cluster problems To obtain BiqCrunch input files for the k cluster problem you can simply use the con version tools available at http www lipn univ paris13 fr BiqCrunch Download which can convert instances from Rudy format and from the format used in 6 to BC When using the conversion tool weights can be ignored with a simple flag if the graph is unweighted Note that the conversion tools add also redundant constraints to the instance to improve the
9. e such that Qk T s As done in SDPA format the right hand side c of 2 the constraints is stored aside In the next section we precise how we indicate that a constraint is an equality or an inequality 1see section 2 for further explanation BiqCrunch User s Guide v1 0 4 lt COMMEN B OOMMENTE lt CONSTRAINTS gt number of constraints lt BLOCKS gt blocks of the matrices lt SIZE gt RIGHT HAND SIDE lt MATRIX gt lt BLOCK gt ROW INDEX COLUMN INDEX lt VALUE gt lt MATRDS BLOCK ROW INDEX COLUMN INDEX lt VALUE gt Code 1 1 Generic structure of a BC instance 1 2 1 Instance syntax A BC file begins with some optional lines of comments which are strings preceded by a semicolon or by a asterisk COMMENT STRING STRING The first line after the comments defines the number of constraints in our model which is a integer non negative number that can be followed by other characters ignored by the reader lt CONSTRAINTS gt INT INT STRING and such that lt INT gt mg mj As we keep the syntax of the SDPA files we define the number of blocks of the matrices of the input file As seen before also this line admit characters after the definition lt BLOCKS gt INT INT STRING In the BC an instance can have 1 or 2 blocks depending on the model if the model contains no constraints or just equality constraints lt INT
10. r the combinatorial problem from the SDP solution These heuristics can be used for any quadratic 0 1 problem During the computation of the bound of the node and after the evaluation of each node BigCrunch uses a variant of the classical randomized rounding heuristic 10 9 that rounds to 1 the variables according to the probability provided by the fractional SDP solution Indeed one has 0 x lt 1 for any feasible solution of the SDP relaxation see 8 for details about the relaxations used This is done simply by comparing these values to a fixed one a which goes from 0 to 1 by a step of 0 01 Then we test if the resulting 0 1 vector is feasible for the combinatorial problem and update the best current feasible solution if needed At root node we generate a random vector of values in 0 1 domain and then we apply the variant of randomized algorithm described before 2 2 Max Cut problem Given an edge weighted graph G with n vertices and edge weights w for ij E the objective is to maximize the total weight of the edges between a subset of vertices and its complement see 4 for details It can be stated as BiqCrunch User s Guide v1 0 8 max Mwijz 1 Q esr lj subject to z 0 1 Note that for max cut ising problems see e g 4 we provide a specific option in the online solver using a particular parameter setting 2 2 1 Max Cut heuristic BiqCrunch for max cut problems uses two different he
11. rm for implementing branch and bound like algorithms Technical report Laboratoire Prism 1995 8 J r me Malick and Fr d ric Roupin On the bridge between combinatorial op timization and nonlinear optimization a family of semidefinite bounds for 0 1 quadratic problems leading to quasi Newton methods Technical report 2011 Avail able at http hal archives ouvertes fr hal 00662367 To appear in Mathematical Programming 9 Prabhakar Raghavan Probabilistic construction of deterministic algorithms approx imating packing integer programs J Comput Syst Sci 37 2 130 143 October 1988 BiqCrunch User s Guide v1 0 11 10 Prabhakar Raghavan and Clark D Tompson Randomized rounding a technique for provably good algorithms and algorithmic proofs Combinatorica 7 4 365 374 December 1987 11 Giovanni Rinaldi Rudy a graph generator http www user tu chemnitz de helm berg rudy tar gz 12 Fr d ric Roupin From linear to semidefinite programming An algorithm to obtain semidefinite relaxations for bivalent quadratic problems Journal of Combinatorial Optimization 8 469 493 2004 10 1007 s10878 004 4838 6 13 Ciyou Zhu Richard H Byrd Peihuang Lu and Jorge Nocedal Algorithm 778 L bfgs b Fortran subroutines for large scale bound constrained optimization ACM Trans Math Softw 23 4 550 560 December 1997 BiqCrunch User s Guide v1 0 12
12. uristics e the same randomized rounding heuristic as the generic BigCrunch during the computation of the bound at each node of the search tree e the Goemans Williamson random hyperplane algorithm 3 after the evaluation of each node 2 2 2 BiqCrunch instances and conversion An instance for the max cut problem should be in a format like the example in Instance 2 1 defining only the objective function coefficient matrix Q0 number of constraints 1 blocks of the matrices n 012727 Qj Code 2 1 Structure of a BC instance for Maz Cut problems To obtain BiqCrunch input files for the max cut or Unconstrained 0 1 quadratic problems see e g 1 you can simply use the conversion tools available at http www lipn univ parisi3 fr BiqCrunch Download which can create instances from the rudy format 11 to BC 2 3 K cluster problem Given a graph G V E the k cluster problem consists of determining a subset S C V of k vertices such that the sum of the weights of the edges between vertices in S is maximized Letting n V denote the number of vertices and w denote the edge weight for ij E and wj 0 for ij E the problem can be modelled as the following 0 1 quadratic problem 1 max xt We subject to Soa k x 0 1 BiqCrunch User s Guide v1 0 9 where W wij S is the weighted adjacency matrix of the graph G 2 3 1 K cluster heuristic We use two types of heuristics to find a
Download Pdf Manuals
Related Search