1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB) */ 7 /* */ 8 /* Licensed under the Apache License, Version 2.0 (the "License"); */ 9 /* you may not use this file except in compliance with the License. */ 10 /* You may obtain a copy of the License at */ 11 /* */ 12 /* http://www.apache.org/licenses/LICENSE-2.0 */ 13 /* */ 14 /* Unless required by applicable law or agreed to in writing, software */ 15 /* distributed under the License is distributed on an "AS IS" BASIS, */ 16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ 17 /* See the License for the specific language governing permissions and */ 18 /* limitations under the License. */ 19 /* */ 20 /* You should have received a copy of the Apache-2.0 license */ 21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 /**@file sepa_oddcycle.c 26 * @ingroup DEFPLUGINS_SEPA 27 * @brief oddcycle separator 28 * @author Robert Waniek 29 * @author Marc Pfetsch 30 * 31 * We separate odd cycle inequalities in the implication graph. Implemented are the classic method 32 * by Groetschel, Lovasz, and Schrijver (GLS) and the levelgraph method by Hoffman and Padberg (HP) 33 * 34 * Odd cycle inequalities are lifted by a heuristic method based on an idea from Alvarez-Valdes, 35 * Parreno, and Tamarit. 36 * 37 * Some part of this code is based on the odd cycle separator of the program colorbitopt by Marc 38 * Pfetsch. 39 */ 40 41 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 42 43 #include <assert.h> 44 #include <string.h> 45 46 #include "blockmemshell/memory.h" 47 #include "dijkstra/dijkstra.h" 48 #include "scip/pub_implics.h" 49 #include "scip/pub_lp.h" 50 #include "scip/pub_message.h" 51 #include "scip/pub_misc.h" 52 #include "scip/pub_misc_sort.h" 53 #include "scip/pub_sepa.h" 54 #include "scip/pub_tree.h" 55 #include "scip/pub_var.h" 56 #include "scip/scip_branch.h" 57 #include "scip/scip_cut.h" 58 #include "scip/scip_general.h" 59 #include "scip/scip_lp.h" 60 #include "scip/scip_mem.h" 61 #include "scip/scip_message.h" 62 #include "scip/scip_numerics.h" 63 #include "scip/scip_param.h" 64 #include "scip/scip_prob.h" 65 #include "scip/scip_sepa.h" 66 #include "scip/scip_sol.h" 67 #include "scip/scip_solvingstats.h" 68 #include "scip/scip_tree.h" 69 #include "scip/scip_var.h" 70 #include "scip/sepa_oddcycle.h" 71 #include <string.h> 72 73 #define SEPA_NAME "oddcycle" 74 #define SEPA_DESC "odd cycle separator" 75 #define SEPA_PRIORITY -15000 76 #define SEPA_FREQ -1 77 #define SEPA_MAXBOUNDDIST 1.0 78 #define SEPA_USESSUBSCIP FALSE /**< does the separator use a secondary SCIP instance? */ 79 #define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */ 80 81 82 /* default values for separator settings */ 83 #define DEFAULT_SCALEFACTOR 1000 /**< factor for scaling of the arc-weights in the Dijkstra algorithm */ 84 #define DEFAULT_USEGLS TRUE /**< use GLS method, otherwise HP method */ 85 #define DEFAULT_LIFTODDCYCLES FALSE /**< lift odd cycle cuts */ 86 #define DEFAULT_REPAIRCYCLES TRUE /**< try to repair violated cycles in which a variable and its negated appear */ 87 #define DEFAULT_ADDSELFARCS TRUE /**< add links between a variable and its negated */ 88 #define DEFAULT_INCLUDETRIANGLES TRUE /**< separate triangles (3-cliques) found as 3-cycles or repaired larger cycles */ 89 #define DEFAULT_MULTIPLECUTS FALSE /**< still try variable as start, even if it is already covered by a cut */ 90 #define DEFAULT_ALLOWMULTIPLECUTS TRUE /**< allow another inequality to use variable, even if it is already covered */ 91 #define DEFAULT_LPLIFTCOEF FALSE /**< TRUE: choose lifting candidate with highest value of coefficient*lpvalue 92 * FALSE: choose lifting candidate with highest coefficient */ 93 #define DEFAULT_RECALCLIFTCOEF TRUE /**< whether lifting coefficients should be recomputed */ 94 #define DEFAULT_MAXSEPACUTS 5000 /**< maximal number of oddcycle cuts separated per separation round */ 95 #define DEFAULT_MAXSEPACUTSROOT 5000 /**< maximal number of oddcycle cuts separated per separation round in root node */ 96 #define DEFAULT_PERCENTTESTVARS 0 /**< percent of variables to try the chosen method on [0-100] */ 97 #define DEFAULT_OFFSETTESTVARS 100 /**< offset of variables to try the chosen method on */ 98 #define DEFAULT_MAXCUTSROOT 1 /**< maximal number of oddcycle cuts generated per root of the levelgraph */ 99 #define DEFAULT_SORTSWITCH 3 /**< unsorted (0), maxlp (1), minlp (2), maxfrac (3), minfrac (4) */ 100 #define DEFAULT_MAXREFERENCE 0 /**< minimal weight on an edge (in level graph or Dijkstra graph) */ 101 #define DEFAULT_MAXROUNDS 10 /**< maximal number of rounds pre node */ 102 #define DEFAULT_MAXROUNDSROOT 10 /**< maximal number of rounds in the root node */ 103 #define DEFAULT_MAXNLEVELS 20 /**< maximal number of levels in level graph */ 104 #define DEFAULT_MAXPERNODESLEVEL 100 /**< maximal percentage of nodes allowed in one level of the levelgraph [0-100] */ 105 #define DEFAULT_OFFSETNODESLEVEL 10 /**< additional offset of nodes allowed in one level of the levelgraph */ 106 #define DEFAULT_SORTROOTNEIGHBORS TRUE /**< sort neighbors of the root in the level graph */ 107 #define DEFAULT_MAXCUTSLEVEL 50 /**< maximal number of cuts produced per level */ 108 #define DEFAULT_MAXUNSUCESSFULL 3 /**< maximal number of unsuccessful calls at each node */ 109 #define DEFAULT_CUTTHRESHOLD -1 /**< maximal number of other cuts s.t. separation is applied (-1 for direct call) */ 110 111 112 /* 113 * Data structures 114 */ 115 116 /** Graph structure for level graph 117 * 118 * This graph is tailored to the heuristic search for odd holes, @see separateHeur(). 119 * 120 * This undirected graph is represented by a directed graph with forward and backward arcs. Arcs are 121 * forward if they lead from a level l to level l+1, i.e., away from the root; backward arcs 122 * lead from a level l+1 to level l. This distinction enables a fast construction and search 123 * process. In the latter only forward or backward arcs have to be searched. 124 * 125 * Target nodes and weights of the arcs incident to each node (adjacency lists) are stored 126 * consecutively in the arrays targetForward, targetBackward, weightForward, and weightBackward. 127 * The end of each list is marked by a -1 in targetForward and targetBackward. 128 */ 129 struct levelGraph 130 { 131 unsigned int nnodes; /**< number of nodes */ 132 unsigned int narcs; /**< number of arcs */ 133 unsigned int maxnodes; /**< maximal number of nodes of the level graph */ 134 unsigned int maxarcs; /**< maximal number of arcs of the level graph */ 135 unsigned int nlevels; /**< number of levels completely inserted so far */ 136 unsigned int* level; /**< level number for each node */ 137 unsigned int lastF; /**< last storage element index in targetForward, weightForward - forward direction */ 138 unsigned int lastB; /**< last storage element index in targetBackward, weightBackward - backward direction */ 139 int* beginForward; /**< forward adjacency list index in targetForward, weightForward for each node */ 140 int* beginBackward; /**< backward adjacency list index in targetBackward, weightBackward for each node */ 141 int* targetForward; /**< target nodes of forward arcs */ 142 int* targetBackward; /**< target nodes of backward arcs */ 143 unsigned int* weightForward; /**< weights of forward arcs */ 144 unsigned int* weightBackward; /**< weights of backwards arcs */ 145 unsigned int sizeForward; /**< size of targetForward and weightForward */ 146 unsigned int sizeBackward; /**< size of targetBackward and weightBackward */ 147 int* beginAdj; /**< index of list of arcs inside a level (in sourceAdj) for each node 148 * (the index points at the first arc starting from this node) */ 149 unsigned int* sourceAdj; /**< source nodes of arcs inside a level */ 150 unsigned int* targetAdj; /**< target nodes of arcs inside a level */ 151 unsigned int* weightAdj; /**< weights of arcs inside a level */ 152 unsigned int* levelAdj; /**< index of the first arc inside a given level */ 153 unsigned int sizeAdj; /**< size of sourceAdj, targetAdj and weightAdj */ 154 }; 155 156 typedef struct levelGraph LEVELGRAPH; 157 158 159 /** sorting type for starting node or root node iteration order 160 * 161 * If the array should be sorted (1-4), the variable array is sorted every round by the chosen 162 * sorttype and the search method tries the nodes in order of the array. If the array is used 163 * unsorted (0), the search methods tries the nodes in order of the array and stores the last 164 * processed start node or root node and continues from this position in the next separation round. 165 */ 166 enum sorttype 167 { 168 UNSORTED = 0, /**< variable array is unsorted */ 169 MAXIMAL_LPVALUE = 1, /**< variable array is sorted by maximal lp-value */ 170 MINIMAL_LPVALUE = 2, /**< variable array is sorted by minimal fractionality */ 171 MAXIMAL_FRACTIONALITY = 3, /**< variable array is sorted by maximal lp-value */ 172 MINIMAL_FRACTIONALITY = 4 /**< variable array is sorted by minimal fractionality */ 173 }; 174 typedef enum sorttype SORTTYPE; 175 176 /** auxiliary data structure for passing graphs */ 177 struct GraphData 178 { 179 SCIP_Bool usegls; /**< Use GLS algorithm? If true, dijstragraph != NULL should hold, otherwise levelgraph != NULL */ 180 LEVELGRAPH* levelgraph; /**< level graph when using HP method, NULL otherwise */ 181 DIJKSTRA_GRAPH* dijkstragraph; /**< Dijkstra graph if using method by GLS, NULL otherwise */ 182 }; 183 typedef struct GraphData GRAPHDATA; 184 185 /** separator data */ 186 struct SCIP_SepaData 187 { 188 int scale; /**< factor for scaling of the arc-weights */ 189 unsigned int ncuts; /**< number of cuts, added by the separator so far (in current and past calls) */ 190 unsigned int oldncuts; /**< number of cuts at the start the current separation round */ 191 int nliftedcuts; /**< number of lifted cuts, added by the separator so far (in current and past calls) */ 192 SCIP_Bool usegls; /**< use GLS method, otherwise HP method */ 193 SCIP_Bool multiplecuts; /**< an odd cycle cut of length L can be generated L times; forbidding multiple cuts 194 * per node might be faster but might miss some cuts in the current round */ 195 SCIP_Bool allowmultiplecuts; /**< allow multiple cuts covering one node */ 196 SCIP_Bool liftoddcycles; /**< TRUE, iff we try to lift odd cycle inequalities */ 197 SCIP_Bool addselfarcs; /**< add arcs between the nodes of a variable and its negated; since not all implications 198 * are in the graph, this often finds more cycles */ 199 SCIP_Bool repaircycles; /**< if a variable and its negated appear in a cycle, we can repair the cycle 200 * by removing both and reconnecting the remaining nodes of the cycle */ 201 SCIP_Bool includetriangles; /**< handle triangles found as 3-cycles or repaired larger cycles */ 202 unsigned int* mapping; /**< mapping for getting the index of a variable in the sorted variable array */ 203 SCIP_Bool lpliftcoef; /**< TRUE: choose lifting candidate with highest value of coefficient*lpvalue 204 * FALSE: choose lifting candidate with highest coefficient */ 205 SCIP_Bool recalcliftcoef; /**< whether lifting coefficients should be recomputed */ 206 int maxsepacuts; /**< max. number of oddcycle cuts separated per separation round */ 207 int maxsepacutsroot; /**< max. number of oddcycle cuts separated per separation round in the root node */ 208 int maxsepacutsround; /**< max. number of oddcycle cuts separated per separation round in the current node */ 209 SORTTYPE sortswitch; /**< sorted type: unsorted (0), maxlp (1), minlp (2), maxfrac (3), minfrac (4) */ 210 int lastroot; /**< save root of last GLS-method run */ 211 SCIP_Bool sortrootneighbors; /**< sort neighbors of the root in the level graph */ 212 int percenttestvars; /**< percentage of variables to try the chosen method on [0-100] */ 213 int offsettestvars; /**< offset of variables to try the chosen method on */ 214 int maxpernodeslevel; /**< percentage of nodes allowed in the same level of the level graph [0-100] */ 215 int offsetnodeslevel; /**< additional offset of nodes allowed in one level of the levelgraph */ 216 unsigned int maxlevelsize; /**< maximal number of nodes allowed in the same level of the level graph */ 217 int maxcutsroot; /**< maximal number of oddcycle cuts generated per root of the levelgraph */ 218 int maxcutslevel; /**< maximal number of oddcycle cuts generated per level of the level graph */ 219 int maxrounds; /**< maximal number of oddcycle separation rounds per node (-1: unlimited) */ 220 int maxroundsroot; /**< maximal number of oddcycle separation rounds in the root node (-1: unlimited) */ 221 int maxreference; /**< minimal weight on an edge (in level graph or Dijkstra graph) */ 222 int maxnlevels; /**< maximal number of levels in level graph */ 223 int maxunsucessfull; /**< maximal number of unsuccessful calls at each node */ 224 int nunsucessfull; /**< number of unsuccessful calls at current node */ 225 int cutthreshold; /**< maximal number of other cuts s.t. separation is applied (-1 for direct call) */ 226 SCIP_Longint lastnode; /**< number of last node */ 227 }; 228 229 230 /* 231 * debugging methods 232 */ 233 234 #ifdef SCIP_OUTPUT 235 236 /** displays cycle of pred data structure w.r.t. variable names of the original problem (including 237 * status: original or negated node in graph) 238 */ 239 static 240 void printCycle( 241 SCIP_VAR** vars, /**< problem variables */ 242 unsigned int* pred, /**< cycle stored as predecessor list */ 243 unsigned int nbinvars, /**< number of binary problem variables */ 244 unsigned int startnode /**< a node of the cycle */ 245 ) 246 { 247 unsigned int varsindex; 248 unsigned int counter; 249 250 assert(vars != NULL); 251 assert(pred != NULL); 252 assert(nbinvars > 0); 253 assert(startnode < 4*nbinvars); 254 255 counter = 0; 256 varsindex = startnode; 257 258 /* print start/end node */ 259 if( varsindex < nbinvars || ( varsindex >= 2*nbinvars && varsindex < 3*nbinvars ) ) 260 { 261 SCIPdebugMsg(scip, "+ %s\n",SCIPvarGetName(vars[varsindex%nbinvars])); 262 } 263 else 264 { 265 SCIPdebugMsg(scip, "- %s\n",SCIPvarGetName(vars[varsindex%nbinvars])); 266 } 267 268 /* print inner nodes */ 269 for( varsindex = pred[startnode]; varsindex != startnode; varsindex = pred[varsindex] ) 270 { 271 if( varsindex < nbinvars || ( varsindex >= 2*nbinvars && varsindex < 3*nbinvars ) ) 272 { 273 SCIPdebugMsg(scip, "+ %s\n",SCIPvarGetName(vars[varsindex%nbinvars])); 274 } 275 else 276 { 277 SCIPdebugMsg(scip, "- %s\n",SCIPvarGetName(vars[varsindex%nbinvars])); 278 } 279 ++counter; 280 } 281 282 /* print start/end node */ 283 if( varsindex < nbinvars || ( varsindex >= 2*nbinvars && varsindex < 3*nbinvars ) ) 284 { 285 SCIPdebugMsg(scip, "+ %s\n",SCIPvarGetName(vars[varsindex%nbinvars])); 286 } 287 else 288 { 289 SCIPdebugMsg(scip, "- %s\n",SCIPvarGetName(vars[varsindex%nbinvars])); 290 } 291 292 ++counter; 293 SCIPdebugMsg(scip, "original cycle has %u variables.\n", counter); 294 } 295 #endif 296 297 298 /* 299 * lifting methods 300 */ 301 302 /** using the level graph (if possible) or Dijkstra graph data structure (depending on the used 303 * method) we determine whether two nodes are adjacent 304 */ 305 static 306 SCIP_Bool isNeighbor( 307 SCIP_VAR** vars, /**< problem variables */ 308 unsigned int nbinvars, /**< number of binary problem variables */ 309 GRAPHDATA* graphdata, /**< graph */ 310 unsigned int a, /**< node index of first variable */ 311 unsigned int b /**< node index of second variable */ 312 ) 313 { 314 unsigned int i; 315 316 assert(vars != NULL); 317 assert(nbinvars > 2); 318 assert(graphdata != NULL); 319 assert(graphdata->levelgraph != NULL || graphdata->usegls); 320 assert(graphdata->dijkstragraph != NULL || ! graphdata->usegls); 321 assert(a < 2*nbinvars); 322 assert(b < 2*nbinvars); 323 assert(a != b); 324 325 /* determine adjacency using the Dijkstra graph */ 326 if( graphdata->usegls ) 327 { 328 DIJKSTRA_GRAPH* dijkstragraph = graphdata->dijkstragraph; 329 if( dijkstragraph->outcnt[a] == 0 || dijkstragraph->outcnt[b] == 0 ) 330 return FALSE; 331 332 /* @todo later: if helpful: sort head and weight list once */ 333 for( i = dijkstragraph->outbeg[a]; i < dijkstragraph->outbeg[a] + dijkstragraph->outcnt[a]; ++i ) 334 { 335 if( dijkstragraph->head[i] == b + 2*nbinvars ) 336 return TRUE; 337 } 338 } 339 else /* determine adjacency using the level graph */ 340 { 341 LEVELGRAPH* levelgraph = graphdata->levelgraph; 342 343 /* if a and b are contained in the level graph (with their arcs), we can check inside the level graph structure */ 344 if( (levelgraph->beginForward[a] != -1 || levelgraph->beginBackward[a] != -1) 345 && (levelgraph->beginForward[b] != -1 || levelgraph->beginBackward[b] != -1) ) 346 { 347 assert(levelgraph->level[a] <= levelgraph->nlevels); 348 assert(levelgraph->level[b] <= levelgraph->nlevels); 349 350 /* if a and b are not in neighbored levels or the same level, they cannot be adjacent */ 351 if( levelgraph->level[a] > levelgraph->level[b] + 1 352 || levelgraph->level[b] > levelgraph->level[a] + 1 ) 353 return FALSE; 354 355 assert(levelgraph->level[a] == levelgraph->level[b] 356 || levelgraph->level[a]+1 == levelgraph->level[b] 357 || levelgraph->level[a] == levelgraph->level[b]+1); 358 359 /* first case of adjacent level */ 360 if( levelgraph->level[a] == levelgraph->level[b]+1 ) 361 { 362 if( levelgraph->beginBackward[a] >= 0 ) 363 { 364 i = (unsigned int) levelgraph->beginBackward[a]; 365 while( levelgraph->targetBackward[i] != -1 ) 366 { 367 if( levelgraph->targetBackward[i] == (int)b ) 368 return TRUE; 369 ++i; 370 } 371 } 372 } 373 else if( levelgraph->level[a] == levelgraph->level[b]-1 ) /* second case of adjacent level */ 374 { 375 if( levelgraph->beginForward[a] >= 0 ) 376 { 377 i = (unsigned int) levelgraph->beginForward[a]; 378 while( levelgraph->targetForward[i] != -1 ) 379 { 380 if( levelgraph->targetForward[i] == (int)b ) 381 return TRUE; 382 ++i; 383 } 384 } 385 } 386 else /* same level (note that an edge between a and b is stored for a if a < b, otherwise it is stored for b) */ 387 { 388 assert(levelgraph->level[a] == levelgraph->level[b]); 389 assert(levelgraph->level[a] > 0); /* root has no neighbor in the same level */ 390 391 if( a < b && levelgraph->beginAdj[a] >= 0 ) 392 { 393 i = (unsigned int) levelgraph->beginAdj[a]; 394 assert(i >= levelgraph->levelAdj[levelgraph->level[a]]); 395 396 while( i < levelgraph->levelAdj[levelgraph->level[a]+1] && levelgraph->sourceAdj[i] == a ) 397 { 398 if( levelgraph->targetAdj[i] == b ) 399 return TRUE; 400 401 /* if adjacency list ends we are done and a and b are not adjacent */ 402 if( levelgraph->sourceAdj[i] == 0 && levelgraph->targetAdj[i] == 0 ) 403 return FALSE; 404 405 assert(levelgraph->sourceAdj[i] < levelgraph->targetAdj[i]); 406 ++i; 407 } 408 } 409 if( b < a && levelgraph->beginAdj[b] >= 0 ) 410 { 411 i = (unsigned int) levelgraph->beginAdj[b]; 412 assert(i >= levelgraph->levelAdj[levelgraph->level[b]]); 413 414 while( i < levelgraph->levelAdj[levelgraph->level[b]+1] && levelgraph->sourceAdj[i] == b ) 415 { 416 if( levelgraph->targetAdj[i] == a ) 417 return TRUE; 418 419 /* if adjacency list ends we are done and a and b are not adjacent */ 420 if( levelgraph->sourceAdj[i] == 0 && levelgraph->targetAdj[i] == 0 ) 421 return FALSE; 422 423 assert(levelgraph->sourceAdj[i] < levelgraph->targetAdj[i]); 424 ++i; 425 } 426 } 427 } 428 } 429 /* if a or b is not in the levels already completely inserted in the levelgraph, we check 430 * their adjacency by the SCIP data structures 431 */ 432 else 433 { 434 SCIP_CLIQUE** cliques; 435 SCIP_VAR** cliquevars; 436 SCIP_Bool* cliquevals; 437 SCIP_Bool originala; 438 SCIP_Bool originalb; 439 unsigned int ncliques; 440 unsigned int ncliquevars; 441 unsigned int j; 442 443 /* get original variables */ 444 originala = TRUE; 445 if( a >= nbinvars ) 446 { 447 a = a - nbinvars; 448 originala = FALSE; 449 } 450 assert(a < nbinvars); 451 452 originalb = TRUE; 453 if( b >= nbinvars ) 454 { 455 b = b - nbinvars; 456 originalb = FALSE; 457 } 458 assert(b < nbinvars); 459 460 /* nodes cannot be connected by trivial observations */ 461 if( SCIPvarGetNCliques(vars[a], originala) == 0 || SCIPvarGetNCliques(vars[b], originalb) == 0 ) 462 return FALSE; 463 464 /* @todo later: possible improvement: do this test for implications and cliques separately if this here is time consuming */ 465 /* one of the nodes seems to have more arcs than the other, we swap them (since adjacency is symmetric) */ 466 if( SCIPvarGetNCliques(vars[a], originala) > SCIPvarGetNCliques(vars[b], originalb) ) 467 { 468 unsigned int temp; 469 SCIP_Bool varfixingtemp; 470 471 temp = b; 472 varfixingtemp = originalb; 473 b = a; 474 originalb = originala; 475 a = temp; 476 originala = varfixingtemp; 477 } 478 479 /* check whether a and b are contained in a clique */ 480 ncliques = (unsigned int) SCIPvarGetNCliques(vars[a], originala); 481 cliques = SCIPvarGetCliques(vars[a], originala); 482 483 assert(cliques != NULL || ncliques == 0); 484 485 for( i = 0; i < ncliques; ++i ) 486 { 487 assert( cliques != NULL ); /* for lint */ 488 ncliquevars = (unsigned int) SCIPcliqueGetNVars(cliques[i]); 489 cliquevars = SCIPcliqueGetVars(cliques[i]); 490 cliquevals = SCIPcliqueGetValues(cliques[i]); 491 492 assert(cliquevars != NULL || ncliquevars == 0); 493 assert(cliquevals != NULL || ncliquevars == 0); 494 495 for( j = 0; j < ncliquevars; ++j ) 496 { 497 assert( cliquevals != NULL && cliquevars != NULL ); /* for lint */ 498 if( SCIPvarGetProbindex(vars[b]) == SCIPvarGetProbindex(cliquevars[j]) ) 499 { 500 if( (cliquevals[j] == FALSE && originalb == TRUE) || ( cliquevals[j] == TRUE && originalb == FALSE ) ) 501 return TRUE; 502 } 503 } 504 } 505 } 506 } 507 508 return FALSE; 509 } 510 511 /** inside the lifting heuristic we determine the lifting coefficient by counting the length of 512 * chains adjacent to the lifting candidate. 513 * 514 * since we have to exclude all chains adjacent to an already lifted node which is not adjacent to 515 * the current lifting candidate we check all chains of the cycle of length three and block them if 516 * they are adjacent. 517 */ 518 static 519 void checkBlocking( 520 unsigned int a, /**< first node of the checked cycle chain of length 3 */ 521 unsigned int b, /**< second node of the checked cycle chain of length 3 */ 522 unsigned int c, /**< third node of the checked cycle chain of length 3 */ 523 unsigned int i, /**< current lifting candidate */ 524 unsigned int* cycle, /**< list of cycle nodes in order of the cycle */ 525 unsigned int ncyclevars, /**< number of variables in the odd cycle */ 526 SCIP_VAR** vars, /**< problem variables */ 527 unsigned int nbinvars, /**< number of binary problem variables */ 528 unsigned int* lifted, /**< list of lifted nodes */ 529 unsigned int* nlifted, /**< number of lifted nodes */ 530 GRAPHDATA* graphdata, /**< graph */ 531 SCIP_Bool* myi /**< flag array, if cycle node is inner point of a counted chain */ 532 ) 533 { 534 unsigned int k; 535 536 assert(a < ncyclevars); 537 assert(b < ncyclevars); 538 assert(c < ncyclevars); 539 assert(cycle != NULL); 540 assert(ncyclevars % 2 == 1); 541 assert(ncyclevars > 2); 542 assert(ncyclevars <= nbinvars); 543 assert(vars != NULL); 544 assert(nbinvars > 2); 545 assert(lifted != NULL); 546 assert(nlifted != NULL); 547 assert(myi != NULL); 548 549 k = 0; 550 while( (myi[a] || myi[b] || myi[c]) && k < *nlifted ) 551 { 552 /* if all three nodes are adjacent to a node which is already lifted and not adjacent with the 553 * current lifting candidate, they cannot be regarded */ 554 if( !isNeighbor(vars, nbinvars, graphdata, i, lifted[k]) 555 && isNeighbor(vars, nbinvars, graphdata, cycle[a], lifted[k]) 556 && isNeighbor(vars, nbinvars, graphdata, cycle[b], lifted[k]) 557 && isNeighbor(vars, nbinvars, graphdata, cycle[c], lifted[k]) ) 558 { 559 myi[a] = FALSE; 560 myi[b] = FALSE; 561 myi[c] = FALSE; 562 } 563 ++k; 564 } 565 } 566 567 /** determine the heuristic lifting coefficient by counting the length of the adjacent chains of the 568 * candidate (we have to exclude all chains that are adjacent to an already lifted node which is 569 * not adjacent to the current candidate) 570 */ 571 static 572 unsigned int getCoef( 573 SCIP* scip, /**< SCIP data structure */ 574 unsigned int i, /**< current lifting candidate */ 575 unsigned int* cycle, /**< list of cycle nodes in order of the cycle */ 576 unsigned int ncyclevars, /**< number of variables in the odd cycle */ 577 SCIP_VAR** vars, /**< problem variables */ 578 unsigned int nbinvars, /**< number of binary problem variables */ 579 unsigned int* lifted, /**< list of lifted nodes */ 580 unsigned int* nlifted, /**< number of lifted nodes */ 581 GRAPHDATA* graphdata, /**< graph data structure */ 582 SCIP_Bool* myi /**< flag array, if cycle node is inner point of a counted chain */ 583 ) 584 { 585 int j; 586 unsigned int k; 587 unsigned int coef; /* coefficient of lifting candidate of the current step */ 588 unsigned int end; 589 590 assert(scip != NULL); 591 assert(i < 2*nbinvars); 592 assert(cycle != NULL); 593 assert(ncyclevars % 2 == 1); 594 assert(ncyclevars > 2); 595 assert(ncyclevars <= 2*nbinvars); 596 assert(vars != NULL); 597 assert(nbinvars > 2); 598 assert(nlifted != NULL); 599 assert(lifted != NULL); 600 601 coef = 0; 602 603 /* get inner nodes of adjacent chains in cycle */ 604 for( j = 1; j < (int)ncyclevars-1; ++j ) 605 { 606 myi[j] = isNeighbor(vars, nbinvars, graphdata, i, cycle[j-1]) && isNeighbor(vars, nbinvars, graphdata, i, cycle[j]) 607 && isNeighbor(vars, nbinvars, graphdata, i, cycle[j+1]); 608 } 609 610 /* the first and last node of the cycle are treated separately */ 611 myi[0] = isNeighbor(vars, nbinvars, graphdata, i, cycle[ncyclevars-1]) 612 && isNeighbor(vars, nbinvars, graphdata, i, cycle[0]) 613 && isNeighbor(vars, nbinvars, graphdata, i, cycle[1]); 614 myi[ncyclevars-1] = isNeighbor(vars, nbinvars, graphdata, i, cycle[ncyclevars-2]) 615 && isNeighbor(vars, nbinvars, graphdata, i, cycle[ncyclevars-1]) 616 && isNeighbor(vars, nbinvars, graphdata, i, cycle[0]); 617 618 /* consider already lifted nodes that are not adjacent to current lifting candidate and 619 * remove all inner cycle nodes that are adjacent to them 620 */ 621 for( j = 1; j < (int)ncyclevars-1; ++j ) 622 { 623 checkBlocking((unsigned int) (j-1), (unsigned int) j, (unsigned int) (j+1), i, cycle, ncyclevars, vars, nbinvars, lifted, nlifted, graphdata, myi); 624 } 625 checkBlocking(ncyclevars-2, ncyclevars-1, 0, i, cycle, ncyclevars, vars, nbinvars, lifted, nlifted, graphdata, myi); 626 checkBlocking(ncyclevars-1, 0, 1, i, cycle, ncyclevars, vars, nbinvars, lifted, nlifted, graphdata, myi); 627 628 /* calculate lifting coefficient */ 629 k = 0; 630 631 /* first, handle the special case, that the first node of the cycle list is part of a chain */ 632 if( myi[0] ) 633 { 634 ++k; 635 end = ncyclevars-1; 636 while( myi[end] && end > 0 ) 637 { 638 ++k; 639 --end; 640 } 641 assert(k == ncyclevars || end > 0); 642 643 /* all cycle nodes build a relevant chain (maximal chain s.t. all inner nodes are in myi) */ 644 if( end == 0 ) 645 { 646 assert(ncyclevars % 2 == 1); 647 coef = (ncyclevars-1)/2; 648 return coef; 649 } 650 assert(!myi[end]); 651 652 /* current nonempty relevant chain cannot be extended */ 653 if( !myi[1] ) 654 { 655 coef = (unsigned int) SCIPfloor(scip,(k+1.0)/2.0); 656 assert(coef <= (ncyclevars-1)/2); 657 k = 0; 658 } 659 } 660 else 661 end = ncyclevars; 662 663 /* find remaining relevant chains */ 664 j = 1; 665 while( j < (int)end ) 666 { 667 /* skip all nodes that are not inner node */ 668 while( j<(int)end && ! myi[j] ) 669 ++j; 670 671 /* collect all inner nodes (chain is extended) */ 672 while( j<(int)end && myi[j] ) 673 { 674 ++k; 675 ++j; 676 } 677 678 if( k > 0 ) 679 { 680 assert(myi[j-1]); 681 coef += (unsigned int) SCIPfloor(scip,(k+1.0)/2.0); 682 assert(coef <= (ncyclevars-1)/2); 683 k = 0; 684 } 685 } 686 687 return coef; 688 } 689 690 /** Lifting Heuristic based on an idea by Alvarez-Valdes, Parreno, Tamarit 691 * 692 * This method is based on the observation, that a non-cycle node can be lifted into the inequality 693 * with coefficient \f$1\f$ if the node is adjacent to the nodes of a 3-chain on the cycle. 694 * 695 * The coefficient can be calculated as 696 * \f$\left\lfloor{\frac{|C|-1}{2}}\right\rfloor\f$ 697 * where \f$C\f$ is the chain on the cycle. 698 * 699 * If the node is connected to several chains, the coefficients of the chains can be summed up, resulting 700 * in a feasible lifting coefficient. 701 * 702 * Additionally further variables can be lifted by considering chains connected to the additional lifting node 703 * which are not connected to already lifted nodes. 704 * 705 * This method is a feasible heuristic which gives a valid lifted inequality. 706 * (Furthermore the first lifting coefficient is always smaller or equal to the largest possible lifting coefficient.) 707 */ 708 static 709 SCIP_RETCODE liftOddCycleCut( 710 SCIP* scip, /**< SCIP data structure */ 711 unsigned int* nlifted, /**< number of lifted variables */ 712 unsigned int* lifted, /**< indices of the lifted variables */ 713 unsigned int* liftcoef, /**< lifting coefficients */ 714 SCIP_SEPADATA* sepadata, /**< separator data structure */ 715 GRAPHDATA* graphdata, /**< graph */ 716 SCIP_VAR** vars, /**< problem variables */ 717 unsigned int nbinvars, /**< number of binary problem variables */ 718 unsigned int startnode, /**< a node of the cycle */ 719 unsigned int* pred, /**< predecessor of each node (original and negated) in odd cycle */ 720 unsigned int ncyclevars, /**< number of variables in the odd cycle */ 721 SCIP_Real* vals, /**< values of the variables in the given solution */ 722 SCIP_RESULT* result /**< pointer to store the result of the separation call */ 723 ) 724 { 725 unsigned int* cycle; /* storage for cycle and lifted nodes (and their coefficients) */ 726 unsigned int* coef; 727 SCIP_Bool* candList; /* lifting candidate list */ 728 unsigned int i; 729 unsigned int j; 730 unsigned int negated; 731 int bestcand; 732 unsigned int liftround; 733 SCIP_Bool* myi; 734 735 assert(scip != NULL); 736 assert(graphdata != NULL); 737 assert(graphdata->levelgraph != NULL || graphdata->usegls); 738 assert(graphdata->dijkstragraph != NULL || ! graphdata->usegls); 739 assert(vars != NULL); 740 assert(nbinvars > 2); 741 assert(startnode < 2*nbinvars); 742 assert(pred != NULL); 743 assert(ncyclevars % 2 == 1); 744 assert(ncyclevars > 2); 745 assert(ncyclevars <= nbinvars); 746 assert(result != NULL); 747 assert(nlifted != NULL); 748 assert(lifted != NULL); 749 assert(liftcoef != NULL); 750 751 /* allocate memory for cycle list */ 752 SCIP_CALL( SCIPallocBufferArray(scip, &cycle, (int) ncyclevars) ); 753 754 /* transform cycle from predecessor list to array in order of appearance in cycle */ 755 cycle[0] = startnode; 756 j = 1; 757 i = pred[startnode]; 758 while( i != startnode ) 759 { 760 cycle[j] = i; 761 i = pred[i]; 762 ++j; 763 } 764 assert(j == ncyclevars); 765 766 /* allocate memory for coefficients of the lifting candidates (used in every step) */ 767 SCIP_CALL( SCIPallocBufferArray(scip, &coef, (int) (2*nbinvars)) ); 768 769 /* allocate memory candidate list and list of lifted nodes */ 770 SCIP_CALL( SCIPallocBufferArray(scip, &candList, (int) (2*nbinvars)) ); 771 772 /* allocate memory for counting of chains in getCoef() */ 773 SCIP_CALL( SCIPallocBufferArray(scip, &myi, (int) ncyclevars) ); 774 775 if( SCIPisStopped(scip) ) 776 goto TERMINATE; 777 778 /* initialize candidate list */ 779 for( i = 0; i < 2*nbinvars; ++i ) 780 candList[i] = TRUE; 781 782 /* remove cycle variables and their negated from candidate list */ 783 for( i = 0; i < ncyclevars; ++i ) 784 { 785 candList[cycle[i]] = FALSE; 786 if( cycle[i] >= nbinvars ) 787 negated = cycle[i] - nbinvars; 788 else 789 negated = cycle[i] + nbinvars; 790 assert(negated < 2*nbinvars); 791 candList[negated] = FALSE; 792 } 793 794 /* no candidates lifted so far */ 795 *nlifted = 0; 796 bestcand = 0; 797 liftround = 0; 798 799 /* try lifting as long as we have lifting candidates */ 800 while( bestcand >= 0 ) 801 { 802 /* in case we use a lifting rule, which does not require the first lifting coefficient of all variables: REMOVE this */ 803 if( sepadata->recalcliftcoef || liftround == 0 ) 804 { 805 for( i = 0; i < 2*nbinvars; ++i ) 806 { 807 if( candList[i] ) 808 { 809 coef[i] = getCoef(scip, i, cycle, ncyclevars, vars, nbinvars, lifted, nlifted, graphdata, myi); 810 assert(coef[i] <= (ncyclevars-1)/2); 811 if( coef[i] < 1 ) 812 candList[i] = FALSE; 813 } 814 } 815 } 816 ++liftround; 817 bestcand = -1; 818 for( i = 0; i < 2*nbinvars; ++i ) 819 { 820 if( candList[i] ) 821 { 822 /* we want to weight our choice of the lifting node by the value of the current lp solution */ 823 if( sepadata->lpliftcoef ) 824 { 825 if( bestcand < 0 || coef[i]*vals[i] > coef[bestcand]*vals[bestcand] ) 826 bestcand = (int) i; 827 } 828 /* we only regard the coefficient */ 829 else 830 { 831 if( bestcand < 0 || coef[i] > coef[bestcand] ) 832 bestcand = (int) i; 833 } 834 } 835 } 836 837 /* there is at least one lifting variable */ 838 if( bestcand >= 0 ) 839 { 840 if( !(sepadata->recalcliftcoef) ) 841 coef[i] = getCoef(scip, (unsigned int) bestcand, cycle, ncyclevars, vars, nbinvars, lifted, nlifted, graphdata, myi); 842 assert(coef[bestcand] <= (ncyclevars-1)/2); 843 candList[bestcand] = FALSE; 844 if( coef[bestcand] > 0 ) 845 { 846 if( bestcand >= (int)nbinvars ) 847 negated = (unsigned int) bestcand - nbinvars; 848 else 849 negated = (unsigned int) bestcand + nbinvars; 850 assert(negated < 2*nbinvars); 851 852 candList[negated] = FALSE; 853 854 assert(*nlifted < nbinvars-ncyclevars); 855 lifted[*nlifted] = (unsigned int) bestcand; 856 liftcoef[*nlifted] = coef[bestcand]; 857 ++(*nlifted); 858 } 859 } 860 } 861 862 TERMINATE: 863 /* free temporary memory */ 864 SCIPfreeBufferArray(scip, &myi); 865 SCIPfreeBufferArray(scip, &candList); 866 SCIPfreeBufferArray(scip, &coef); 867 SCIPfreeBufferArray(scip, &cycle); 868 869 return SCIP_OKAY; 870 } 871 872 873 /* 874 * methods for both techniques 875 */ 876 877 /** add the inequality corresponding to the given odd cycle to the LP (if violated) 878 * after lifting it (if requested by user flag) 879 */ 880 static 881 SCIP_RETCODE generateOddCycleCut( 882 SCIP* scip, /**< SCIP data structure */ 883 SCIP_SEPA* sepa, /**< separator */ 884 SCIP_SOL* sol, /**< given primal solution */ 885 SCIP_VAR** vars, /**< problem variables */ 886 unsigned int nbinvars, /**< number of binary problem variables */ 887 unsigned int startnode, /**< a node of the cycle */ 888 unsigned int* pred, /**< predecessor of each node (original and negated) in odd cycle */ 889 unsigned int ncyclevars, /**< number of variables in the odd cycle */ 890 unsigned int* incut, /**< TRUE iff node is covered already by a cut */ 891 SCIP_Real* vals, /**< values of the variables in the given solution */ 892 SCIP_SEPADATA* sepadata, /**< separator data structure */ 893 GRAPHDATA* graphdata, /**< graph data structure */ 894 SCIP_RESULT* result /**< pointer to store the result of the separation call */ 895 ) 896 { 897 unsigned int i; 898 unsigned int negatedcount; 899 unsigned int negated; 900 901 /* memory for lifting */ 902 unsigned int nlifted; /* number of lifted variables */ 903 unsigned int* lifted; /* index of the lifted variables */ 904 unsigned int* liftcoef; /* lifting coefficient */ 905 906 /* memory for cut generation */ 907 SCIP_ROW* cut; 908 char cutname[SCIP_MAXSTRLEN]; 909 910 assert(scip != NULL); 911 assert(vars != NULL); 912 assert(startnode < 2*nbinvars); 913 assert(pred != NULL); 914 assert(ncyclevars % 2 == 1); 915 assert(ncyclevars <= nbinvars); 916 assert(incut != NULL); 917 assert(graphdata != NULL); 918 assert(graphdata->levelgraph != NULL || graphdata->usegls); 919 assert(graphdata->dijkstragraph != NULL || ! graphdata->usegls); 920 assert(result != NULL); 921 922 #ifdef SCIP_OUTPUT 923 /* debug method that prints out all found cycles */ 924 printCycle(vars, pred, nbinvars, startnode); 925 #endif 926 927 /* cycle contains only one node */ 928 if( ncyclevars < 3 ) 929 { 930 SCIPdebugMsg(scip, "fixing variable\n"); 931 /* strengthening variable bounds due to single-variable-cycle */ 932 if( startnode < nbinvars ) 933 { 934 SCIP_CALL( SCIPchgVarUb(scip, vars[startnode], 0.0) ); 935 } 936 else 937 { 938 negated = startnode - nbinvars; 939 assert(negated < nbinvars); 940 SCIP_CALL( SCIPchgVarLb(scip, vars[negated], 1.0) ); 941 } 942 *result = SCIP_REDUCEDDOM; 943 return SCIP_OKAY; 944 } 945 946 /* cycle is a triangle (can be excluded by user) */ 947 if( ncyclevars < 5 && ! sepadata->includetriangles ) 948 return SCIP_OKAY; 949 950 if( SCIPisStopped(scip) ) 951 return SCIP_OKAY; 952 953 /* lift the cycle inequality */ 954 nlifted = 0; 955 lifted = NULL; 956 liftcoef = NULL; 957 if( sepadata->liftoddcycles ) 958 { 959 SCIP_CALL( SCIPallocBufferArray(scip, &lifted, (int) (nbinvars - ncyclevars)) ); 960 SCIP_CALL( SCIPallocBufferArray(scip, &liftcoef, (int) (nbinvars - ncyclevars)) ); 961 SCIP_CALL( liftOddCycleCut(scip, &nlifted, lifted, liftcoef, sepadata, graphdata, vars, nbinvars, startnode, pred, ncyclevars, vals, result) ); 962 } 963 /* if we don't try to lift, we generate and add the cut as is */ 964 965 /* create cut */ 966 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "oddcycle_%d", sepadata->ncuts); 967 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), (ncyclevars-1)/2.0, FALSE, FALSE, TRUE) ); 968 SCIP_CALL( SCIPcacheRowExtensions(scip, cut) ); 969 negatedcount = 0; 970 971 /* add variables of odd cycle to cut inequality */ 972 i = pred[startnode]; 973 while( i != startnode ) 974 { 975 assert(i < 2*nbinvars); 976 if( i < nbinvars ) 977 { 978 /* inserting original variable */ 979 SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[i], 1.0) ); 980 incut[i] = TRUE; 981 } 982 else 983 { 984 negated = i - nbinvars; 985 assert(negated < nbinvars); 986 987 /* inserting negated variable */ 988 SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[negated], -1.0) ); 989 ++negatedcount; 990 incut[negated] = TRUE; 991 } 992 i = pred[i]; 993 } 994 assert(startnode == i); 995 996 /* insert startnode */ 997 if( startnode < nbinvars ) 998 { 999 /* inserting original variable */ 1000 SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[startnode], 1.0) ); 1001 incut[startnode] = TRUE; 1002 } 1003 else 1004 { 1005 negated = startnode - nbinvars; 1006 assert(negated < nbinvars); 1007 1008 /* inserting negated variable */ 1009 SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[negated], -1.0) ); 1010 ++negatedcount; 1011 incut[negated] = TRUE; 1012 } 1013 1014 /* add lifted variables to cut inequality (if existing) */ 1015 for( i = 0; i < nlifted; ++i) 1016 { 1017 assert(lifted != NULL); 1018 assert(liftcoef != NULL); 1019 if( lifted[i] < nbinvars ) 1020 { 1021 assert(vars[lifted[i]] != NULL); 1022 SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[lifted[i]], (SCIP_Real) liftcoef[i]) ); 1023 } 1024 else 1025 { 1026 negated = lifted[i] - nbinvars; 1027 assert(negated < nbinvars); 1028 assert(vars[negated] != NULL); 1029 SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[negated], -1.0*liftcoef[i]) ); 1030 negatedcount += liftcoef[i]; 1031 } 1032 } 1033 1034 /* modify right hand side corresponding to number of added negated variables */ 1035 SCIP_CALL( SCIPchgRowRhs(scip, cut, SCIProwGetRhs(cut) - negatedcount) ); 1036 SCIP_CALL( SCIPflushRowExtensions(scip, cut) ); 1037 1038 /* set cut rank: for oddcycle cuts we always set to 1 */ 1039 SCIProwChgRank(cut, 1); 1040 1041 /* not every odd cycle has to be violated due to incompleteness of the implication graph */ 1042 if( SCIPisCutEfficacious(scip, sol, cut) ) 1043 { 1044 SCIP_Bool infeasible; 1045 1046 SCIP_CALL( SCIPaddRow(scip, cut, FALSE, &infeasible) ); 1047 ++sepadata->ncuts; 1048 if ( nlifted > 0 ) 1049 ++sepadata->nliftedcuts; 1050 if ( infeasible ) 1051 *result = SCIP_CUTOFF; 1052 else 1053 { 1054 SCIP_CALL( SCIPaddPoolCut(scip, cut) ); 1055 1056 if( *result == SCIP_DIDNOTFIND ) 1057 *result = SCIP_SEPARATED; 1058 } 1059 1060 #ifdef SCIP_OUTPUT 1061 SCIP_CALL( SCIPprintRow(scip, cut, NULL) ); 1062 #endif 1063 1064 assert(*result == SCIP_CUTOFF || *result == SCIP_SEPARATED || *result == SCIP_REDUCEDDOM); 1065 } 1066 1067 SCIP_CALL( SCIPreleaseRow(scip, &cut) ); 1068 1069 if( sepadata->liftoddcycles ) 1070 { 1071 SCIPfreeBufferArray(scip, &liftcoef); 1072 SCIPfreeBufferArray(scip, &lifted); 1073 } 1074 return SCIP_OKAY; 1075 } 1076 1077 /** check whether the given object is really a cycle without sub-cycles (sub-cycles may be 1078 * calculated by the GLS algorithm in case there is no violated odd cycle inequality) and removes 1079 * pairs of original and negated variables from the cycle 1080 */ 1081 static 1082 SCIP_RETCODE cleanCycle( 1083 SCIP* scip, /**< SCIP data structure */ 1084 unsigned int* pred, /**< predecessor list of current cycle segment */ 1085 SCIP_Bool* incycle, /**< flag array iff node is in cycle segment */ 1086 unsigned int* incut, /**< flag array iff node is already covered by a cut */ 1087 unsigned int x, /**< index of current variable */ 1088 unsigned int startnode, /**< index of first variable of cycle segment */ 1089 unsigned int nbinvars, /**< number of binary problem variables */ 1090 unsigned int* ncyclevars, /**< number of nodes in current cycle segment */ 1091 SCIP_Bool repaircycles, /**< user flag if we should try to repair damaged cycles */ 1092 SCIP_Bool allowmultiplecuts, /**< user flag if we allow multiple cuts per node */ 1093 SCIP_Bool* success /**< FALSE iff an irreparable cycle appears */ 1094 ) 1095 { 1096 unsigned int negx; 1097 1098 assert(scip != NULL); 1099 assert(pred != NULL); 1100 assert(incycle != NULL); 1101 assert(incut != NULL); 1102 assert(ncyclevars != NULL); 1103 assert(*ncyclevars <= nbinvars); 1104 assert(success != NULL); 1105 assert(*success); 1106 1107 assert(x < 2*nbinvars); 1108 1109 /* skip variable if it is already covered by a cut and we do not allow multiple cuts per node */ 1110 if( incut[x] && !allowmultiplecuts ) 1111 { 1112 *success = FALSE; 1113 return SCIP_OKAY; 1114 } 1115 1116 /* get index of negated variable of current variable */ 1117 if( x < nbinvars ) 1118 negx = x + nbinvars; 1119 else 1120 negx = x - nbinvars; 1121 assert(negx < 2*nbinvars); 1122 1123 /* given object is not an odd cycle (contains sub-cycle) or contains original and negated 1124 * variable pair but we should not repair this 1125 */ 1126 if( incycle[x] || (incycle[negx] && !repaircycles) ) 1127 { 1128 *success = FALSE; 1129 return SCIP_OKAY; 1130 } 1131 1132 /* cycle does not contain original and negated variable pair */ 1133 if( !incycle[negx] ) 1134 { 1135 assert(!incycle[x]); 1136 incycle[x] = TRUE; 1137 ++(*ncyclevars); 1138 return SCIP_OKAY; 1139 } 1140 1141 /* delete original and negated variable and cross-link their neighbors the following way, if possible: 1142 * suppose the cycle contains segments: 1143 * startnode - ... - a - neg(x) - c1 - c2 - ... - cn-1 - cn - x - z=pred(x) 1144 * 1145 * because of the chain a - neg(x) - x - cn it holds that 1146 * a=1 => x=0 => neg(x)=1 => cn=0 and 1147 * cn=1 => x=0 => neg(x)=1 => a=0 1148 * because of the chain z - x - neg(x) - b it holds that 1149 * z=1 => x=0 => neg(x)=1 => c1=0 and 1150 * c1=1 => x=0 => neg(x)=1 => z=0 1151 * 1152 * in addition to that, in our linked list structure we need to relink the chain c1-...-cn in reverse order. 1153 * so we gain the order: a - cn - cn-1 - ... - c2 - c1 - z 1154 */ 1155 1156 /* if negated variable is first node in cycle, 1157 * cross-linking not possible because there is no successor z of neg(x) contained in cycle yet 1158 */ 1159 if( negx == startnode ) 1160 { 1161 *success = FALSE; 1162 return SCIP_OKAY; 1163 } 1164 1165 /* if original and negated variable are neighbors, cross linking is not possible, 1166 * but x and neg(x) can simply be removed 1167 * a - neg(x)=pred[a] - x=pred[neg(x)] - z=pred[x] --> a - z=pred[x]=:pred[a] 1168 */ 1169 if( pred[negx] == x ) 1170 { 1171 unsigned int a; 1172 1173 /* find a */ 1174 a = startnode; 1175 while( pred[a] != negx ) 1176 a = pred[a]; 1177 1178 /* link a and z */ 1179 pred[a] = pred[x]; 1180 } 1181 /* cross linking as mentioned above */ 1182 else 1183 { 1184 unsigned int a; 1185 unsigned int z; 1186 1187 /* memory for chain reverse */ 1188 unsigned int* chain; 1189 unsigned int nchain; 1190 1191 unsigned int i; 1192 1193 /* allocate temporary memory */ 1194 SCIP_CALL( SCIPallocBufferArray(scip, &chain, (int) *ncyclevars) ); 1195 1196 /* find and store a */ 1197 a = startnode; 1198 while( pred[a] != negx ) 1199 a = pred[a]; 1200 1201 /* store chain */ 1202 i = pred[negx]; 1203 nchain = 0; 1204 while( i != x ) 1205 { 1206 chain[nchain] = i; 1207 ++nchain; 1208 i = pred[i]; 1209 } 1210 assert(nchain > 0); 1211 1212 /* store z */ 1213 z = pred[x]; 1214 1215 /* link a and c1 */ 1216 pred[a] = chain[nchain-1]; 1217 1218 /* link cn and z */ 1219 pred[chain[0]] = z; 1220 1221 /* reverse the chain */ 1222 for( i = nchain-1; i > 0; --i ) 1223 pred[chain[i]] = chain[i-1]; 1224 1225 /* free temporary memory */ 1226 SCIPfreeBufferArray(scip, &chain); 1227 } 1228 1229 /* remove negated variable from cycle */ 1230 assert(!incycle[x] && incycle[negx]); 1231 incycle[negx] = FALSE; 1232 --(*ncyclevars); 1233 1234 return SCIP_OKAY; 1235 } 1236 1237 1238 /* 1239 * methods for separateHeur() 1240 */ 1241 1242 /** memory reallocation method (the graph is normally very dense, so we dynamically allocate only the memory we need) 1243 * 1244 * Since the array sizes differ the method can be called for each of the three data structure types: 1245 * - Forward: sizeForward, targetForward, weightForward 1246 * - Backward: sizeBackward, targetBackward, weightBackward 1247 * - Adj (inner level edges): sizeAdj, sourceAdj, targetAdj, weightAdj 1248 */ 1249 static 1250 SCIP_RETCODE checkArraySizesHeur( 1251 SCIP* scip, /**< SCIP data structure */ 1252 LEVELGRAPH* graph, /**< LEVELGRAPH data structure */ 1253 unsigned int* size, /**< given size */ 1254 int** targetArray, /**< given target array (or NULL if sourceAdjArray and targetAdjArray given) */ 1255 unsigned int** weightArray, /**< given weight array */ 1256 unsigned int** sourceAdjArray, /**< given sourceAdj array (or NULL if targetArray given) */ 1257 unsigned int** targetAdjArray, /**< given targetAdj array (or NULL if targetArray given) */ 1258 SCIP_Bool* success /**< FALSE, iff memory reallocation fails */ 1259 ) 1260 { 1261 SCIP_Real memorylimit; 1262 unsigned int additional; 1263 SCIP_Bool avoidmemout; 1264 1265 assert(scip != NULL); 1266 assert(graph != NULL); 1267 assert(size != NULL); 1268 assert(targetArray != NULL || (sourceAdjArray != NULL && targetAdjArray != NULL)); 1269 assert(weightArray != NULL); 1270 assert(success != NULL); 1271 1272 SCIPdebugMsg(scip, "reallocating...\n"); 1273 1274 additional = MIN(graph->maxarcs + graph->maxnodes - *size, *size) * ((int) sizeof(**weightArray)); 1275 if( targetArray != NULL ) 1276 { 1277 additional += MIN(graph->maxarcs + graph->maxnodes - *size, *size) * ((int) sizeof(**targetArray)); 1278 } 1279 else 1280 { 1281 additional += MIN(graph->maxarcs + graph->maxnodes - *size, *size) * ((int) sizeof(**sourceAdjArray)); 1282 additional += MIN(graph->maxarcs + graph->maxnodes - *size, *size) * ((int) sizeof(**targetAdjArray)); 1283 } 1284 1285 SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) ); 1286 if( !SCIPisInfinity(scip, memorylimit) ) 1287 { 1288 memorylimit -= SCIPgetMemUsed(scip)/1048576.0; 1289 memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0; 1290 } 1291 1292 SCIP_CALL( SCIPgetBoolParam(scip, "misc/avoidmemout", &avoidmemout) ); 1293 /* if memorylimit would be exceeded or any other limit is reached free all data and exit */ 1294 if( (avoidmemout && memorylimit <= additional/1048576.0) || SCIPisStopped(scip) ) 1295 { 1296 *success = FALSE; 1297 SCIPdebugMsg(scip, "...memory limit exceeded\n"); 1298 return SCIP_OKAY; 1299 } 1300 1301 *size = 2 * (*size); 1302 1303 SCIP_CALL( SCIPreallocBufferArray(scip, weightArray, (int) MIN(graph->maxarcs + graph->maxnodes, *size)) ); 1304 if( targetArray != NULL ) 1305 { 1306 SCIP_CALL( SCIPreallocBufferArray(scip, targetArray, (int) MIN(graph->maxarcs + graph->maxnodes, *size)) ); 1307 } 1308 else 1309 { 1310 assert(sourceAdjArray != NULL); 1311 assert(targetAdjArray != NULL); 1312 SCIP_CALL( SCIPreallocBufferArray(scip, sourceAdjArray, (int) MIN(graph->maxarcs, *size)) ); 1313 SCIP_CALL( SCIPreallocBufferArray(scip, targetAdjArray, (int) MIN(graph->maxarcs, *size)) ); 1314 } 1315 1316 /* if memorylimit is exceeded free all data and exit */ 1317 SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) ); 1318 if( !SCIPisInfinity(scip, memorylimit) ) 1319 { 1320 memorylimit -= SCIPgetMemUsed(scip)/1048576.0; 1321 memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0; 1322 } 1323 1324 if( avoidmemout && memorylimit <= 2.0*SCIPgetMemExternEstim(scip)/1048576.0 ) 1325 { 1326 *success = FALSE; 1327 SCIPdebugMsg(scip, "...memory limit exceeded\n"); 1328 return SCIP_OKAY; 1329 } 1330 1331 SCIPdebugMsg(scip, "...with success\n"); 1332 1333 return SCIP_OKAY; 1334 } 1335 1336 /** Add arc to level graph */ 1337 static 1338 SCIP_RETCODE addArc( 1339 SCIP* scip, /**< SCIP data structure */ 1340 LEVELGRAPH* graph, /**< LEVELGRAPH data structure */ 1341 unsigned int u, /**< source node */ 1342 unsigned int v, /**< target node */ 1343 unsigned int level, /**< number of current level */ 1344 unsigned int weight, /**< weight of the arc */ 1345 unsigned int* nAdj, /**< array of numbers of arcs inside levels */ 1346 SCIP_Bool* success /**< FALSE, iff memory reallocation fails */ 1347 ) 1348 { 1349 /* arc is a forward arc */ 1350 if( graph->level[v] == level+1 ) 1351 { 1352 graph->targetForward[graph->lastF] = (int) v; 1353 graph->weightForward[graph->lastF] = weight; 1354 ++(graph->lastF); 1355 ++(graph->narcs); 1356 if( graph->lastF == graph->sizeForward ) 1357 { 1358 SCIP_CALL( checkArraySizesHeur(scip, graph, &(graph->sizeForward), &(graph->targetForward), 1359 &(graph->weightForward), NULL, NULL, success) ); 1360 if( !(*success) ) 1361 return SCIP_OKAY; 1362 } 1363 } 1364 else 1365 { 1366 assert(graph->level[v] == level || graph->level[v] == level-1); 1367 1368 /* arc is a backward arc */ 1369 if( graph->level[v] == level-1 ) 1370 { 1371 graph->targetBackward[graph->lastB] = (int) v; 1372 graph->weightBackward[graph->lastB] = weight; 1373 ++(graph->lastB); 1374 ++(graph->narcs); 1375 1376 if( graph->lastB == graph->sizeBackward ) 1377 { 1378 SCIP_CALL( checkArraySizesHeur(scip, graph, &(graph->sizeBackward), &(graph->targetBackward), 1379 &(graph->weightBackward), NULL, NULL, success) ); 1380 if( !(*success) ) 1381 return SCIP_OKAY; 1382 } 1383 } 1384 else /* arc is in the same level */ 1385 { 1386 assert(graph->level[v] == level); 1387 1388 /* add arc only once, i.e., if u < v */ 1389 if( u < v ) 1390 { 1391 graph->sourceAdj[graph->levelAdj[level+1]+*nAdj] = u; 1392 graph->targetAdj[graph->levelAdj[level+1]+*nAdj] = v; 1393 graph->weightAdj[graph->levelAdj[level+1]+*nAdj] = weight; 1394 ++(*nAdj); 1395 ++(graph->narcs); 1396 1397 if( graph->levelAdj[level+1]+*nAdj == graph->sizeAdj ) 1398 { 1399 SCIP_CALL( checkArraySizesHeur(scip, graph, &(graph->sizeAdj), NULL, &(graph->weightAdj), 1400 &(graph->sourceAdj), &(graph->targetAdj), success) ); 1401 if( !(*success) ) 1402 return SCIP_OKAY; 1403 } 1404 } 1405 } 1406 } 1407 return SCIP_OKAY; 1408 } 1409 1410 /** add implications from cliques of the given node u 1411 * 1412 * @see createNextLevel() 1413 */ 1414 static 1415 SCIP_RETCODE addNextLevelCliques( 1416 SCIP* scip, /**< SCIP data structure */ 1417 SCIP_SEPADATA* sepadata, /**< separator data structure */ 1418 SCIP_VAR** vars, /**< problem variables */ 1419 SCIP_Real* vals, /**< values of the binary variables in the current LP relaxation */ 1420 unsigned int u, /**< current node */ 1421 LEVELGRAPH* graph, /**< LEVELGRAPH data structure */ 1422 unsigned int level, /**< number of current level */ 1423 SCIP_Bool* inlevelgraph, /**< flag array if node is already inserted in level graph */ 1424 unsigned int* newlevel, /**< array of nodes of the next level */ 1425 unsigned int* nnewlevel, /**< number of nodes of the next level */ 1426 unsigned int* nAdj, /**< array of numbers of arcs inside levels */ 1427 SCIP_Bool* success /**< FALSE, iff memory reallocation fails */ 1428 ) 1429 { 1430 SCIP_Bool varfixing; 1431 unsigned int ncliques; 1432 unsigned int nbinvars; 1433 unsigned int varsidx; 1434 SCIP_CLIQUE** cliques; 1435 unsigned int ncliquevars; 1436 SCIP_VAR** cliquevars; 1437 SCIP_Bool* cliquevals; 1438 unsigned int j; 1439 unsigned int k; 1440 1441 assert(scip != NULL); 1442 assert(vars != NULL); 1443 assert(vals != NULL); 1444 assert(graph != NULL); 1445 assert(graph->targetForward != NULL); 1446 assert(graph->weightForward != NULL); 1447 assert(graph->targetBackward != NULL); 1448 assert(graph->weightBackward != NULL); 1449 assert(graph->sourceAdj != NULL); 1450 assert(graph->targetAdj != NULL); 1451 assert(graph->weightAdj != NULL); 1452 assert(inlevelgraph != NULL); 1453 assert(newlevel != NULL); 1454 assert(nnewlevel != NULL); 1455 assert(nAdj != NULL); 1456 assert(success != NULL); 1457 1458 assert(u < graph->maxnodes); 1459 1460 nbinvars = (graph->maxnodes)/2; 1461 1462 /* current node signifies a problem variable */ 1463 if( u < nbinvars ) 1464 { 1465 varfixing = TRUE; 1466 varsidx = u; 1467 } 1468 /* current node signifies a negated variable */ 1469 else 1470 { 1471 varfixing = FALSE; 1472 varsidx = u - nbinvars; 1473 } 1474 assert(varsidx < nbinvars); 1475 assert(!SCIPisFeasIntegral(scip, vals[varsidx])); 1476 1477 /* get cliques of the current variable */ 1478 ncliques = (unsigned int) SCIPvarGetNCliques(vars[varsidx], varfixing); 1479 if( ncliques == 0 ) 1480 return SCIP_OKAY; 1481 1482 cliques = SCIPvarGetCliques(vars[varsidx], varfixing); 1483 assert(cliques != NULL); 1484 1485 for( j = 0; j < ncliques; ++j ) 1486 { 1487 ncliquevars = (unsigned int) SCIPcliqueGetNVars(cliques[j]); 1488 cliquevars = SCIPcliqueGetVars(cliques[j]); 1489 cliquevals = SCIPcliqueGetValues(cliques[j]); 1490 1491 assert(cliquevars != NULL || ncliquevars == 0); 1492 assert(cliquevals != NULL || ncliquevars == 0); 1493 1494 for( k = 0; k < ncliquevars; ++k ) 1495 { 1496 unsigned int l; 1497 unsigned int v; 1498 unsigned int weight; 1499 1500 assert( cliquevars != NULL && cliquevals != NULL ); /* for lint */ 1501 1502 l = sepadata->mapping[SCIPvarGetProbindex(cliquevars[k])]; 1503 assert(l < nbinvars); 1504 1505 /* skip integral neighbors */ 1506 if( SCIPisFeasIntegral(scip, vals[l]) ) 1507 continue; 1508 1509 /* consider clique with negated variable (x = 1 -> y >= 1 <=> x = 1 -> neg(y) <= 0) */ 1510 if( cliquevals[k] == FALSE ) 1511 v = l + nbinvars; 1512 /* x = 1 -> y <= 0 */ 1513 else 1514 v = l; 1515 assert(v < graph->maxnodes); 1516 1517 /* if variable is a new node, it will be assigned to the next level, 1518 * but if the level contains more nodes than allowed 1519 * (defined by percent per level plus offset), 1520 * we skip the rest of the nodes 1521 */ 1522 if( !inlevelgraph[v] && (*nnewlevel) <= sepadata->maxlevelsize ) 1523 { 1524 ++(graph->nnodes); 1525 graph->level[v] = level+1; 1526 inlevelgraph[v] = TRUE; 1527 newlevel[*nnewlevel] = v; 1528 ++(*nnewlevel); 1529 } 1530 assert(*nnewlevel > sepadata->maxlevelsize || inlevelgraph[v]); 1531 1532 /* calculate arc weight and add arc, if the neighbor node is on the same or a neighbor level */ 1533 if( inlevelgraph[v] && (graph->level[v] == level+1 || graph->level[v] == level || graph->level[v] == level-1)) 1534 { 1535 int tmp; 1536 1537 /* the computation of 1.0 - vals[v] if v is negated is ensured by the fact that v > nbinvars in this case */ 1538 /* set weight of arc (x,y) to 1 - x* -y* */ 1539 if( varfixing ) 1540 { 1541 /* x = 1 -> y <= 0 or y >= 1 */ 1542 tmp = (int) SCIPfeasCeil(scip, sepadata->scale * (1 - vals[varsidx] - vals[v])); 1543 weight = (unsigned int) MAX(tmp, sepadata->maxreference); 1544 } 1545 else 1546 { 1547 /* x = 0 <-> neg(x) = 1 -> y <= 0 or y >= 1 */ 1548 tmp = (int) SCIPfeasCeil(scip, sepadata->scale * (1.0 - (1.0 - vals[varsidx]) - vals[v])); 1549 weight = (unsigned int) MAX(tmp, sepadata->maxreference); 1550 } 1551 1552 /* add arc from current to neighbor node */ 1553 SCIP_CALL( addArc(scip, graph, u, v, level, weight, nAdj, success) ); 1554 if( !(*success) ) 1555 return SCIP_OKAY; 1556 } 1557 } 1558 } 1559 return SCIP_OKAY; 1560 } 1561 1562 1563 /** sort level of root neighbors 1564 * 1565 * If we limit the size of nodes of a level, we want to add the best neighbors to the next level. 1566 * Since sorting every level is too expensive, we sort the neighbors of the root (if requested). 1567 * 1568 * Create the first level as follows: 1569 * - create flag array for binary variables and their negated and set their values FALSE 1570 * - iterate over the implication and clique neighbors of the root and set their flag array values to TRUE 1571 * - create variable array and insert all variables with flag value TRUE 1572 * - sort variable array by maximal fractionality 1573 * - add variables from sorted array to levelgraph until first level is full (or all variables are inserted) 1574 * 1575 * Even inserting all variables might help for the following creation of further levels since the neighbors 1576 * of nodes with high fractionality often have high fractionalities themselves and would be inserted first 1577 * when further levels would have been sorted (which actually is not the case). 1578 */ 1579 static 1580 SCIP_RETCODE insertSortedRootNeighbors( 1581 SCIP* scip, /**< SCIP data structure */ 1582 LEVELGRAPH* graph, /**< LEVELGRAPH data structure */ 1583 unsigned int nbinvars, /**< number of binary problem variables */ 1584 unsigned int ncurlevel, /**< number of nodes of the current level */ 1585 unsigned int u, /**< source node */ 1586 SCIP_Real* vals, /**< values of the binary variables in the current LP relaxation */ 1587 SCIP_VAR** vars, /**< problem variables */ 1588 SCIP_SEPADATA* sepadata, /**< separator data structure */ 1589 unsigned int* nnewlevel, /**< number of nodes of the next level */ 1590 SCIP_Bool* inlevelgraph, /**< nodes in new graph corr. to old graph (-1 if unassigned) */ 1591 unsigned int level, /**< number of current level */ 1592 unsigned int* newlevel, /**< array of nodes of the next level */ 1593 SCIP_Bool* success /**< FALSE, iff memory reallocation fails */ 1594 ) 1595 { 1596 /* storage for the neighbors of the root */ 1597 unsigned int root; 1598 unsigned int nneighbors; 1599 SCIP_Bool* isneighbor; 1600 int* neighbors; 1601 SCIP_Real* sortvals; 1602 1603 SCIP_Bool varfixing; 1604 unsigned int varsidx; 1605 1606 /* storage for cliques to the neighbors of the root node */ 1607 unsigned int ncliques; 1608 SCIP_CLIQUE** cliques; 1609 unsigned int ncliquevars; 1610 SCIP_VAR** cliquevars; 1611 SCIP_Bool* cliquevals; 1612 1613 unsigned int j; 1614 unsigned int k; 1615 unsigned int v; 1616 1617 /* allocate flag array for neighbor detection */ 1618 SCIP_CALL( SCIPallocBufferArray(scip, &isneighbor, (int) graph->maxnodes) ); 1619 BMSclearMemoryArray(isneighbor, graph->maxnodes); 1620 1621 nbinvars = (graph->maxnodes)/2; 1622 1623 assert(ncurlevel == 1); 1624 root = u; 1625 1626 /* current node signifies a problem variable */ 1627 if( root < nbinvars ) 1628 { 1629 varfixing = TRUE; 1630 varsidx = root; 1631 } 1632 /* current node signifies a negated variable */ 1633 else 1634 { 1635 varfixing = FALSE; 1636 varsidx = root - nbinvars; 1637 } 1638 assert(varsidx < nbinvars); 1639 assert(! SCIPisFeasIntegral(scip, vals[varsidx])); 1640 nneighbors = 0; 1641 1642 /* count cliques of the root */ 1643 ncliques = (unsigned int) SCIPvarGetNCliques(vars[varsidx], varfixing); 1644 if( ncliques > 0 ) 1645 { 1646 cliques = SCIPvarGetCliques(vars[varsidx], varfixing); 1647 assert(cliques != NULL); 1648 1649 for( j = 0; j < ncliques; ++j ) 1650 { 1651 ncliquevars = (unsigned int) SCIPcliqueGetNVars(cliques[j]); 1652 cliquevars = SCIPcliqueGetVars(cliques[j]); 1653 cliquevals = SCIPcliqueGetValues(cliques[j]); 1654 1655 assert(cliquevars != NULL || ncliquevars == 0); 1656 assert(cliquevals != NULL || ncliquevars == 0); 1657 1658 for( k = 0; k < ncliquevars; ++k ) 1659 { 1660 unsigned int kidx; 1661 1662 assert( cliquevars != NULL && cliquevals != NULL ); /* for lint */ 1663 1664 kidx = sepadata->mapping[SCIPvarGetProbindex(cliquevars[k])]; 1665 assert(kidx < nbinvars); 1666 1667 /* skip root */ 1668 if( kidx == varsidx ) 1669 continue; 1670 1671 /* skip integral neighbors */ 1672 if( SCIPisFeasIntegral(scip, vals[kidx])) 1673 continue; 1674 1675 if( cliquevals[k] == TRUE ) 1676 { 1677 if ( ! isneighbor[kidx] ) 1678 { 1679 ++nneighbors; 1680 isneighbor[kidx] = TRUE; 1681 } 1682 } 1683 else 1684 { 1685 assert(cliquevals[k] == FALSE); 1686 if ( ! isneighbor[kidx + nbinvars] ) 1687 { 1688 ++nneighbors; 1689 isneighbor[kidx+nbinvars] = TRUE; 1690 } 1691 } 1692 } 1693 } 1694 } 1695 1696 /* root cannot be part of the next level */ 1697 assert(! isneighbor[root]); 1698 1699 /* allocate memory for sorting of root neighbors */ 1700 SCIP_CALL( SCIPallocBufferArray(scip, &neighbors, (int) nneighbors) ); 1701 SCIP_CALL( SCIPallocBufferArray(scip, &sortvals, (int) nneighbors) ); 1702 1703 k = 0; 1704 for( j = 0; j < graph->maxnodes; ++j ) 1705 { 1706 if( isneighbor[j] ) 1707 { 1708 assert(j != root); 1709 assert(!SCIPisFeasIntegral(scip, vals[j])); 1710 1711 neighbors[k] = (int) j; 1712 sortvals[k] = MIN(1.0 - vals[j], vals[j]); 1713 ++k; 1714 } 1715 } 1716 assert(k == nneighbors); 1717 1718 /* sort neighbors by fractionality */ 1719 SCIPsortDownRealInt(sortvals, neighbors, (int) nneighbors); 1720 1721 /* free temporary memory */ 1722 SCIPfreeBufferArray(scip, &sortvals); 1723 1724 /* insert sorted neighbors until level size limit is reached (or all neighbors are inserted) */ 1725 for( j = 0; j < nneighbors && (*nnewlevel) <= sepadata->maxlevelsize; ++j ) 1726 { 1727 int tmp; 1728 1729 v = (unsigned int) neighbors[j]; 1730 assert( v < 2 * nbinvars ); 1731 1732 /* only the root is contained in the levelgraph */ 1733 assert(! inlevelgraph[v] || v == root+nbinvars || v == root-nbinvars); 1734 1735 /* insert neighbor into levelgraph */ 1736 ++(graph->nnodes); 1737 graph->level[v] = level + 1; 1738 inlevelgraph[v] = TRUE; 1739 newlevel[*nnewlevel] = v; 1740 ++(*nnewlevel); 1741 1742 assert(! SCIPisFeasIntegral(scip, vals[varsidx])); 1743 assert(! SCIPisFeasIntegral(scip, vals[v])); 1744 1745 graph->targetForward[graph->lastF] = (int) v; 1746 /* the computation of 1.0 - vals[v] if v is negated is ensured by the fact that v > nbinvars in this case */ 1747 if( varfixing ) 1748 { 1749 tmp = (int) SCIPfeasCeil(scip, sepadata->scale * (1.0 - vals[varsidx] - vals[v])); 1750 graph->weightForward[graph->lastF] = (unsigned int) MAX(tmp, sepadata->maxreference); 1751 } 1752 else 1753 { 1754 assert( ! varfixing ); 1755 tmp = (int) SCIPfeasCeil(scip, sepadata->scale * (1.0 - (1.0 - vals[varsidx]) - vals[v])); 1756 graph->weightForward[graph->lastF] = (unsigned int) MAX(tmp, sepadata->maxreference); 1757 } 1758 ++(graph->lastF); 1759 ++(graph->narcs); 1760 if( graph->lastF == graph->sizeForward ) 1761 { 1762 SCIP_CALL( checkArraySizesHeur(scip, graph, &(graph->sizeForward), &(graph->targetForward), 1763 &(graph->weightForward), NULL, NULL, success) ); 1764 1765 if( !(*success) ) 1766 break; 1767 } 1768 } 1769 1770 /* free temporary memory */ 1771 SCIPfreeBufferArray(scip, &neighbors); 1772 SCIPfreeBufferArray(scip, &isneighbor); 1773 1774 return SCIP_OKAY; 1775 } 1776 1777 /** Find shortest path from start node to root 1778 * 1779 * We perform a BFS to find the shortest path to the root. D stores the distance to the start 1780 * node, P stores the partent nodes in the shortest path tree (-1 if node has not been reached). 1781 */ 1782 static 1783 SCIP_RETCODE findShortestPathToRoot( 1784 SCIP* scip, /**< SCIP data structure */ 1785 int scale, /**< scaling factor for edge weights */ 1786 LEVELGRAPH* graph, /**< LEVELGRAPH data structure */ 1787 unsigned int startnode, /**< start node for path search */ 1788 unsigned int* distance, /**< distances of searched nodes from root */ 1789 unsigned int* queue, /**< node queue for path search */ 1790 SCIP_Bool* inQueue, /**< whether node is in the queue */ 1791 int* parentTree /**< parent tree (-1 if no parent) */ 1792 ) 1793 { 1794 unsigned int i; 1795 int startQueue; 1796 int endQueue; 1797 unsigned int u; 1798 int v; 1799 unsigned int d; 1800 1801 assert(scip != NULL); 1802 assert(graph != NULL); 1803 assert(graph->beginBackward != NULL); 1804 assert(graph->targetBackward != NULL); 1805 assert(graph->weightBackward != NULL); 1806 assert(distance != NULL); 1807 assert(queue != NULL); 1808 assert(inQueue != NULL); 1809 assert(parentTree != NULL); 1810 assert(scale >= 0); 1811 1812 /* initialize distances */ 1813 for( i = 0; i < graph->maxnodes; ++i ) 1814 { 1815 distance[i] = 2 * (graph->nnodes) * (unsigned) scale; 1816 parentTree[i] = -1; 1817 inQueue[i] = FALSE; 1818 } 1819 distance[startnode] = 0; 1820 1821 /* initialize queue */ 1822 startQueue = 0; 1823 endQueue = 0; 1824 queue[0] = startnode; 1825 1826 /* as long as queue is not empty */ 1827 while( startQueue <= endQueue ) 1828 { 1829 /* pop first node from queue */ 1830 u = queue[startQueue]; 1831 ++startQueue; 1832 1833 /* check adjacent nodes */ 1834 assert(graph->beginBackward[u] >= 0); 1835 i = (unsigned int) graph->beginBackward[u]; 1836 for( v = graph->targetBackward[i]; v >= 0; v = graph->targetBackward[++i] ) 1837 { 1838 /* distance to u via current arc: */ 1839 d = distance[u] + graph->weightBackward[i]; 1840 1841 /* if we found a shorter connection */ 1842 if( d < distance[v] ) 1843 { 1844 distance[v] = d; 1845 parentTree[v] = (int) u; 1846 1847 /* insert in queue if not already present */ 1848 if( !inQueue[v] ) 1849 { 1850 ++endQueue; 1851 queue[endQueue] = (unsigned int) v; 1852 inQueue[v] = TRUE; 1853 } 1854 } 1855 } 1856 /* it is not necessary to stop if we found the root (in this case there are no arcs left) and we stop anyway */ 1857 } 1858 assert(parentTree[u] != -1); 1859 1860 return SCIP_OKAY; 1861 } 1862 1863 1864 /** Block shortest path 1865 * 1866 * We traverse the shortest path found by findShortestPathToRoot() and block all neighbors (in the 1867 * original graph) of nodes in the path, i.e., we set blocked to TRUE. We do not block neighbors of 1868 * the root node, since they have to be used. For the start node we only block nodes on the 1869 * previous layers, 1870 * 1871 * @see findShortestPathToRoot() 1872 */ 1873 static 1874 SCIP_RETCODE blockRootPath( 1875 SCIP* scip, /**< SCIP data structure */ 1876 LEVELGRAPH* graph, /**< LEVELGRAPH data structure */ 1877 unsigned int startnode, /**< start node */ 1878 SCIP_Bool* inlevelgraph, /**< nodes in new graph corr. to old graph (-1 if unassigned) */ 1879 SCIP_Bool* blocked, /**< whether node is blocked */ 1880 int* parentTree, /**< parent tree */ 1881 unsigned int root /**< root of the current level graph */ 1882 ) 1883 { 1884 unsigned int u; 1885 unsigned int i; 1886 int v; 1887 1888 assert(scip != NULL); 1889 assert(graph != NULL); 1890 assert(graph->level != NULL); 1891 assert(graph->beginForward != NULL); 1892 assert(graph->targetForward != NULL); 1893 assert(graph->beginBackward != NULL); 1894 assert(graph->targetBackward != NULL); 1895 assert(graph->sourceAdj != NULL); 1896 assert(graph->targetAdj != NULL); 1897 assert(inlevelgraph != NULL); 1898 assert(blocked != NULL); 1899 assert(parentTree != NULL); 1900 1901 assert(parentTree[root] >= 0); 1902 1903 /* follow the path from the predecessor of root to the start node and block all neighbors */ 1904 u = (unsigned int) parentTree[root]; 1905 while( u != startnode ) 1906 { 1907 /* block neighbors of u in higher level */ 1908 i = (unsigned int) graph->beginForward[u]; 1909 for( v = graph->targetForward[i]; v >= 0; v = graph->targetForward[++i] ) 1910 { 1911 assert(inlevelgraph[v]); 1912 blocked[v] = TRUE; 1913 } 1914 1915 /* block neighbors of u in lower level */ 1916 i = (unsigned int) graph->beginBackward[u]; 1917 for( v = graph->targetBackward[i]; v >= 0; v = graph->targetBackward[++i] ) 1918 { 1919 assert(inlevelgraph[v]); 1920 blocked[v] = TRUE; 1921 } 1922 1923 /* block neighbors of u in same level */ 1924 assert(graph->level[u] > 0); 1925 for( i = graph->levelAdj[graph->level[u]]; i < graph->levelAdj[graph->level[u]+1]; ++i ) 1926 { 1927 assert(graph->sourceAdj[i] < graph->targetAdj[i]); 1928 assert(graph->level[graph->sourceAdj[i]] == graph->level[graph->targetAdj[i]]); 1929 1930 /* remember that these arcs are only stored for one direction */ 1931 if( graph->sourceAdj[i] == u ) 1932 { 1933 blocked[graph->targetAdj[i]] = TRUE; 1934 } 1935 if( graph->targetAdj[i] == u ) 1936 { 1937 blocked[graph->sourceAdj[i]] = TRUE; 1938 } 1939 } 1940 1941 /* get next node on the path */ 1942 u = (unsigned int) parentTree[u]; 1943 } 1944 assert(u == startnode); 1945 1946 /* block nodes adjacent to start node on previous level */ 1947 assert(graph->beginBackward[u] > 0); 1948 i = (unsigned int) graph->beginBackward[u]; 1949 for( v = graph->targetBackward[i]; v >= 0; v = graph->targetBackward[++i] ) 1950 blocked[v] = TRUE; 1951 1952 return SCIP_OKAY; 1953 } 1954 1955 1956 /** Find shortest path from root to target node 1957 * 1958 * We perform a BFS to find the shortest path from the root. The only difference to 1959 * findShortestPathToRoot() is that we avoid nodes that are blocked. 1960 */ 1961 static 1962 SCIP_RETCODE 1963 findUnblockedShortestPathToRoot( 1964 SCIP* scip, /**< SCIP data structure */ 1965 int scale, /**< scaling factor for edge weights */ 1966 LEVELGRAPH* graph, /**< LEVELGRAPH data structure */ 1967 unsigned int startnode, /**< start node for path search */ 1968 unsigned int* distance, /**< distances of searched nodes from root */ 1969 unsigned int* queue, /**< node queue for path search */ 1970 SCIP_Bool* inQueue, /**< whether node is in the queue */ 1971 int* parentTreeBackward, /**< parent tree (-1 if no parent) */ 1972 unsigned int root, /**< root of the current level graph */ 1973 SCIP_Bool* blocked /**< whether nodes can be used */ 1974 ) 1975 { 1976 unsigned int i; 1977 int startQueue; 1978 int endQueue; 1979 unsigned int u; 1980 int v; 1981 unsigned int d; 1982 int* parentTree; 1983 int* transform; 1984 1985 assert(scip != NULL); 1986 assert(graph != NULL); 1987 assert(graph->beginBackward != NULL); 1988 assert(graph->targetBackward != NULL); 1989 assert(graph->weightBackward != NULL); 1990 assert(distance != NULL); 1991 assert(queue != NULL); 1992 assert(inQueue != NULL); 1993 assert(scale >= 0); 1994 1995 /* allocate temporary memory */ 1996 SCIP_CALL( SCIPallocBufferArray(scip, &parentTree, (int) graph->maxnodes) ); 1997 SCIP_CALL( SCIPallocBufferArray(scip, &transform, (int) graph->maxnodes) ); 1998 1999 assert(parentTree != NULL); 2000 assert(transform != NULL); 2001 2002 /* initialize distances */ 2003 for( i = 0; i < graph->maxnodes; ++i ) 2004 { 2005 distance[i] = 2 * (graph->nnodes) * (unsigned)scale; 2006 parentTree[i] = -1; 2007 parentTreeBackward[i] = -1; 2008 transform[i] = -1; 2009 inQueue[i] = FALSE; 2010 } 2011 distance[startnode] = 0; 2012 2013 /* initialize queue */ 2014 startQueue = 0; 2015 endQueue = 0; 2016 queue[0] = startnode; 2017 2018 /* as long as queue is not empty */ 2019 while( startQueue <= endQueue ) 2020 { 2021 /* pop first node from queue */ 2022 u = queue[startQueue]; 2023 ++startQueue; 2024 2025 /* check adjacent nodes */ 2026 assert(graph->beginBackward[u] >= 0); 2027 i = (unsigned int) graph->beginBackward[u]; 2028 for( v = graph->targetBackward[i]; v >= 0; v = graph->targetBackward[++i] ) 2029 { 2030 if( blocked[v] && v != (int) root) 2031 continue; 2032 2033 /* distance to u via current arc: */ 2034 d = distance[u] + graph->weightBackward[i]; 2035 2036 /* if we found a shorter connection */ 2037 if( d < distance[v] ) 2038 { 2039 distance[v] = d; 2040 parentTree[v] = (int) u; 2041 2042 /* insert in queue if not already present */ 2043 if( !inQueue[v] ) 2044 { 2045 ++endQueue; 2046 queue[endQueue] = (unsigned int) v; 2047 inQueue[v] = TRUE; 2048 } 2049 } 2050 } 2051 /* it is not necessary to stop if we found the root (in this case there are no arcs left) and we stop anyway */ 2052 } 2053 2054 /* reverse order such that it is a path from the root */ 2055 v = (int) root; 2056 transform[0] = (int) root; 2057 i = 1; 2058 while(parentTree[v] >= 0) 2059 { 2060 transform[i] = parentTree[v]; 2061 ++i; 2062 v = parentTree[v]; 2063 } 2064 --i; 2065 while(i > 0) 2066 { 2067 parentTreeBackward[transform[i]] = transform[i-1]; 2068 --i; 2069 } 2070 2071 /* free temporary memory */ 2072 SCIPfreeBufferArray(scip, &transform); 2073 SCIPfreeBufferArray(scip, &parentTree); 2074 2075 return SCIP_OKAY; 2076 } 2077 2078 /** create next level of level graph for odd cycle separation 2079 * 2080 * @see separateHeur() 2081 */ 2082 static 2083 SCIP_RETCODE createNextLevel( 2084 SCIP* scip, /**< SCIP data structure */ 2085 SCIP_SEPADATA* sepadata, /**< separator data structure */ 2086 SCIP_VAR** vars, /**< problem variables */ 2087 SCIP_Real* vals, /**< values of the binary variables in the current LP relaxation */ 2088 LEVELGRAPH* graph, /**< LEVELGRAPH data structure */ 2089 unsigned int level, /**< number of current level */ 2090 SCIP_Bool* inlevelgraph, /**< flag array if node is already inserted in level graph */ 2091 unsigned int* curlevel, /**< array of nodes of the current level */ 2092 unsigned int ncurlevel, /**< number of nodes of the current level */ 2093 unsigned int* newlevel, /**< array of nodes of the next level */ 2094 unsigned int* nnewlevel, /**< number of nodes of the next level */ 2095 SCIP_Bool* success /**< FALSE, iff memory reallocation fails */ 2096 ) 2097 { 2098 unsigned int i; 2099 unsigned int nbinvars; 2100 unsigned int nAdj; 2101 2102 assert(scip != NULL); 2103 assert(vars != NULL); 2104 assert(vals != NULL); 2105 assert(graph != NULL); 2106 assert(graph->level != NULL); 2107 assert(graph->beginForward != NULL); 2108 assert(graph->targetForward != NULL); 2109 assert(graph->weightForward != NULL); 2110 assert(graph->beginBackward != NULL); 2111 assert(graph->targetBackward != NULL); 2112 assert(graph->weightBackward != NULL); 2113 assert(graph->beginAdj != NULL); 2114 assert(graph->levelAdj != NULL); 2115 assert(graph->sourceAdj != NULL); 2116 assert(graph->targetAdj != NULL); 2117 assert(graph->weightAdj != NULL); 2118 assert(inlevelgraph != NULL); 2119 assert(curlevel != NULL); 2120 assert(newlevel != NULL); 2121 assert(success != NULL); 2122 2123 *nnewlevel = 0; 2124 nAdj = 0; 2125 assert(graph->maxnodes % 2 == 0); 2126 nbinvars = (graph->maxnodes)/2; 2127 2128 /* for every node in current level add its implications and assign its neighbors to the next 2129 * level, if neighbor is not already existing in the level graph 2130 */ 2131 for( i = 0; i < ncurlevel; ++i ) 2132 { 2133 unsigned int negated; 2134 unsigned int u; 2135 2136 /* get node */ 2137 u = curlevel[i]; 2138 assert(u < graph->maxnodes); 2139 assert(graph->level[u] == level); 2140 assert(graph->beginForward[u] < 0); 2141 assert(graph->beginBackward[u] < 0); 2142 assert(graph->beginAdj[u] < 0); 2143 assert(inlevelgraph[u]); 2144 2145 /* get negated */ 2146 if( u < nbinvars ) 2147 negated = u + nbinvars; 2148 else 2149 negated = u - nbinvars; 2150 assert(negated < graph->maxnodes); 2151 assert(negated < nbinvars || u < nbinvars); 2152 assert(negated >= nbinvars || u >= nbinvars); 2153 2154 /* initialize adjacency lists for node u */ 2155 graph->beginForward[u] = (int) graph->lastF; 2156 graph->beginBackward[u] = (int) graph->lastB; 2157 graph->beginAdj[u] = (int) (graph->levelAdj[level+1] + nAdj); 2158 2159 /* if we want to add arcs between a variable and its negated */ 2160 if( sepadata->addselfarcs ) 2161 { 2162 /* add negated variable, if not existing in the levelgraph, 2163 * but if the level contains more nodes than allowed 2164 * (defined by percent per level plus offset), 2165 * we skip the rest of the nodes 2166 */ 2167 if( !inlevelgraph[negated] && (*nnewlevel) <= sepadata->maxlevelsize ) 2168 { 2169 ++(graph->nnodes); 2170 graph->level[negated] = level+1; 2171 inlevelgraph[negated] = TRUE; 2172 newlevel[*nnewlevel] = negated; 2173 ++(*nnewlevel); 2174 } 2175 assert( *nnewlevel > sepadata->maxlevelsize || inlevelgraph[negated] ); 2176 2177 /* add self-arc if negated variable is on a neighbored level */ 2178 if( inlevelgraph[negated] && ((graph->level[negated] == level - 1) 2179 || (graph->level[negated] == level) || (graph->level[negated] == level + 1)) ) 2180 { 2181 /* add arc from u to its negated variable */ 2182 SCIP_CALL( addArc(scip, graph, u, negated, level, 0, &nAdj, success) ); 2183 if( !(*success) ) 2184 return SCIP_OKAY; 2185 } 2186 } 2187 2188 /* insert level of sorted root neighbors (if requested) */ 2189 if( graph->nlevels == 0 && sepadata->sortrootneighbors ) 2190 { 2191 SCIP_CALL( insertSortedRootNeighbors(scip, graph, nbinvars, ncurlevel, u, vals, vars, 2192 sepadata, nnewlevel, inlevelgraph, level, newlevel, success) ); 2193 } 2194 else 2195 { 2196 SCIP_CALL( addNextLevelCliques(scip, sepadata, vars, vals, u, graph, level, inlevelgraph, 2197 newlevel, nnewlevel, &nAdj, success) ); 2198 } 2199 if( !(*success) ) 2200 return SCIP_OKAY; 2201 2202 /* every node has a backward arc */ 2203 assert(graph->lastB > (unsigned int) graph->beginBackward[u] || graph->nlevels == 0 ); 2204 2205 /* root has outgoing arcs otherwise we would have skipped it */ 2206 assert(graph->lastF > 0); 2207 2208 /* close adjacency lists */ 2209 graph->targetForward[graph->lastF] = -1; 2210 ++(graph->lastF); 2211 if( graph->lastF == graph->sizeForward ) 2212 { 2213 SCIP_CALL( checkArraySizesHeur(scip, graph, &(graph->sizeForward), &(graph->targetForward), 2214 &(graph->weightForward), NULL, NULL, success) ); 2215 2216 if( !(*success) ) 2217 return SCIP_OKAY; 2218 } 2219 graph->targetBackward[graph->lastB] = -1; 2220 ++(graph->lastB); 2221 if( graph->lastB == graph->sizeBackward ) 2222 { 2223 SCIP_CALL( checkArraySizesHeur(scip, graph, &(graph->sizeBackward), &(graph->targetBackward), 2224 &(graph->weightBackward), NULL, NULL, success) ); 2225 2226 if( !(*success) ) 2227 return SCIP_OKAY; 2228 } 2229 2230 /* terminate adjacency list with 0 for current level lifting */ 2231 graph->sourceAdj[graph->levelAdj[level+1]+nAdj] = 0; 2232 graph->targetAdj[graph->levelAdj[level+1]+nAdj] = 0; 2233 } 2234 graph->levelAdj[level+2] = graph->levelAdj[level+1]+nAdj; 2235 2236 return SCIP_OKAY; 2237 } 2238 2239 /** The heuristic method for finding odd cycles by Hoffman, Padberg uses a level graph 2240 * which is constructed as follows: 2241 * First we choose a node (i.e. a variable of the problem or its negated) as root 2242 * and assign it to level 0 (and no other node is assigned to level 0). 2243 * All neighbors of the root are assigned to level 1 and the arcs between are added. 2244 * 2245 * In general: 2246 * All neighbors of nodes in level i that are assigned to level i+1, if they do not already appear in levels <= i. 2247 * All arcs between nodes in level i and their neighbors are added. 2248 * 2249 * In the construction we only take nodes that are contained in the fractional graph, 2250 * i.e., their current LP values are not integral. 2251 * 2252 * Since SCIP stores implications between original and negated variables, 2253 * the level graph has at most twice the number of fractional binary variables of the problem. 2254 * 2255 * Since the implication graph of SCIP is (normally) incomplete, 2256 * it is possible to use arcs between an original variable and its negated 2257 * to obtain more cycles which are valid but not found due to missing links. 2258 */ 2259 static 2260 SCIP_RETCODE separateHeur( 2261 SCIP* scip, /**< SCIP data structure */ 2262 SCIP_SEPA* sepa, /**< separator */ 2263 SCIP_SEPADATA* sepadata, /**< separator data structure */ 2264 SCIP_SOL* sol, /**< given primal solution */ 2265 SCIP_RESULT* result /**< pointer to store the result of the separation call */ 2266 ) 2267 { 2268 /* memory for variable data */ 2269 SCIP_VAR** scipvars; /* variables of the current SCIP (unsorted) */ 2270 SCIP_VAR** vars; /* variables of the current SCIP (sorted if requested) */ 2271 SCIP_Real* vals; /* LP-values of the variables (and negated variables) */ 2272 unsigned int nbinvars; /* number of nodecandidates for implicationgraph */ 2273 unsigned int* incut; /* flag array for check if a variable is already covered by a cut */ 2274 2275 /* storage for levelgraph */ 2276 LEVELGRAPH graph; 2277 unsigned int* curlevel; 2278 unsigned int* newlevel; 2279 unsigned int ncurlevel; 2280 unsigned int nnewlevel; 2281 SCIP_Bool* inlevelgraph; 2282 2283 /* storage for path finding */ 2284 unsigned int* queue; 2285 SCIP_Bool* inQueue; 2286 int* parentTree; 2287 int* parentTreeBackward; 2288 unsigned int* distance; 2289 SCIP_Bool* blocked; 2290 2291 /* counter and limits */ 2292 unsigned int maxroots; /* maximum of level graph roots */ 2293 unsigned int rootcounter; /* counter of tried roots */ 2294 unsigned int ncutsroot; /* counter of cuts per root */ 2295 unsigned int ncutslevel; /* counter of cuts per level */ 2296 2297 unsigned int i; 2298 unsigned int j; 2299 unsigned int k; 2300 2301 int nscipbinvars; 2302 int nscipintvars; 2303 int nscipimplvars; 2304 int nintegral; 2305 int l; 2306 2307 assert(scip != NULL); 2308 assert(sepadata != NULL); 2309 assert(result != NULL); 2310 2311 SCIP_CALL( SCIPgetVarsData(scip, &scipvars, NULL, &nscipbinvars, &nscipintvars, &nscipimplvars, NULL) ); 2312 assert(nscipbinvars >= 0); 2313 assert(nscipintvars >= 0); 2314 assert(nscipimplvars >= 0); 2315 2316 nintegral = nscipbinvars + nscipintvars + nscipimplvars; 2317 assert(scipvars != NULL || ((nscipbinvars == 0) && (nscipintvars == 0) && (nscipimplvars == 0) && (nintegral == 0))); 2318 2319 /* collect binary variables, including implicit binary */ 2320 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nintegral) ); 2321 for (l = 0; l < nscipbinvars; ++l) 2322 vars[l] = scipvars[l]; /*lint !e613*/ 2323 2324 nbinvars = (unsigned int) nscipbinvars; 2325 for (l = nscipbinvars; l < nintegral; ++l) 2326 { 2327 assert( SCIPvarGetType(scipvars[l]) != SCIP_VARTYPE_CONTINUOUS ); /*lint !e613*/ 2328 if ( SCIPvarIsBinary(scipvars[l]) ) /*lint !e613*/ 2329 vars[nbinvars++] = scipvars[l]; /*lint !e613*/ 2330 } 2331 2332 if( nbinvars == 0 ) 2333 { 2334 SCIPfreeBufferArray(scip, &vars); 2335 return SCIP_OKAY; 2336 } 2337 2338 /* initialize flag array to avoid multiple cuts per variable, if requested by user-flag */ 2339 SCIP_CALL( SCIPallocBufferArray(scip, &vals, (int) (2 * nbinvars)) ); 2340 2341 /* prepare values */ 2342 assert( vars != NULL ); 2343 switch( sepadata->sortswitch ) 2344 { 2345 case UNSORTED : 2346 /* if no sorting is requested, we use the normal variable array */ 2347 break; 2348 2349 case MAXIMAL_LPVALUE : 2350 /* store lp-values */ 2351 for( i = 0; i < nbinvars; ++i ) 2352 vals[i] = SCIPgetSolVal(scip, sol, vars[i]); 2353 2354 /* sort by lp-value, maximal first */ 2355 SCIPsortDownRealPtr(vals, (void**)vars, (int) nbinvars); 2356 break; 2357 2358 case MINIMAL_LPVALUE : 2359 /* store lp-values */ 2360 for( i = 0; i < nbinvars; ++i ) 2361 vals[i] = SCIPgetSolVal(scip, sol, vars[i]); 2362 2363 /* sort by lp-value, minimal first */ 2364 SCIPsortRealPtr(vals, (void**)vars, (int) nbinvars); 2365 break; 2366 2367 case MAXIMAL_FRACTIONALITY : 2368 /* store lp-values and determine fractionality */ 2369 for( i = 0; i < nbinvars; ++i ) 2370 { 2371 vals[i] = SCIPgetSolVal(scip, sol, vars[i]); 2372 vals[i] = MIN(1.0 - vals[i], vals[i]); 2373 } 2374 2375 /* sort by fractionality, maximal first */ 2376 SCIPsortDownRealPtr(vals, (void**)vars, (int) nbinvars); 2377 break; 2378 2379 case MINIMAL_FRACTIONALITY : 2380 /* store lp-values and determine fractionality */ 2381 for( i = 0; i < nbinvars; ++i ) 2382 { 2383 vals[i] = SCIPgetSolVal(scip, sol, vars[i]); 2384 vals[i] = MIN(1.0 - vals[i], vals[i]); 2385 } 2386 2387 /* sort by fractionality, minimal first */ 2388 SCIPsortRealPtr(vals, (void**)vars, (int) nbinvars); 2389 break; 2390 2391 default : 2392 SCIPerrorMessage("invalid sortswitch value\n"); 2393 SCIPABORT(); 2394 return SCIP_INVALIDDATA; /*lint !e527*/ 2395 } 2396 assert(vars != NULL); 2397 2398 /* create mapping for getting the index of a variable via its probindex to the index in the sorted variable array */ 2399 SCIP_CALL( SCIPallocBufferArray(scip, &(sepadata->mapping), nintegral) ); 2400 2401 /* initialize LP value and cut flag for all variables */ 2402 for( i = 0; i < nbinvars; ++i ) 2403 { 2404 assert( 0 <= SCIPvarGetProbindex(vars[i]) && SCIPvarGetProbindex(vars[i]) < nintegral); /* since binary, integer, and implicit variables are first */ 2405 sepadata->mapping[SCIPvarGetProbindex(vars[i])] = i; 2406 vals[i] = SCIPgetSolVal(scip, sol, vars[i]); /* need to get new values, since they might be corrupted */ 2407 } 2408 2409 for( i = nbinvars; i < 2*nbinvars; ++i ) 2410 vals[i] = 1.0 - vals[i - nbinvars]; 2411 2412 /* determine size of level graph */ 2413 graph.maxnodes = 2 * nbinvars; 2414 2415 /* the implication graph is redundant and therefore more implications and clique arcs may occur than should be possible 2416 * @todo later: filtering of edges which were already added 2417 */ 2418 /* graph.maxarcs = nbinvars*(2*nbinvars-1); */ /* = 2*nbinvars*(2*nbinvars-1)/2 */ 2419 graph.maxarcs = UINT_MAX; 2420 2421 /* set sizes for graph memory storage */ 2422 graph.sizeForward = 100 * graph.maxnodes; 2423 graph.sizeBackward = 100 * graph.maxnodes; 2424 graph.sizeAdj = 100 * graph.maxnodes; 2425 2426 /* allocate memory for level graph structure */ 2427 SCIP_CALL( SCIPallocBufferArray(scip, &graph.level, (int) graph.maxnodes) ); 2428 SCIP_CALL( SCIPallocBufferArray(scip, &graph.beginForward, (int) graph.maxnodes) ); 2429 SCIP_CALL( SCIPallocBufferArray(scip, &graph.beginBackward, (int) graph.maxnodes) ); 2430 SCIP_CALL( SCIPallocBufferArray(scip, &graph.targetForward, (int) MIN(graph.sizeForward, graph.maxarcs)) ); 2431 SCIP_CALL( SCIPallocBufferArray(scip, &graph.targetBackward, (int) MIN(graph.sizeBackward, graph.maxarcs)) ); 2432 SCIP_CALL( SCIPallocBufferArray(scip, &graph.weightForward, (int) MIN(graph.sizeForward, graph.maxarcs)) ); 2433 SCIP_CALL( SCIPallocBufferArray(scip, &graph.weightBackward, (int) MIN(graph.sizeBackward, graph.maxarcs)) ); 2434 2435 SCIP_CALL( SCIPallocBufferArray(scip, &curlevel, (int) graph.maxnodes) ); 2436 SCIP_CALL( SCIPallocBufferArray(scip, &newlevel, (int) graph.maxnodes) ); 2437 SCIP_CALL( SCIPallocBufferArray(scip, &graph.beginAdj, (int) graph.maxnodes) ); 2438 SCIP_CALL( SCIPallocBufferArray(scip, &graph.sourceAdj, (int) MIN(graph.sizeAdj, graph.maxarcs)) ); 2439 SCIP_CALL( SCIPallocBufferArray(scip, &graph.targetAdj, (int) MIN(graph.sizeAdj, graph.maxarcs)) ); 2440 SCIP_CALL( SCIPallocBufferArray(scip, &graph.weightAdj, (int) MIN(graph.sizeAdj, graph.maxarcs)) ); 2441 SCIP_CALL( SCIPallocBufferArray(scip, &graph.levelAdj, (int) graph.maxnodes) ); 2442 SCIP_CALL( SCIPallocBufferArray(scip, &inlevelgraph, (int) graph.maxnodes) ); 2443 2444 SCIP_CALL( SCIPallocBufferArray(scip, &queue, (int) graph.maxnodes) ); 2445 SCIP_CALL( SCIPallocBufferArray(scip, &inQueue, (int) graph.maxnodes) ); 2446 SCIP_CALL( SCIPallocBufferArray(scip, &parentTree, (int) graph.maxnodes) ); 2447 SCIP_CALL( SCIPallocBufferArray(scip, &parentTreeBackward, (int) graph.maxnodes) ); 2448 SCIP_CALL( SCIPallocBufferArray(scip, &distance, (int) graph.maxnodes) ); 2449 SCIP_CALL( SCIPallocBufferArray(scip, &blocked, (int) graph.maxnodes) ); 2450 2451 SCIP_CALL( SCIPallocBufferArray(scip, &incut, (int) (2 * nbinvars)) ); 2452 2453 /* initialize cut flag for all variables */ 2454 BMSclearMemoryArray(incut, 2*nbinvars); 2455 2456 /* determine the number of level graph roots */ 2457 maxroots = (unsigned int) SCIPceil(scip, sepadata->offsettestvars + (0.02 * nbinvars * sepadata->percenttestvars)); 2458 sepadata->maxlevelsize = (unsigned int) SCIPceil(scip, sepadata->offsetnodeslevel + 0.01 * sepadata->maxpernodeslevel * graph.maxnodes); 2459 rootcounter = 0; 2460 2461 /* check each node as root */ 2462 for( i = (unsigned int) sepadata->lastroot; i < graph.maxnodes && rootcounter < maxroots 2463 && sepadata->ncuts - sepadata->oldncuts < (unsigned int) sepadata->maxsepacutsround 2464 && !SCIPisStopped(scip) ; ++i ) 2465 { 2466 /* skip node if it is already covered by a cut and if we do not want to search cycles starting 2467 * with a node already covered by a cut */ 2468 if( incut[i] && ! sepadata->multiplecuts ) 2469 continue; 2470 2471 /* skip variable if its LP-value is not fractional */ 2472 if( SCIPisFeasIntegral(scip, vals[i]) ) 2473 continue; 2474 2475 /* consider original and negated variable pair and skip variable if there is only one edge leaving the pair */ 2476 if( SCIPvarGetNCliques(vars[i % nbinvars], TRUE) + SCIPvarGetNCliques(vars[i % nbinvars], FALSE) == 0 ) 2477 continue; 2478 2479 /* skip variable having too less implics and cliques itself */ 2480 if( i < nbinvars ) 2481 { 2482 if( SCIPvarGetNCliques(vars[i % nbinvars], TRUE ) == 0 ) 2483 continue; 2484 if( !(sepadata->addselfarcs) && SCIPvarGetNCliques(vars[i % nbinvars], TRUE ) == 0 ) 2485 continue; 2486 } 2487 else 2488 { 2489 if( SCIPvarGetNCliques(vars[i % nbinvars], FALSE) == 0 ) 2490 continue; 2491 2492 if( !(sepadata->addselfarcs) && SCIPvarGetNCliques(vars[i % nbinvars], FALSE) == 0 ) 2493 continue; 2494 } 2495 2496 /* node is actually considered as root node for the level graph */ 2497 ++rootcounter; 2498 ncutsroot = 0; 2499 2500 /* initialize graph */ 2501 for( j = 0; j < graph.maxnodes; ++j) 2502 { 2503 graph.beginForward[j] = -1; 2504 graph.beginBackward[j] = -1; 2505 graph.beginAdj[j] = -1; 2506 inlevelgraph[j] = FALSE; 2507 blocked[j] = FALSE; 2508 } 2509 graph.lastF = 0; 2510 graph.lastB = 0; 2511 graph.nlevels = 0; 2512 graph.narcs = 0; 2513 2514 /* insert root (first level contains root only) */ 2515 inlevelgraph[i] = TRUE; 2516 graph.level[i] = 0; 2517 graph.levelAdj[0] = 0; 2518 graph.nnodes = 1; 2519 curlevel[0] = i; 2520 ncurlevel = 1; 2521 2522 /* there are no arcs inside the root level */ 2523 graph.levelAdj[graph.nlevels+1] = 0; 2524 2525 /* create new levels until there are not more nodes for a new level */ 2526 do 2527 { 2528 SCIP_Bool success; 2529 success = TRUE; 2530 2531 /* all neighbors of nodes in level i that are assigned to level i+1, 2532 if they do not already appear in levels <= i. */ 2533 SCIP_CALL( createNextLevel(scip, sepadata, vars, vals, &graph, graph.nlevels, inlevelgraph, 2534 curlevel, ncurlevel, newlevel, &nnewlevel, &success) ); 2535 2536 if( !success ) 2537 goto TERMINATE; 2538 2539 /* search for odd holes */ 2540 if( graph.nlevels > 0 && (sepadata->includetriangles || graph.nlevels > 1) ) 2541 { 2542 unsigned int maxcutslevel; 2543 2544 ncutslevel = 0; 2545 2546 /* calculate maximal cuts in this level due to cut limitations (per level, per root, per separation round) */ 2547 maxcutslevel = (unsigned int) sepadata->maxcutslevel; 2548 maxcutslevel = (unsigned int) MIN((int) maxcutslevel, (int) ncutsroot - sepadata->maxcutsroot); 2549 maxcutslevel = (unsigned int) MIN((int) maxcutslevel, sepadata->maxsepacutsround + (int) sepadata->oldncuts - (int) sepadata->ncuts); 2550 2551 /* for each cross edge in this level find both shortest paths to root (as long as no limits are reached) */ 2552 for( j = graph.levelAdj[graph.nlevels+1]; j < graph.levelAdj[graph.nlevels+2] 2553 && ncutslevel < maxcutslevel && !SCIPisStopped(scip); ++j ) 2554 { 2555 unsigned int ncyclevars; 2556 unsigned int u; 2557 2558 /* storage for cut generation */ 2559 unsigned int* pred; /* predecessor list */ 2560 SCIP_Bool* incycle; /* flag array for check of double variables in found cycle */ 2561 2562 assert(graph.sourceAdj[j] < graph.targetAdj[j]); 2563 2564 /* find shortest path from source to root and update weight of cycle */ 2565 SCIP_CALL( findShortestPathToRoot(scip, sepadata->scale, &graph, graph.sourceAdj[j], distance, queue, inQueue, parentTree) ); 2566 2567 #ifndef NDEBUG 2568 /* check that this path ends in the root node */ 2569 u = i; 2570 k = 1; 2571 while( u != graph.sourceAdj[j] ) 2572 { 2573 assert(parentTree[u] != -1 && k <= graph.maxnodes); 2574 u = (unsigned int) parentTree[u]; 2575 ++k; 2576 } 2577 #endif 2578 2579 /* block all nodes that are adjacent to nodes of the first path */ 2580 for( k = 0; k < graph.nnodes; ++k ) 2581 blocked[k] = FALSE; 2582 SCIP_CALL( blockRootPath(scip, &graph, graph.sourceAdj[j], inlevelgraph, blocked, parentTree, i) ); 2583 2584 /* if the target is block, no violated odd hole can be found */ 2585 if( blocked[graph.targetAdj[j]] ) 2586 continue; 2587 2588 /* find shortest path from root to target node avoiding blocked nodes */ 2589 SCIP_CALL( findUnblockedShortestPathToRoot(scip, sepadata->scale, &graph, 2590 graph.targetAdj[j], distance, queue, inQueue, parentTreeBackward, i, blocked) ); 2591 2592 /* no odd cycle cut found */ 2593 if( parentTreeBackward[graph.targetAdj[j]] < 0 ) 2594 continue; 2595 2596 /* allocate and initialize predecessor list and flag array representing odd cycle */ 2597 SCIP_CALL( SCIPallocBufferArray(scip, &pred, (int) (2 * nbinvars)) ); 2598 SCIP_CALL( SCIPallocBufferArray(scip, &incycle, (int) (2 * nbinvars)) ); 2599 for( k = 0; k < 2 * nbinvars; ++k ) 2600 { 2601 pred[k] = DIJKSTRA_UNUSED; 2602 incycle[k] = FALSE; 2603 } 2604 ncyclevars = 0; 2605 success = TRUE; 2606 2607 /* check cycle for x-neg(x)-sub-cycles and clean them 2608 * (note that a variable cannot appear twice in a cycle since it is only once in the graph) 2609 * convert parentTreeBackward and parentTree to pred&incycle structure for generateOddCycleCut 2610 */ 2611 u = graph.targetAdj[j]; 2612 2613 /* add path to root to cycle */ 2614 while( success && u != i ) 2615 { 2616 /* insert u in predecessor list */ 2617 pred[u] = (unsigned int) parentTreeBackward[u]; 2618 2619 /* remove pairs of original and negated variable from cycle */ 2620 SCIP_CALL( cleanCycle(scip, pred, incycle, incut, u, graph.targetAdj[j], nbinvars, &ncyclevars, 2621 sepadata->repaircycles, sepadata->allowmultiplecuts, &success) ); 2622 2623 assert(parentTreeBackward[u] >= 0 || u == i); 2624 2625 /* select next node on path */ 2626 u = (unsigned int) parentTreeBackward[u]; 2627 } 2628 2629 /* add path from root to cycle */ 2630 while( success && u != graph.sourceAdj[j] ) 2631 { 2632 /* insert u in predecessor list */ 2633 pred[u] = (unsigned int) parentTree[u]; 2634 2635 /* remove pairs of original and negated variable from cycle */ 2636 SCIP_CALL( cleanCycle(scip, pred, incycle, incut, u, graph.targetAdj[j], nbinvars, &ncyclevars, 2637 sepadata->repaircycles, sepadata->allowmultiplecuts, &success) ); 2638 2639 /* select next node on path */ 2640 u = (unsigned int) parentTree[u]; 2641 } 2642 assert(!success || u == graph.sourceAdj[j]); 2643 2644 /* close the cycle */ 2645 if( success ) 2646 { 2647 pred[u] = graph.targetAdj[j]; 2648 2649 /* remove pairs of original and negated variable from cycle */ 2650 SCIP_CALL( cleanCycle(scip, pred, incycle, incut, u, graph.targetAdj[j], nbinvars, &ncyclevars, 2651 sepadata->repaircycles, sepadata->allowmultiplecuts, &success) ); 2652 } 2653 2654 /* generate cut (if cycle is valid) */ 2655 if(success) 2656 { 2657 GRAPHDATA graphdata; 2658 unsigned int oldncuts; 2659 2660 graphdata.usegls = FALSE; 2661 graphdata.levelgraph = &graph; 2662 graphdata.dijkstragraph = NULL; 2663 2664 oldncuts = sepadata->ncuts; 2665 2666 SCIP_CALL( generateOddCycleCut(scip, sepa, sol, vars, nbinvars, graph.targetAdj[j], pred, ncyclevars, 2667 incut, vals, sepadata, &graphdata, result) ); 2668 2669 if(oldncuts < sepadata->ncuts) 2670 { 2671 ++ncutsroot; 2672 ++ncutslevel; 2673 } 2674 } 2675 2676 /* free temporary memory */ 2677 SCIPfreeBufferArray(scip, &incycle); 2678 SCIPfreeBufferArray(scip, &pred); 2679 2680 if ( *result == SCIP_CUTOFF || *result == SCIP_REDUCEDDOM ) 2681 break; 2682 } 2683 } 2684 2685 if ( *result == SCIP_CUTOFF || *result == SCIP_REDUCEDDOM ) 2686 break; 2687 2688 /* copy new level to current one */ 2689 ++(graph.nlevels); 2690 for( j = 0; j < nnewlevel; ++j ) 2691 curlevel[j] = newlevel[j]; 2692 ncurlevel = nnewlevel; 2693 } 2694 /* stop level creation loop if new level is empty or any limit is reached */ 2695 while( nnewlevel > 0 && !SCIPisStopped(scip) 2696 && graph.nlevels < (unsigned int) sepadata->maxnlevels 2697 && ncutsroot < (unsigned int) sepadata->maxcutsroot 2698 && sepadata->ncuts - sepadata->oldncuts < (unsigned int) sepadata->maxsepacutsround); 2699 } 2700 2701 /* store the last tried root (when running without sorting the variable array, we don't want 2702 * to always check the same variables and therefore start next time where we stopped last time) 2703 */ 2704 if( sepadata->sortswitch == UNSORTED ) 2705 { 2706 if( i == graph.maxnodes ) 2707 sepadata->lastroot = 0; 2708 else 2709 sepadata->lastroot = (int) i; 2710 } 2711 2712 TERMINATE: 2713 /* free memory */ 2714 SCIPfreeBufferArray(scip, &incut); 2715 2716 SCIPfreeBufferArray(scip, &blocked); 2717 SCIPfreeBufferArray(scip, &distance); 2718 SCIPfreeBufferArray(scip, &parentTreeBackward); 2719 SCIPfreeBufferArray(scip, &parentTree); 2720 SCIPfreeBufferArray(scip, &inQueue); 2721 SCIPfreeBufferArray(scip, &queue); 2722 2723 SCIPfreeBufferArray(scip, &inlevelgraph); 2724 SCIPfreeBufferArray(scip, &graph.levelAdj); 2725 SCIPfreeBufferArray(scip, &graph.weightAdj); 2726 SCIPfreeBufferArray(scip, &graph.targetAdj); 2727 SCIPfreeBufferArray(scip, &graph.sourceAdj); 2728 SCIPfreeBufferArray(scip, &graph.beginAdj); 2729 SCIPfreeBufferArray(scip, &newlevel); 2730 SCIPfreeBufferArray(scip, &curlevel); 2731 2732 SCIPfreeBufferArray(scip, &graph.weightBackward); 2733 SCIPfreeBufferArray(scip, &graph.weightForward); 2734 SCIPfreeBufferArray(scip, &graph.targetBackward); 2735 SCIPfreeBufferArray(scip, &graph.targetForward); 2736 SCIPfreeBufferArray(scip, &graph.beginBackward); 2737 SCIPfreeBufferArray(scip, &graph.beginForward); 2738 SCIPfreeBufferArray(scip, &graph.level); 2739 2740 SCIPfreeBufferArray(scip, &(sepadata->mapping)); 2741 SCIPfreeBufferArray(scip, &vals); 2742 SCIPfreeBufferArray(scip, &vars); 2743 2744 return SCIP_OKAY; 2745 } 2746 2747 2748 /* methods for separateGLS() */ 2749 2750 /** memory reallocation method (the graph is normally very dense, so we dynamically allocate only the memory we need) */ 2751 static 2752 SCIP_RETCODE checkArraySizesGLS( 2753 SCIP* scip, /**< SCIP data structure */ 2754 unsigned int maxarcs, /**< maximal size of graph->head and graph->weight */ 2755 unsigned int* arraysize, /**< current size of graph->head and graph->weight */ 2756 DIJKSTRA_GRAPH* graph, /**< Dijkstra Graph data structure */ 2757 SCIP_Bool* success /**< FALSE, iff memory reallocation fails */ 2758 ) 2759 { 2760 SCIP_Real memorylimit; 2761 unsigned int additional; 2762 unsigned int j; 2763 unsigned int oldarraysize; 2764 2765 assert(scip != NULL); 2766 assert(arraysize != NULL); 2767 assert(graph != NULL); 2768 assert(graph->head != NULL); 2769 assert(graph->weight != NULL); 2770 assert(success != NULL); 2771 2772 SCIPdebugMsg(scip, "reallocating graph->head and graph->weight...\n"); 2773 2774 additional = (MIN(maxarcs, 2 * (*arraysize)) - (*arraysize)) * ((int) sizeof(*(graph->head))); 2775 additional += (MIN(maxarcs, 2 * (*arraysize)) - (*arraysize)) * ((int) sizeof(*(graph->weight))); 2776 2777 SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) ); 2778 if( !SCIPisInfinity(scip, memorylimit) ) 2779 { 2780 memorylimit -= SCIPgetMemUsed(scip)/1048576.0; 2781 memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0; 2782 } 2783 2784 /* if memorylimit would be exceeded or any other limit is reached free all data and exit */ 2785 if( memorylimit <= additional/1048576.0 || SCIPisStopped(scip) ) 2786 { 2787 *success = FALSE; 2788 SCIPdebugMsg(scip, "...memory limit exceeded\n"); 2789 return SCIP_OKAY; 2790 } 2791 2792 oldarraysize = *arraysize; 2793 *arraysize = 2*(*arraysize); 2794 2795 SCIP_CALL( SCIPreallocBufferArray(scip, &(graph->head), (int) MIN(maxarcs, (*arraysize))) ); 2796 SCIP_CALL( SCIPreallocBufferArray(scip, &(graph->weight), (int) MIN(maxarcs, (*arraysize))) ); 2797 2798 /* if memorylimit exceeded, leave the separator */ 2799 SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) ); 2800 2801 if( !SCIPisInfinity(scip, memorylimit) ) 2802 { 2803 memorylimit -= SCIPgetMemUsed(scip)/1048576.0; 2804 memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0; 2805 } 2806 2807 if( memorylimit <= 2.0*SCIPgetMemExternEstim(scip)/1048576.0 ) 2808 { 2809 SCIPdebugMsg(scip, "...memory limit exceeded - freeing all arrays\n"); 2810 *success = FALSE; 2811 return SCIP_OKAY; 2812 } 2813 2814 /* initialize new segments of graph as empty graph */ 2815 for( j = oldarraysize; j < MIN(maxarcs,(*arraysize)); ++j ) 2816 { 2817 (graph->head)[j] = DIJKSTRA_UNUSED; 2818 (graph->weight)[j] = DIJKSTRA_UNUSED; 2819 } 2820 2821 SCIPdebugMsg(scip, "...with success\n"); 2822 2823 return SCIP_OKAY; 2824 } 2825 2826 /** add implications from cliques of the given node */ 2827 static 2828 SCIP_RETCODE addGLSCliques( 2829 SCIP* scip, /**< SCIP data structure */ 2830 SCIP_SEPADATA* sepadata, /**< separator data structure */ 2831 SCIP_VAR** vars, /**< problem variables */ 2832 unsigned int varsidx, /**< index of current variable inside the problem variables */ 2833 unsigned int dijkindex, /**< index of current variable inside the Dijkstra Graph */ 2834 SCIP_Real* vals, /**< value of the variables in the given solution */ 2835 unsigned int nbinvars, /**< number of binary problem variables */ 2836 unsigned int ncliques, /**< number of cliques of the current node */ 2837 DIJKSTRA_GRAPH* graph, /**< Dijkstra Graph data structure */ 2838 unsigned int* narcs, /**< current number of arcs inside the Dijkstra Graph */ 2839 unsigned int maxarcs, /**< maximal number of arcs inside the Dijkstra Graph */ 2840 SCIP_Bool original, /**< TRUE, iff variable is a problem variable */ 2841 SCIP_Bool* emptygraph, /**< TRUE, iff there is no arc in the implication graph of the binary variables of SCIP */ 2842 unsigned int* arraysize, /**< current size of graph->head and graph->weight */ 2843 SCIP_Bool* success /**< FALSE, iff memory reallocation fails */ 2844 ) 2845 { 2846 SCIP_VAR* neighbor; /* current neighbor of the current variable */ 2847 unsigned int neighindex; 2848 SCIP_CLIQUE** cliques; /* cliques of the current variable (with x==0/1) */ 2849 unsigned int ncliquevars; /* number of variables of a clique */ 2850 SCIP_VAR** cliquevars; /* variables of a clique */ 2851 SCIP_Bool* cliquevals; /* is the cliquevariable fixed to TRUE or to FALSE */ 2852 unsigned int k; 2853 unsigned int m; 2854 2855 assert(scip != NULL); 2856 assert(sepadata != NULL); 2857 assert(vars != NULL); 2858 assert(graph != NULL); 2859 assert(graph->head != NULL); 2860 assert(graph->weight != NULL); 2861 assert(narcs != NULL); 2862 assert(emptygraph != NULL); 2863 assert(arraysize != NULL); 2864 assert(success != NULL); 2865 2866 /* if current variable has cliques of current clique-type */ 2867 cliques = SCIPvarGetCliques(vars[varsidx], original); 2868 assert(cliques != NULL || ncliques == 0); 2869 2870 for( k = 0; k < ncliques; ++k ) 2871 { 2872 assert( cliques != NULL ); /* for lint */ 2873 2874 /* get clique data */ 2875 cliquevars = SCIPcliqueGetVars(cliques[k]); 2876 ncliquevars = (unsigned int) SCIPcliqueGetNVars(cliques[k]); 2877 cliquevals = SCIPcliqueGetValues(cliques[k]); 2878 2879 assert(cliquevars != NULL || ncliquevars == 0); 2880 assert(cliquevals != NULL || ncliquevars == 0); 2881 2882 /* add arcs for all fractional variables in clique */ 2883 for( m = 0; m < ncliquevars; ++m ) 2884 { 2885 int tmp; 2886 2887 assert( cliquevars != NULL && cliquevals != NULL ); /* for lint */ 2888 neighbor = cliquevars[m]; 2889 2890 neighindex = sepadata->mapping[SCIPvarGetProbindex(neighbor)]; 2891 assert(neighindex < nbinvars); 2892 2893 /* ignore current variable */ 2894 if( neighindex == varsidx ) 2895 continue; 2896 2897 /* we use only variables with fractional LP-solution values */ 2898 if( SCIPisFeasIntegral(scip, vals[neighindex]) ) 2899 continue; 2900 2901 /* forward direction (the backward is created at the occurrence of the current variable in the cliquevars of the neighbor) */ 2902 /* x==1 */ 2903 if( original ) 2904 { 2905 /* implication to y=0 (I->III) */ 2906 if( cliquevals[m] ) 2907 { 2908 tmp = (int) SCIPfeasCeil(scip, sepadata->scale * (1 - vals[varsidx] - vals[neighindex] )); 2909 graph->weight[*narcs] = (unsigned int) MAX(0, tmp); 2910 graph->head[*narcs] = neighindex + 2 * nbinvars; 2911 } 2912 /* implication to y=1 (I->IV) (cliquevals[m] == FALSE) */ 2913 else 2914 { 2915 tmp = (int) SCIPfeasCeil(scip, sepadata->scale * (1 - vals[varsidx] - (1 - vals[neighindex]) )); 2916 graph->weight[*narcs] = (unsigned int) MAX(0, tmp); 2917 graph->head[*narcs] = neighindex + 3 * nbinvars; 2918 } 2919 } 2920 /* x==0 */ 2921 else 2922 { 2923 /* implication to y=0 (II->III) */ 2924 if( cliquevals[m] ) 2925 { 2926 tmp = (int) SCIPfeasCeil(scip, sepadata->scale * (1 - (1 - vals[varsidx]) - vals[neighindex] )); 2927 graph->weight[*narcs] = (unsigned int) MAX(0, tmp); 2928 graph->head[*narcs] = neighindex + 2 * nbinvars; 2929 } 2930 /* implication to y=1 (II->IV) (cliquevals[m] == FALSE) */ 2931 else 2932 { 2933 tmp = (int) SCIPfeasCeil(scip, sepadata->scale * (1 - (1 - vals[varsidx]) - (1-vals[neighindex]) )) ; 2934 graph->weight[*narcs] = (unsigned int) MAX(0, tmp); 2935 graph->head[*narcs] = neighindex + 3 * nbinvars; 2936 } 2937 } 2938 2939 /* update minimum and maximum weight values */ 2940 if( graph->weight[*narcs] < graph->minweight ) 2941 graph->minweight = graph->weight[*narcs]; 2942 2943 if( graph->weight[*narcs] > graph->maxweight ) 2944 graph->maxweight = graph->weight[*narcs]; 2945 2946 ++(*narcs); 2947 if( *arraysize == *narcs ) 2948 { 2949 SCIP_CALL( checkArraySizesGLS(scip, maxarcs, arraysize, graph, success) ); 2950 2951 if( !(*success) ) 2952 return SCIP_OKAY; 2953 } 2954 assert((*narcs) < maxarcs); 2955 ++(graph->outcnt[dijkindex]); 2956 2957 *emptygraph = FALSE; 2958 } 2959 } 2960 2961 return SCIP_OKAY; 2962 } 2963 2964 /** The classical method for finding odd cycles by Groetschel, Lovasz, Schrijver uses a bipartite graph 2965 * which contains in each partition a node for every node in the original graph. 2966 * All arcs uv of the original graph are copied to arcs from u of the first partition to v' of the second partition 2967 * and from u' of the second partition to v of the first partition. 2968 * A Dijkstra algorithm is used to find a path from a node x to its copy x', if existing. 2969 * The nodes in the original graph corresponding to the nodes on the path form an odd cycle. 2970 * 2971 * Since SCIP stores implications between original and negated variables, 2972 * our original graph has at most twice the number of binary variables of the problem. 2973 * By creating the bipartite graph we gain 4 segments of the graph: 2974 * 2975 * I - nodes of the original variables in the first bipartition \n 2976 * II - nodes of the negated variables in the first bipartition \n 2977 * III - nodes of the original variables in the second bipartition \n 2978 * IV - nodes of the negated variables in the second bipartition 2979 * 2980 * The length of every segment if the number of binary variables in the original problem. 2981 * 2982 * Since the implication graph of SCIP is (normally) incomplete, 2983 * it is possible to use arcs between an original variable and its negated 2984 * to obtain more cycles which are valid but not found due to missing links. 2985 */ 2986 static 2987 SCIP_RETCODE separateGLS( 2988 SCIP* scip, /**< SCIP data structure */ 2989 SCIP_SEPA* sepa, /**< separator */ 2990 SCIP_SEPADATA* sepadata, /**< separator data structure */ 2991 SCIP_SOL* sol, /**< given primal solution */ 2992 SCIP_RESULT* result /**< pointer to store the result of the separation call */ 2993 ) 2994 { 2995 SCIP_Bool emptygraph; /* flag if graph contains an arc */ 2996 2997 SCIP_Real* vals; /* values of the variables in the given solution */ 2998 unsigned int* incut; 2999 3000 unsigned int i; 3001 unsigned int j; 3002 3003 SCIP_VAR** scipvars; /* variables of the current SCIP (unsorted) */ 3004 SCIP_VAR** vars; /* variables of the current SCIP (sorted if requested) */ 3005 unsigned int nbinvars; /* number of binary problem variables */ 3006 SCIP_Bool original; /* flag if the current variable is original or negated */ 3007 3008 unsigned int ncliques; /* number of cliques of the current variable */ 3009 3010 DIJKSTRA_GRAPH graph; /* Dijkstra graph data structure */ 3011 unsigned int arraysize; /* current size of graph->head and graph->weight */ 3012 unsigned int narcs; /* number of arcs in the Dijkstra graph */ 3013 unsigned int maxarcs; /* maximum number of arcs in the Dijkstra graph */ 3014 unsigned int maxstarts; /* maximum number of start nodes */ 3015 unsigned int startcounter; /* counter of tried start nodes */ 3016 unsigned long long cutoff; /* cutoff value for Dijkstra algorithm */ 3017 3018 unsigned int startnode; /* start node for Dijkstra algorithm */ 3019 unsigned int endnode; /* target node for Dijkstra algorithm */ 3020 unsigned long long* dist; /* distance matrix for Dijkstra algorithm */ 3021 unsigned int* pred; /* predecessor list for found cycle */ 3022 unsigned int* entry; /* storage for Dijkstra algorithm */ 3023 unsigned int* order; /* storage for Dijkstra algorithm */ 3024 unsigned int dijkindex; 3025 SCIP_Bool success; /* flag for check for several errors */ 3026 3027 SCIP_Bool* incycle; /* flag array if variable is contained in the found cycle */ 3028 unsigned int* pred2; /* temporary predecessor list for backprojection of found cycle */ 3029 3030 int nscipbinvars; 3031 int nscipintvars; 3032 int nscipimplvars; 3033 int nintegral; 3034 int k; 3035 3036 assert(scip != NULL); 3037 assert(sepadata != NULL); 3038 assert(result != NULL); 3039 3040 success = TRUE; 3041 emptygraph = TRUE; 3042 3043 SCIP_CALL( SCIPgetVarsData(scip, &scipvars, NULL, &nscipbinvars, &nscipintvars, &nscipimplvars, NULL) ); 3044 assert(nscipbinvars >= 0); 3045 assert(nscipintvars >= 0); 3046 assert(nscipimplvars >= 0); 3047 3048 nintegral = nscipbinvars + nscipintvars + nscipimplvars; 3049 assert(scipvars != NULL || ((nscipbinvars == 0) && (nscipintvars == 0) && (nscipimplvars == 0) && (nintegral == 0))); 3050 3051 /* collect binary variables, including implicit binary */ 3052 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nintegral) ); 3053 for (k = 0; k < nscipbinvars; ++k) 3054 vars[k] = scipvars[k]; /*lint !e613*/ 3055 3056 nbinvars = (unsigned int) nscipbinvars; 3057 for (k = nscipbinvars; k < nintegral; ++k) 3058 { 3059 assert( SCIPvarGetType(scipvars[k]) != SCIP_VARTYPE_CONTINUOUS ); /*lint !e613*/ 3060 if ( SCIPvarIsBinary(scipvars[k]) ) /*lint !e613*/ 3061 vars[nbinvars++] = scipvars[k]; /*lint !e613*/ 3062 } 3063 3064 if( nbinvars == 0 ) 3065 { 3066 SCIPfreeBufferArray(scip, &vars); 3067 return SCIP_OKAY; 3068 } 3069 3070 /* initialize flag array to avoid multiple cuts per variable, if requested by user-flag */ 3071 SCIP_CALL( SCIPallocBufferArray(scip, &vals, (int) (2 * nbinvars)) ); 3072 3073 /* prepare values */ 3074 assert( vars != NULL ); 3075 switch( sepadata->sortswitch ) 3076 { 3077 case UNSORTED : 3078 /* if no sorting is requested, we use the normal variable array */ 3079 break; 3080 3081 case MAXIMAL_LPVALUE : 3082 /* store lp-values */ 3083 for( i = 0; i < nbinvars; ++i ) 3084 vals[i] = SCIPgetSolVal(scip, sol, vars[i]); 3085 3086 /* sort by lp-value, maximal first */ 3087 SCIPsortDownRealPtr(vals, (void**)vars, (int) nbinvars); 3088 break; 3089 3090 case MINIMAL_LPVALUE : 3091 /* store lp-values */ 3092 for( i = 0; i < nbinvars; ++i ) 3093 vals[i] = SCIPgetSolVal(scip, sol, vars[i]); 3094 3095 /* sort by lp-value, minimal first */ 3096 SCIPsortRealPtr(vals, (void**)vars, (int) nbinvars); 3097 break; 3098 3099 case MAXIMAL_FRACTIONALITY : 3100 /* store lp-values and determine fractionality */ 3101 for( i = 0; i < nbinvars; ++i ) 3102 { 3103 vals[i] = SCIPgetSolVal(scip, sol, vars[i]); 3104 vals[i] = MIN(1.0 - vals[i], vals[i]); 3105 } 3106 3107 /* sort by fractionality, maximal first */ 3108 SCIPsortDownRealPtr(vals, (void**)vars, (int) nbinvars); 3109 break; 3110 3111 case MINIMAL_FRACTIONALITY : 3112 /* store lp-values and determine fractionality */ 3113 for( i = 0; i < nbinvars; ++i ) 3114 { 3115 vals[i] = SCIPgetSolVal(scip, sol, vars[i]); 3116 vals[i] = MIN(1.0 - vals[i], vals[i]); 3117 } 3118 3119 /* sort by fractionality, minimal first */ 3120 SCIPsortRealPtr(vals, (void**)vars, (int) nbinvars); 3121 break; 3122 3123 default : 3124 SCIPerrorMessage("invalid sortswitch value\n"); 3125 SCIPABORT(); 3126 return SCIP_INVALIDDATA; /*lint !e527*/ 3127 } 3128 assert(vars != NULL); 3129 3130 /* create mapping for getting the index of a variable via its probindex to the index in the sorted variable array */ 3131 SCIP_CALL( SCIPallocBufferArray(scip, &(sepadata->mapping), nintegral) ); 3132 SCIP_CALL( SCIPallocBufferArray(scip, &incut, (int) (4 * nbinvars)) ); 3133 BMSclearMemoryArray(incut, 4 * nbinvars); 3134 3135 /* initialize LP value and cut flag for all variables */ 3136 for( i = 0; i < nbinvars; ++i ) 3137 { 3138 assert( 0 <= SCIPvarGetProbindex(vars[i]) && SCIPvarGetProbindex(vars[i]) < nintegral); /* since binary, integer, and implicit variables are first */ 3139 sepadata->mapping[SCIPvarGetProbindex(vars[i])] = i; 3140 vals[i] = SCIPgetSolVal(scip, sol, vars[i]); /* need to get new values, since they might be corrupted */ 3141 } 3142 3143 for( i = nbinvars; i < 2*nbinvars; ++i ) 3144 vals[i] = 1 - vals[i - nbinvars]; 3145 3146 /* initialize number of nodes in Dijkstra graph (2*2*n nodes in a mirrored bipartite graph with negated variables) */ 3147 graph.nodes = 4 * nbinvars; 3148 3149 /* Initialize number of arcs in Dijkstra graph, should be (nbinvars+1) * graph.nodes, but might deviate, because 3150 * there might be parallel arcs: 3151 * nbinvars-1 possible arcs per node (it is not possible to be linked to variable and negated) 3152 * + 1 self-arc (arc to negated variable) 3153 * + 1 dummy arc for Dijkstra data structure 3154 * = nbinvars+1 arcs per node 3155 * * graph.nodes 3156 * = (nbinvars+1)*graph.nodes 3157 * + graph.nodes => separating entries for arclist) 3158 * 3159 * Number is corrected below. 3160 */ 3161 graph.arcs = 0; 3162 3163 /* the implication graph is redundant and therefore more implications and clique arcs may occur than should be possible 3164 * @todo later: filtering of edges which were already added, maxarcs should be graph.arcs rather than INT_MAX; 3165 */ 3166 maxarcs = UINT_MAX; 3167 3168 /* allocate memory for Dijkstra graph arrays */ 3169 arraysize = 100 * graph.nodes; 3170 SCIP_CALL( SCIPallocBufferArray(scip, &graph.outbeg, (int) graph.nodes) ); 3171 SCIP_CALL( SCIPallocBufferArray(scip, &graph.outcnt, (int) graph.nodes) ); 3172 SCIP_CALL( SCIPallocBufferArray(scip, &graph.head, (int) MIN(maxarcs, arraysize)) ); 3173 SCIP_CALL( SCIPallocBufferArray(scip, &graph.weight, (int) MIN(maxarcs, arraysize)) ); 3174 SCIP_CALL( SCIPallocBufferArray(scip, &dist, (int) graph.nodes) ); 3175 SCIP_CALL( SCIPallocBufferArray(scip, &pred, (int) graph.nodes) ); 3176 SCIP_CALL( SCIPallocBufferArray(scip, &entry, (int) graph.nodes) ); 3177 SCIP_CALL( SCIPallocBufferArray(scip, &order, (int) graph.nodes) ); 3178 3179 /* initialize Dijkstra graph as empty graph */ 3180 for( i = 0; i < MIN(arraysize, maxarcs); ++i ) 3181 { 3182 graph.head[i] = DIJKSTRA_UNUSED; 3183 graph.weight[i] = DIJKSTRA_UNUSED; 3184 } 3185 graph.minweight = DIJKSTRA_FARAWAY; 3186 graph.maxweight = 0; 3187 narcs = 0; 3188 3189 #ifndef NDEBUG 3190 for( i = 0; i < graph.nodes; ++i ) 3191 { 3192 graph.outbeg[i] = 0; 3193 graph.outcnt[i] = 0; 3194 } 3195 #endif 3196 3197 /* add arcs from first to second partition to Dijkstra graph (based on the original fractional implication graph) */ 3198 for( dijkindex = 0; dijkindex < 2 * nbinvars; ++dijkindex ) 3199 { 3200 graph.outbeg[dijkindex] = narcs; 3201 graph.outcnt[dijkindex] = 0; 3202 3203 /* decide if we have original or negated variable */ 3204 if( dijkindex < nbinvars ) 3205 { 3206 i = dijkindex; 3207 original = TRUE; 3208 } 3209 else 3210 { 3211 i = dijkindex - nbinvars; 3212 original = FALSE; 3213 } 3214 assert(i < nbinvars); 3215 3216 /* if the variable has a fractional value we add it to the graph */ 3217 if( ! SCIPisFeasIntegral(scip, vals[i]) ) 3218 { 3219 ncliques = (unsigned int) SCIPvarGetNCliques(vars[i], original); 3220 3221 /* insert arcs for cliques (take var => getCliques => take cliquevar => add forward-arc) */ 3222 /* add clique arcs of clique-type "original" if current variable has them */ 3223 if( ncliques >= 1 ) 3224 { 3225 /* x==1/0 -> y==0/1 (I/II -> III/IV) */ 3226 SCIP_CALL( addGLSCliques(scip, sepadata, vars, i, dijkindex, vals, nbinvars, ncliques, &graph, 3227 &narcs, maxarcs, original, &emptygraph, &arraysize, &success) ); 3228 3229 if( !success ) 3230 goto TERMINATE; 3231 } 3232 } 3233 3234 /* add link to copy of negated variable (useful if/because the implication graph is incomplete) */ 3235 if( sepadata->addselfarcs && graph.outcnt[dijkindex] > 0 ) 3236 { 3237 /* I -> IV */ 3238 if( original ) 3239 { 3240 assert(dijkindex < nbinvars); 3241 graph.head[narcs] = dijkindex + 3*nbinvars; 3242 } 3243 /* II -> III */ 3244 else 3245 { 3246 assert(dijkindex >= nbinvars && dijkindex < 2*nbinvars); 3247 graph.head[narcs] = dijkindex + nbinvars; 3248 } 3249 graph.weight[narcs] = 0; 3250 3251 /* update minimum and maximum weight values */ 3252 if( graph.weight[narcs] < graph.minweight ) 3253 graph.minweight = graph.weight[narcs]; 3254 3255 if( graph.weight[narcs] > graph.maxweight ) 3256 graph.maxweight = graph.weight[narcs]; 3257 3258 ++narcs; 3259 if( arraysize == narcs ) 3260 { 3261 SCIP_CALL( checkArraySizesGLS(scip, maxarcs, &arraysize, &graph, &success) ); 3262 if( !success ) 3263 goto TERMINATE; 3264 } 3265 assert(narcs < maxarcs); 3266 ++(graph.outcnt[dijkindex]); 3267 } 3268 3269 /* add separating arc */ 3270 graph.head[narcs] = DIJKSTRA_UNUSED; 3271 graph.weight[narcs] = DIJKSTRA_UNUSED; 3272 ++narcs; 3273 if( arraysize == narcs ) 3274 { 3275 SCIP_CALL( checkArraySizesGLS(scip, maxarcs, &arraysize, &graph, &success) ); 3276 if( !success ) 3277 goto TERMINATE; 3278 } 3279 assert(narcs < maxarcs); 3280 } 3281 3282 /* if the graph is empty, there is nothing to do */ 3283 if( emptygraph ) 3284 goto TERMINATE; 3285 3286 /* add arcs from second to first partition to Dijkstra graph */ 3287 for( i = 0; i < 2*nbinvars; ++i ) 3288 { 3289 graph.outbeg[2 * nbinvars + i] = narcs; 3290 graph.outcnt[2 * nbinvars + i] = 0; 3291 3292 /* copy all arcs to head from the second to the first bipartition */ 3293 for( j = graph.outbeg[i]; j < graph.outbeg[i] + graph.outcnt[i]; ++j ) 3294 { 3295 /* there are only arcs from first bipartition to the second */ 3296 assert(graph.head[j] >= 2*nbinvars && graph.head[j] < 4*nbinvars); 3297 3298 /* the backward arcs head from III->I or IV->II */ 3299 graph.head[narcs] = graph.head[j] - 2 * nbinvars; 3300 graph.weight[narcs] = graph.weight[j]; 3301 ++narcs; 3302 if( arraysize == narcs ) 3303 { 3304 SCIP_CALL( checkArraySizesGLS(scip, maxarcs, &arraysize, &graph, &success) ); 3305 3306 if( !success ) 3307 goto TERMINATE; 3308 } 3309 assert(narcs < maxarcs); 3310 ++(graph.outcnt[2*nbinvars+i]); 3311 } 3312 3313 /* add separating arc */ 3314 graph.head[narcs] = DIJKSTRA_UNUSED; 3315 graph.weight[narcs] = DIJKSTRA_UNUSED; 3316 ++narcs; 3317 3318 if( arraysize == narcs ) 3319 { 3320 SCIP_CALL( checkArraySizesGLS(scip, maxarcs, &arraysize, &graph, &success) ); 3321 3322 if( !success ) 3323 goto TERMINATE; 3324 } 3325 assert(narcs < maxarcs); 3326 } 3327 3328 /* correct number of arcs */ 3329 graph.arcs = narcs; 3330 3331 SCIPdebugMsg(scip, "--- graph successfully created (%u nodes, %u arcs) ---\n", graph.nodes, narcs); 3332 3333 /* graph is now prepared for Dijkstra methods */ 3334 assert( dijkstraGraphIsValid(&graph) ); 3335 3336 #ifdef SCIP_ODDCYCLE_WRITEGRAPH 3337 { 3338 char probname [SCIP_MAXSTRLEN]; 3339 char filename [SCIP_MAXSTRLEN]; 3340 char* name; 3341 3342 (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN, "%s", SCIPgetProbName(scip)); 3343 SCIPsplitFilename(probname, NULL, &name, NULL, NULL); 3344 (void) SCIPsnprintf(filename, SCIP_MAXSTRLEN, "%s_%d.gml", name, SCIPgetNLPs(scip)); 3345 SCIP_CALL( SCIPwriteCliqueGraph(scip, filename, TRUE, TRUE) ); 3346 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Wrote clique/implication graph to <%s>.\n", filename); 3347 } 3348 #endif 3349 3350 /* determine the number of start nodes */ 3351 maxstarts = (unsigned int) SCIPceil(scip, sepadata->offsettestvars + (0.02 * nbinvars * sepadata->percenttestvars)); 3352 startcounter = 0; 3353 3354 /* allocate and initialize predecessor list and flag array representing odd cycle */ 3355 SCIP_CALL( SCIPallocBufferArray(scip, &pred2, (int) (2 * nbinvars)) ); 3356 SCIP_CALL( SCIPallocBufferArray(scip, &incycle, (int) (2 * nbinvars)) ); 3357 3358 /* separate odd cycle inequalities by GLS method */ 3359 cutoff = (unsigned long long) (0.5 * sepadata->scale); 3360 for( i = (unsigned int) sepadata->lastroot; i < 2 * nbinvars 3361 && startcounter < maxstarts 3362 && sepadata->ncuts - sepadata->oldncuts < (unsigned int) sepadata->maxsepacutsround 3363 && !SCIPisStopped(scip); ++i ) 3364 { 3365 unsigned int ncyclevars; /* cycle length */ 3366 SCIP_Bool edgedirection; /* partitionindicator for backprojection from bipartite graph to original graph: 3367 * is the current edge a backwards edge, i.e., from second to first partition? */ 3368 3369 /* skip isolated node */ 3370 if( graph.head[graph.outbeg[i]] == DIJKSTRA_UNUSED ) 3371 continue; 3372 3373 /* if node has only one arc, there is no odd cycle containing this node 3374 * (but there are invalid odd circuits containing the only neighbor twice) 3375 */ 3376 if( graph.head[graph.outbeg[i]+1] == DIJKSTRA_UNUSED ) 3377 continue; 3378 3379 /* search shortest path from node to its counter part in the other partition */ 3380 startnode = i; 3381 endnode = i + 2 * nbinvars; 3382 3383 /* skip node if it is already covered by a cut and 3384 * we do not want to search cycles starting with a node already covered by a cut 3385 */ 3386 if( incut[startnode] && ! sepadata->multiplecuts ) 3387 continue; 3388 3389 ++startcounter; 3390 3391 if ( sepadata->allowmultiplecuts ) 3392 (void) dijkstraPairCutoffIgnore(&graph, startnode, endnode, incut, cutoff, dist, pred, entry, order); 3393 else 3394 (void) dijkstraPairCutoff(&graph, startnode, endnode, cutoff, dist, pred, entry, order); 3395 3396 /* no odd cycle cut found */ 3397 if( dist[endnode] == DIJKSTRA_FARAWAY ) 3398 continue; 3399 3400 /* skip check if cutoff has been exceeded */ 3401 if ( dist[endnode] >= cutoff ) 3402 continue; 3403 3404 /* detect cycle including: 3405 * project bipartitioned graph to original graph of variables and their negated 3406 * (pred&incycle-structure for generateOddCycleCut) 3407 * check cycles for double variables and try to clean variable-negated-sub-cycles if existing 3408 */ 3409 for( j = 0; j < 2 * nbinvars; ++j ) 3410 { 3411 pred2[j] = DIJKSTRA_UNUSED; 3412 incycle[j] = FALSE; 3413 } 3414 3415 ncyclevars = 0; 3416 edgedirection = TRUE; 3417 success = TRUE; 3418 3419 /* construct odd cycle in implication graph from shortest path on bipartite graph */ 3420 for( dijkindex = endnode; dijkindex != startnode && success; dijkindex = pred[dijkindex], edgedirection = !edgedirection ) 3421 { 3422 if( edgedirection ) 3423 { 3424 /* check that current node is in second partition and next node is in first partition */ 3425 assert(dijkindex >= 2 * nbinvars && dijkindex < 4 * nbinvars); 3426 assert(pred[dijkindex] < 2*nbinvars); 3427 3428 pred2[dijkindex - 2 * nbinvars] = pred[dijkindex]; 3429 3430 /* check whether the object found is really a cycle without sub-cycles 3431 * (sub-cycles may occur in case there is not violated odd cycle inequality) 3432 * and remove pairs of original and negated variable from cycle 3433 */ 3434 SCIP_CALL( cleanCycle(scip, pred2, incycle, incut, dijkindex-2*nbinvars, endnode-2*nbinvars, nbinvars, 3435 &ncyclevars, sepadata->repaircycles, sepadata->allowmultiplecuts, &success) ); 3436 } 3437 else 3438 { 3439 /* check that current node is in first partition and next node is in second partition */ 3440 assert(dijkindex < 2 * nbinvars); 3441 assert(pred[dijkindex] >= 2 * nbinvars && pred[dijkindex] < 4 * nbinvars); 3442 3443 pred2[dijkindex] = pred[dijkindex] - 2 * nbinvars; 3444 3445 /* check whether the object found is really a cycle without sub-cycles 3446 * (sub-cycles may occur in case there is not violated odd cycle inequality) 3447 * and remove pairs of original and negated variable from cycle 3448 */ 3449 SCIP_CALL( cleanCycle(scip, pred2, incycle, incut, dijkindex, endnode-2*nbinvars, nbinvars, &ncyclevars, 3450 sepadata->repaircycles, sepadata->allowmultiplecuts, &success) ); 3451 } 3452 } 3453 3454 if( success ) 3455 { 3456 GRAPHDATA graphdata; 3457 3458 /* generate cut */ 3459 graphdata.usegls = TRUE; 3460 graphdata.dijkstragraph = &graph; 3461 graphdata.levelgraph = NULL; 3462 3463 SCIP_CALL( generateOddCycleCut(scip, sepa, sol, vars, nbinvars, startnode, pred2, ncyclevars, incut, vals, sepadata, &graphdata, result) ); 3464 } 3465 } 3466 3467 /* free temporary memory */ 3468 SCIPfreeBufferArray(scip, &incycle); 3469 SCIPfreeBufferArray(scip, &pred2); 3470 3471 /* store the last tried root (when running without sorting the variable array, we don't want 3472 * to always check the same variables and therefore start next time where we stopped last time) 3473 */ 3474 if( sepadata->sortswitch == UNSORTED ) 3475 { 3476 if( i == 2 * nbinvars ) 3477 sepadata->lastroot = 0; 3478 else 3479 sepadata->lastroot = (int) i; 3480 } 3481 3482 TERMINATE: 3483 /* free temporary memory */ 3484 SCIPfreeBufferArray(scip, &order); 3485 SCIPfreeBufferArray(scip, &entry); 3486 SCIPfreeBufferArray(scip, &pred); 3487 SCIPfreeBufferArray(scip, &dist); 3488 SCIPfreeBufferArray(scip, &graph.weight); 3489 SCIPfreeBufferArray(scip, &graph.head); 3490 SCIPfreeBufferArray(scip, &graph.outcnt); 3491 SCIPfreeBufferArray(scip, &graph.outbeg); 3492 SCIPfreeBufferArray(scip, &incut); 3493 SCIPfreeBufferArray(scip, &(sepadata->mapping)); 3494 SCIPfreeBufferArray(scip, &vals); 3495 SCIPfreeBufferArray(scip, &vars); 3496 3497 return SCIP_OKAY; 3498 } 3499 3500 3501 /** separation method */ 3502 static 3503 SCIP_RETCODE separateOddCycles( 3504 SCIP* scip, /**< SCIP data structure */ 3505 SCIP_SEPA* sepa, /**< separator */ 3506 SCIP_SOL* sol, /**< given primal solution */ 3507 int depth, /**< current depth */ 3508 SCIP_RESULT* result /**< pointer to store the result of the separation call */ 3509 ) 3510 { 3511 SCIP_SEPADATA* sepadata; 3512 int ncalls; 3513 SCIPdebug( int oldnliftedcuts; ) 3514 int nfrac = 0; 3515 3516 *result = SCIP_DIDNOTRUN; 3517 3518 /* get separator data */ 3519 sepadata = SCIPsepaGetData(sepa); 3520 assert(sepadata != NULL); 3521 3522 ncalls = SCIPsepaGetNCallsAtNode(sepa); 3523 3524 /* only call separator a given number of rounds at each b&b node */ 3525 if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot) 3526 || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) ) 3527 return SCIP_OKAY; 3528 3529 /* only call separator if enough binary variables are present */ 3530 if( SCIPgetNBinVars(scip) < 3 || (! sepadata->includetriangles && SCIPgetNBinVars(scip) < 5) ) 3531 { 3532 SCIPdebugMsg(scip, "skipping separator: not enough binary variables\n"); 3533 return SCIP_OKAY; 3534 } 3535 3536 /* only call separator if enough fractional variables are present */ 3537 if ( sol != NULL ) 3538 { 3539 SCIP_VAR** vars; 3540 SCIP_Real solval; 3541 int nvars; 3542 int v; 3543 3544 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 3545 3546 /* first compute fractional variables */ 3547 for( v = 0; v < nvars; ++v ) 3548 { 3549 solval = SCIPgetSolVal(scip, sol, vars[v]); 3550 3551 if ( ! SCIPisFeasIntegral(scip, solval) ) 3552 ++nfrac; 3553 } 3554 } 3555 else 3556 nfrac = SCIPgetNLPBranchCands(scip); 3557 3558 if( nfrac < 3 || (! sepadata->includetriangles && nfrac < 5) ) 3559 { 3560 SCIPdebugMsg(scip, "skipping separator: not enough fractional variables\n"); 3561 return SCIP_OKAY; 3562 } 3563 3564 /* only call separator if enough implications and cliques are present */ 3565 if( SCIPgetNImplications(scip) + SCIPgetNCliques(scip) < 3 ) 3566 { 3567 SCIPdebugMsg(scip, "skipping separator: not enough implications present\n"); 3568 return SCIP_OKAY; 3569 } 3570 3571 /* only run if number of cuts already found is small enough */ 3572 if ( sepadata->cutthreshold >= 0 && SCIPgetNCutsFoundRound(scip) >= sepadata->cutthreshold ) 3573 return SCIP_OKAY; 3574 3575 /* store node number and reset number of unsuccessful calls */ 3576 if ( sepadata->lastnode != SCIPnodeGetNumber(SCIPgetCurrentNode(scip)) ) 3577 { 3578 sepadata->nunsucessfull = 0; 3579 sepadata->lastnode = SCIPnodeGetNumber(SCIPgetCurrentNode(scip)); 3580 } 3581 else 3582 { 3583 if ( sepadata->nunsucessfull > sepadata->maxunsucessfull ) 3584 { 3585 SCIPdebugMsg(scip, "skipping separator: number of unsucessfull calls = %d.\n", sepadata->nunsucessfull); 3586 return SCIP_OKAY; 3587 } 3588 } 3589 3590 *result = SCIP_DIDNOTFIND; 3591 sepadata->oldncuts = sepadata->ncuts; 3592 SCIPdebug( oldnliftedcuts = sepadata->nliftedcuts; ) 3593 3594 if( depth == 0 ) 3595 sepadata->maxsepacutsround = sepadata->maxsepacutsroot; 3596 else 3597 sepadata->maxsepacutsround = sepadata->maxsepacuts; 3598 3599 /* perform the actual separation routines */ 3600 if( sepadata->usegls ) 3601 { 3602 SCIPdebugMsg(scip, "using GLS method for finding odd cycles\n"); 3603 SCIP_CALL( separateGLS(scip, sepa, sepadata, sol, result) ); 3604 } 3605 else 3606 { 3607 SCIPdebugMsg(scip, "using level graph heuristic for finding odd cycles\n"); 3608 SCIP_CALL( separateHeur(scip, sepa, sepadata, sol, result) ); 3609 } 3610 3611 if( sepadata->ncuts - sepadata->oldncuts > 0 ) 3612 { 3613 SCIPdebug( SCIPdebugMsg(scip, "added %u cuts (%d allowed), %d lifted.\n", sepadata->ncuts - sepadata->oldncuts, 3614 sepadata->maxsepacutsround, sepadata->nliftedcuts - oldnliftedcuts); ) 3615 sepadata->nunsucessfull = 0; 3616 } 3617 else 3618 { 3619 SCIPdebugMsg(scip, "no cuts added (%d allowed)\n", sepadata->maxsepacutsround); 3620 ++sepadata->nunsucessfull; 3621 } 3622 SCIPdebugMsg(scip, "total sepatime: %.2f - total number of added cuts: %u\n", SCIPsepaGetTime(sepa), sepadata->ncuts); 3623 3624 return SCIP_OKAY; 3625 } 3626 3627 3628 /* 3629 * Callback methods of separator 3630 */ 3631 3632 /** copy method for separator plugins (called when SCIP copies plugins) */ 3633 static 3634 SCIP_DECL_SEPACOPY(sepaCopyOddcycle) 3635 { /*lint --e{715}*/ 3636 assert(scip != NULL); 3637 assert(sepa != NULL); 3638 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0); 3639 3640 /* call inclusion method of constraint handler */ 3641 SCIP_CALL( SCIPincludeSepaOddcycle(scip) ); 3642 3643 return SCIP_OKAY; 3644 } 3645 3646 3647 /** destructor of separator to free user data (called when SCIP is exiting) */ 3648 static 3649 SCIP_DECL_SEPAFREE(sepaFreeOddcycle) 3650 { 3651 SCIP_SEPADATA* sepadata; 3652 3653 sepadata = SCIPsepaGetData(sepa); 3654 assert(sepadata != NULL); 3655 3656 SCIPfreeBlockMemory(scip, &sepadata); 3657 SCIPsepaSetData(sepa, NULL); 3658 3659 return SCIP_OKAY; 3660 } 3661 3662 3663 /** initialization method of separator (called after problem was transformed) */ 3664 static 3665 SCIP_DECL_SEPAINIT(sepaInitOddcycle) 3666 { 3667 SCIP_SEPADATA* sepadata; 3668 3669 sepadata = SCIPsepaGetData(sepa); 3670 assert(sepadata != NULL); 3671 3672 sepadata->ncuts = 0; 3673 sepadata->oldncuts = 0; 3674 sepadata->nliftedcuts = 0; 3675 sepadata->lastroot = 0; 3676 3677 return SCIP_OKAY; 3678 } 3679 3680 3681 /** solving process initialization method of separator (called when branch and bound process is about to begin) */ 3682 static 3683 SCIP_DECL_SEPAINITSOL(sepaInitsolOddcycle) 3684 { 3685 SCIP_SEPADATA* sepadata; 3686 3687 assert(sepa != NULL); 3688 3689 sepadata = SCIPsepaGetData(sepa); 3690 assert(sepadata != NULL); 3691 3692 sepadata->nunsucessfull = 0; 3693 sepadata->lastnode = -1; 3694 3695 return SCIP_OKAY; 3696 } 3697 3698 3699 /** LP solution separation method of separator */ 3700 static 3701 SCIP_DECL_SEPAEXECLP(sepaExeclpOddcycle) 3702 { /*lint --e{715}*/ 3703 assert(sepa != NULL); 3704 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0); 3705 assert(scip != NULL); 3706 assert(result != NULL); 3707 3708 SCIP_CALL( separateOddCycles(scip, sepa, NULL, depth, result) ); 3709 3710 return SCIP_OKAY; 3711 } 3712 3713 /** arbitrary primal solution separation method of separator */ 3714 static 3715 SCIP_DECL_SEPAEXECSOL(sepaExecsolOddcycle) 3716 { /*lint --e{715}*/ 3717 assert(sepa != NULL); 3718 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0); 3719 assert(scip != NULL); 3720 assert(result != NULL); 3721 3722 SCIP_CALL( separateOddCycles(scip, sepa, sol, depth, result) ); 3723 3724 return SCIP_OKAY; 3725 } 3726 3727 3728 /* 3729 * separator specific interface methods 3730 */ 3731 3732 /** creates the oddcycle separator and includes it in SCIP */ 3733 SCIP_RETCODE SCIPincludeSepaOddcycle( 3734 SCIP* scip /**< SCIP data structure */ 3735 ) 3736 { 3737 SCIP_SEPADATA* sepadata; 3738 SCIP_SEPA* sepa; 3739 3740 /* create oddcycle separator data */ 3741 SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) ); 3742 sepadata->nunsucessfull = 0; 3743 sepadata->lastnode = -1; 3744 3745 /* include separator */ 3746 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST, 3747 SEPA_USESSUBSCIP, SEPA_DELAY, 3748 sepaExeclpOddcycle, sepaExecsolOddcycle, 3749 sepadata) ); 3750 3751 assert(sepa != NULL); 3752 3753 /* set non-NULL pointers to callback methods */ 3754 SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyOddcycle) ); 3755 SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeOddcycle) ); 3756 SCIP_CALL( SCIPsetSepaInit(scip, sepa, sepaInitOddcycle) ); 3757 SCIP_CALL( SCIPsetSepaInitsol(scip, sepa, sepaInitsolOddcycle) ); 3758 3759 /* add oddcycle separator parameters */ 3760 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/usegls", 3761 "Should the search method by Groetschel, Lovasz, Schrijver be used? Otherwise use levelgraph method by Hoffman, Padberg.", 3762 &sepadata->usegls, FALSE, DEFAULT_USEGLS, NULL, NULL) ); 3763 3764 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/liftoddcycles", 3765 "Should odd cycle cuts be lifted?", 3766 &sepadata->liftoddcycles, FALSE, DEFAULT_LIFTODDCYCLES, NULL, NULL) ); 3767 3768 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxsepacuts", 3769 "maximal number of oddcycle cuts separated per separation round", 3770 &sepadata->maxsepacuts, FALSE, DEFAULT_MAXSEPACUTS, 0, INT_MAX, NULL, NULL) ); 3771 3772 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxsepacutsroot", 3773 "maximal number of oddcycle cuts separated per separation round in the root node", 3774 &sepadata->maxsepacutsroot, FALSE, DEFAULT_MAXSEPACUTSROOT, 0, INT_MAX, NULL, NULL) ); 3775 3776 /* add advanced parameters */ 3777 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxrounds", 3778 "maximal number of oddcycle separation rounds per node (-1: unlimited)", 3779 &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) ); 3780 3781 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxroundsroot", 3782 "maximal number of oddcycle separation rounds in the root node (-1: unlimited)", 3783 &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) ); 3784 3785 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/scalingfactor", 3786 "factor for scaling of the arc-weights", 3787 &sepadata->scale, TRUE, DEFAULT_SCALEFACTOR, 1, INT_MAX, NULL, NULL) ); 3788 3789 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/addselfarcs", 3790 "add links between a variable and its negated", 3791 &sepadata->addselfarcs, TRUE, DEFAULT_ADDSELFARCS, NULL, NULL) ); 3792 3793 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/repaircycles", 3794 "try to repair violated cycles with double appearance of a variable", 3795 &sepadata->repaircycles, TRUE, DEFAULT_REPAIRCYCLES, NULL, NULL) ); 3796 3797 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/includetriangles", 3798 "separate triangles found as 3-cycles or repaired larger cycles", 3799 &sepadata->includetriangles, TRUE, DEFAULT_INCLUDETRIANGLES, NULL, NULL) ); 3800 3801 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/multiplecuts", 3802 "Even if a variable is already covered by a cut, still try it as start node for a cycle search?", 3803 &sepadata->multiplecuts, TRUE, DEFAULT_MULTIPLECUTS, NULL, NULL) ); 3804 3805 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/allowmultiplecuts", 3806 "Even if a variable is already covered by a cut, still allow another cut to cover it too?", 3807 &sepadata->allowmultiplecuts, TRUE, DEFAULT_ALLOWMULTIPLECUTS, NULL, NULL) ); 3808 3809 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/lpliftcoef", 3810 "Choose lifting candidate by coef*lpvalue or only by coef?", 3811 &sepadata->lpliftcoef, TRUE, DEFAULT_LPLIFTCOEF, NULL, NULL) ); 3812 3813 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/recalcliftcoef", 3814 "Calculate lifting coefficient of every candidate in every step (or only if its chosen)?", 3815 &sepadata->recalcliftcoef, TRUE, DEFAULT_RECALCLIFTCOEF, NULL, NULL) ); 3816 3817 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/sortswitch", 3818 "use sorted variable array (unsorted(0), maxlp(1), minlp(2), maxfrac(3), minfrac(4))", 3819 (int*) &sepadata->sortswitch, TRUE, DEFAULT_SORTSWITCH, 0, 4, NULL, NULL) ); 3820 3821 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/sortrootneighbors", 3822 "sort level of the root neighbors by fractionality (maxfrac)", 3823 &sepadata->sortrootneighbors, TRUE, DEFAULT_SORTROOTNEIGHBORS, NULL, NULL) ); 3824 3825 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/percenttestvars", 3826 "percentage of variables to try the chosen method on [0-100]", 3827 &sepadata->percenttestvars, TRUE, DEFAULT_PERCENTTESTVARS, 0, 100, NULL, NULL) ); 3828 3829 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/offsettestvars", 3830 "offset of variables to try the chosen method on (additional to the percentage of testvars)", 3831 &sepadata->offsettestvars, TRUE, DEFAULT_OFFSETTESTVARS, 0, INT_MAX, NULL, NULL) ); 3832 3833 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxpernodeslevel", 3834 "percentage of nodes allowed in the same level of the level graph [0-100]", 3835 &sepadata->maxpernodeslevel, TRUE, DEFAULT_MAXPERNODESLEVEL, 0, 100, NULL, NULL) ); 3836 3837 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/offsetnodeslevel", 3838 "offset of nodes allowed in the same level of the level graph (additional to the percentage of levelnodes)", 3839 &sepadata->offsetnodeslevel, TRUE, DEFAULT_OFFSETNODESLEVEL, 0, INT_MAX, NULL, NULL) ); 3840 3841 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxnlevels", 3842 "maximal number of levels in level graph", 3843 &sepadata->maxnlevels, TRUE, DEFAULT_MAXNLEVELS, 0, INT_MAX, NULL, NULL) ); 3844 3845 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxcutsroot", 3846 "maximal number of oddcycle cuts generated per chosen variable as root of the level graph", 3847 &sepadata->maxcutsroot, TRUE, DEFAULT_MAXCUTSROOT, 0, INT_MAX, NULL, NULL) ); 3848 3849 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxcutslevel", 3850 "maximal number of oddcycle cuts generated in every level of the level graph", 3851 &sepadata->maxcutslevel, TRUE, DEFAULT_MAXCUTSLEVEL, 0, INT_MAX, NULL, NULL) ); 3852 3853 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxreference", 3854 "minimal weight on an edge (in level graph or bipartite graph)", 3855 &sepadata->maxreference, TRUE, DEFAULT_MAXREFERENCE, 0, INT_MAX, NULL, NULL) ); 3856 3857 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxunsucessfull", 3858 "number of unsuccessful calls at current node", 3859 &sepadata->maxunsucessfull, TRUE, DEFAULT_MAXUNSUCESSFULL, 0, INT_MAX, NULL, NULL) ); 3860 3861 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/cutthreshold", 3862 "maximal number of other cuts s.t. separation is applied (-1 for direct call)", 3863 &sepadata->cutthreshold, TRUE, DEFAULT_CUTTHRESHOLD, -1, INT_MAX, NULL, NULL) ); 3864 3865 return SCIP_OKAY; 3866 } 3867