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;
202 unsigned int* mapping;
208 int maxsepacutsround;
214 int maxpernodeslevel;
215 int offsetnodeslevel;
216 unsigned int maxlevelsize;
244 unsigned int startnode
247 unsigned int varsindex;
248 unsigned int counter;
256 varsindex = startnode;
269 for( varsindex = pred[startnode]; varsindex != startnode; varsindex = pred[varsindex] )
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;
440 unsigned int ncliquevars;
472 varfixingtemp = originalb;
474 originalb = originala;
476 originala = varfixingtemp;
485 for(
i = 0;
i < ncliques; ++
i )
492 assert(cliquevars !=
NULL || ncliquevars == 0);
493 assert(cliquevals !=
NULL || ncliquevars == 0);
495 for( j = 0; j < ncliquevars; ++j )
500 if( (cliquevals[j] ==
FALSE && originalb ==
TRUE) || ( cliquevals[j] ==
TRUE && originalb ==
FALSE ) )
525 unsigned int ncyclevars,
528 unsigned int* lifted,
529 unsigned int* nlifted,
540 assert(ncyclevars % 2 == 1);
550 while( (myi[
a] || myi[
b] || myi[
c]) && k < *nlifted )
576 unsigned int ncyclevars,
579 unsigned int* lifted,
580 unsigned int* nlifted,
593 assert(ncyclevars % 2 == 1);
604 for( j = 1; j < (int)ncyclevars-1; ++j )
621 for( j = 1; j < (int)ncyclevars-1; ++j )
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);
636 while( myi[end] && end > 0 )
641 assert(k == ncyclevars || end > 0);
646 assert(ncyclevars % 2 == 1);
647 coef = (ncyclevars-1)/2;
656 assert(coef <= (ncyclevars-1)/2);
665 while( j < (
int)end )
668 while( j<(
int)end && ! myi[j] )
672 while( j<(
int)end && myi[j] )
682 assert(coef <= (ncyclevars-1)/2);
711 unsigned int* nlifted,
712 unsigned int* lifted,
713 unsigned int* liftcoef,
718 unsigned int startnode,
720 unsigned int ncyclevars,
730 unsigned int negated;
732 unsigned int liftround;
743 assert(ncyclevars % 2 == 1);
755 cycle[0] = startnode;
758 while(
i != startnode )
783 for(
i = 0;
i < ncyclevars; ++
i )
785 candList[cycle[
i]] =
FALSE;
791 candList[negated] =
FALSE;
803 if(
sepadata->recalcliftcoef || liftround == 0 )
810 assert(coef[
i] <= (ncyclevars-1)/2);
852 candList[negated] =
FALSE;
855 lifted[*nlifted] = (
unsigned int)
bestcand;
856 liftcoef[*nlifted] = coef[
bestcand];
887 unsigned int startnode,
889 unsigned int ncyclevars,
898 unsigned int negatedcount;
899 unsigned int negated;
902 unsigned int nlifted;
903 unsigned int* lifted;
904 unsigned int* liftcoef;
914 assert(ncyclevars % 2 == 1);
947 if( ncyclevars < 5 && ! sepadata->includetriangles )
961 SCIP_CALL(
liftOddCycleCut(
scip, &nlifted, lifted, liftcoef,
sepadata, graphdata,
vars,
nbinvars, startnode, pred, ncyclevars, vals,
result) );
973 while(
i != startnode )
990 incut[negated] =
TRUE;
1001 incut[startnode] =
TRUE;
1011 incut[negated] =
TRUE;
1015 for(
i = 0;
i < nlifted; ++
i)
1030 negatedcount += liftcoef[
i];
1086 unsigned int* incut,
1088 unsigned int startnode,
1090 unsigned int* ncyclevars,
1110 if( incut[
x] && !allowmultiplecuts )
1126 if( incycle[
x] || (incycle[negx] && !repaircycles) )
1133 if( !incycle[negx] )
1159 if( negx == startnode )
1169 if( pred[negx] ==
x )
1175 while( pred[
a] != negx )
1188 unsigned int* chain;
1189 unsigned int nchain;
1198 while( pred[
a] != negx )
1216 pred[
a] = chain[nchain-1];
1222 for(
i = nchain-1;
i > 0; --
i )
1223 pred[chain[
i]] = chain[
i-1];
1230 assert(!incycle[
x] && incycle[negx]);
1231 incycle[negx] =
FALSE;
1255 unsigned int** weightArray,
1256 unsigned int** sourceAdjArray,
1257 unsigned int** targetAdjArray,
1262 unsigned int additional;
1274 additional =
MIN(graph->maxarcs + graph->maxnodes - *size, *size) * ((int)
sizeof(**weightArray));
1275 if( targetArray !=
NULL )
1277 additional +=
MIN(graph->maxarcs + graph->maxnodes - *size, *size) * ((int)
sizeof(**targetArray));
1281 additional +=
MIN(graph->maxarcs + graph->maxnodes - *size, *size) * ((int)
sizeof(**sourceAdjArray));
1282 additional +=
MIN(graph->maxarcs + graph->maxnodes - *size, *size) * ((int)
sizeof(**targetAdjArray));
1294 if( (avoidmemout && memorylimit <= additional/1048576.0) ||
SCIPisStopped(
scip) )
1301 *size = 2 * (*size);
1304 if( targetArray !=
NULL )
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 )
1359 &(graph->weightForward),
NULL,
NULL, success) );
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 )
1379 &(graph->weightBackward),
NULL,
NULL, success) );
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) );
1424 unsigned int* newlevel,
1425 unsigned int* nnewlevel,
1431 unsigned int ncliques;
1433 unsigned int varsidx;
1435 unsigned int ncliquevars;
1458 assert(u < graph->maxnodes);
1485 for( j = 0; j < ncliques; ++j )
1491 assert(cliquevars !=
NULL || ncliquevars == 0);
1492 assert(cliquevals !=
NULL || ncliquevars == 0);
1494 for( k = 0; k < ncliquevars; ++k )
1498 unsigned int weight;
1510 if( cliquevals[k] ==
FALSE )
1515 assert(v < graph->maxnodes);
1522 if( !inlevelgraph[v] && (*nnewlevel) <=
sepadata->maxlevelsize )
1525 graph->level[v] = level+1;
1526 inlevelgraph[v] =
TRUE;
1527 newlevel[*nnewlevel] = v;
1533 if( inlevelgraph[v] && (graph->level[v] == level+1 || graph->level[v] == level || graph->level[v] == level-1))
1543 weight = (
unsigned int)
MAX(tmp,
sepadata->maxreference);
1549 weight = (
unsigned int)
MAX(tmp,
sepadata->maxreference);
1584 unsigned int ncurlevel,
1589 unsigned int* nnewlevel,
1592 unsigned int* newlevel,
1598 unsigned int nneighbors;
1604 unsigned int varsidx;
1607 unsigned int ncliques;
1609 unsigned int ncliquevars;
1649 for( j = 0; j < ncliques; ++j )
1655 assert(cliquevars !=
NULL || ncliquevars == 0);
1656 assert(cliquevals !=
NULL || ncliquevars == 0);
1658 for( k = 0; k < ncliquevars; ++k )
1668 if( kidx == varsidx )
1675 if( cliquevals[k] ==
TRUE )
1677 if ( ! isneighbor[kidx] )
1680 isneighbor[kidx] =
TRUE;
1686 if ( ! isneighbor[kidx +
nbinvars] )
1697 assert(! isneighbor[root]);
1704 for( j = 0; j < graph->maxnodes; ++j )
1711 neighbors[k] = (int) j;
1712 sortvals[k] =
MIN(1.0 - vals[j], vals[j]);
1725 for( j = 0; j < nneighbors && (*nnewlevel) <=
sepadata->maxlevelsize; ++j )
1729 v = (
unsigned int) neighbors[j];
1737 graph->level[v] = level + 1;
1738 inlevelgraph[v] =
TRUE;
1739 newlevel[*nnewlevel] = v;
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 )
1763 &(graph->weightForward),
NULL,
NULL, success) );
1787 unsigned int startnode,
1788 unsigned int* distance,
1789 unsigned int* queue,
1813 for(
i = 0;
i < graph->maxnodes; ++
i )
1815 distance[
i] = 2 * (graph->nnodes) * (
unsigned) scale;
1819 distance[startnode] = 0;
1824 queue[0] = startnode;
1827 while( startQueue <= endQueue )
1830 u = queue[startQueue];
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] )
1845 parentTree[v] = (int) u;
1851 queue[endQueue] = (
unsigned int) v;
1858 assert(parentTree[u] != -1);
1877 unsigned int startnode,
1901 assert(parentTree[root] >= 0);
1904 u = (
unsigned int) parentTree[root];
1905 while( u != startnode )
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] )
1924 assert(graph->level[u] > 0);
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 )
1933 blocked[graph->targetAdj[
i]] =
TRUE;
1935 if( graph->targetAdj[
i] == u )
1937 blocked[graph->sourceAdj[
i]] =
TRUE;
1942 u = (
unsigned int) parentTree[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] )
1967 unsigned int startnode,
1968 unsigned int* distance,
1969 unsigned int* queue,
1971 int* parentTreeBackward,
2003 for(
i = 0;
i < graph->maxnodes; ++
i )
2005 distance[
i] = 2 * (graph->nnodes) * (
unsigned)scale;
2007 parentTreeBackward[
i] = -1;
2011 distance[startnode] = 0;
2016 queue[0] = startnode;
2019 while( startQueue <= endQueue )
2022 u = queue[startQueue];
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] )
2040 parentTree[v] = (int) u;
2046 queue[endQueue] = (
unsigned int) v;
2056 transform[0] = (int) root;
2058 while(parentTree[v] >= 0)
2060 transform[
i] = parentTree[v];
2067 parentTreeBackward[transform[
i]] = transform[
i-1];
2091 unsigned int* curlevel,
2092 unsigned int ncurlevel,
2093 unsigned int* newlevel,
2094 unsigned int* nnewlevel,
2125 assert(graph->maxnodes % 2 == 0);
2131 for(
i = 0;
i < ncurlevel; ++
i )
2133 unsigned int negated;
2138 assert(u < graph->maxnodes);
2139 assert(graph->level[u] == level);
2140 assert(graph->beginForward[u] < 0);
2141 assert(graph->beginBackward[u] < 0);
2142 assert(graph->beginAdj[u] < 0);
2150 assert(negated < graph->maxnodes);
2155 graph->beginForward[u] = (int) graph->lastF;
2156 graph->beginBackward[u] = (int) graph->lastB;
2157 graph->beginAdj[u] = (int) (graph->levelAdj[level+1] + nAdj);
2167 if( !inlevelgraph[negated] && (*nnewlevel) <=
sepadata->maxlevelsize )
2170 graph->level[negated] = level+1;
2171 inlevelgraph[negated] =
TRUE;
2172 newlevel[*nnewlevel] = negated;
2175 assert( *nnewlevel >
sepadata->maxlevelsize || inlevelgraph[negated] );
2178 if( inlevelgraph[negated] && ((graph->level[negated] == level - 1)
2179 || (graph->level[negated] == level) || (graph->level[negated] == level + 1)) )
2189 if( graph->nlevels == 0 &&
sepadata->sortrootneighbors )
2192 sepadata, nnewlevel, inlevelgraph, level, newlevel, success) );
2197 newlevel, nnewlevel, &nAdj, success) );
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 )
2214 &(graph->weightForward),
NULL,
NULL, success) );
2219 graph->targetBackward[graph->lastB] = -1;
2221 if( graph->lastB == graph->sizeBackward )
2224 &(graph->weightBackward),
NULL,
NULL, success) );
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;
2277 unsigned int* curlevel;
2278 unsigned int* newlevel;
2279 unsigned int ncurlevel;
2280 unsigned int nnewlevel;
2284 unsigned int* queue;
2287 int* parentTreeBackward;
2288 unsigned int* distance;
2292 unsigned int maxroots;
2293 unsigned int rootcounter;
2294 unsigned int ncutsroot;
2295 unsigned int ncutslevel;
2312 assert(nscipbinvars >= 0);
2313 assert(nscipintvars >= 0);
2314 assert(nscipimplvars >= 0);
2316 nintegral = nscipbinvars + nscipintvars + nscipimplvars;
2317 assert(scipvars !=
NULL || ((nscipbinvars == 0) && (nscipintvars == 0) && (nscipimplvars == 0) && (nintegral == 0)));
2321 for (l = 0; l < nscipbinvars; ++l)
2322 vars[l] = scipvars[l];
2324 nbinvars = (
unsigned int) nscipbinvars;
2325 for (l = nscipbinvars; l < nintegral; ++l)
2372 vals[
i] =
MIN(1.0 - vals[
i], vals[
i]);
2384 vals[
i] =
MIN(1.0 - vals[
i], vals[
i]);
2419 graph.maxarcs = UINT_MAX;
2422 graph.sizeForward = 100 * graph.maxnodes;
2423 graph.sizeBackward = 100 * graph.maxnodes;
2424 graph.sizeAdj = 100 * graph.maxnodes;
2462 for(
i = (
unsigned int)
sepadata->lastroot;
i < graph.maxnodes && rootcounter < maxroots
2468 if( incut[
i] && !
sepadata->multiplecuts )
2501 for( j = 0; j < graph.maxnodes; ++j)
2503 graph.beginForward[j] = -1;
2504 graph.beginBackward[j] = -1;
2505 graph.beginAdj[j] = -1;
2506 inlevelgraph[j] =
FALSE;
2515 inlevelgraph[
i] =
TRUE;
2517 graph.levelAdj[0] = 0;
2523 graph.levelAdj[graph.nlevels+1] = 0;
2534 curlevel, ncurlevel, newlevel, &nnewlevel, &success) );
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]
2555 unsigned int ncyclevars;
2562 assert(graph.sourceAdj[j] < graph.targetAdj[j]);
2571 while( u != graph.sourceAdj[j] )
2573 assert(parentTree[u] != -1 && k <= graph.maxnodes);
2574 u = (
unsigned int) parentTree[u];
2580 for( k = 0; k < graph.nnodes; ++k )
2585 if( blocked[graph.targetAdj[j]] )
2590 graph.targetAdj[j], distance, queue, inQueue, parentTreeBackward,
i, blocked) );
2593 if( parentTreeBackward[graph.targetAdj[j]] < 0 )
2599 for( k = 0; k < 2 *
nbinvars; ++k )
2611 u = graph.targetAdj[j];
2614 while( success && u !=
i )
2617 pred[u] = (
unsigned int) parentTreeBackward[u];
2623 assert(parentTreeBackward[u] >= 0 || u ==
i);
2626 u = (
unsigned int) parentTreeBackward[u];
2630 while( success && u != graph.sourceAdj[j] )
2633 pred[u] = (
unsigned int) parentTree[u];
2640 u = (
unsigned int) parentTree[u];
2642 assert(!success || u == graph.sourceAdj[j]);
2647 pred[u] = graph.targetAdj[j];
2658 unsigned int oldncuts;
2669 if(oldncuts < sepadata->ncuts)
2690 for( j = 0; j < nnewlevel; ++j )
2691 curlevel[j] = newlevel[j];
2692 ncurlevel = nnewlevel;
2696 && graph.nlevels < (
unsigned int)
sepadata->maxnlevels
2697 && ncutsroot < (
unsigned int)
sepadata->maxcutsroot
2706 if(
i == graph.maxnodes )
2754 unsigned int maxarcs,
2755 unsigned int* arraysize,
2761 unsigned int additional;
2763 unsigned int oldarraysize;
2774 additional = (
MIN(maxarcs, 2 * (*arraysize)) - (*arraysize)) * ((
int)
sizeof(*(graph->
head)));
2775 additional += (
MIN(maxarcs, 2 * (*arraysize)) - (*arraysize)) * ((
int)
sizeof(*(graph->
weight)));
2792 oldarraysize = *arraysize;
2793 *arraysize = 2*(*arraysize);
2815 for( j = oldarraysize; j <
MIN(maxarcs,(*arraysize)); ++j )
2832 unsigned int varsidx,
2833 unsigned int dijkindex,
2836 unsigned int ncliques,
2838 unsigned int*
narcs,
2839 unsigned int maxarcs,
2842 unsigned int* arraysize,
2847 unsigned int neighindex;
2849 unsigned int ncliquevars;
2870 for( k = 0; k < ncliques; ++k )
2879 assert(cliquevars !=
NULL || ncliquevars == 0);
2880 assert(cliquevals !=
NULL || ncliquevars == 0);
2883 for( m = 0; m < ncliquevars; ++m )
2888 neighbor = cliquevars[m];
2894 if( neighindex == varsidx )
2947 if( *arraysize == *
narcs )
2955 ++(graph->
outcnt[dijkindex]);
2957 *emptygraph =
FALSE;
2998 unsigned int* incut;
3008 unsigned int ncliques;
3011 unsigned int arraysize;
3013 unsigned int maxarcs;
3014 unsigned int maxstarts;
3015 unsigned int startcounter;
3016 unsigned long long cutoff;
3018 unsigned int startnode;
3019 unsigned int endnode;
3020 unsigned long long* dist;
3022 unsigned int* entry;
3023 unsigned int* order;
3024 unsigned int dijkindex;
3028 unsigned int* pred2;
3044 assert(nscipbinvars >= 0);
3045 assert(nscipintvars >= 0);
3046 assert(nscipimplvars >= 0);
3048 nintegral = nscipbinvars + nscipintvars + nscipimplvars;
3049 assert(scipvars !=
NULL || ((nscipbinvars == 0) && (nscipintvars == 0) && (nscipimplvars == 0) && (nintegral == 0)));
3053 for (k = 0; k < nscipbinvars; ++k)
3054 vars[k] = scipvars[k];
3056 nbinvars = (
unsigned int) nscipbinvars;
3057 for (k = nscipbinvars; k < nintegral; ++k)
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 )
3198 for( dijkindex = 0; dijkindex < 2 *
nbinvars; ++dijkindex )
3201 graph.
outcnt[dijkindex] = 0;
3227 &
narcs, maxarcs, original, &emptygraph, &arraysize, &success) );
3259 if( arraysize ==
narcs )
3266 ++(graph.
outcnt[dijkindex]);
3273 if( arraysize ==
narcs )
3302 if( arraysize ==
narcs )
3318 if( arraysize ==
narcs )
3336#ifdef SCIP_ODDCYCLE_WRITEGRAPH
3361 && startcounter < maxstarts
3365 unsigned int ncyclevars;
3386 if( incut[startnode] && !
sepadata->multiplecuts )
3401 if ( dist[endnode] >=
cutoff )
3409 for( j = 0; j < 2 *
nbinvars; ++j )
3416 edgedirection =
TRUE;
3420 for( dijkindex = endnode; dijkindex != startnode && success; dijkindex = pred[dijkindex], edgedirection = !edgedirection )
3428 pred2[dijkindex - 2 *
nbinvars] = pred[dijkindex];
3435 &ncyclevars,
sepadata->repaircycles,
sepadata->allowmultiplecuts, &success) );
3443 pred2[dijkindex] = pred[dijkindex] - 2 *
nbinvars;
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");
3748 sepaExeclpOddcycle, sepaExecsolOddcycle,
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)",
#define DEFAULT_MAXSEPACUTSROOT
#define DEFAULT_MAXSEPACUTS
#define DEFAULT_MAXROUNDSROOT
#define DEFAULT_MAXROUNDS
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.
struct DIJKSTRA_Graph DIJKSTRA_GRAPH
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
#define SEPA_MAXBOUNDDIST
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)
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_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 DEFAULT_INCLUDETRIANGLES
#define DEFAULT_MULTIPLECUTS
#define DEFAULT_SORTSWITCH
#define DEFAULT_MAXUNSUCESSFULL
#define DEFAULT_OFFSETTESTVARS
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
struct GraphData GRAPHDATA
#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
struct SCIP_Clique SCIP_CLIQUE
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)
struct SCIP_Sepa SCIP_SEPA
#define SCIP_DECL_SEPACOPY(x)
#define SCIP_DECL_SEPAINIT(x)
@ SCIP_VARTYPE_CONTINUOUS