SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
oddcycle separator
We separate odd cycle inequalities in the implication graph. Implemented are the classic method by Groetschel, Lovasz, and Schrijver (GLS) and the levelgraph method by Hoffman and Padberg (HP)
Odd cycle inequalities are lifted by a heuristic method based on an idea from Alvarez-Valdes, Parreno, and Tamarit.
Some part of this code is based on the odd cycle separator of the program colorbitopt by Marc Pfetsch.
Definition in file sepa_oddcycle.c.
#include <assert.h>#include <string.h>#include "scip/sepa_oddcycle.h"#include "scip/pub_misc.h"#include "dijkstra/dijkstra.h"Go to the source code of this file.
Typedefs | |
| typedef struct levelGraph | LEVELGRAPH |
| typedef enum sorttype | SORTTYPE |
| typedef struct GraphData | GRAPHDATA |
Enumerations | |
| enum | sorttype { UNSORTED = 0, MAXIMAL_LPVALUE = 1, MINIMAL_LPVALUE = 2, MAXIMAL_FRACTIONALITY = 3, MINIMAL_FRACTIONALITY = 4 } |
Functions | |
| static SCIP_Bool | isNeighbor (SCIP_VAR **vars, unsigned int nbinvars, GRAPHDATA *graphdata, unsigned int a, unsigned int b) |
| 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) |
| 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) |
| 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) |
| 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) |
| 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) |
| 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) |
| 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) |
| 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) |
| 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) |
| static SCIP_RETCODE | findShortestPathToRoot (SCIP *scip, int scale, LEVELGRAPH *graph, unsigned int startnode, unsigned int *distance, unsigned int *queue, SCIP_Bool *inQueue, int *parentTree) |
| static SCIP_RETCODE | blockRootPath (SCIP *scip, LEVELGRAPH *graph, unsigned int startnode, SCIP_Bool *inlevelgraph, SCIP_Bool *blocked, int *parentTree, unsigned int root) |
| 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) |
| 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) |
| static SCIP_RETCODE | separateHeur (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_RESULT *result) |
| static SCIP_RETCODE | checkArraySizesGLS (SCIP *scip, unsigned int maxarcs, unsigned int *arraysize, DIJKSTRA_GRAPH *graph, SCIP_Bool *success) |
| 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) |
| static SCIP_RETCODE | separateGLS (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_RESULT *result) |
| static | SCIP_DECL_SEPACOPY (sepaCopyOddcycle) |
| static | SCIP_DECL_SEPAFREE (sepaFreeOddcycle) |
| static | SCIP_DECL_SEPAINIT (sepaInitOddcycle) |
| static | SCIP_DECL_SEPAINITSOL (sepaInitsolOddcycle) |
| static | SCIP_DECL_SEPAEXECLP (sepaExeclpOddcycle) |
| SCIP_RETCODE | SCIPincludeSepaOddcycle (SCIP *scip) |
| #define SEPA_NAME "oddcycle" |
Definition at line 41 of file sepa_oddcycle.c.
Referenced by SCIP_DECL_SEPACOPY(), and SCIPincludeSepaOddcycle().
| #define SEPA_DESC "odd cycle separator" |
Definition at line 42 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define SEPA_PRIORITY -15000 |
Definition at line 43 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define SEPA_FREQ -1 |
Definition at line 44 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define SEPA_MAXBOUNDDIST 1.0 |
Definition at line 45 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define SEPA_USESSUBSCIP FALSE |
does the separator use a secondary SCIP instance?
Definition at line 46 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define SEPA_DELAY FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 47 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define DEFAULT_SCALEFACTOR 1000 |
factor for scaling of the arc-weights in the Dijkstra algorithm
Definition at line 51 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define DEFAULT_USEGLS TRUE |
use GLS method, otherwise HP method
Definition at line 52 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define DEFAULT_LIFTODDCYCLES FALSE |
lift odd cycle cuts
Definition at line 53 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define DEFAULT_REPAIRCYCLES TRUE |
try to repair violated cycles in which a variable and its negated appear
Definition at line 54 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define DEFAULT_ADDSELFARCS TRUE |
add links between a variable and its negated
Definition at line 55 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define DEFAULT_INCLUDETRIANGLES TRUE |
separate triangles (3-cliques) found as 3-cycles or repaired larger cycles
Definition at line 56 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define DEFAULT_MULTIPLECUTS FALSE |
still try variable as start, even if it is already covered by a cut
Definition at line 57 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define DEFAULT_ALLOWMULTIPLECUTS TRUE |
allow another inequality to use variable, even if it is already covered
Definition at line 58 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define DEFAULT_LPLIFTCOEF FALSE |
TRUE: choose lifting candidate with highest value of coefficient*lpvalue FALSE: choose lifting candidate with highest coefficient
Definition at line 59 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define DEFAULT_RECALCLIFTCOEF TRUE |
whether lifting coefficients should be recomputed
Definition at line 62 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define DEFAULT_MAXSEPACUTS 5000 |
maximal number of oddcycle cuts separated per separation round
Definition at line 63 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define DEFAULT_MAXSEPACUTSROOT 5000 |
maximal number of oddcycle cuts separated per separation round in root node
Definition at line 64 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define DEFAULT_PERCENTTESTVARS 0 |
percent of variables to try the chosen method on [0-100]
Definition at line 65 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define DEFAULT_OFFSETTESTVARS 100 |
offset of variables to try the chosen method on
Definition at line 66 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define DEFAULT_MAXCUTSROOT 1 |
maximal number of oddcycle cuts generated per root of the levelgraph
Definition at line 67 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define DEFAULT_SORTSWITCH 3 |
unsorted (0), maxlp (1), minlp (2), maxfrac (3), minfrac (4)
Definition at line 68 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define DEFAULT_MAXREFERENCE 0 |
minimal weight on an edge (in level graph or Dijkstra graph)
Definition at line 69 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define DEFAULT_MAXROUNDS 10 |
maximal number of rounds pre node
Definition at line 70 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define DEFAULT_MAXROUNDSROOT 10 |
maximal number of rounds in the root node
Definition at line 71 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define DEFAULT_MAXNLEVELS 20 |
maximal number of levels in level graph
Definition at line 72 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define DEFAULT_MAXPERNODESLEVEL 100 |
maximal percentage of nodes allowed in one level of the levelgraph [0-100]
Definition at line 73 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define DEFAULT_OFFSETNODESLEVEL 10 |
additional offset of nodes allowed in one level of the levelgraph
Definition at line 74 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define DEFAULT_SORTROOTNEIGHBORS TRUE |
sort neighbors of the root in the level graph
Definition at line 75 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define DEFAULT_MAXCUTSLEVEL 50 |
maximal number of cuts produced per level
Definition at line 76 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define DEFAULT_MAXUNSUCESSFULL 3 |
maximal number of unsuccessful calls at each node
Definition at line 77 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| #define DEFAULT_CUTTHRESHOLD -1 |
maximal number of other cuts s.t. separation is applied (-1 for direct call)
Definition at line 78 of file sepa_oddcycle.c.
Referenced by SCIPincludeSepaOddcycle().
| typedef struct levelGraph LEVELGRAPH |
Definition at line 125 of file sepa_oddcycle.c.
Definition at line 143 of file sepa_oddcycle.c.
Definition at line 152 of file sepa_oddcycle.c.
| enum sorttype |
sorting type for starting node or root node iteration order
If the array should be sorted (1-4), the variable array is sorted every round by the chosen sorttype and the search method tries the nodes in order of the array. If the array is used unsorted (0), the search methods tries the nodes in order of the array and stores the last processed start node or root node and continues from this position in the next separation round.
Definition at line 135 of file sepa_oddcycle.c.
|
static |
using the level graph (if possible) or Dijkstra graph data structure (depending on the used method) we determine whether two nodes are adjacent
| vars | problem variables |
| nbinvars | number of binary problem variables |
| graphdata | graph |
| a | node index of first variable |
| b | node index of second variable |
Definition at line 275 of file sepa_oddcycle.c.
References checkBlocking(), GraphData::dijkstragraph, FALSE, DIJKSTRA_Graph::head, GraphData::levelgraph, DIJKSTRA_Graph::outbeg, DIJKSTRA_Graph::outcnt, SCIP_Bool, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPvarGetCliques(), SCIPvarGetNCliques(), SCIPvarGetProbindex(), TRUE, and GraphData::usegls.
Referenced by checkBlocking(), and getCoef().
|
static |
inside the lifting heuristic we determine the lifting coefficient by counting the length of chains adjacent to the lifting candidate.
since we have to exclude all chains adjacent to an already lifted node which is not adjacent to the current lifting candidate we check all chains of the cycle of length three and block them if they are adjacent.
| a | first node of the checked cycle chain of length 3 |
| b | second node of the checked cycle chain of length 3 |
| c | third node of the checked cycle chain of length 3 |
| i | current lifting candidate |
| cycle | list of cycle nodes in order of the cycle |
| ncyclevars | number of variables in the odd cycle |
| vars | problem variables |
| nbinvars | number of binary problem variables |
| lifted | list of lifted nodes |
| nlifted | number of lifted nodes |
| graphdata | graph |
| myi | flag array, if cycle node is inner point of a counted chain |
Definition at line 488 of file sepa_oddcycle.c.
References FALSE, getCoef(), and isNeighbor().
Referenced by getCoef(), and isNeighbor().
|
static |
determine the heuristic lifting coefficient by counting the length of the adjacent chains of the candidate (we have to exclude all chains that are adjacent to an already lifted node which is not adjacent to the current candidate)
| scip | SCIP data structure |
| i | current lifting candidate |
| cycle | list of cycle nodes in order of the cycle |
| ncyclevars | number of variables in the odd cycle |
| vars | problem variables |
| nbinvars | number of binary problem variables |
| lifted | list of lifted nodes |
| nlifted | number of lifted nodes |
| graphdata | graph data structure |
| myi | flag array, if cycle node is inner point of a counted chain |
Definition at line 541 of file sepa_oddcycle.c.
References checkBlocking(), isNeighbor(), liftOddCycleCut(), and SCIPfloor().
Referenced by checkBlocking(), and liftOddCycleCut().
|
static |
Lifting Heuristic based on an idea by Alvarez-Valdes, Parreno, Tamarit
This method is based on the observation, that a non-cycle node can be lifted into the inequality with coefficient \(1\) if the node is adjacent to the nodes of a 3-chain on the cycle.
The coefficient can be calculated as \(\left\lfloor{\frac{|C|-1}{2}}\right\rfloor\) where \(C\) is the chain on the cycle.
If the node is connected to several chains, the coefficients of the chains can be summed up, resulting in a feasible lifting coefficient.
Additionally further variables can be lifted by considering chains connected to the additional lifting node which are not connected to already lifted nodes.
This method is a feasible heuristic which gives a valid lifted inequality. (Furthermore the first lifting coefficient is always smaller or equal to the largest possible lifting coefficient.)
| scip | SCIP data structure |
| nlifted | number of lifted variables |
| lifted | indices of the lifted variables |
| liftcoef | lifting coefficients |
| sepadata | separator data structure |
| graphdata | graph |
| vars | problem variables |
| nbinvars | number of binary problem variables |
| startnode | a node of the cycle |
| pred | predecessor of each node (original and negated) in odd cycle |
| ncyclevars | number of variables in the odd cycle |
| vals | values of the variables in the given solution |
| result | pointer to store the result of the separation call |
Definition at line 678 of file sepa_oddcycle.c.
References GraphData::dijkstragraph, FALSE, generateOddCycleCut(), getCoef(), GraphData::levelgraph, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisStopped(), TRUE, and GraphData::usegls.
Referenced by generateOddCycleCut(), and getCoef().
|
static |
add the inequality corresponding to the given odd cycle to the LP (if violated) after lifting it (if requested by user flag)
| scip | SCIP data structure |
| sepa | separator |
| sol | given primal solution |
| vars | problem variables |
| nbinvars | number of binary problem variables |
| startnode | a node of the cycle |
| pred | predecessor of each node (original and negated) in odd cycle |
| ncyclevars | number of variables in the odd cycle |
| incut | TRUE iff node is covered already by a cut |
| vals | values of the variables in the given solution |
| sepadata | separator data structure |
| graphdata | graph data structure |
| result | pointer to store the result of the separation call |
Definition at line 850 of file sepa_oddcycle.c.
References cleanCycle(), GraphData::dijkstragraph, FALSE, GraphData::levelgraph, liftOddCycleCut(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_SEPARATED, SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarToRow(), SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPchgRowRhs(), SCIPchgVarLb(), SCIPchgVarUb(), SCIPcreateEmptyRowSepa(), SCIPdebugMsg, SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPinfinity(), SCIPisCutEfficacious(), SCIPisStopped(), SCIPprintRow(), SCIPreleaseRow(), SCIProwChgRank(), SCIProwGetRhs(), SCIPsnprintf(), TRUE, and GraphData::usegls.
Referenced by liftOddCycleCut(), separateGLS(), and separateHeur().
|
static |
check whether the given object is really a cycle without sub-cycles (sub-cycles may be calculated by the GLS algorithm in case there is no violated odd cycle inequality) and removes pairs of original and negated variables from the cycle
| scip | SCIP data structure |
| pred | predecessor list of current cycle segment |
| incycle | flag array iff node is in cycle segment |
| incut | flag array iff node is already covered by a cut |
| x | index of current variable |
| startnode | index of first variable of cycle segment |
| nbinvars | number of binary problem variables |
| ncyclevars | number of nodes in current cycle segment |
| repaircycles | user flag if we should try to repair damaged cycles |
| allowmultiplecuts | user flag if we allow multiple cuts per node |
| success | FALSE iff an irreparable cycle appears |
Definition at line 1051 of file sepa_oddcycle.c.
References checkArraySizesHeur(), FALSE, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, and TRUE.
Referenced by generateOddCycleCut(), separateGLS(), and separateHeur().
|
static |
memory reallocation method (the graph is normally very dense, so we dynamically allocate only the memory we need)
Since the array sizes differ the method can be called for each of the three data structure types:
| scip | SCIP data structure |
| graph | LEVELGRAPH data structure |
| size | given size |
| targetArray | given target array (or NULL if sourceAdjArray and targetAdjArray given) |
| weightArray | given weight array |
| sourceAdjArray | given sourceAdj array (or NULL if targetArray given) |
| targetAdjArray | given targetAdj array (or NULL if targetArray given) |
| success | FALSE, iff memory reallocation fails |
Definition at line 1219 of file sepa_oddcycle.c.
References addArc(), FALSE, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetRealParam(), SCIPisInfinity(), SCIPisStopped(), and SCIPreallocBufferArray.
Referenced by addArc(), cleanCycle(), createNextLevel(), and insertSortedRootNeighbors().
|
static |
Add arc to level graph
| scip | SCIP data structure |
| graph | LEVELGRAPH data structure |
| u | source node |
| v | target node |
| level | number of current level |
| weight | weight of the arc |
| nAdj | array of numbers of arcs inside levels |
| success | FALSE, iff memory reallocation fails |
Definition at line 1304 of file sepa_oddcycle.c.
References addNextLevelCliques(), checkArraySizesHeur(), SCIP_CALL, and SCIP_OKAY.
Referenced by addNextLevelCliques(), checkArraySizesHeur(), and createNextLevel().
|
static |
add implications from cliques of the given node u
| scip | SCIP data structure |
| sepadata | separator data structure |
| vars | problem variables |
| vals | values of the binary variables in the current LP relaxation |
| u | current node |
| graph | LEVELGRAPH data structure |
| level | number of current level |
| inlevelgraph | flag array if node is already inserted in level graph |
| newlevel | array of nodes of the next level |
| nnewlevel | number of nodes of the next level |
| nAdj | array of numbers of arcs inside levels |
| success | FALSE, iff memory reallocation fails |
Definition at line 1381 of file sepa_oddcycle.c.
References addArc(), FALSE, insertSortedRootNeighbors(), MAX, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPfeasCeil(), SCIPisFeasIntegral(), SCIPvarGetCliques(), SCIPvarGetNCliques(), SCIPvarGetProbindex(), and TRUE.
Referenced by addArc(), and createNextLevel().
|
static |
sort level of root neighbors
If we limit the size of nodes of a level, we want to add the best neighbors to the next level. Since sorting every level is too expensive, we sort the neighbors of the root (if requested).
Create the first level as follows:
Even inserting all variables might help for the following creation of further levels since the neighbors of nodes with high fractionality often have high fractionalities themselves and would be inserted first when further levels would have been sorted (which actually is not the case).
| scip | SCIP data structure |
| graph | LEVELGRAPH data structure |
| nbinvars | number of binary problem variables |
| ncurlevel | number of nodes of the current level |
| u | source node |
| vals | values of the binary variables in the current LP relaxation |
| vars | problem variables |
| sepadata | separator data structure |
| nnewlevel | number of nodes of the next level |
| inlevelgraph | nodes in new graph corr. to old graph (-1 if unassigned) |
| level | number of current level |
| newlevel | array of nodes of the next level |
| success | FALSE, iff memory reallocation fails |
Definition at line 1546 of file sepa_oddcycle.c.
References BMSclearMemoryArray, checkArraySizesHeur(), FALSE, findShortestPathToRoot(), MAX, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPfeasCeil(), SCIPfreeBufferArray, SCIPisFeasIntegral(), SCIPsortDownRealInt(), SCIPvarGetCliques(), SCIPvarGetNCliques(), SCIPvarGetProbindex(), and TRUE.
Referenced by addNextLevelCliques(), and createNextLevel().
|
static |
Find shortest path from start node to root
We perform a BFS to find the shortest path to the root. D stores the distance to the start node, P stores the partent nodes in the shortest path tree (-1 if node has not been reached).
| scip | SCIP data structure |
| scale | scaling factor for edge weights |
| graph | LEVELGRAPH data structure |
| startnode | start node for path search |
| distance | distances of searched nodes from root |
| queue | node queue for path search |
| inQueue | whether node is in the queue |
| parentTree | parent tree (-1 if no parent) |
Definition at line 1749 of file sepa_oddcycle.c.
References blockRootPath(), FALSE, SCIP_OKAY, and TRUE.
Referenced by insertSortedRootNeighbors(), and separateHeur().
|
static |
Block shortest path
We traverse the shortest path found by findShortestPathToRoot() and block all neighbors (in the original graph) of nodes in the path, i.e., we set blocked to TRUE. We do not block neighbors of the root node, since they have to be used. For the start node we only block nodes on the previous layers,
| scip | SCIP data structure |
| graph | LEVELGRAPH data structure |
| startnode | start node |
| inlevelgraph | nodes in new graph corr. to old graph (-1 if unassigned) |
| blocked | whether node is blocked |
| parentTree | parent tree |
| root | root of the current level graph |
Definition at line 1839 of file sepa_oddcycle.c.
References findUnblockedShortestPathToRoot(), SCIP_OKAY, and TRUE.
Referenced by findShortestPathToRoot(), and separateHeur().
|
static |
Find shortest path from root to target node
We perform a BFS to find the shortest path from the root. The only difference to findShortestPathToRoot() is that we avoid nodes that are blocked.
| scip | SCIP data structure |
| scale | scaling factor for edge weights |
| graph | LEVELGRAPH data structure |
| startnode | start node for path search |
| distance | distances of searched nodes from root |
| queue | node queue for path search |
| inQueue | whether node is in the queue |
| parentTreeBackward | parent tree (-1 if no parent) |
| root | root of the current level graph |
| blocked | whether nodes can be used |
Definition at line 1928 of file sepa_oddcycle.c.
References createNextLevel(), FALSE, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, and TRUE.
Referenced by blockRootPath(), and separateHeur().
|
static |
create next level of level graph for odd cycle separation
| scip | SCIP data structure |
| sepadata | separator data structure |
| vars | problem variables |
| vals | values of the binary variables in the current LP relaxation |
| graph | LEVELGRAPH data structure |
| level | number of current level |
| inlevelgraph | flag array if node is already inserted in level graph |
| curlevel | array of nodes of the current level |
| ncurlevel | number of nodes of the current level |
| newlevel | array of nodes of the next level |
| nnewlevel | number of nodes of the next level |
| success | FALSE, iff memory reallocation fails |
Definition at line 2047 of file sepa_oddcycle.c.
References addArc(), addNextLevelCliques(), checkArraySizesHeur(), insertSortedRootNeighbors(), SCIP_CALL, SCIP_OKAY, separateHeur(), and TRUE.
Referenced by findUnblockedShortestPathToRoot(), and separateHeur().
|
static |
The heuristic method for finding odd cycles by Hoffman, Padberg uses a level graph which is constructed as follows: First we choose a node (i.e. a variable of the problem or its negated) as root and assign it to level 0 (and no other node is assigned to level 0). All neighbors of the root are assigned to level 1 and the arcs between are added.
In general: All neighbors of nodes in level i that are assigned to level i+1, if they do not already appear in levels <= i. All arcs between nodes in level i and their neighbors are added.
In the construction we only take nodes that are contained in the fractional graph, i.e., their current LP values are not integral.
Since SCIP stores implications between original and negated variables, the level graph has at most twice the number of fractional binary variables of the problem.
Since the implication graph of SCIP is (normally) incomplete, it is possible to use arcs between an original variable and its negated to obtain more cycles which are valid but not found due to missing links.
| scip | SCIP data structure |
| sepa | separator |
| sepadata | separator data structure |
| sol | given primal solution |
| result | pointer to store the result of the separation call |
Definition at line 2224 of file sepa_oddcycle.c.
References blockRootPath(), BMSclearMemoryArray, checkArraySizesGLS(), cleanCycle(), createNextLevel(), DIJKSTRA_UNUSED, GraphData::dijkstragraph, FALSE, findShortestPathToRoot(), findUnblockedShortestPathToRoot(), generateOddCycleCut(), GraphData::levelgraph, MAXIMAL_FRACTIONALITY, MAXIMAL_LPVALUE, MINIMAL_FRACTIONALITY, MINIMAL_LPVALUE, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPABORT, SCIPallocBufferArray, SCIPceil(), SCIPerrorMessage, SCIPfreeBufferArray, SCIPgetSolVal(), SCIPgetVarsData(), SCIPisFeasIntegral(), SCIPisStopped(), SCIPsortDownRealPtr(), SCIPsortRealPtr(), SCIPvarGetNCliques(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarIsBinary(), TRUE, UNSORTED, and GraphData::usegls.
Referenced by createNextLevel(), and SCIP_DECL_SEPAEXECLP().
|
static |
memory reallocation method (the graph is normally very dense, so we dynamically allocate only the memory we need)
| scip | SCIP data structure |
| maxarcs | maximal size of graph->head and graph->weight |
| arraysize | current size of graph->head and graph->weight |
| graph | Dijkstra Graph data structure |
| success | FALSE, iff memory reallocation fails |
Definition at line 2716 of file sepa_oddcycle.c.
References addGLSCliques(), DIJKSTRA_UNUSED, FALSE, DIJKSTRA_Graph::head, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetRealParam(), SCIPisInfinity(), SCIPisStopped(), SCIPreallocBufferArray, and DIJKSTRA_Graph::weight.
Referenced by addGLSCliques(), separateGLS(), and separateHeur().
|
static |
add implications from cliques of the given node
| scip | SCIP data structure |
| sepadata | separator data structure |
| vars | problem variables |
| varsidx | index of current variable inside the problem variables |
| dijkindex | index of current variable inside the Dijkstra Graph |
| vals | value of the variables in the given solution |
| nbinvars | number of binary problem variables |
| ncliques | number of cliques of the current node |
| graph | Dijkstra Graph data structure |
| narcs | current number of arcs inside the Dijkstra Graph |
| maxarcs | maximal number of arcs inside the Dijkstra Graph |
| original | TRUE, iff variable is a problem variable |
| emptygraph | TRUE, iff there is no arc in the implication graph of the binary variables of SCIP |
| arraysize | current size of graph->head and graph->weight |
| success | FALSE, iff memory reallocation fails |
Definition at line 2794 of file sepa_oddcycle.c.
References checkArraySizesGLS(), FALSE, DIJKSTRA_Graph::head, MAX, DIJKSTRA_Graph::maxweight, DIJKSTRA_Graph::minweight, narcs, DIJKSTRA_Graph::outcnt, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPfeasCeil(), SCIPisFeasIntegral(), SCIPvarGetCliques(), SCIPvarGetProbindex(), separateGLS(), and DIJKSTRA_Graph::weight.
Referenced by checkArraySizesGLS(), and separateGLS().
|
static |
The classical method for finding odd cycles by Groetschel, Lovasz, Schrijver uses a bipartite graph which contains in each partition a node for every node in the original graph. All arcs uv of the original graph are copied to arcs from u of the first partition to v' of the second partition and from u' of the second partition to v of the first partition. A Dijkstra algorithm is used to find a path from a node x to its copy x', if existing. The nodes in the original graph corresponding to the nodes on the path form an odd cycle.
Since SCIP stores implications between original and negated variables, our original graph has at most twice the number of binary variables of the problem. By creating the bipartite graph we gain 4 segments of the graph:
I - nodes of the original variables in the first bipartition
II - nodes of the negated variables in the first bipartition
III - nodes of the original variables in the second bipartition
IV - nodes of the negated variables in the second bipartition
The length of every segment if the number of binary variables in the original problem.
Since the implication graph of SCIP is (normally) incomplete, it is possible to use arcs between an original variable and its negated to obtain more cycles which are valid but not found due to missing links.
| scip | SCIP data structure |
| sepa | separator |
| sepadata | separator data structure |
| sol | given primal solution |
| result | pointer to store the result of the separation call |
Definition at line 2953 of file sepa_oddcycle.c.
References addGLSCliques(), DIJKSTRA_Graph::arcs, BMSclearMemoryArray, checkArraySizesGLS(), cleanCycle(), DIJKSTRA_FARAWAY, DIJKSTRA_UNUSED, GraphData::dijkstragraph, dijkstraGraphIsValid(), dijkstraPairCutoff(), dijkstraPairCutoffIgnore(), FALSE, generateOddCycleCut(), DIJKSTRA_Graph::head, GraphData::levelgraph, MAXIMAL_FRACTIONALITY, MAXIMAL_LPVALUE, DIJKSTRA_Graph::maxweight, MINIMAL_FRACTIONALITY, MINIMAL_LPVALUE, DIJKSTRA_Graph::minweight, narcs, DIJKSTRA_Graph::nodes, DIJKSTRA_Graph::outbeg, DIJKSTRA_Graph::outcnt, SCIP_Bool, SCIP_CALL, SCIP_DECL_SEPACOPY(), SCIP_INVALIDDATA, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIP_VERBLEVEL_HIGH, SCIPABORT, SCIPallocBufferArray, SCIPceil(), SCIPdebugMsg, SCIPerrorMessage, SCIPfreeBufferArray, SCIPgetNLPs(), SCIPgetProbName(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPisFeasIntegral(), SCIPisStopped(), SCIPsnprintf(), SCIPsortDownRealPtr(), SCIPsortRealPtr(), SCIPsplitFilename(), SCIPvarGetNCliques(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarIsBinary(), SCIPverbMessage(), SCIPwriteCliqueGraph(), TRUE, UNSORTED, GraphData::usegls, and DIJKSTRA_Graph::weight.
Referenced by addGLSCliques(), and SCIP_DECL_SEPAEXECLP().
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 3473 of file sepa_oddcycle.c.
References SCIP_CALL, SCIP_DECL_SEPAFREE(), SCIP_OKAY, SCIPincludeSepaOddcycle(), SCIPsepaGetName(), and SEPA_NAME.
Referenced by separateGLS().
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 3488 of file sepa_oddcycle.c.
References SCIP_DECL_SEPAINIT(), SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), and SCIPsepaSetData().
Referenced by SCIP_DECL_SEPACOPY().
|
static |
initialization method of separator (called after problem was transformed)
Definition at line 3504 of file sepa_oddcycle.c.
References SCIP_DECL_SEPAINITSOL(), SCIP_OKAY, and SCIPsepaGetData().
Referenced by SCIP_DECL_SEPAFREE().
|
static |
solving process initialization method of separator (called when branch and bound process is about to begin)
Definition at line 3522 of file sepa_oddcycle.c.
References SCIP_DECL_SEPAEXECLP(), SCIP_OKAY, and SCIPsepaGetData().
Referenced by SCIP_DECL_SEPAINIT().
|
static |
LP solution separation method of separator
Definition at line 3540 of file sepa_oddcycle.c.
References SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIPdebug, SCIPdebugMsg, SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetNBinVars(), SCIPgetNCliques(), SCIPgetNCutsFoundRound(), SCIPgetNImplications(), SCIPgetNLPBranchCands(), SCIPincludeSepaOddcycle(), SCIPnodeGetNumber(), SCIPsepaGetData(), SCIPsepaGetNCallsAtNode(), SCIPsepaGetTime(), separateGLS(), and separateHeur().
Referenced by SCIP_DECL_SEPAINITSOL().