Scippy

SCIP

Solving Constraint Integer Programs

sepa_oddcycle.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2024 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 */
129struct 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
156typedef 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 */
166enum 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};
174typedef enum sorttype SORTTYPE;
175
176/** auxiliary data structure for passing graphs */
177struct 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};
183typedef struct GraphData GRAPHDATA;
184
185/** separator data */
186struct 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 */
239static
240void 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 */
305static
306SCIP_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 */
518static
519void 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 */
571static
572unsigned 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 */
708static
709SCIP_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 */
880static
881SCIP_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 */
1081static
1082SCIP_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 */
1249static
1250SCIP_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 */
1337static
1338SCIP_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 */
1414static
1415SCIP_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 */
1579static
1580SCIP_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 */
1782static
1783SCIP_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 */
1873static
1874SCIP_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 */
1961static
1962SCIP_RETCODE
1963findUnblockedShortestPathToRoot(
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 */
2082static
2083SCIP_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 */
2259static
2260SCIP_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) */
2751static
2752SCIP_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 */
2827static
2828SCIP_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 */
2986static
2987SCIP_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 */
3502static
3503SCIP_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) */
3633static
3634SCIP_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) */
3648static
3649SCIP_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) */
3664static
3665SCIP_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) */
3682static
3683SCIP_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 */
3700static
3701SCIP_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 */
3714static
3715SCIP_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 */
3733SCIP_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}
a
SCIP_VAR * a
Definition: circlepacking.c:66
b
SCIP_VAR ** b
Definition: circlepacking.c:65
x
SCIP_VAR ** x
Definition: circlepacking.c:63
NULL
#define NULL
Definition: def.h:266
SCIP_MAXSTRLEN
#define SCIP_MAXSTRLEN
Definition: def.h:287
SCIP_Longint
#define SCIP_Longint
Definition: def.h:157
SCIP_Bool
#define SCIP_Bool
Definition: def.h:91
MIN
#define MIN(x, y)
Definition: def.h:242
SCIP_Real
#define SCIP_Real
Definition: def.h:172
TRUE
#define TRUE
Definition: def.h:93
FALSE
#define FALSE
Definition: def.h:94
MAX
#define MAX(x, y)
Definition: def.h:238
SCIPABORT
#define SCIPABORT()
Definition: def.h:345
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:373
dijkstraPairCutoffIgnore
unsigned int dijkstraPairCutoffIgnore(const DIJKSTRA_GRAPH *G, unsigned int source, unsigned int target, unsigned int *ignore, unsigned long long cutoff, unsigned long long *dist, unsigned int *pred, unsigned int *entry, unsigned int *order)
Definition: dijkstra.c:507
dijkstraGraphIsValid
DIJKSTRA_Bool dijkstraGraphIsValid(const DIJKSTRA_GRAPH *G)
Definition: dijkstra.c:42
dijkstraPairCutoff
unsigned int dijkstraPairCutoff(const DIJKSTRA_GRAPH *G, unsigned int source, unsigned int target, unsigned long long cutoff, unsigned long long *dist, unsigned int *pred, unsigned int *entry, unsigned int *order)
Definition: dijkstra.c:396
dijkstra.h
Definitions for Disjkstra's shortest path algorithm.
DIJKSTRA_UNUSED
#define DIJKSTRA_UNUSED
Definition: dijkstra.h:48
DIJKSTRA_FARAWAY
#define DIJKSTRA_FARAWAY
Definition: dijkstra.h:47
nnodes
#define nnodes
Definition: gastrans.c:74
narcs
#define narcs
Definition: gastrans.c:77
SCIPsplitFilename
void SCIPsplitFilename(char *filename, char **path, char **name, char **extension, char **compression)
Definition: misc.c:11126
SCIPisStopped
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:734
SCIPgetProbName
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1067
SCIPgetVarsData
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1866
SCIPgetNBinVars
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
SCIPverbMessage
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
SCIPdebugMsg
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIPgetBoolParam
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:250
SCIPaddIntParam
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
SCIPgetRealParam
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:307
SCIPaddBoolParam
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
SCIPgetNLPBranchCands
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip_branch.c:428
SCIPaddPoolCut
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:361
SCIPisCutEfficacious
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:117
SCIPaddRow
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:250
SCIPgetMemExternEstim
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
Definition: scip_mem.c:126
SCIPgetMemUsed
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition: scip_mem.c:100
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
SCIPreallocBufferArray
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:128
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
SCIPfreeBlockMemory
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
SCIPallocBlockMemory
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIPnodeGetNumber
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7510
SCIPcacheRowExtensions
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1635
SCIProwGetRhs
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17302
SCIPflushRowExtensions
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1658
SCIPaddVarToRow
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1701
SCIPprintRow
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2212
SCIPreleaseRow
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1562
SCIPcreateEmptyRowSepa
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1453
SCIProwChgRank
void SCIProwChgRank(SCIP_ROW *row, int rank)
Definition: lp.c:17534
SCIPchgRowRhs
SCIP_RETCODE SCIPchgRowRhs(SCIP *scip, SCIP_ROW *row, SCIP_Real rhs)
Definition: scip_lp.c:1607
SCIPsetSepaInitsol
SCIP_RETCODE SCIPsetSepaInitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAINITSOL((*sepainitsol)))
Definition: scip_sepa.c:215
SCIPincludeSepaBasic
SCIP_RETCODE SCIPincludeSepaBasic(SCIP *scip, SCIP_SEPA **sepa, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
Definition: scip_sepa.c:109
SCIPsepaGetName
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:743
SCIPsepaGetNCallsAtNode
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
Definition: sepa.c:880
SCIPsetSepaFree
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip_sepa.c:167
SCIPsepaGetTime
SCIP_Real SCIPsepaGetTime(SCIP_SEPA *sepa)
Definition: sepa.c:850
SCIPsepaGetData
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition: sepa.c:633
SCIPsepaSetData
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition: sepa.c:643
SCIPsetSepaCopy
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip_sepa.c:151
SCIPsetSepaInit
SCIP_RETCODE SCIPsetSepaInit(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAINIT((*sepainit)))
Definition: scip_sepa.c:183
SCIPgetSolVal
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1213
SCIPgetNImplications
int SCIPgetNImplications(SCIP *scip)
Definition: scip_solvingstats.c:4459
SCIPgetNCutsFoundRound
int SCIPgetNCutsFoundRound(SCIP *scip)
Definition: scip_solvingstats.c:1051
SCIPgetNLPs
SCIP_Longint SCIPgetNLPs(SCIP *scip)
Definition: scip_solvingstats.c:427
SCIPinfinity
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip_numerics.c:510
SCIPfeasCeil
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:917
SCIPfloor
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:631
SCIPisInfinity
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:521
SCIPisFeasIntegral
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:881
SCIPceil
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:643
SCIPgetCurrentNode
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:91
SCIPvarIsBinary
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17598
SCIPchgVarLb
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4799
SCIPwriteCliqueGraph
SCIP_RETCODE SCIPwriteCliqueGraph(SCIP *scip, const char *fname, SCIP_Bool writenodeweights)
Definition: scip_var.c:7833
SCIPchgVarUb
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4889
SCIPvarGetType
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17583
SCIPvarGetProbindex
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17767
SCIPvarGetName
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17418
SCIPvarGetNCliques
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18429
SCIPgetNCliques
int SCIPgetNCliques(SCIP *scip)
Definition: scip_var.c:7698
SCIPvarGetCliques
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18440
SCIPincludeSepaOddcycle
SCIP_RETCODE SCIPincludeSepaOddcycle(SCIP *scip)
Definition: sepa_oddcycle.c:3733
SCIPsortRealPtr
void SCIPsortRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
SCIPsortDownRealPtr
void SCIPsortDownRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
SCIPsortDownRealInt
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIPsnprintf
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10880
SCIPcliqueGetVars
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
Definition: implics.c:3380
SCIPcliqueGetNVars
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
Definition: implics.c:3370
SCIPcliqueGetValues
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
Definition: implics.c:3392
memory.h
memory allocation routines
BMSclearMemoryArray
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
pub_implics.h
public methods for implications, variable bounds, and cliques
pub_lp.h
public methods for LP management
pub_message.h
public methods for message output
SCIPerrorMessage
#define SCIPerrorMessage
Definition: pub_message.h:64
SCIPdebug
#define SCIPdebug(x)
Definition: pub_message.h:93
pub_misc.h
public data structures and miscellaneous methods
pub_misc_sort.h
methods for sorting joint arrays of various types
pub_sepa.h
public methods for separators
pub_tree.h
public methods for branch and bound tree
pub_var.h
public methods for problem variables
scip_branch.h
public methods for branching rule plugins and branching
scip_cut.h
public methods for cuts and aggregation rows
scip_general.h
general public methods
scip_lp.h
public methods for the LP relaxation, rows and columns
scip_mem.h
public methods for memory management
scip_message.h
public methods for message handling
scip_numerics.h
public methods for numerical tolerances
scip_param.h
public methods for SCIP parameter handling
scip_prob.h
public methods for global and local (sub)problems
scip_sepa.h
public methods for separator plugins
scip_sol.h
public methods for solutions
scip_solvingstats.h
public methods for querying solving statistics
scip_tree.h
public methods for the branch-and-bound tree
scip_var.h
public methods for SCIP variables
blockRootPath
static SCIP_RETCODE blockRootPath(SCIP *scip, LEVELGRAPH *graph, unsigned int startnode, SCIP_Bool *inlevelgraph, SCIP_Bool *blocked, int *parentTree, unsigned int root)
Definition: sepa_oddcycle.c:1874
DEFAULT_SORTROOTNEIGHBORS
#define DEFAULT_SORTROOTNEIGHBORS
Definition: sepa_oddcycle.c:106
SEPA_PRIORITY
#define SEPA_PRIORITY
Definition: sepa_oddcycle.c:75
isNeighbor
static SCIP_Bool isNeighbor(SCIP_VAR **vars, unsigned int nbinvars, GRAPHDATA *graphdata, unsigned int a, unsigned int b)
Definition: sepa_oddcycle.c:306
separateOddCycles
static SCIP_RETCODE separateOddCycles(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, int depth, SCIP_RESULT *result)
Definition: sepa_oddcycle.c:3503
SCIP_DECL_SEPAEXECSOL
static SCIP_DECL_SEPAEXECSOL(sepaExecsolOddcycle)
Definition: sepa_oddcycle.c:3715
SEPA_DELAY
#define SEPA_DELAY
Definition: sepa_oddcycle.c:79
addNextLevelCliques
static SCIP_RETCODE addNextLevelCliques(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_VAR **vars, SCIP_Real *vals, unsigned int u, LEVELGRAPH *graph, unsigned int level, SCIP_Bool *inlevelgraph, unsigned int *newlevel, unsigned int *nnewlevel, unsigned int *nAdj, SCIP_Bool *success)
Definition: sepa_oddcycle.c:1415
SCIP_DECL_SEPACOPY
static SCIP_DECL_SEPACOPY(sepaCopyOddcycle)
Definition: sepa_oddcycle.c:3634
SCIP_DECL_SEPAFREE
static SCIP_DECL_SEPAFREE(sepaFreeOddcycle)
Definition: sepa_oddcycle.c:3649
SCIP_DECL_SEPAINIT
static SCIP_DECL_SEPAINIT(sepaInitOddcycle)
Definition: sepa_oddcycle.c:3665
findUnblockedShortestPathToRoot
static SCIP_RETCODE findUnblockedShortestPathToRoot(SCIP *scip, int scale, LEVELGRAPH *graph, unsigned int startnode, unsigned int *distance, unsigned int *queue, SCIP_Bool *inQueue, int *parentTreeBackward, unsigned int root, SCIP_Bool *blocked)
Definition: sepa_oddcycle.c:1963
checkBlocking
static void checkBlocking(unsigned int a, unsigned int b, unsigned int c, unsigned int i, unsigned int *cycle, unsigned int ncyclevars, SCIP_VAR **vars, unsigned int nbinvars, unsigned int *lifted, unsigned int *nlifted, GRAPHDATA *graphdata, SCIP_Bool *myi)
Definition: sepa_oddcycle.c:519
SCIP_DECL_SEPAINITSOL
static SCIP_DECL_SEPAINITSOL(sepaInitsolOddcycle)
Definition: sepa_oddcycle.c:3683
SEPA_DESC
#define SEPA_DESC
Definition: sepa_oddcycle.c:74
DEFAULT_REPAIRCYCLES
#define DEFAULT_REPAIRCYCLES
Definition: sepa_oddcycle.c:86
addArc
static SCIP_RETCODE addArc(SCIP *scip, LEVELGRAPH *graph, unsigned int u, unsigned int v, unsigned int level, unsigned int weight, unsigned int *nAdj, SCIP_Bool *success)
Definition: sepa_oddcycle.c:1338
sorttype
sorttype
Definition: sepa_oddcycle.c:167
UNSORTED
@ UNSORTED
Definition: sepa_oddcycle.c:168
MAXIMAL_LPVALUE
@ MAXIMAL_LPVALUE
Definition: sepa_oddcycle.c:169
MINIMAL_FRACTIONALITY
@ MINIMAL_FRACTIONALITY
Definition: sepa_oddcycle.c:172
MINIMAL_LPVALUE
@ MINIMAL_LPVALUE
Definition: sepa_oddcycle.c:170
MAXIMAL_FRACTIONALITY
@ MAXIMAL_FRACTIONALITY
Definition: sepa_oddcycle.c:171
DEFAULT_MAXCUTSROOT
#define DEFAULT_MAXCUTSROOT
Definition: sepa_oddcycle.c:98
getCoef
static unsigned int getCoef(SCIP *scip, unsigned int i, unsigned int *cycle, unsigned int ncyclevars, SCIP_VAR **vars, unsigned int nbinvars, unsigned int *lifted, unsigned int *nlifted, GRAPHDATA *graphdata, SCIP_Bool *myi)
Definition: sepa_oddcycle.c:572
checkArraySizesHeur
static SCIP_RETCODE checkArraySizesHeur(SCIP *scip, LEVELGRAPH *graph, unsigned int *size, int **targetArray, unsigned int **weightArray, unsigned int **sourceAdjArray, unsigned int **targetAdjArray, SCIP_Bool *success)
Definition: sepa_oddcycle.c:1250
separateHeur
static SCIP_RETCODE separateHeur(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_RESULT *result)
Definition: sepa_oddcycle.c:2260
liftOddCycleCut
static SCIP_RETCODE liftOddCycleCut(SCIP *scip, unsigned int *nlifted, unsigned int *lifted, unsigned int *liftcoef, SCIP_SEPADATA *sepadata, GRAPHDATA *graphdata, SCIP_VAR **vars, unsigned int nbinvars, unsigned int startnode, unsigned int *pred, unsigned int ncyclevars, SCIP_Real *vals, SCIP_RESULT *result)
Definition: sepa_oddcycle.c:709
findShortestPathToRoot
static SCIP_RETCODE findShortestPathToRoot(SCIP *scip, int scale, LEVELGRAPH *graph, unsigned int startnode, unsigned int *distance, unsigned int *queue, SCIP_Bool *inQueue, int *parentTree)
Definition: sepa_oddcycle.c:1783
DEFAULT_MAXROUNDSROOT
#define DEFAULT_MAXROUNDSROOT
Definition: sepa_oddcycle.c:102
SEPA_USESSUBSCIP
#define SEPA_USESSUBSCIP
Definition: sepa_oddcycle.c:78
createNextLevel
static SCIP_RETCODE createNextLevel(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_VAR **vars, SCIP_Real *vals, LEVELGRAPH *graph, unsigned int level, SCIP_Bool *inlevelgraph, unsigned int *curlevel, unsigned int ncurlevel, unsigned int *newlevel, unsigned int *nnewlevel, SCIP_Bool *success)
Definition: sepa_oddcycle.c:2083
DEFAULT_SCALEFACTOR
#define DEFAULT_SCALEFACTOR
Definition: sepa_oddcycle.c:83
DEFAULT_MAXNLEVELS
#define DEFAULT_MAXNLEVELS
Definition: sepa_oddcycle.c:103
addGLSCliques
static SCIP_RETCODE addGLSCliques(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_VAR **vars, unsigned int varsidx, unsigned int dijkindex, SCIP_Real *vals, unsigned int nbinvars, unsigned int ncliques, DIJKSTRA_GRAPH *graph, unsigned int *narcs, unsigned int maxarcs, SCIP_Bool original, SCIP_Bool *emptygraph, unsigned int *arraysize, SCIP_Bool *success)
Definition: sepa_oddcycle.c:2828
insertSortedRootNeighbors
static SCIP_RETCODE insertSortedRootNeighbors(SCIP *scip, LEVELGRAPH *graph, unsigned int nbinvars, unsigned int ncurlevel, unsigned int u, SCIP_Real *vals, SCIP_VAR **vars, SCIP_SEPADATA *sepadata, unsigned int *nnewlevel, SCIP_Bool *inlevelgraph, unsigned int level, unsigned int *newlevel, SCIP_Bool *success)
Definition: sepa_oddcycle.c:1580
DEFAULT_ALLOWMULTIPLECUTS
#define DEFAULT_ALLOWMULTIPLECUTS
Definition: sepa_oddcycle.c:90
DEFAULT_RECALCLIFTCOEF
#define DEFAULT_RECALCLIFTCOEF
Definition: sepa_oddcycle.c:93
DEFAULT_MAXCUTSLEVEL
#define DEFAULT_MAXCUTSLEVEL
Definition: sepa_oddcycle.c:107
DEFAULT_MAXSEPACUTSROOT
#define DEFAULT_MAXSEPACUTSROOT
Definition: sepa_oddcycle.c:95
DEFAULT_LPLIFTCOEF
#define DEFAULT_LPLIFTCOEF
Definition: sepa_oddcycle.c:91
SCIP_DECL_SEPAEXECLP
static SCIP_DECL_SEPAEXECLP(sepaExeclpOddcycle)
Definition: sepa_oddcycle.c:3701
DEFAULT_MAXPERNODESLEVEL
#define DEFAULT_MAXPERNODESLEVEL
Definition: sepa_oddcycle.c:104
DEFAULT_USEGLS
#define DEFAULT_USEGLS
Definition: sepa_oddcycle.c:84
generateOddCycleCut
static SCIP_RETCODE generateOddCycleCut(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_VAR **vars, unsigned int nbinvars, unsigned int startnode, unsigned int *pred, unsigned int ncyclevars, unsigned int *incut, SCIP_Real *vals, SCIP_SEPADATA *sepadata, GRAPHDATA *graphdata, SCIP_RESULT *result)
Definition: sepa_oddcycle.c:881
SEPA_MAXBOUNDDIST
#define SEPA_MAXBOUNDDIST
Definition: sepa_oddcycle.c:77
DEFAULT_INCLUDETRIANGLES
#define DEFAULT_INCLUDETRIANGLES
Definition: sepa_oddcycle.c:88
DEFAULT_MULTIPLECUTS
#define DEFAULT_MULTIPLECUTS
Definition: sepa_oddcycle.c:89
SEPA_FREQ
#define SEPA_FREQ
Definition: sepa_oddcycle.c:76
DEFAULT_SORTSWITCH
#define DEFAULT_SORTSWITCH
Definition: sepa_oddcycle.c:99
DEFAULT_MAXSEPACUTS
#define DEFAULT_MAXSEPACUTS
Definition: sepa_oddcycle.c:94
SEPA_NAME
#define SEPA_NAME
Definition: sepa_oddcycle.c:73
SORTTYPE
enum sorttype SORTTYPE
Definition: sepa_oddcycle.c:174
DEFAULT_MAXUNSUCESSFULL
#define DEFAULT_MAXUNSUCESSFULL
Definition: sepa_oddcycle.c:108
DEFAULT_OFFSETTESTVARS
#define DEFAULT_OFFSETTESTVARS
Definition: sepa_oddcycle.c:97
DEFAULT_MAXROUNDS
#define DEFAULT_MAXROUNDS
Definition: sepa_oddcycle.c:101
separateGLS
static SCIP_RETCODE separateGLS(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_RESULT *result)
Definition: sepa_oddcycle.c:2987
LEVELGRAPH
struct levelGraph LEVELGRAPH
Definition: sepa_oddcycle.c:156
checkArraySizesGLS
static SCIP_RETCODE checkArraySizesGLS(SCIP *scip, unsigned int maxarcs, unsigned int *arraysize, DIJKSTRA_GRAPH *graph, SCIP_Bool *success)
Definition: sepa_oddcycle.c:2752
DEFAULT_PERCENTTESTVARS
#define DEFAULT_PERCENTTESTVARS
Definition: sepa_oddcycle.c:96
DEFAULT_ADDSELFARCS
#define DEFAULT_ADDSELFARCS
Definition: sepa_oddcycle.c:87
DEFAULT_OFFSETNODESLEVEL
#define DEFAULT_OFFSETNODESLEVEL
Definition: sepa_oddcycle.c:105
cleanCycle
static SCIP_RETCODE cleanCycle(SCIP *scip, unsigned int *pred, SCIP_Bool *incycle, unsigned int *incut, unsigned int x, unsigned int startnode, unsigned int nbinvars, unsigned int *ncyclevars, SCIP_Bool repaircycles, SCIP_Bool allowmultiplecuts, SCIP_Bool *success)
Definition: sepa_oddcycle.c:1082
DEFAULT_MAXREFERENCE
#define DEFAULT_MAXREFERENCE
Definition: sepa_oddcycle.c:100
DEFAULT_CUTTHRESHOLD
#define DEFAULT_CUTTHRESHOLD
Definition: sepa_oddcycle.c:109
DEFAULT_LIFTODDCYCLES
#define DEFAULT_LIFTODDCYCLES
Definition: sepa_oddcycle.c:85
sepa_oddcycle.h
oddcycle separator
DIJKSTRA_Graph
Definition: dijkstra.h:53
DIJKSTRA_Graph::arcs
unsigned int arcs
Definition: dijkstra.h:57
DIJKSTRA_Graph::minweight
unsigned int minweight
Definition: dijkstra.h:60
DIJKSTRA_Graph::head
unsigned int * head
Definition: dijkstra.h:59
DIJKSTRA_Graph::outbeg
unsigned int * outbeg
Definition: dijkstra.h:55
DIJKSTRA_Graph::nodes
unsigned int nodes
Definition: dijkstra.h:54
DIJKSTRA_Graph::weight
unsigned int * weight
Definition: dijkstra.h:58
DIJKSTRA_Graph::outcnt
unsigned int * outcnt
Definition: dijkstra.h:56
DIJKSTRA_Graph::maxweight
unsigned int maxweight
Definition: dijkstra.h:61
GraphData::levelgraph
LEVELGRAPH * levelgraph
Definition: sepa_oddcycle.c:180
GraphData::usegls
SCIP_Bool usegls
Definition: sepa_oddcycle.c:179
GraphData::dijkstragraph
DIJKSTRA_GRAPH * dijkstragraph
Definition: sepa_oddcycle.c:181
SCIP_Clique
Definition: struct_implics.h:76
SCIP_Row
Definition: struct_lp.h:202
SCIP_Sepa
Definition: struct_sepa.h:47
SCIP_Sol
Definition: struct_sol.h:74
SCIP_Var
Definition: struct_var.h:208
SCIP_VERBLEVEL_HIGH
@ SCIP_VERBLEVEL_HIGH
Definition: type_message.h:56
SCIP_DIDNOTRUN
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
SCIP_CUTOFF
@ SCIP_CUTOFF
Definition: type_result.h:48
SCIP_REDUCEDDOM
@ SCIP_REDUCEDDOM
Definition: type_result.h:51
SCIP_DIDNOTFIND
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
SCIP_SEPARATED
@ SCIP_SEPARATED
Definition: type_result.h:49
SCIP_RESULT
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
SCIP_INVALIDDATA
@ SCIP_INVALIDDATA
Definition: type_retcode.h:52
SCIP_OKAY
@ SCIP_OKAY
Definition: type_retcode.h:42
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_SEPADATA
struct SCIP_SepaData SCIP_SEPADATA
Definition: type_sepa.h:52
SCIP_VARTYPE_CONTINUOUS
@ SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:71