sepa_oddcycle.c
Go to the documentation of this file.
21 * We separate odd cycle inequalities in the implication graph. Implemented are the classic method
22 * by Groetschel, Lovasz, and Schrijver (GLS) and the levelgraph method by Hoffman and Padberg (HP)
31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
69 #define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */
73 #define DEFAULT_SCALEFACTOR 1000 /**< factor for scaling of the arc-weights in the Dijkstra algorithm */
76 #define DEFAULT_REPAIRCYCLES TRUE /**< try to repair violated cycles in which a variable and its negated appear */
78 #define DEFAULT_INCLUDETRIANGLES TRUE /**< separate triangles (3-cliques) found as 3-cycles or repaired larger cycles */
79 #define DEFAULT_MULTIPLECUTS FALSE /**< still try variable as start, even if it is already covered by a cut */
80 #define DEFAULT_ALLOWMULTIPLECUTS TRUE /**< allow another inequality to use variable, even if it is already covered */
81 #define DEFAULT_LPLIFTCOEF FALSE /**< TRUE: choose lifting candidate with highest value of coefficient*lpvalue
84 #define DEFAULT_MAXSEPACUTS 5000 /**< maximal number of oddcycle cuts separated per separation round */
85 #define DEFAULT_MAXSEPACUTSROOT 5000 /**< maximal number of oddcycle cuts separated per separation round in root node */
86 #define DEFAULT_PERCENTTESTVARS 0 /**< percent of variables to try the chosen method on [0-100] */
88 #define DEFAULT_MAXCUTSROOT 1 /**< maximal number of oddcycle cuts generated per root of the levelgraph */
89 #define DEFAULT_SORTSWITCH 3 /**< unsorted (0), maxlp (1), minlp (2), maxfrac (3), minfrac (4) */
90 #define DEFAULT_MAXREFERENCE 0 /**< minimal weight on an edge (in level graph or Dijkstra graph) */
94 #define DEFAULT_MAXPERNODESLEVEL 100 /**< maximal percentage of nodes allowed in one level of the levelgraph [0-100] */
95 #define DEFAULT_OFFSETNODESLEVEL 10 /**< additional offset of nodes allowed in one level of the levelgraph */
99 #define DEFAULT_CUTTHRESHOLD -1 /**< maximal number of other cuts s.t. separation is applied (-1 for direct call) */
110 * This undirected graph is represented by a directed graph with forward and backward arcs. Arcs are
127 unsigned int lastF; /**< last storage element index in targetForward, weightForward - forward direction */
128 unsigned int lastB; /**< last storage element index in targetBackward, weightBackward - backward direction */
129 int* beginForward; /**< forward adjacency list index in targetForward, weightForward for each node */
130 int* beginBackward; /**< backward adjacency list index in targetBackward, weightBackward for each node */
154 * processed start node or root node and continues from this position in the next separation round.
157 {
163 };
168 {
169 SCIP_Bool usegls; /**< Use GLS algorithm? If true, dijstragraph != NULL should hold, otherwise levelgraph != NULL */
172 };
179 unsigned int ncuts; /**< number of cuts, added by the separator so far (in current and past calls) */
181 int nliftedcuts; /**< number of lifted cuts, added by the separator so far (in current and past calls) */
183 SCIP_Bool multiplecuts; /**< an odd cycle cut of length L can be generated L times; forbidding multiple cuts
187 SCIP_Bool addselfarcs; /**< add arcs between the nodes of a variable and its negated; since not all implications
189 SCIP_Bool repaircycles; /**< if a variable and its negated appear in a cycle, we can repair the cycle
191 SCIP_Bool includetriangles; /**< handle triangles found as 3-cycles or repaired larger cycles */
192 unsigned int* mapping; /**< mapping for getting the index of a variable in the sorted variable array */
193 SCIP_Bool lpliftcoef; /**< TRUE: choose lifting candidate with highest value of coefficient*lpvalue
197 int maxsepacutsroot; /**< max. number of oddcycle cuts separated per separation round in the root node */
198 int maxsepacutsround; /**< max. number of oddcycle cuts separated per separation round in the current node */
199 SORTTYPE sortswitch; /**< sorted type: unsorted (0), maxlp (1), minlp (2), maxfrac (3), minfrac (4) */
204 int maxpernodeslevel; /**< percentage of nodes allowed in the same level of the level graph [0-100] */
206 unsigned int maxlevelsize; /**< maximal number of nodes allowed in the same level of the level graph */
208 int maxcutslevel; /**< maximal number of oddcycle cuts generated per level of the level graph */
210 int maxroundsroot; /**< maximal number of oddcycle separation rounds in the root node (-1: unlimited) */
215 int cutthreshold; /**< maximal number of other cuts s.t. separation is applied (-1 for direct call) */
226 /** displays cycle of pred data structure w.r.t. variable names of the original problem (including
323 for( i = dijkstragraph->outbeg[a]; i < dijkstragraph->outbeg[a] + dijkstragraph->outcnt[a]; ++i )
333 /* if a and b are contained in the level graph (with their arcs), we can check inside the level graph structure */
376 else /* same level (note that an edge between a and b is stored for a if a < b, otherwise it is stored for b) */
451 if( SCIPvarGetNCliques(vars[a], originala) == 0 || SCIPvarGetNCliques(vars[b], originalb) == 0 )
454 /* @todo later: possible improvement: do this test for implications and cliques separately if this here is time consuming */
455 /* one of the nodes seems to have more arcs than the other, we swap them (since adjacency is symmetric) */
490 if( (cliquevals[j] == FALSE && originalb == TRUE) || ( cliquevals[j] == TRUE && originalb == FALSE ) )
504 * since we have to exclude all chains adjacent to an already lifted node which is not adjacent to
505 * the current lifting candidate we check all chains of the cycle of length three and block them if
557 /** determine the heuristic lifting coefficient by counting the length of the adjacent chains of the
596 myi[j] = isNeighbor(vars, nbinvars, graphdata, i, cycle[j-1]) && isNeighbor(vars, nbinvars, graphdata, i, cycle[j])
613 checkBlocking((unsigned int) (j-1), (unsigned int) j, (unsigned int) (j+1), i, cycle, ncyclevars, vars, nbinvars, lifted, nlifted, graphdata, myi);
615 checkBlocking(ncyclevars-2, ncyclevars-1, 0, i, cycle, ncyclevars, vars, nbinvars, lifted, nlifted, graphdata, myi);
616 checkBlocking(ncyclevars-1, 0, 1, i, cycle, ncyclevars, vars, nbinvars, lifted, nlifted, graphdata, myi);
682 * This method is based on the observation, that a non-cycle node can be lifted into the inequality
689 * If the node is connected to several chains, the coefficients of the chains can be summed up, resulting
692 * Additionally further variables can be lifted by considering chains connected to the additional lifting node
696 * (Furthermore the first lifting coefficient is always smaller or equal to the largest possible lifting coefficient.)
792 /* in case we use a lifting rule, which does not require the first lifting coefficient of all variables: REMOVE this */
831 coef[i] = getCoef(scip, (unsigned int) bestcand, cycle, ncyclevars, vars, nbinvars, lifted, nlifted, graphdata, myi);
951 SCIP_CALL( liftOddCycleCut(scip, &nlifted, lifted, liftcoef, sepadata, graphdata, vars, nbinvars, startnode, pred, ncyclevars, vals, result) );
957 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), (ncyclevars-1)/2.0, FALSE, FALSE, TRUE) );
1068 * calculated by the GLS algorithm in case there is no violated odd cycle inequality) and removes
1099 /* skip variable if it is already covered by a cut and we do not allow multiple cuts per node */
1131 /* delete original and negated variable and cross-link their neighbors the following way, if possible:
1142 * in addition to that, in our linked list structure we need to relink the chain c1-...-cn in reverse order.
1232 /** memory reallocation method (the graph is normally very dense, so we dynamically allocate only the memory we need)
1234 * Since the array sizes differ the method can be called for each of the three data structure types:
1244 int** targetArray, /**< given target array (or NULL if sourceAdjArray and targetAdjArray given) */
1263 additional = MIN(graph->maxarcs + graph->maxnodes - *size, *size) * ((int) sizeof(**weightArray));
1266 additional += MIN(graph->maxarcs + graph->maxnodes - *size, *size) * ((int) sizeof(**targetArray));
1270 additional += MIN(graph->maxarcs + graph->maxnodes - *size, *size) * ((int) sizeof(**sourceAdjArray));
1271 additional += MIN(graph->maxarcs + graph->maxnodes - *size, *size) * ((int) sizeof(**targetAdjArray));
1291 SCIP_CALL( SCIPreallocBufferArray(scip, weightArray, (int) MIN(graph->maxarcs + graph->maxnodes, *size)) );
1294 SCIP_CALL( SCIPreallocBufferArray(scip, targetArray, (int) MIN(graph->maxarcs + graph->maxnodes, *size)) );
1518 /* calculate arc weight and add arc, if the neighbor node is on the same or a neighbor level */
1519 if( inlevelgraph[v] && (graph->level[v] == level+1 || graph->level[v] == level || graph->level[v] == level-1))
1523 /* the computation of 1.0 - vals[v] if v is negated is ensured by the fact that v > nbinvars in this case */
1551 * If we limit the size of nodes of a level, we want to add the best neighbors to the next level.
1552 * Since sorting every level is too expensive, we sort the neighbors of the root (if requested).
1556 * - iterate over the implication and clique neighbors of the root and set their flag array values to TRUE
1559 * - add variables from sorted array to levelgraph until first level is full (or all variables are inserted)
1561 * Even inserting all variables might help for the following creation of further levels since the neighbors
1562 * of nodes with high fractionality often have high fractionalities themselves and would be inserted first
1710 /* insert sorted neighbors until level size limit is reached (or all neighbors are inserted) */
1732 /* the computation of 1.0 - vals[v] if v is negated is ensured by the fact that v > nbinvars in this case */
1766 * node, P stores the partent nodes in the shortest path tree (-1 if node has not been reached).
1841 /* it is not necessary to stop if we found the root (in this case there are no arcs left) and we stop anyway */
1851 * We traverse the shortest path found by findShortestPathToRoot() and block all neighbors (in the
1852 * original graph) of nodes in the path, i.e., we set blocked to TRUE. We do not block neighbors of
2035 /* it is not necessary to stop if we found the root (in this case there are no arcs left) and we stop anyway */
2230 * All neighbors of nodes in level i that are assigned to level i+1, if they do not already appear in levels <= i.
2295 SCIP_CALL( SCIPgetVarsData(scip, &scipvars, NULL, &nscipbinvars, &nscipintvars, &nscipimplvars, NULL) );
2301 assert(scipvars != NULL || ((nscipbinvars == 0) && (nscipintvars == 0) && (nscipimplvars == 0) && (nintegral == 0)));
2382 /* create mapping for getting the index of a variable via its probindex to the index in the sorted variable array */
2388 assert( 0 <= SCIPvarGetProbindex(vars[i]) && SCIPvarGetProbindex(vars[i]) < nintegral); /* since binary, integer, and implicit variables are first */
2390 vals[i] = SCIPgetSolVal(scip, sol, vars[i]); /* need to get new values, since they might be corrupted */
2399 /* the implication graph is redundant and therefore more implications and clique arcs may occur than should be possible
2414 SCIP_CALL( SCIPallocBufferArray(scip, &graph.targetForward, (int) MIN(graph.sizeForward, graph.maxarcs)) );
2415 SCIP_CALL( SCIPallocBufferArray(scip, &graph.targetBackward, (int) MIN(graph.sizeBackward, graph.maxarcs)) );
2416 SCIP_CALL( SCIPallocBufferArray(scip, &graph.weightForward, (int) MIN(graph.sizeForward, graph.maxarcs)) );
2417 SCIP_CALL( SCIPallocBufferArray(scip, &graph.weightBackward, (int) MIN(graph.sizeBackward, graph.maxarcs)) );
2422 SCIP_CALL( SCIPallocBufferArray(scip, &graph.sourceAdj, (int) MIN(graph.sizeAdj, graph.maxarcs)) );
2423 SCIP_CALL( SCIPallocBufferArray(scip, &graph.targetAdj, (int) MIN(graph.sizeAdj, graph.maxarcs)) );
2424 SCIP_CALL( SCIPallocBufferArray(scip, &graph.weightAdj, (int) MIN(graph.sizeAdj, graph.maxarcs)) );
2441 maxroots = (unsigned int) SCIPceil(scip, sepadata->offsettestvars + (0.02 * nbinvars * sepadata->percenttestvars));
2442 sepadata->maxlevelsize = (unsigned int) SCIPceil(scip, sepadata->offsetnodeslevel + 0.01 * sepadata->maxpernodeslevel * graph.maxnodes);
2459 /* consider original and negated variable pair and skip variable if there is only one edge leaving the pair */
2460 if( SCIPvarGetNCliques(vars[i % nbinvars], TRUE) + SCIPvarGetNCliques(vars[i % nbinvars], FALSE) == 0 )
2530 /* calculate maximal cuts in this level due to cut limitations (per level, per root, per separation round) */
2533 maxcutslevel = (unsigned int) MIN(maxcutslevel, sepadata->maxsepacutsround + sepadata->oldncuts - sepadata->ncuts);
2535 /* for each cross edge in this level find both shortest paths to root (as long as no limits are reached) */
2549 SCIP_CALL( findShortestPathToRoot(scip, sepadata->scale, &graph, graph.sourceAdj[j], distance, queue, inQueue, parentTree) );
2566 SCIP_CALL( blockRootPath(scip, &graph, graph.sourceAdj[j], inlevelgraph, blocked, parentTree, i) );
2604 SCIP_CALL( cleanCycle(scip, pred, incycle, incut, u, graph.targetAdj[j], nbinvars, &ncyclevars,
2620 SCIP_CALL( cleanCycle(scip, pred, incycle, incut, u, graph.targetAdj[j], nbinvars, &ncyclevars,
2634 SCIP_CALL( cleanCycle(scip, pred, incycle, incut, u, graph.targetAdj[j], nbinvars, &ncyclevars,
2650 SCIP_CALL( generateOddCycleCut(scip, sepa, sol, vars, nbinvars, graph.targetAdj[j], pred, ncyclevars,
2734 /** memory reallocation method (the graph is normally very dense, so we dynamically allocate only the memory we need) */
2759 additional += (MIN(maxarcs, 2 * (*arraysize)) - (*arraysize)) * ((int) sizeof(*(graph->weight)));
2825 SCIP_Bool* emptygraph, /**< TRUE, iff there is no arc in the implication graph of the binary variables of SCIP */
2885 /* forward direction (the backward is created at the occurrence of the current variable in the cliquevars of the neighbor) */
2899 tmp = (int) SCIPfeasCeil(scip, sepadata->scale * (1 - vals[varsidx] - (1 - vals[neighindex]) ));
2910 tmp = (int) SCIPfeasCeil(scip, sepadata->scale * (1 - (1 - vals[varsidx]) - vals[neighindex] ));
2917 tmp = (int) SCIPfeasCeil(scip, sepadata->scale * (1 - (1 - vals[varsidx]) - (1-vals[neighindex]) )) ;
2948 /** The classical method for finding odd cycles by Groetschel, Lovasz, Schrijver uses a bipartite graph
2950 * All arcs uv of the original graph are copied to arcs from u of the first partition to v' of the second partition
3027 SCIP_CALL( SCIPgetVarsData(scip, &scipvars, NULL, &nscipbinvars, &nscipintvars, &nscipimplvars, NULL) );
3033 assert(scipvars != NULL || ((nscipbinvars == 0) && (nscipintvars == 0) && (nscipimplvars == 0) && (nintegral == 0)));
3114 /* create mapping for getting the index of a variable via its probindex to the index in the sorted variable array */
3122 assert( 0 <= SCIPvarGetProbindex(vars[i]) && SCIPvarGetProbindex(vars[i]) < nintegral); /* since binary, integer, and implicit variables are first */
3124 vals[i] = SCIPgetSolVal(scip, sol, vars[i]); /* need to get new values, since they might be corrupted */
3130 /* initialize number of nodes in Dijkstra graph (2*2*n nodes in a mirrored bipartite graph with negated variables) */
3133 /* Initialize number of arcs in Dijkstra graph, should be (nbinvars+1) * graph.nodes, but might deviate, because
3147 /* the implication graph is redundant and therefore more implications and clique arcs may occur than should be possible
3148 * @todo later: filtering of edges which were already added, maxarcs should be graph.arcs rather than INT_MAX;
3181 /* add arcs from first to second partition to Dijkstra graph (based on the original fractional implication graph) */
3218 /* add link to copy of negated variable (useful if/because the implication graph is incomplete) */
3315 SCIPdebugMsg(scip, "--- graph successfully created (%u nodes, %u arcs) ---\n", graph.nodes, narcs);
3330 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Wrote clique/implication graph to <%s>.\n", filename);
3335 maxstarts = (unsigned int) SCIPceil(scip, sepadata->offsettestvars + (0.02 * nbinvars * sepadata->percenttestvars));
3350 SCIP_Bool edgedirection; /* partitionindicator for backprojection from bipartite graph to original graph:
3376 (void) dijkstraPairCutoffIgnore(&graph, startnode, endnode, incut, cutoff, dist, pred, entry, order);
3404 for( dijkindex = endnode; dijkindex != startnode && success; dijkindex = pred[dijkindex], edgedirection = !edgedirection )
3418 SCIP_CALL( cleanCycle(scip, pred2, incycle, incut, dijkindex-2*nbinvars, endnode-2*nbinvars, nbinvars,
3433 SCIP_CALL( cleanCycle(scip, pred2, incycle, incut, dijkindex, endnode-2*nbinvars, nbinvars, &ncyclevars,
3447 SCIP_CALL( generateOddCycleCut(scip, sepa, sol, vars, nbinvars, startnode, pred2, ncyclevars, incut, vals, sepadata, &graphdata, result) );
3571 SCIPdebugMsg(scip, "skipping separator: number of unsucessfull calls = %d.\n", sepadata->nunsucessfull);
3599 SCIPdebugMsg(scip, "added %u cuts (%d allowed), %d lifted.\n", sepadata->ncuts - sepadata->oldncuts,
3608 SCIPdebugMsg(scip, "total sepatime: %.2f - total number of added cuts: %u\n", SCIPsepaGetTime(sepa), sepadata->ncuts);
3636 {
3652 {
3667 /** solving process initialization method of separator (called when branch and bound process is about to begin) */
3670 {
3732 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST,
3747 "Should the search method by Groetschel, Lovasz, Schrijver be used? Otherwise use levelgraph method by Hoffman, Padberg.",
3788 "Even if a variable is already covered by a cut, still try it as start node for a cycle search?",
3824 "offset of nodes allowed in the same level of the level graph (additional to the percentage of levelnodes)",
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:510
Definition: type_result.h:33
static SCIP_RETCODE separateHeur(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_RESULT *result)
Definition: sepa_oddcycle.c:2245
Definition: sepa_oddcycle.c:160
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1547
public methods for SCIP parameter handling
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:872
public methods for branch and bound tree
Definition: struct_scip.h:58
public methods for memory management
Definitions for Disjkstra's shortest path algorithm.
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1570
public methods for implications, variable bounds, and cliques
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:379
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1602
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17706
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:1325
void SCIPsortDownRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
Definition: struct_var.h:198
void SCIPsplitFilename(char *filename, char **path, char **name, char **extension, char **compression)
Definition: misc.c:10236
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1918
Definition: type_message.h:45
public methods for problem variables
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:386
Definition: sepa_oddcycle.c:163
Definition: type_result.h:40
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:700
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4613
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
Definition: struct_sepa.h:37
public methods for SCIP variables
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip_sepa.c:220
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:155
public methods for separator plugins
public methods for numerical tolerances
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:1073
public methods for querying solving statistics
Definition: struct_sol.h:63
Definition: sepa_oddcycle.c:162
public methods for the branch-and-bound tree
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:161
static SCIP_RETCODE separateGLS(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_RESULT *result)
Definition: sepa_oddcycle.c:2972
Definition: type_result.h:35
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:1949
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:2813
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4703
Definition: sepa_oddcycle.c:161
DIJKSTRA_Bool dijkstraGraphIsValid(const DIJKSTRA_GRAPH *G)
Definition: dijkstra.c:32
Definition: type_retcode.h:33
SCIP_RETCODE SCIPsetSepaInitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAINITSOL((*sepainitsol)))
Definition: scip_sepa.c:284
static SCIP_DECL_SEPAINITSOL(sepaInitsolOddcycle)
Definition: sepa_oddcycle.c:3670
Definition: type_result.h:42
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:296
Definition: sepa_oddcycle.c:168
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:294
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:178
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:497
public data structures and miscellaneous methods
SCIP_RETCODE SCIPchgRowRhs(SCIP *scip, SCIP_ROW *row, SCIP_Real rhs)
Definition: scip_lp.c:1519
Definition: dijkstra.h:43
Definition: struct_lp.h:192
public methods for LP management
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:1365
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:563
SCIP_RETCODE SCIPwriteCliqueGraph(SCIP *scip, const char *fname, SCIP_Bool writenodeweights)
Definition: scip_var.c:7608
public methods for cuts and aggregation rows
public methods for the LP relaxation, rows and columns
methods for sorting joint arrays of various types
static SCIP_Bool isNeighbor(SCIP_VAR **vars, unsigned int nbinvars, GRAPHDATA *graphdata, unsigned int a, unsigned int b)
Definition: sepa_oddcycle.c:297
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:1567
public methods for branching rule plugins and branching
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:1241
static SCIP_RETCODE checkArraySizesGLS(SCIP *scip, unsigned int maxarcs, unsigned int *arraysize, DIJKSTRA_GRAPH *graph, SCIP_Bool *success)
Definition: sepa_oddcycle.c:2737
general public methods
Definition: sepa_oddcycle.c:159
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip_sepa.c:236
SCIP_RETCODE SCIPsetSepaInit(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAINIT((*sepainit)))
Definition: scip_sepa.c:252
public methods for solutions
static SCIP_RETCODE separateOddCycles(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_RESULT *result)
Definition: sepa_oddcycle.c:3488
public methods for message output
Definition: struct_implics.h:66
public methods for message handling
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2094
void SCIPsortRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
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:1860
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:952
public methods for separators
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:1402
SCIP_RETCODE SCIPincludeSepaOddcycle(SCIP *scip)
Definition: sepa_oddcycle.c:3720
Definition: type_retcode.h:43
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:2068
Definition: objbenders.h:33
public methods for global and local (sub)problems
oddcycle separator
static SCIP_DECL_SEPAEXECSOL(sepaExecsolOddcycle)
Definition: sepa_oddcycle.c:3702
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1410
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:1770
Definition: type_result.h:39
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:129
memory allocation routines
Definition: type_var.h:58