73#define SEPA_NAME "oddcycle"
74#define SEPA_DESC "odd cycle separator"
75#define SEPA_PRIORITY -15000
77#define SEPA_MAXBOUNDDIST 1.0
78#define SEPA_USESSUBSCIP FALSE
79#define SEPA_DELAY FALSE
83#define DEFAULT_SCALEFACTOR 1000
84#define DEFAULT_USEGLS TRUE
85#define DEFAULT_LIFTODDCYCLES FALSE
86#define DEFAULT_REPAIRCYCLES TRUE
87#define DEFAULT_ADDSELFARCS TRUE
88#define DEFAULT_INCLUDETRIANGLES TRUE
89#define DEFAULT_MULTIPLECUTS FALSE
90#define DEFAULT_ALLOWMULTIPLECUTS TRUE
91#define DEFAULT_LPLIFTCOEF FALSE
93#define DEFAULT_RECALCLIFTCOEF TRUE
94#define DEFAULT_MAXSEPACUTS 5000
95#define DEFAULT_MAXSEPACUTSROOT 5000
96#define DEFAULT_PERCENTTESTVARS 0
97#define DEFAULT_OFFSETTESTVARS 100
98#define DEFAULT_MAXCUTSROOT 1
99#define DEFAULT_SORTSWITCH 3
100#define DEFAULT_MAXREFERENCE 0
101#define DEFAULT_MAXROUNDS 10
102#define DEFAULT_MAXROUNDSROOT 10
103#define DEFAULT_MAXNLEVELS 20
104#define DEFAULT_MAXPERNODESLEVEL 100
105#define DEFAULT_OFFSETNODESLEVEL 10
106#define DEFAULT_SORTROOTNEIGHBORS TRUE
107#define DEFAULT_MAXCUTSLEVEL 50
108#define DEFAULT_MAXUNSUCESSFULL 3
109#define DEFAULT_CUTTHRESHOLD -1
133 unsigned int maxnodes;
134 unsigned int maxarcs;
135 unsigned int nlevels;
143 unsigned int* weightForward;
144 unsigned int* weightBackward;
145 unsigned int sizeForward;
146 unsigned int sizeBackward;
149 unsigned int* sourceAdj;
150 unsigned int* targetAdj;
151 unsigned int* weightAdj;
152 unsigned int* levelAdj;
153 unsigned int sizeAdj;
190 unsigned int oldncuts;
193 SCIP_Bool multiplecuts;
195 SCIP_Bool allowmultiplecuts;
196 SCIP_Bool liftoddcycles;
197 SCIP_Bool addselfarcs;
199 SCIP_Bool repaircycles;
201 SCIP_Bool includetriangles;
202 unsigned int* mapping;
203 SCIP_Bool lpliftcoef;
205 SCIP_Bool recalcliftcoef;
208 int maxsepacutsround;
211 SCIP_Bool sortrootneighbors;
214 int maxpernodeslevel;
215 int offsetnodeslevel;
216 unsigned int maxlevelsize;
226 SCIP_Longint lastnode;
248 unsigned int counter;
329 if( dijkstragraph->
outcnt[
a] == 0 || dijkstragraph->
outcnt[
b] == 0 )
344 if( (levelgraph->beginForward[
a] != -1 || levelgraph->beginBackward[
a] != -1)
345 && (levelgraph->beginForward[
b] != -1 || levelgraph->beginBackward[
b] != -1) )
347 assert(levelgraph->level[
a] <= levelgraph->nlevels);
348 assert(levelgraph->level[
b] <= levelgraph->nlevels);
351 if( levelgraph->level[
a] > levelgraph->level[
b] + 1
352 || levelgraph->level[
b] > levelgraph->level[
a] + 1 )
355 assert(levelgraph->level[
a] == levelgraph->level[
b]
356 || levelgraph->level[
a]+1 == levelgraph->level[
b]
357 || levelgraph->level[
a] == levelgraph->level[
b]+1);
360 if( levelgraph->level[
a] == levelgraph->level[
b]+1 )
362 if( levelgraph->beginBackward[
a] >= 0 )
364 i = (
unsigned int) levelgraph->beginBackward[
a];
365 while( levelgraph->targetBackward[
i] != -1 )
367 if( levelgraph->targetBackward[
i] == (
int)
b )
373 else if( levelgraph->level[
a] == levelgraph->level[
b]-1 )
375 if( levelgraph->beginForward[
a] >= 0 )
377 i = (
unsigned int) levelgraph->beginForward[
a];
378 while( levelgraph->targetForward[
i] != -1 )
380 if( levelgraph->targetForward[
i] == (
int)
b )
388 assert(levelgraph->level[
a] == levelgraph->level[
b]);
389 assert(levelgraph->level[
a] > 0);
393 i = (
unsigned int) levelgraph->beginAdj[
a];
394 assert(
i >= levelgraph->levelAdj[levelgraph->level[
a]]);
398 if( levelgraph->targetAdj[
i] ==
b )
402 if( levelgraph->sourceAdj[
i] == 0 && levelgraph->targetAdj[
i] == 0 )
405 assert(levelgraph->sourceAdj[
i] < levelgraph->targetAdj[
i]);
411 i = (
unsigned int) levelgraph->beginAdj[
b];
412 assert(
i >= levelgraph->levelAdj[levelgraph->level[
b]]);
416 if( levelgraph->targetAdj[
i] ==
a )
420 if( levelgraph->sourceAdj[
i] == 0 && levelgraph->targetAdj[
i] == 0 )
423 assert(levelgraph->sourceAdj[
i] < levelgraph->targetAdj[
i]);
439 unsigned int ncliques;
485 for(
i = 0;
i < ncliques; ++
i )
623 checkBlocking((
unsigned int) (
j-1), (
unsigned int)
j, (
unsigned int) (
j+1),
i,
cycle,
ncyclevars,
vars,
nbinvars,
lifted,
nlifted,
graphdata,
myi);
625 checkBlocking(
ncyclevars-2,
ncyclevars-1, 0,
i,
cycle,
ncyclevars,
vars,
nbinvars,
lifted,
nlifted,
graphdata,
myi);
626 checkBlocking(
ncyclevars-1, 0, 1,
i,
cycle,
ncyclevars,
vars,
nbinvars,
lifted,
nlifted,
graphdata,
myi);
665 while(
j < (
int)
end )
961 SCIP_CALL(
liftOddCycleCut(
scip, &
nlifted,
lifted,
liftcoef,
sepadata,
graphdata,
vars,
nbinvars,
startnode,
pred,
ncyclevars, vals,
result) );
1044 SCIP_Bool infeasible;
1086 unsigned int*
incut,
1091 SCIP_Bool repaircycles,
1092 SCIP_Bool allowmultiplecuts,
1110 if(
incut[
x] && !allowmultiplecuts )
1188 unsigned int*
chain;
1261 SCIP_Real memorylimit;
1301 *size = 2 * (*size);
1344 unsigned int weight,
1350 if( graph->level[v] == level+1 )
1352 graph->targetForward[graph->lastF] = (int) v;
1353 graph->weightForward[graph->lastF] = weight;
1356 if( graph->lastF == graph->sizeForward )
1366 assert(graph->level[v] == level || graph->level[v] == level-1);
1369 if( graph->level[v] == level-1 )
1371 graph->targetBackward[graph->lastB] = (int) v;
1372 graph->weightBackward[graph->lastB] = weight;
1376 if( graph->lastB == graph->sizeBackward )
1386 assert(graph->level[v] == level);
1391 graph->sourceAdj[graph->levelAdj[level+1]+*
nAdj] =
u;
1392 graph->targetAdj[graph->levelAdj[level+1]+*
nAdj] = v;
1393 graph->weightAdj[graph->levelAdj[level+1]+*
nAdj] = weight;
1397 if( graph->levelAdj[level+1]+*
nAdj == graph->sizeAdj )
1400 &(graph->sourceAdj), &(graph->targetAdj),
success) );
1431 unsigned int ncliques;
1485 for(
j = 0;
j < ncliques; ++
j )
1498 unsigned int weight;
1525 graph->level[v] = level+1;
1533 if(
inlevelgraph[v] && (graph->level[v] == level+1 || graph->level[v] == level || graph->level[v] == level-1))
1601 SCIP_Real* sortvals;
1607 unsigned int ncliques;
1649 for(
j = 0;
j < ncliques; ++
j )
1704 for(
j = 0;
j < graph->maxnodes; ++
j )
1712 sortvals[
k] =
MIN(1.0 - vals[
j], vals[
j]);
1737 graph->level[v] = level + 1;
1745 graph->targetForward[graph->lastF] = (int) v;
1750 graph->weightForward[graph->lastF] = (
unsigned int)
MAX(
tmp,
sepadata->maxreference);
1756 graph->weightForward[graph->lastF] = (
unsigned int)
MAX(
tmp,
sepadata->maxreference);
1760 if( graph->lastF == graph->sizeForward )
1788 unsigned int* distance,
1789 unsigned int* queue,
1813 for(
i = 0;
i < graph->maxnodes; ++
i )
1815 distance[
i] = 2 * (graph->nnodes) * (
unsigned) scale;
1834 assert(graph->beginBackward[
u] >= 0);
1835 i = (
unsigned int) graph->beginBackward[
u];
1836 for( v = graph->targetBackward[
i]; v >= 0; v = graph->targetBackward[++
i] )
1839 d = distance[
u] + graph->weightBackward[
i];
1842 if(
d < distance[v] )
1851 queue[
endQueue] = (
unsigned int) v;
1908 i = (
unsigned int) graph->beginForward[
u];
1909 for( v = graph->targetForward[
i]; v >= 0; v = graph->targetForward[++
i] )
1916 i = (
unsigned int) graph->beginBackward[
u];
1917 for( v = graph->targetBackward[
i]; v >= 0; v = graph->targetBackward[++
i] )
1925 for(
i = graph->levelAdj[graph->level[
u]];
i < graph->levelAdj[graph->level[
u]+1]; ++
i )
1927 assert(graph->sourceAdj[
i] < graph->targetAdj[
i]);
1928 assert(graph->level[graph->sourceAdj[
i]] == graph->level[graph->targetAdj[
i]]);
1931 if( graph->sourceAdj[
i] ==
u )
1935 if( graph->targetAdj[
i] ==
u )
1947 assert(graph->beginBackward[
u] > 0);
1948 i = (
unsigned int) graph->beginBackward[
u];
1949 for( v = graph->targetBackward[
i]; v >= 0; v = graph->targetBackward[++
i] )
1968 unsigned int* distance,
1969 unsigned int* queue,
2003 for(
i = 0;
i < graph->maxnodes; ++
i )
2005 distance[
i] = 2 * (graph->nnodes) * (
unsigned)scale;
2026 assert(graph->beginBackward[
u] >= 0);
2027 i = (
unsigned int) graph->beginBackward[
u];
2028 for( v = graph->targetBackward[
i]; v >= 0; v = graph->targetBackward[++
i] )
2030 if(
blocked[v] && v != (
int) root)
2034 d = distance[
u] + graph->weightBackward[
i];
2037 if(
d < distance[v] )
2046 queue[
endQueue] = (
unsigned int) v;
2125 assert(graph->maxnodes % 2 == 0);
2139 assert(graph->level[
u] == level);
2140 assert(graph->beginForward[
u] < 0);
2141 assert(graph->beginBackward[
u] < 0);
2142 assert(graph->beginAdj[
u] < 0);
2155 graph->beginForward[
u] = (int) graph->lastF;
2156 graph->beginBackward[
u] = (int) graph->lastB;
2157 graph->beginAdj[
u] = (int) (graph->levelAdj[level+1] +
nAdj);
2170 graph->level[
negated] = level+1;
2179 || (graph->level[
negated] == level) || (graph->level[
negated] == level + 1)) )
2189 if( graph->nlevels == 0 &&
sepadata->sortrootneighbors )
2203 assert(graph->lastB > (
unsigned int) graph->beginBackward[
u] || graph->nlevels == 0 );
2206 assert(graph->lastF > 0);
2209 graph->targetForward[graph->lastF] = -1;
2211 if( graph->lastF == graph->sizeForward )
2219 graph->targetBackward[graph->lastB] = -1;
2221 if( graph->lastB == graph->sizeBackward )
2231 graph->sourceAdj[graph->levelAdj[level+1]+
nAdj] = 0;
2232 graph->targetAdj[graph->levelAdj[level+1]+
nAdj] = 0;
2234 graph->levelAdj[level+2] = graph->levelAdj[level+1]+
nAdj;
2273 unsigned int*
incut;
2284 unsigned int* queue;
2288 unsigned int* distance;
2372 vals[
i] =
MIN(1.0 - vals[
i], vals[
i]);
2384 vals[
i] =
MIN(1.0 - vals[
i], vals[
i]);
2422 graph.sizeForward = 100 * graph.maxnodes;
2423 graph.sizeBackward = 100 * graph.maxnodes;
2424 graph.sizeAdj = 100 * graph.maxnodes;
2501 for(
j = 0;
j < graph.maxnodes; ++
j)
2503 graph.beginForward[
j] = -1;
2504 graph.beginBackward[
j] = -1;
2505 graph.beginAdj[
j] = -1;
2517 graph.levelAdj[0] = 0;
2523 graph.levelAdj[graph.nlevels+1] = 0;
2540 if( graph.nlevels > 0 && (
sepadata->includetriangles || graph.nlevels > 1) )
2542 unsigned int maxcutslevel;
2547 maxcutslevel = (
unsigned int)
sepadata->maxcutslevel;
2548 maxcutslevel = (
unsigned int)
MIN((
int) maxcutslevel, (int)
ncutsroot -
sepadata->maxcutsroot);
2549 maxcutslevel = (
unsigned int)
MIN((
int) maxcutslevel,
sepadata->maxsepacutsround + (int)
sepadata->oldncuts - (
int)
sepadata->ncuts);
2552 for(
j = graph.levelAdj[graph.nlevels+1];
j < graph.levelAdj[graph.nlevels+2]
2562 assert(graph.sourceAdj[
j] < graph.targetAdj[
j]);
2571 while(
u != graph.sourceAdj[
j] )
2580 for(
k = 0;
k < graph.nnodes; ++
k )
2611 u = graph.targetAdj[
j];
2630 while(
success &&
u != graph.sourceAdj[
j] )
2647 pred[
u] = graph.targetAdj[
j];
2658 unsigned int oldncuts;
2696 && graph.nlevels < (
unsigned int)
sepadata->maxnlevels
2706 if(
i == graph.maxnodes )
2754 unsigned int maxarcs,
2755 unsigned int* arraysize,
2760 SCIP_Real memorylimit;
2774 additional = (
MIN(maxarcs, 2 * (*arraysize)) - (*arraysize)) * ((
int)
sizeof(*(graph->
head)));
2775 additional += (
MIN(maxarcs, 2 * (*arraysize)) - (*arraysize)) * ((
int)
sizeof(*(graph->
weight)));
2793 *arraysize = 2*(*arraysize);
2836 unsigned int ncliques,
2838 unsigned int*
narcs,
2839 unsigned int maxarcs,
2842 unsigned int* arraysize,
2870 for(
k = 0;
k < ncliques; ++
k )
2947 if( *arraysize == *
narcs )
2998 unsigned int*
incut;
3008 unsigned int ncliques;
3011 unsigned int arraysize;
3013 unsigned int maxarcs;
3016 unsigned long long cutoff;
3020 unsigned long long* dist;
3022 unsigned int*
entry;
3023 unsigned int*
order;
3028 unsigned int*
pred2;
3104 vals[
i] =
MIN(1.0 - vals[
i], vals[
i]);
3116 vals[
i] =
MIN(1.0 - vals[
i], vals[
i]);
3169 arraysize = 100 * graph.
nodes;
3180 for(
i = 0;
i <
MIN(arraysize, maxarcs); ++
i )
3259 if( arraysize ==
narcs )
3273 if( arraysize ==
narcs )
3302 if( arraysize ==
narcs )
3318 if( arraysize ==
narcs )
3336#ifdef SCIP_ODDCYCLE_WRITEGRAPH
3463 SCIP_CALL(
generateOddCycleCut(
scip, sepa,
sol,
vars,
nbinvars,
startnode,
pred2,
ncyclevars,
incut, vals,
sepadata, &
graphdata,
result) );
3547 for( v = 0; v <
nvars; ++v )
3560 SCIPdebugMsg(
scip,
"skipping separator: not enough fractional variables\n");
3567 SCIPdebugMsg(
scip,
"skipping separator: not enough implications present\n");
3607 SCIPdebugMsg(
scip,
"using level graph heuristic for finding odd cycles\n");
3761 "Should the search method by Groetschel, Lovasz, Schrijver be used? Otherwise use levelgraph method by Hoffman, Padberg.",
3765 "Should odd cycle cuts be lifted?",
3769 "maximal number of oddcycle cuts separated per separation round",
3773 "maximal number of oddcycle cuts separated per separation round in the root node",
3778 "maximal number of oddcycle separation rounds per node (-1: unlimited)",
3782 "maximal number of oddcycle separation rounds in the root node (-1: unlimited)",
3786 "factor for scaling of the arc-weights",
3790 "add links between a variable and its negated",
3794 "try to repair violated cycles with double appearance of a variable",
3798 "separate triangles found as 3-cycles or repaired larger cycles",
3802 "Even if a variable is already covered by a cut, still try it as start node for a cycle search?",
3806 "Even if a variable is already covered by a cut, still allow another cut to cover it too?",
3810 "Choose lifting candidate by coef*lpvalue or only by coef?",
3814 "Calculate lifting coefficient of every candidate in every step (or only if its chosen)?",
3818 "use sorted variable array (unsorted(0), maxlp(1), minlp(2), maxfrac(3), minfrac(4))",
3822 "sort level of the root neighbors by fractionality (maxfrac)",
3826 "percentage of variables to try the chosen method on [0-100]",
3830 "offset of variables to try the chosen method on (additional to the percentage of testvars)",
3834 "percentage of nodes allowed in the same level of the level graph [0-100]",
3838 "offset of nodes allowed in the same level of the level graph (additional to the percentage of levelnodes)",
3842 "maximal number of levels in level graph",
3846 "maximal number of oddcycle cuts generated per chosen variable as root of the level graph",
3850 "maximal number of oddcycle cuts generated in every level of the level graph",
3854 "minimal weight on an edge (in level graph or bipartite graph)",
3858 "number of unsuccessful calls at current node",
3862 "maximal number of other cuts s.t. separation is applied (-1 for direct call)",
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)
DIJKSTRA_Bool dijkstraGraphIsValid(const DIJKSTRA_GRAPH *G)
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)
Definitions for Disjkstra's shortest path algorithm.
void SCIPsplitFilename(char *filename, char **path, char **name, char **extension, char **compression)
SCIP_Bool SCIPisStopped(SCIP *scip)
const char * SCIPgetProbName(SCIP *scip)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
int SCIPgetNBinVars(SCIP *scip)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
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)
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
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)
int SCIPgetNLPBranchCands(SCIP *scip)
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPreallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
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)
void SCIProwChgRank(SCIP_ROW *row, int rank)
SCIP_RETCODE SCIPchgRowRhs(SCIP *scip, SCIP_ROW *row, SCIP_Real rhs)
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)
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa,)
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
SCIP_Real SCIPsepaGetTime(SCIP_SEPA *sepa)
SCIP_RETCODE SCIPsetSepaInit(SCIP *scip, SCIP_SEPA *sepa,)
SCIP_RETCODE SCIPsetSepaInitsol(SCIP *scip, SCIP_SEPA *sepa,)
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa,)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
int SCIPgetNImplications(SCIP *scip)
int SCIPgetNCutsFoundRound(SCIP *scip)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_RETCODE SCIPwriteCliqueGraph(SCIP *scip, const char *fname, SCIP_Bool writenodeweights)
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
int SCIPvarGetProbindex(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
int SCIPgetNCliques(SCIP *scip)
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
SCIP_RETCODE SCIPincludeSepaOddcycle(SCIP *scip)
void SCIPsortRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
void SCIPsortDownRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
assert(minobj< SCIPgetCutoffbound(scip))
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
public methods for implications, variable bounds, and cliques
public methods for LP management
public methods for message output
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for separators
public methods for branch and bound tree
public methods for problem variables
public methods for branching rule plugins and branching
public methods for cuts and aggregation rows
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for separator plugins
public methods for solutions
public methods for querying solving statistics
public methods for the branch-and-bound tree
public methods for SCIP variables
static SCIP_RETCODE blockRootPath(SCIP *scip, LEVELGRAPH *graph, unsigned int startnode, SCIP_Bool *inlevelgraph, SCIP_Bool *blocked, int *parentTree, unsigned int root)
#define DEFAULT_SORTROOTNEIGHBORS
static SCIP_Bool isNeighbor(SCIP_VAR **vars, unsigned int nbinvars, GRAPHDATA *graphdata, unsigned int a, unsigned int b)
static SCIP_RETCODE separateOddCycles(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, int depth, SCIP_RESULT *result)
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 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 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)
#define DEFAULT_REPAIRCYCLES
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)
#define DEFAULT_MAXCUTSROOT
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 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 separateHeur(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_RESULT *result)
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 findShortestPathToRoot(SCIP *scip, int scale, LEVELGRAPH *graph, unsigned int startnode, unsigned int *distance, unsigned int *queue, SCIP_Bool *inQueue, int *parentTree)
#define DEFAULT_MAXROUNDSROOT
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)
#define DEFAULT_SCALEFACTOR
#define DEFAULT_MAXNLEVELS
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 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)
#define DEFAULT_ALLOWMULTIPLECUTS
#define DEFAULT_RECALCLIFTCOEF
#define DEFAULT_MAXCUTSLEVEL
#define DEFAULT_MAXSEPACUTSROOT
#define DEFAULT_LPLIFTCOEF
#define DEFAULT_MAXPERNODESLEVEL
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)
#define SEPA_MAXBOUNDDIST
#define DEFAULT_INCLUDETRIANGLES
#define DEFAULT_MULTIPLECUTS
#define DEFAULT_SORTSWITCH
#define DEFAULT_MAXSEPACUTS
#define DEFAULT_MAXUNSUCESSFULL
#define DEFAULT_OFFSETTESTVARS
#define DEFAULT_MAXROUNDS
static SCIP_RETCODE separateGLS(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_RESULT *result)
struct levelGraph LEVELGRAPH
static SCIP_RETCODE checkArraySizesGLS(SCIP *scip, unsigned int maxarcs, unsigned int *arraysize, DIJKSTRA_GRAPH *graph, SCIP_Bool *success)
#define DEFAULT_PERCENTTESTVARS
#define DEFAULT_ADDSELFARCS
#define DEFAULT_OFFSETNODESLEVEL
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)
#define DEFAULT_MAXREFERENCE
#define DEFAULT_CUTTHRESHOLD
#define DEFAULT_LIFTODDCYCLES
DIJKSTRA_GRAPH * dijkstragraph
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE
struct SCIP_SepaData SCIP_SEPADATA
#define SCIP_DECL_SEPAINITSOL(x)
#define SCIP_DECL_SEPAEXECSOL(x)
#define SCIP_DECL_SEPAEXECLP(x)
#define SCIP_DECL_SEPAFREE(x)
#define SCIP_DECL_SEPACOPY(x)
#define SCIP_DECL_SEPAINIT(x)
@ SCIP_VARTYPE_CONTINUOUS