SCIP
Solving Constraint Integer Programs
sepa_oddcycle.c File Reference
Detailed Description
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 "blockmemshell/memory.h"#include "dijkstra/dijkstra.h"#include "scip/pub_implics.h"#include "scip/pub_lp.h"#include "scip/pub_message.h"#include "scip/pub_misc.h"#include "scip/pub_misc_sort.h"#include "scip/pub_sepa.h"#include "scip/pub_tree.h"#include "scip/pub_var.h"#include "scip/scip_branch.h"#include "scip/scip_cut.h"#include "scip/scip_general.h"#include "scip/scip_lp.h"#include "scip/scip_mem.h"#include "scip/scip_message.h"#include "scip/scip_numerics.h"#include "scip/scip_param.h"#include "scip/scip_prob.h"#include "scip/scip_sepa.h"#include "scip/scip_sol.h"#include "scip/scip_solvingstats.h"#include "scip/scip_tree.h"#include "scip/scip_var.h"#include "scip/sepa_oddcycle.h"Go to the source code of this file.
Data Structures | |
| struct | GraphData |
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_RETCODE | separateOddCycles (SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, int depth, 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) |
| static | SCIP_DECL_SEPAEXECSOL (sepaExecsolOddcycle) |
| SCIP_RETCODE | SCIPincludeSepaOddcycle (SCIP *scip) |
Macro Definition Documentation
◆ SEPA_NAME
| #define SEPA_NAME "oddcycle" |
Definition at line 73 of file sepa_oddcycle.c.
◆ SEPA_DESC
| #define SEPA_DESC "odd cycle separator" |
Definition at line 74 of file sepa_oddcycle.c.
◆ SEPA_PRIORITY
| #define SEPA_PRIORITY -15000 |
Definition at line 75 of file sepa_oddcycle.c.
◆ SEPA_FREQ
| #define SEPA_FREQ -1 |
Definition at line 76 of file sepa_oddcycle.c.
◆ SEPA_MAXBOUNDDIST
| #define SEPA_MAXBOUNDDIST 1.0 |
Definition at line 77 of file sepa_oddcycle.c.
◆ SEPA_USESSUBSCIP
| #define SEPA_USESSUBSCIP FALSE |
does the separator use a secondary SCIP instance?
Definition at line 78 of file sepa_oddcycle.c.
◆ SEPA_DELAY
| #define SEPA_DELAY FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 79 of file sepa_oddcycle.c.
◆ DEFAULT_SCALEFACTOR
| #define DEFAULT_SCALEFACTOR 1000 |
factor for scaling of the arc-weights in the Dijkstra algorithm
Definition at line 83 of file sepa_oddcycle.c.
◆ DEFAULT_USEGLS
| #define DEFAULT_USEGLS TRUE |
use GLS method, otherwise HP method
Definition at line 84 of file sepa_oddcycle.c.
◆ DEFAULT_LIFTODDCYCLES
| #define DEFAULT_LIFTODDCYCLES FALSE |
lift odd cycle cuts
Definition at line 85 of file sepa_oddcycle.c.
◆ DEFAULT_REPAIRCYCLES
| #define DEFAULT_REPAIRCYCLES TRUE |
try to repair violated cycles in which a variable and its negated appear
Definition at line 86 of file sepa_oddcycle.c.
◆ DEFAULT_ADDSELFARCS
| #define DEFAULT_ADDSELFARCS TRUE |
add links between a variable and its negated
Definition at line 87 of file sepa_oddcycle.c.
◆ DEFAULT_INCLUDETRIANGLES
| #define DEFAULT_INCLUDETRIANGLES TRUE |
separate triangles (3-cliques) found as 3-cycles or repaired larger cycles
Definition at line 88 of file sepa_oddcycle.c.
◆ DEFAULT_MULTIPLECUTS
| #define DEFAULT_MULTIPLECUTS FALSE |
still try variable as start, even if it is already covered by a cut
Definition at line 89 of file sepa_oddcycle.c.
◆ DEFAULT_ALLOWMULTIPLECUTS
| #define DEFAULT_ALLOWMULTIPLECUTS TRUE |
allow another inequality to use variable, even if it is already covered
Definition at line 90 of file sepa_oddcycle.c.
◆ DEFAULT_LPLIFTCOEF
| #define DEFAULT_LPLIFTCOEF FALSE |
TRUE: choose lifting candidate with highest value of coefficient*lpvalue FALSE: choose lifting candidate with highest coefficient
Definition at line 92 of file sepa_oddcycle.c.
◆ DEFAULT_RECALCLIFTCOEF
| #define DEFAULT_RECALCLIFTCOEF TRUE |
whether lifting coefficients should be recomputed
Definition at line 93 of file sepa_oddcycle.c.
◆ DEFAULT_MAXSEPACUTS
| #define DEFAULT_MAXSEPACUTS 5000 |
maximal number of oddcycle cuts separated per separation round
Definition at line 94 of file sepa_oddcycle.c.
◆ DEFAULT_MAXSEPACUTSROOT
| #define DEFAULT_MAXSEPACUTSROOT 5000 |
maximal number of oddcycle cuts separated per separation round in root node
Definition at line 95 of file sepa_oddcycle.c.
◆ DEFAULT_PERCENTTESTVARS
| #define DEFAULT_PERCENTTESTVARS 0 |
percent of variables to try the chosen method on [0-100]
Definition at line 96 of file sepa_oddcycle.c.
◆ DEFAULT_OFFSETTESTVARS
| #define DEFAULT_OFFSETTESTVARS 100 |
offset of variables to try the chosen method on
Definition at line 97 of file sepa_oddcycle.c.
◆ DEFAULT_MAXCUTSROOT
| #define DEFAULT_MAXCUTSROOT 1 |
maximal number of oddcycle cuts generated per root of the levelgraph
Definition at line 98 of file sepa_oddcycle.c.
◆ DEFAULT_SORTSWITCH
| #define DEFAULT_SORTSWITCH 3 |
unsorted (0), maxlp (1), minlp (2), maxfrac (3), minfrac (4)
Definition at line 99 of file sepa_oddcycle.c.
◆ DEFAULT_MAXREFERENCE
| #define DEFAULT_MAXREFERENCE 0 |
minimal weight on an edge (in level graph or Dijkstra graph)
Definition at line 100 of file sepa_oddcycle.c.
◆ DEFAULT_MAXROUNDS
| #define DEFAULT_MAXROUNDS 10 |
maximal number of rounds pre node
Definition at line 101 of file sepa_oddcycle.c.
◆ DEFAULT_MAXROUNDSROOT
| #define DEFAULT_MAXROUNDSROOT 10 |
maximal number of rounds in the root node
Definition at line 102 of file sepa_oddcycle.c.
◆ DEFAULT_MAXNLEVELS
| #define DEFAULT_MAXNLEVELS 20 |
maximal number of levels in level graph
Definition at line 103 of file sepa_oddcycle.c.
◆ DEFAULT_MAXPERNODESLEVEL
| #define DEFAULT_MAXPERNODESLEVEL 100 |
maximal percentage of nodes allowed in one level of the levelgraph [0-100]
Definition at line 104 of file sepa_oddcycle.c.
◆ DEFAULT_OFFSETNODESLEVEL
| #define DEFAULT_OFFSETNODESLEVEL 10 |
additional offset of nodes allowed in one level of the levelgraph
Definition at line 105 of file sepa_oddcycle.c.
◆ DEFAULT_SORTROOTNEIGHBORS
| #define DEFAULT_SORTROOTNEIGHBORS TRUE |
sort neighbors of the root in the level graph
Definition at line 106 of file sepa_oddcycle.c.
◆ DEFAULT_MAXCUTSLEVEL
| #define DEFAULT_MAXCUTSLEVEL 50 |
maximal number of cuts produced per level
Definition at line 107 of file sepa_oddcycle.c.
◆ DEFAULT_MAXUNSUCESSFULL
| #define DEFAULT_MAXUNSUCESSFULL 3 |
maximal number of unsuccessful calls at each node
Definition at line 108 of file sepa_oddcycle.c.
◆ DEFAULT_CUTTHRESHOLD
| #define DEFAULT_CUTTHRESHOLD -1 |
maximal number of other cuts s.t. separation is applied (-1 for direct call)
Definition at line 109 of file sepa_oddcycle.c.
Typedef Documentation
◆ LEVELGRAPH
| typedef struct levelGraph LEVELGRAPH |
Definition at line 156 of file sepa_oddcycle.c.
◆ SORTTYPE
Definition at line 174 of file sepa_oddcycle.c.
◆ GRAPHDATA
Definition at line 183 of file sepa_oddcycle.c.
Enumeration Type Documentation
◆ sorttype
| 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 166 of file sepa_oddcycle.c.
Function Documentation
◆ isNeighbor()
|
static |
using the level graph (if possible) or Dijkstra graph data structure (depending on the used method) we determine whether two nodes are adjacent
- Parameters
-
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 306 of file sepa_oddcycle.c.
References a, b, GraphData::dijkstragraph, FALSE, DIJKSTRA_Graph::head, GraphData::levelgraph, NULL, DIJKSTRA_Graph::outbeg, DIJKSTRA_Graph::outcnt, SCIP_Bool, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPvarGetCliques(), SCIPvarGetNCliques(), SCIPvarGetProbindex(), TRUE, and GraphData::usegls.
Referenced by checkBlocking(), and getCoef().
◆ checkBlocking()
|
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.
- Parameters
-
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 519 of file sepa_oddcycle.c.
References a, b, FALSE, isNeighbor(), and NULL.
Referenced by getCoef().
◆ getCoef()
|
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)
- Parameters
-
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 572 of file sepa_oddcycle.c.
References checkBlocking(), isNeighbor(), NULL, and SCIPfloor().
Referenced by liftOddCycleCut().
◆ 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.)
- Parameters
-
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 709 of file sepa_oddcycle.c.
References GraphData::dijkstragraph, FALSE, getCoef(), GraphData::levelgraph, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisStopped(), TRUE, and GraphData::usegls.
Referenced by generateOddCycleCut().
◆ generateOddCycleCut()
|
static |
add the inequality corresponding to the given odd cycle to the LP (if violated) after lifting it (if requested by user flag)
- Parameters
-
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 881 of file sepa_oddcycle.c.
References GraphData::dijkstragraph, FALSE, GraphData::levelgraph, liftOddCycleCut(), NULL, 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 separateGLS(), and separateHeur().
◆ cleanCycle()
|
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
- Parameters
-
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 1082 of file sepa_oddcycle.c.
References a, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, TRUE, and x.
Referenced by separateGLS(), and separateHeur().
◆ checkArraySizesHeur()
|
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:
- Forward: sizeForward, targetForward, weightForward
- Backward: sizeBackward, targetBackward, weightBackward
- Adj (inner level edges): sizeAdj, sourceAdj, targetAdj, weightAdj
- Parameters
-
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 1250 of file sepa_oddcycle.c.
References FALSE, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPgetBoolParam(), SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetRealParam(), SCIPisInfinity(), SCIPisStopped(), and SCIPreallocBufferArray.
Referenced by addArc(), createNextLevel(), and insertSortedRootNeighbors().
◆ addArc()
|
static |
Add arc to level graph
- Parameters
-
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 1338 of file sepa_oddcycle.c.
References checkArraySizesHeur(), NULL, SCIP_CALL, and SCIP_OKAY.
Referenced by addNextLevelCliques(), and createNextLevel().
◆ addNextLevelCliques()
|
static |
add implications from cliques of the given node u
- See also
- createNextLevel()
- Parameters
-
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 1415 of file sepa_oddcycle.c.
References addArc(), FALSE, MAX, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPfeasCeil(), SCIPisFeasIntegral(), SCIPvarGetCliques(), SCIPvarGetNCliques(), SCIPvarGetProbindex(), and TRUE.
Referenced by createNextLevel().
◆ insertSortedRootNeighbors()
|
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:
- create flag array for binary variables and their negated and set their values FALSE
- iterate over the implication and clique neighbors of the root and set their flag array values to TRUE
- create variable array and insert all variables with flag value TRUE
- sort variable array by maximal fractionality
- add variables from sorted array to levelgraph until first level is full (or all variables are inserted)
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).
- Parameters
-
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 1580 of file sepa_oddcycle.c.
References BMSclearMemoryArray, checkArraySizesHeur(), FALSE, MAX, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPfeasCeil(), SCIPfreeBufferArray, SCIPisFeasIntegral(), SCIPsortDownRealInt(), SCIPvarGetCliques(), SCIPvarGetNCliques(), SCIPvarGetProbindex(), and TRUE.
Referenced by createNextLevel().
◆ findShortestPathToRoot()
|
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).
- Parameters
-
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 1783 of file sepa_oddcycle.c.
References FALSE, NULL, SCIP_OKAY, and TRUE.
Referenced by separateHeur().
◆ blockRootPath()
|
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,
- See also
- findShortestPathToRoot()
- Parameters
-
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 1874 of file sepa_oddcycle.c.
References NULL, SCIP_OKAY, and TRUE.
Referenced by separateHeur().
◆ findUnblockedShortestPathToRoot()
|
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.
- Parameters
-
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 1963 of file sepa_oddcycle.c.
References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, and TRUE.
Referenced by separateHeur().
◆ createNextLevel()
|
static |
create next level of level graph for odd cycle separation
- See also
- separateHeur()
- Parameters
-
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 2083 of file sepa_oddcycle.c.
References addArc(), addNextLevelCliques(), checkArraySizesHeur(), insertSortedRootNeighbors(), NULL, SCIP_CALL, SCIP_OKAY, and TRUE.
Referenced by separateHeur().
◆ 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.
- Parameters
-
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 2260 of file sepa_oddcycle.c.
References blockRootPath(), BMSclearMemoryArray, cleanCycle(), createNextLevel(), DIJKSTRA_UNUSED, GraphData::dijkstragraph, FALSE, findShortestPathToRoot(), findUnblockedShortestPathToRoot(), generateOddCycleCut(), GraphData::levelgraph, MAXIMAL_FRACTIONALITY, MAXIMAL_LPVALUE, MIN, MINIMAL_FRACTIONALITY, MINIMAL_LPVALUE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, 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 separateOddCycles().
◆ checkArraySizesGLS()
|
static |
memory reallocation method (the graph is normally very dense, so we dynamically allocate only the memory we need)
- Parameters
-
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 2752 of file sepa_oddcycle.c.
References DIJKSTRA_UNUSED, FALSE, DIJKSTRA_Graph::head, MIN, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetRealParam(), SCIPisInfinity(), SCIPisStopped(), SCIPreallocBufferArray, and DIJKSTRA_Graph::weight.
Referenced by addGLSCliques(), and separateGLS().
◆ addGLSCliques()
|
static |
add implications from cliques of the given node
- Parameters
-
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 2828 of file sepa_oddcycle.c.
References checkArraySizesGLS(), FALSE, DIJKSTRA_Graph::head, MAX, DIJKSTRA_Graph::maxweight, DIJKSTRA_Graph::minweight, narcs, NULL, DIJKSTRA_Graph::outcnt, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPfeasCeil(), SCIPisFeasIntegral(), SCIPvarGetCliques(), SCIPvarGetProbindex(), and DIJKSTRA_Graph::weight.
Referenced by separateGLS().
◆ 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.
- Parameters
-
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 2987 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, MIN, MINIMAL_FRACTIONALITY, MINIMAL_LPVALUE, DIJKSTRA_Graph::minweight, narcs, DIJKSTRA_Graph::nodes, NULL, DIJKSTRA_Graph::outbeg, DIJKSTRA_Graph::outcnt, SCIP_Bool, SCIP_CALL, 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 separateOddCycles().
◆ separateOddCycles()
|
static |
separation method
- Parameters
-
scip SCIP data structure sepa separator sol given primal solution depth current depth result pointer to store the result of the separation call
Definition at line 3503 of file sepa_oddcycle.c.
References NULL, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIPdebug, SCIPdebugMsg, SCIPgetCurrentNode(), SCIPgetNBinVars(), SCIPgetNCliques(), SCIPgetNCutsFoundRound(), SCIPgetNImplications(), SCIPgetNLPBranchCands(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPisFeasIntegral(), SCIPnodeGetNumber(), SCIPsepaGetData(), SCIPsepaGetNCallsAtNode(), SCIPsepaGetTime(), separateGLS(), and separateHeur().
Referenced by SCIP_DECL_SEPAEXECLP(), and SCIP_DECL_SEPAEXECSOL().
◆ SCIP_DECL_SEPACOPY()
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 3634 of file sepa_oddcycle.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaOddcycle(), SCIPsepaGetName(), and SEPA_NAME.
◆ SCIP_DECL_SEPAFREE()
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 3649 of file sepa_oddcycle.c.
References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), and SCIPsepaSetData().
◆ SCIP_DECL_SEPAINIT()
|
static |
initialization method of separator (called after problem was transformed)
Definition at line 3665 of file sepa_oddcycle.c.
References NULL, SCIP_OKAY, and SCIPsepaGetData().
◆ SCIP_DECL_SEPAINITSOL()
|
static |
solving process initialization method of separator (called when branch and bound process is about to begin)
Definition at line 3683 of file sepa_oddcycle.c.
References NULL, SCIP_OKAY, and SCIPsepaGetData().
◆ SCIP_DECL_SEPAEXECLP()
|
static |
LP solution separation method of separator
Definition at line 3701 of file sepa_oddcycle.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPsepaGetName(), SEPA_NAME, and separateOddCycles().
◆ SCIP_DECL_SEPAEXECSOL()
|
static |
arbitrary primal solution separation method of separator
Definition at line 3715 of file sepa_oddcycle.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPsepaGetName(), SEPA_NAME, and separateOddCycles().