41 #define SEPA_NAME "oddcycle" 42 #define SEPA_DESC "odd cycle separator" 43 #define SEPA_PRIORITY -15000 45 #define SEPA_MAXBOUNDDIST 1.0 46 #define SEPA_USESSUBSCIP FALSE 47 #define SEPA_DELAY FALSE 51 #define DEFAULT_SCALEFACTOR 1000 52 #define DEFAULT_USEGLS TRUE 53 #define DEFAULT_LIFTODDCYCLES FALSE 54 #define DEFAULT_REPAIRCYCLES TRUE 55 #define DEFAULT_ADDSELFARCS TRUE 56 #define DEFAULT_INCLUDETRIANGLES TRUE 57 #define DEFAULT_MULTIPLECUTS FALSE 58 #define DEFAULT_ALLOWMULTIPLECUTS TRUE 59 #define DEFAULT_LPLIFTCOEF FALSE 61 #define DEFAULT_RECALCLIFTCOEF TRUE 62 #define DEFAULT_MAXSEPACUTS 5000 63 #define DEFAULT_MAXSEPACUTSROOT 5000 64 #define DEFAULT_PERCENTTESTVARS 0 65 #define DEFAULT_OFFSETTESTVARS 100 66 #define DEFAULT_MAXCUTSROOT 1 67 #define DEFAULT_SORTSWITCH 3 68 #define DEFAULT_MAXREFERENCE 0 69 #define DEFAULT_MAXROUNDS 10 70 #define DEFAULT_MAXROUNDSROOT 10 71 #define DEFAULT_MAXNLEVELS 20 72 #define DEFAULT_MAXPERNODESLEVEL 100 73 #define DEFAULT_OFFSETNODESLEVEL 10 74 #define DEFAULT_SORTROOTNEIGHBORS TRUE 75 #define DEFAULT_MAXCUTSLEVEL 50 76 #define DEFAULT_MAXUNSUCESSFULL 3 77 #define DEFAULT_CUTTHRESHOLD -1 101 unsigned int maxnodes;
102 unsigned int maxarcs;
103 unsigned int nlevels;
111 unsigned int* weightForward;
112 unsigned int* weightBackward;
113 unsigned int sizeForward;
114 unsigned int sizeBackward;
117 unsigned int* sourceAdj;
118 unsigned int* targetAdj;
119 unsigned int* weightAdj;
120 unsigned int* levelAdj;
121 unsigned int sizeAdj;
124 typedef struct levelGraph LEVELGRAPH;
148 LEVELGRAPH* levelgraph;
158 unsigned int oldncuts;
170 unsigned int* mapping;
176 int maxsepacutsround;
182 int maxpernodeslevel;
183 int offsetnodeslevel;
184 unsigned int maxlevelsize;
211 unsigned int nbinvars,
212 unsigned int startnode
215 unsigned int varsindex;
216 unsigned int counter;
218 assert(vars != NULL);
219 assert(pred != NULL);
220 assert(nbinvars > 0);
221 assert(startnode < 4*nbinvars);
224 varsindex = startnode;
227 if( varsindex < nbinvars || ( varsindex >= 2*nbinvars && varsindex < 3*nbinvars ) )
237 for( varsindex = pred[startnode]; varsindex != startnode; varsindex = pred[varsindex] )
239 if( varsindex < nbinvars || ( varsindex >= 2*nbinvars && varsindex < 3*nbinvars ) )
251 if( varsindex < nbinvars || ( varsindex >= 2*nbinvars && varsindex < 3*nbinvars ) )
276 unsigned int nbinvars,
284 assert(vars != NULL);
285 assert(nbinvars > 2);
286 assert(graphdata != NULL);
289 assert(a < 2*nbinvars);
290 assert(b < 2*nbinvars);
297 if( dijkstragraph->
outcnt[a] == 0 || dijkstragraph->
outcnt[b] == 0 )
301 for( i = dijkstragraph->
outbeg[a]; i < dijkstragraph->outbeg[a] + dijkstragraph->
outcnt[a]; ++i )
303 if( dijkstragraph->
head[i] == b + 2*nbinvars )
309 LEVELGRAPH* levelgraph = graphdata->
levelgraph;
312 if( (levelgraph->beginForward[a] != -1 || levelgraph->beginBackward[a] != -1)
313 && (levelgraph->beginForward[b] != -1 || levelgraph->beginBackward[b] != -1) )
315 assert(levelgraph->level[a] <= levelgraph->nlevels);
316 assert(levelgraph->level[b] <= levelgraph->nlevels);
319 if( levelgraph->level[a] > levelgraph->level[b] + 1
320 || levelgraph->level[b] > levelgraph->level[a] + 1 )
323 assert(levelgraph->level[a] == levelgraph->level[b]
324 || levelgraph->level[a]+1 == levelgraph->level[b]
325 || levelgraph->level[a] == levelgraph->level[b]+1);
328 if( levelgraph->level[a] == levelgraph->level[b]+1 )
330 if( levelgraph->beginBackward[a] >= 0 )
332 i = (
unsigned int) levelgraph->beginBackward[a];
333 while( levelgraph->targetBackward[i] != -1 )
335 if( levelgraph->targetBackward[i] == (
int)b )
341 else if( levelgraph->level[a] == levelgraph->level[b]-1 )
343 if( levelgraph->beginForward[a] >= 0 )
345 i = (
unsigned int) levelgraph->beginForward[a];
346 while( levelgraph->targetForward[i] != -1 )
348 if( levelgraph->targetForward[i] == (
int)b )
356 assert(levelgraph->level[a] == levelgraph->level[b]);
357 assert(levelgraph->level[a] > 0);
359 if( a < b && levelgraph->beginAdj[a] >= 0 )
361 i = (
unsigned int) levelgraph->beginAdj[a];
362 assert(i >= levelgraph->levelAdj[levelgraph->level[a]]);
364 while( i < levelgraph->levelAdj[levelgraph->level[a]+1] && levelgraph->sourceAdj[i] == a )
366 if( levelgraph->targetAdj[i] == b )
370 if( levelgraph->sourceAdj[i] == 0 && levelgraph->targetAdj[i] == 0 )
373 assert(levelgraph->sourceAdj[i] < levelgraph->targetAdj[i]);
377 if( b < a && levelgraph->beginAdj[b] >= 0 )
379 i = (
unsigned int) levelgraph->beginAdj[b];
380 assert(i >= levelgraph->levelAdj[levelgraph->level[b]]);
382 while( i < levelgraph->levelAdj[levelgraph->level[b]+1] && levelgraph->sourceAdj[i] == b )
384 if( levelgraph->targetAdj[i] == a )
388 if( levelgraph->sourceAdj[i] == 0 && levelgraph->targetAdj[i] == 0 )
391 assert(levelgraph->sourceAdj[i] < levelgraph->targetAdj[i]);
407 unsigned int ncliques;
408 unsigned int ncliquevars;
418 assert(a < nbinvars);
426 assert(b < nbinvars);
440 varfixingtemp = originalb;
442 originalb = originala;
444 originala = varfixingtemp;
451 assert(cliques != NULL || ncliques == 0);
453 for( i = 0; i < ncliques; ++i )
455 assert( cliques != NULL );
460 assert(cliquevars != NULL || ncliquevars == 0);
461 assert(cliquevals != NULL || ncliquevars == 0);
463 for( j = 0; j < ncliquevars; ++j )
465 assert( cliquevals != NULL && cliquevars != NULL );
468 if( (cliquevals[j] ==
FALSE && originalb ==
TRUE) || ( cliquevals[j] ==
TRUE && originalb ==
FALSE ) )
493 unsigned int ncyclevars,
495 unsigned int nbinvars,
496 unsigned int* lifted,
497 unsigned int* nlifted,
504 assert(a < ncyclevars);
505 assert(b < ncyclevars);
506 assert(c < ncyclevars);
507 assert(cycle != NULL);
508 assert(ncyclevars % 2 == 1);
509 assert(ncyclevars > 2);
510 assert(ncyclevars <= nbinvars);
511 assert(vars != NULL);
512 assert(nbinvars > 2);
513 assert(lifted != NULL);
514 assert(nlifted != NULL);
518 while( (myi[a] || myi[b] || myi[c]) && k < *nlifted )
522 if( !
isNeighbor(vars, nbinvars, graphdata, i, lifted[k])
523 &&
isNeighbor(vars, nbinvars, graphdata, cycle[a], lifted[k])
524 &&
isNeighbor(vars, nbinvars, graphdata, cycle[b], lifted[k])
525 &&
isNeighbor(vars, nbinvars, graphdata, cycle[c], lifted[k]) )
544 unsigned int ncyclevars,
546 unsigned int nbinvars,
547 unsigned int* lifted,
548 unsigned int* nlifted,
558 assert(scip != NULL);
559 assert(i < 2*nbinvars);
560 assert(cycle != NULL);
561 assert(ncyclevars % 2 == 1);
562 assert(ncyclevars > 2);
563 assert(ncyclevars <= 2*nbinvars);
564 assert(vars != NULL);
565 assert(nbinvars > 2);
566 assert(nlifted != NULL);
567 assert(lifted != NULL);
572 for( j = 1; j < (int)ncyclevars-1; ++j )
574 myi[j] =
isNeighbor(vars, nbinvars, graphdata, i, cycle[j-1]) &&
isNeighbor(vars, nbinvars, graphdata, i, cycle[j])
575 &&
isNeighbor(vars, nbinvars, graphdata, i, cycle[j+1]);
579 myi[0] =
isNeighbor(vars, nbinvars, graphdata, i, cycle[ncyclevars-1])
580 &&
isNeighbor(vars, nbinvars, graphdata, i, cycle[0])
581 &&
isNeighbor(vars, nbinvars, graphdata, i, cycle[1]);
582 myi[ncyclevars-1] =
isNeighbor(vars, nbinvars, graphdata, i, cycle[ncyclevars-2])
583 &&
isNeighbor(vars, nbinvars, graphdata, i, cycle[ncyclevars-1])
584 &&
isNeighbor(vars, nbinvars, graphdata, i, cycle[0]);
589 for( j = 1; j < (int)ncyclevars-1; ++j )
591 checkBlocking((
unsigned int) (j-1), (
unsigned int) j, (
unsigned int) (j+1), i, cycle, ncyclevars, vars, nbinvars, lifted, nlifted, graphdata, myi);
593 checkBlocking(ncyclevars-2, ncyclevars-1, 0, i, cycle, ncyclevars, vars, nbinvars, lifted, nlifted, graphdata, myi);
594 checkBlocking(ncyclevars-1, 0, 1, i, cycle, ncyclevars, vars, nbinvars, lifted, nlifted, graphdata, myi);
604 while( myi[end] && end > 0 )
609 assert(k == ncyclevars || end > 0);
614 assert(ncyclevars % 2 == 1);
615 coef = (ncyclevars-1)/2;
623 coef = (
unsigned int)
SCIPfloor(scip,(k+1.0)/2.0);
624 assert(coef <= (ncyclevars-1)/2);
633 while( j < (
int)end )
636 while( j<(
int)end && ! myi[j] )
640 while( j<(
int)end && myi[j] )
649 coef += (
unsigned int)
SCIPfloor(scip,(k+1.0)/2.0);
650 assert(coef <= (ncyclevars-1)/2);
679 unsigned int* nlifted,
680 unsigned int* lifted,
681 unsigned int* liftcoef,
685 unsigned int nbinvars,
686 unsigned int startnode,
688 unsigned int ncyclevars,
698 unsigned int negated;
700 unsigned int liftround;
703 assert(scip != NULL);
704 assert(graphdata != NULL);
707 assert(vars != NULL);
708 assert(nbinvars > 2);
709 assert(startnode < 2*nbinvars);
710 assert(pred != NULL);
711 assert(ncyclevars % 2 == 1);
712 assert(ncyclevars > 2);
713 assert(ncyclevars <= nbinvars);
714 assert(result != NULL);
715 assert(nlifted != NULL);
716 assert(lifted != NULL);
717 assert(liftcoef != NULL);
723 cycle[0] = startnode;
726 while( i != startnode )
732 assert(j == ncyclevars);
747 for( i = 0; i < 2*nbinvars; ++i )
751 for( i = 0; i < ncyclevars; ++i )
753 candList[cycle[i]] =
FALSE;
754 if( cycle[i] >= nbinvars )
755 negated = cycle[i] - nbinvars;
757 negated = cycle[i] + nbinvars;
758 assert(negated < 2*nbinvars);
759 candList[negated] =
FALSE;
768 while( bestcand >= 0 )
771 if( sepadata->recalcliftcoef || liftround == 0 )
773 for( i = 0; i < 2*nbinvars; ++i )
777 coef[i] =
getCoef(scip, i, cycle, ncyclevars, vars, nbinvars, lifted, nlifted, graphdata, myi);
778 assert(coef[i] <= (ncyclevars-1)/2);
786 for( i = 0; i < 2*nbinvars; ++i )
791 if( sepadata->lpliftcoef )
793 if( bestcand < 0 || coef[i]*vals[i] > coef[bestcand]*vals[bestcand] )
799 if( bestcand < 0 || coef[i] > coef[bestcand] )
808 if( !(sepadata->recalcliftcoef) )
809 coef[i] =
getCoef(scip, (
unsigned int) bestcand, cycle, ncyclevars, vars, nbinvars, lifted, nlifted, graphdata, myi);
810 assert(coef[bestcand] <= (ncyclevars-1)/2);
811 candList[bestcand] =
FALSE;
812 if( coef[bestcand] > 0 )
814 if( bestcand >= (
int)nbinvars )
815 negated = (
unsigned int) bestcand - nbinvars;
817 negated = (
unsigned int) bestcand + nbinvars;
818 assert(negated < 2*nbinvars);
820 candList[negated] =
FALSE;
822 assert(*nlifted < nbinvars-ncyclevars);
823 lifted[*nlifted] = (
unsigned int) bestcand;
824 liftcoef[*nlifted] = coef[bestcand];
854 unsigned int nbinvars,
855 unsigned int startnode,
857 unsigned int ncyclevars,
866 unsigned int negatedcount;
867 unsigned int negated;
870 unsigned int nlifted;
871 unsigned int* lifted;
872 unsigned int* liftcoef;
878 assert(scip != NULL);
879 assert(vars != NULL);
880 assert(startnode < 2*nbinvars);
881 assert(pred != NULL);
882 assert(ncyclevars % 2 == 1);
883 assert(ncyclevars <= nbinvars);
884 assert(incut != NULL);
885 assert(graphdata != NULL);
888 assert(result != NULL);
892 printCycle(vars, pred, nbinvars, startnode);
900 if( startnode < nbinvars )
906 negated = startnode - nbinvars;
907 assert(negated < nbinvars);
915 if( ncyclevars < 5 && ! sepadata->includetriangles )
925 if( sepadata->liftoddcycles )
929 SCIP_CALL(
liftOddCycleCut(scip, &nlifted, lifted, liftcoef, sepadata, graphdata, vars, nbinvars, startnode, pred, ncyclevars, vals, result) );
941 while( i != startnode )
943 assert(i < 2*nbinvars);
952 negated = i - nbinvars;
953 assert(negated < nbinvars);
958 incut[negated] =
TRUE;
962 assert(startnode == i);
965 if( startnode < nbinvars )
969 incut[startnode] =
TRUE;
973 negated = startnode - nbinvars;
974 assert(negated < nbinvars);
979 incut[negated] =
TRUE;
983 for( i = 0; i < nlifted; ++i)
985 assert(lifted != NULL);
986 assert(liftcoef != NULL);
987 if( lifted[i] < nbinvars )
989 assert(vars[lifted[i]] != NULL);
994 negated = lifted[i] - nbinvars;
995 assert(negated < nbinvars);
996 assert(vars[negated] != NULL);
998 negatedcount += liftcoef[i];
1017 ++sepadata->nliftedcuts;
1037 if( sepadata->liftoddcycles )
1054 unsigned int* incut,
1056 unsigned int startnode,
1057 unsigned int nbinvars,
1058 unsigned int* ncyclevars,
1066 assert(scip != NULL);
1067 assert(pred != NULL);
1068 assert(incycle != NULL);
1069 assert(incut != NULL);
1070 assert(ncyclevars != NULL);
1071 assert(*ncyclevars <= nbinvars);
1072 assert(success != NULL);
1075 assert(x < 2*nbinvars);
1078 if( incut[x] && !allowmultiplecuts )
1086 negx = x + nbinvars;
1088 negx = x - nbinvars;
1089 assert(negx < 2*nbinvars);
1094 if( incycle[x] || (incycle[negx] && !repaircycles) )
1101 if( !incycle[negx] )
1103 assert(!incycle[x]);
1127 if( negx == startnode )
1137 if( pred[negx] == x )
1143 while( pred[a] != negx )
1156 unsigned int* chain;
1157 unsigned int nchain;
1166 while( pred[a] != negx )
1184 pred[a] = chain[nchain-1];
1190 for( i = nchain-1; i > 0; --i )
1191 pred[chain[i]] = chain[i-1];
1198 assert(!incycle[x] && incycle[negx]);
1199 incycle[negx] =
FALSE;
1223 unsigned int** weightArray,
1224 unsigned int** sourceAdjArray,
1225 unsigned int** targetAdjArray,
1230 unsigned int additional;
1232 assert(scip != NULL);
1233 assert(graph != NULL);
1234 assert(size != NULL);
1235 assert(targetArray != NULL || (sourceAdjArray != NULL && targetAdjArray != NULL));
1236 assert(weightArray != NULL);
1237 assert(success != NULL);
1241 additional = MIN(graph->maxarcs + graph->maxnodes - *size, *size) * ((int)
sizeof(**weightArray));
1242 if( targetArray != NULL )
1244 additional += MIN(graph->maxarcs + graph->maxnodes - *size, *size) * ((int)
sizeof(**targetArray));
1248 additional += MIN(graph->maxarcs + graph->maxnodes - *size, *size) * ((int)
sizeof(**sourceAdjArray));
1249 additional += MIN(graph->maxarcs + graph->maxnodes - *size, *size) * ((int)
sizeof(**targetAdjArray));
1261 if( memorylimit <= additional/1048576.0 ||
SCIPisStopped(scip) )
1268 *size = 2 * (*size);
1271 if( targetArray != NULL )
1309 unsigned int weight,
1315 if( graph->level[v] == level+1 )
1317 graph->targetForward[graph->lastF] = (int) v;
1318 graph->weightForward[graph->lastF] = weight;
1321 if( graph->lastF == graph->sizeForward )
1324 &(graph->weightForward), NULL, NULL, success) );
1331 assert(graph->level[v] == level || graph->level[v] == level-1);
1334 if( graph->level[v] == level-1 )
1336 graph->targetBackward[graph->lastB] = (int) v;
1337 graph->weightBackward[graph->lastB] = weight;
1341 if( graph->lastB == graph->sizeBackward )
1344 &(graph->weightBackward), NULL, NULL, success) );
1351 assert(graph->level[v] == level);
1356 graph->sourceAdj[graph->levelAdj[level+1]+*nAdj] = u;
1357 graph->targetAdj[graph->levelAdj[level+1]+*nAdj] = v;
1358 graph->weightAdj[graph->levelAdj[level+1]+*nAdj] = weight;
1362 if( graph->levelAdj[level+1]+*nAdj == graph->sizeAdj )
1365 &(graph->sourceAdj), &(graph->targetAdj), success) );
1389 unsigned int* newlevel,
1390 unsigned int* nnewlevel,
1396 unsigned int ncliques;
1397 unsigned int nbinvars;
1398 unsigned int varsidx;
1400 unsigned int ncliquevars;
1406 assert(scip != NULL);
1407 assert(vars != NULL);
1408 assert(vals != NULL);
1409 assert(graph != NULL);
1410 assert(graph->targetForward != NULL);
1411 assert(graph->weightForward != NULL);
1412 assert(graph->targetBackward != NULL);
1413 assert(graph->weightBackward != NULL);
1414 assert(graph->sourceAdj != NULL);
1415 assert(graph->targetAdj != NULL);
1416 assert(graph->weightAdj != NULL);
1417 assert(inlevelgraph != NULL);
1418 assert(newlevel != NULL);
1419 assert(nnewlevel != NULL);
1420 assert(nAdj != NULL);
1421 assert(success != NULL);
1423 assert(u < graph->maxnodes);
1425 nbinvars = (graph->maxnodes)/2;
1437 varsidx = u - nbinvars;
1439 assert(varsidx < nbinvars);
1448 assert(cliques != NULL);
1450 for( j = 0; j < ncliques; ++j )
1456 assert(cliquevars != NULL || ncliquevars == 0);
1457 assert(cliquevals != NULL || ncliquevars == 0);
1459 for( k = 0; k < ncliquevars; ++k )
1463 unsigned int weight;
1465 assert( cliquevars != NULL && cliquevals != NULL );
1468 assert(l < nbinvars);
1475 if( cliquevals[k] ==
FALSE )
1480 assert(v < graph->maxnodes);
1487 if( !inlevelgraph[v] && (*nnewlevel) <= sepadata->maxlevelsize )
1490 graph->level[v] = level+1;
1491 inlevelgraph[v] =
TRUE;
1492 newlevel[*nnewlevel] = v;
1495 assert(*nnewlevel > sepadata->maxlevelsize || inlevelgraph[v]);
1498 if( inlevelgraph[v] && (graph->level[v] == level+1 || graph->level[v] == level || graph->level[v] == level-1))
1507 tmp = (int)
SCIPfeasCeil(scip, sepadata->scale * (1 - vals[varsidx] - vals[v]));
1508 weight = (
unsigned int)
MAX(tmp, sepadata->maxreference);
1513 tmp = (int)
SCIPfeasCeil(scip, sepadata->scale * (1.0 - (1.0 - vals[varsidx]) - vals[v]));
1514 weight = (
unsigned int)
MAX(tmp, sepadata->maxreference);
1548 unsigned int nbinvars,
1549 unsigned int ncurlevel,
1554 unsigned int* nnewlevel,
1557 unsigned int* newlevel,
1563 unsigned int nneighbors;
1569 unsigned int varsidx;
1572 unsigned int ncliques;
1574 unsigned int ncliquevars;
1586 nbinvars = (graph->maxnodes)/2;
1588 assert(ncurlevel == 1);
1592 if( root < nbinvars )
1601 varsidx = root - nbinvars;
1603 assert(varsidx < nbinvars);
1612 assert(cliques != NULL);
1614 for( j = 0; j < ncliques; ++j )
1620 assert(cliquevars != NULL || ncliquevars == 0);
1621 assert(cliquevals != NULL || ncliquevars == 0);
1623 for( k = 0; k < ncliquevars; ++k )
1627 assert( cliquevars != NULL && cliquevals != NULL );
1630 assert(kidx < nbinvars);
1633 if( kidx == varsidx )
1640 if( cliquevals[k] ==
TRUE )
1642 if ( ! isneighbor[kidx] )
1645 isneighbor[kidx] =
TRUE;
1650 assert(cliquevals[k] ==
FALSE);
1651 if ( ! isneighbor[kidx + nbinvars] )
1654 isneighbor[kidx+nbinvars] =
TRUE;
1662 assert(! isneighbor[root]);
1669 for( j = 0; j < graph->maxnodes; ++j )
1676 neighbors[k] = (int) j;
1677 sortvals[k] = MIN(1.0 - vals[j], vals[j]);
1681 assert(k == nneighbors);
1690 for( j = 0; j < nneighbors && (*nnewlevel) <= sepadata->maxlevelsize; ++j )
1694 v = (
unsigned int) neighbors[j];
1695 assert( v < 2 * nbinvars );
1698 assert(! inlevelgraph[v] || v == root+nbinvars || v == root-nbinvars);
1702 graph->level[v] = level + 1;
1703 inlevelgraph[v] =
TRUE;
1704 newlevel[*nnewlevel] = v;
1710 graph->targetForward[graph->lastF] = (int) v;
1714 tmp = (int)
SCIPfeasCeil(scip, sepadata->scale * (1.0 - vals[varsidx] - vals[v]));
1715 graph->weightForward[graph->lastF] = (
unsigned int)
MAX(tmp, sepadata->maxreference);
1719 assert( ! varfixing );
1720 tmp = (int)
SCIPfeasCeil(scip, sepadata->scale * (1.0 - (1.0 - vals[varsidx]) - vals[v]));
1721 graph->weightForward[graph->lastF] = (
unsigned int)
MAX(tmp, sepadata->maxreference);
1725 if( graph->lastF == graph->sizeForward )
1728 &(graph->weightForward), NULL, NULL, success) );
1752 unsigned int startnode,
1753 unsigned int* distance,
1754 unsigned int* queue,
1766 assert(scip != NULL);
1767 assert(graph != NULL);
1768 assert(graph->beginBackward != NULL);
1769 assert(graph->targetBackward != NULL);
1770 assert(graph->weightBackward != NULL);
1771 assert(distance != NULL);
1772 assert(queue != NULL);
1773 assert(inQueue != NULL);
1774 assert(parentTree != NULL);
1777 for( i = 0; i < graph->maxnodes; ++i )
1779 distance[i] = 2*(graph->nnodes)*scale;
1783 distance[startnode] = 0;
1788 queue[0] = startnode;
1791 while( startQueue <= endQueue )
1794 u = queue[startQueue];
1798 assert(graph->beginBackward[u] >= 0);
1799 i = (
unsigned int) graph->beginBackward[u];
1800 for( v = graph->targetBackward[i]; v >= 0; v = graph->targetBackward[++i] )
1803 d = distance[u] + graph->weightBackward[i];
1806 if( d < distance[v] )
1809 parentTree[v] = (int) u;
1815 queue[endQueue] = (
unsigned int) v;
1822 assert(parentTree[u] != -1);
1841 unsigned int startnode,
1852 assert(scip != NULL);
1853 assert(graph != NULL);
1854 assert(graph->level != NULL);
1855 assert(graph->beginForward != NULL);
1856 assert(graph->targetForward != NULL);
1857 assert(graph->beginBackward != NULL);
1858 assert(graph->targetBackward != NULL);
1859 assert(graph->sourceAdj != NULL);
1860 assert(graph->targetAdj != NULL);
1861 assert(inlevelgraph != NULL);
1862 assert(blocked != NULL);
1863 assert(parentTree != NULL);
1865 assert(parentTree[root] >= 0);
1868 u = (
unsigned int) parentTree[root];
1869 while( u != startnode )
1872 i = (
unsigned int) graph->beginForward[u];
1873 for( v = graph->targetForward[i]; v >= 0; v = graph->targetForward[++i] )
1875 assert(inlevelgraph[v]);
1880 i = (
unsigned int) graph->beginBackward[u];
1881 for( v = graph->targetBackward[i]; v >= 0; v = graph->targetBackward[++i] )
1883 assert(inlevelgraph[v]);
1888 assert(graph->level[u] > 0);
1889 for( i = graph->levelAdj[graph->level[u]]; i < graph->levelAdj[graph->level[u]+1]; ++i )
1891 assert(graph->sourceAdj[i] < graph->targetAdj[i]);
1892 assert(graph->level[graph->sourceAdj[i]] == graph->level[graph->targetAdj[i]]);
1895 if( graph->sourceAdj[i] == u )
1897 blocked[graph->targetAdj[i]] =
TRUE;
1899 if( graph->targetAdj[i] == u )
1901 blocked[graph->sourceAdj[i]] =
TRUE;
1906 u = (
unsigned int) parentTree[u];
1908 assert(u == startnode);
1911 assert(graph->beginBackward[u] > 0);
1912 i = (
unsigned int) graph->beginBackward[u];
1913 for( v = graph->targetBackward[i]; v >= 0; v = graph->targetBackward[++i] )
1931 unsigned int startnode,
1932 unsigned int* distance,
1933 unsigned int* queue,
1935 int* parentTreeBackward,
1949 assert(scip != NULL);
1950 assert(graph != NULL);
1951 assert(graph->beginBackward != NULL);
1952 assert(graph->targetBackward != NULL);
1953 assert(graph->weightBackward != NULL);
1954 assert(distance != NULL);
1955 assert(queue != NULL);
1956 assert(inQueue != NULL);
1962 assert(parentTree != NULL);
1963 assert(transform != NULL);
1966 for( i = 0; i < graph->maxnodes; ++i )
1968 distance[i] = 2*(graph->nnodes)*scale;
1970 parentTreeBackward[i] = -1;
1974 distance[startnode] = 0;
1979 queue[0] = startnode;
1982 while( startQueue <= endQueue )
1985 u = queue[startQueue];
1989 assert(graph->beginBackward[u] >= 0);
1990 i = (
unsigned int) graph->beginBackward[u];
1991 for( v = graph->targetBackward[i]; v >= 0; v = graph->targetBackward[++i] )
1993 if( blocked[v] && v != (
int) root)
1997 d = distance[u] + graph->weightBackward[i];
2000 if( d < distance[v] )
2003 parentTree[v] = (int) u;
2009 queue[endQueue] = (
unsigned int) v;
2019 transform[0] = (int) root;
2021 while(parentTree[v] >= 0)
2023 transform[i] = parentTree[v];
2030 parentTreeBackward[transform[i]] = transform[i-1];
2054 unsigned int* curlevel,
2055 unsigned int ncurlevel,
2056 unsigned int* newlevel,
2057 unsigned int* nnewlevel,
2062 unsigned int nbinvars;
2065 assert(scip != NULL);
2066 assert(vars != NULL);
2067 assert(vals != NULL);
2068 assert(graph != NULL);
2069 assert(graph->level != NULL);
2070 assert(graph->beginForward != NULL);
2071 assert(graph->targetForward != NULL);
2072 assert(graph->weightForward != NULL);
2073 assert(graph->beginBackward != NULL);
2074 assert(graph->targetBackward != NULL);
2075 assert(graph->weightBackward != NULL);
2076 assert(graph->beginAdj != NULL);
2077 assert(graph->levelAdj != NULL);
2078 assert(graph->sourceAdj != NULL);
2079 assert(graph->targetAdj != NULL);
2080 assert(graph->weightAdj != NULL);
2081 assert(inlevelgraph != NULL);
2082 assert(curlevel != NULL);
2083 assert(newlevel != NULL);
2084 assert(success != NULL);
2088 assert(graph->maxnodes % 2 == 0);
2089 nbinvars = (graph->maxnodes)/2;
2094 for( i = 0; i < ncurlevel; ++i )
2096 unsigned int negated;
2101 assert(u < graph->maxnodes);
2102 assert(graph->level[u] == level);
2103 assert(graph->beginForward[u] < 0);
2104 assert(graph->beginBackward[u] < 0);
2105 assert(graph->beginAdj[u] < 0);
2106 assert(inlevelgraph[u]);
2110 negated = u + nbinvars;
2112 negated = u - nbinvars;
2113 assert(negated < graph->maxnodes);
2114 assert(negated < nbinvars || u < nbinvars);
2115 assert(negated >= nbinvars || u >= nbinvars);
2118 graph->beginForward[u] = (int) graph->lastF;
2119 graph->beginBackward[u] = (
int) graph->lastB;
2120 graph->beginAdj[u] = (int) (graph->levelAdj[level+1] + nAdj);
2123 if( sepadata->addselfarcs )
2130 if( !inlevelgraph[negated] && (*nnewlevel) <= sepadata->maxlevelsize )
2133 graph->level[negated] = level+1;
2134 inlevelgraph[negated] =
TRUE;
2135 newlevel[*nnewlevel] = negated;
2138 assert( *nnewlevel > sepadata->maxlevelsize || inlevelgraph[negated] );
2141 if( inlevelgraph[negated] && ((graph->level[negated] == level - 1)
2142 || (graph->level[negated] == level) || (graph->level[negated] == level + 1)) )
2145 SCIP_CALL(
addArc(scip, graph, u, negated, level, 0, &nAdj, success) );
2152 if( graph->nlevels == 0 && sepadata->sortrootneighbors )
2155 sepadata, nnewlevel, inlevelgraph, level, newlevel, success) );
2160 newlevel, nnewlevel, &nAdj, success) );
2166 assert(graph->lastB > (
unsigned int) graph->beginBackward[u] || graph->nlevels == 0 );
2169 assert(graph->lastF > 0);
2172 graph->targetForward[graph->lastF] = -1;
2174 if( graph->lastF == graph->sizeForward )
2177 &(graph->weightForward), NULL, NULL, success) );
2182 graph->targetBackward[graph->lastB] = -1;
2184 if( graph->lastB == graph->sizeBackward )
2187 &(graph->weightBackward), NULL, NULL, success) );
2194 graph->sourceAdj[graph->levelAdj[level+1]+nAdj] = 0;
2195 graph->targetAdj[graph->levelAdj[level+1]+nAdj] = 0;
2197 graph->levelAdj[level+2] = graph->levelAdj[level+1]+nAdj;
2235 unsigned int nbinvars;
2236 unsigned int* incut;
2240 unsigned int* curlevel;
2241 unsigned int* newlevel;
2242 unsigned int ncurlevel;
2243 unsigned int nnewlevel;
2247 unsigned int* queue;
2250 int* parentTreeBackward;
2251 unsigned int* distance;
2255 unsigned int maxroots;
2256 unsigned int rootcounter;
2257 unsigned int ncutsroot;
2258 unsigned int ncutslevel;
2270 assert(scip != NULL);
2271 assert(sepadata != NULL);
2272 assert(result != NULL);
2275 assert(nscipbinvars >= 0);
2276 assert(nscipintvars >= 0);
2277 assert(nscipimplvars >= 0);
2279 nintegral = nscipbinvars + nscipintvars + nscipimplvars;
2280 assert(scipvars != NULL || ((nscipbinvars == 0) && (nscipintvars == 0) && (nscipimplvars == 0) && (nintegral == 0)));
2284 for (l = 0; l < nscipbinvars; ++l)
2285 vars[l] = scipvars[l];
2287 nbinvars = (
unsigned int) nscipbinvars;
2288 for (l = nscipbinvars; l < nintegral; ++l)
2292 vars[nbinvars++] = scipvars[l];
2305 assert( vars != NULL );
2306 switch( sepadata->sortswitch )
2314 for( i = 0; i < nbinvars; ++i )
2323 for( i = 0; i < nbinvars; ++i )
2332 for( i = 0; i < nbinvars; ++i )
2335 vals[i] = MIN(1.0 - vals[i], vals[i]);
2344 for( i = 0; i < nbinvars; ++i )
2347 vals[i] = MIN(1.0 - vals[i], vals[i]);
2359 assert(vars != NULL);
2365 for( i = 0; i < nbinvars; ++i )
2372 for( i = nbinvars; i < 2*nbinvars; ++i )
2373 vals[i] = 1.0 - vals[i - nbinvars];
2376 graph.maxnodes = 2 * nbinvars;
2382 graph.maxarcs = UINT_MAX;
2385 graph.sizeForward = 100 * graph.maxnodes;
2386 graph.sizeBackward = 100 * graph.maxnodes;
2387 graph.sizeAdj = 100 * graph.maxnodes;
2420 maxroots = (
unsigned int)
SCIPceil(scip, sepadata->offsettestvars + (0.02 * nbinvars * sepadata->percenttestvars));
2421 sepadata->maxlevelsize = (
unsigned int)
SCIPceil(scip, sepadata->offsetnodeslevel + 0.01 * sepadata->maxpernodeslevel * graph.maxnodes);
2425 for( i = (
unsigned int) sepadata->lastroot; i < graph.maxnodes && rootcounter < maxroots
2426 && sepadata->ncuts - sepadata->oldncuts < (
unsigned int) sepadata->maxsepacutsround
2431 if( incut[i] && ! sepadata->multiplecuts )
2464 for( j = 0; j < graph.maxnodes; ++j)
2466 graph.beginForward[j] = -1;
2467 graph.beginBackward[j] = -1;
2468 graph.beginAdj[j] = -1;
2469 inlevelgraph[j] =
FALSE;
2478 inlevelgraph[i] =
TRUE;
2480 graph.levelAdj[0] = 0;
2486 graph.levelAdj[graph.nlevels+1] = 0;
2497 curlevel, ncurlevel, newlevel, &nnewlevel, &success) );
2503 if( graph.nlevels > 0 && (sepadata->includetriangles || graph.nlevels > 1) )
2505 unsigned int maxcutslevel;
2510 maxcutslevel = (
unsigned int) sepadata->maxcutslevel;
2511 maxcutslevel = (
unsigned int) MIN(maxcutslevel, ncutsroot-sepadata->maxcutsroot);
2512 maxcutslevel = (
unsigned int) MIN(maxcutslevel, sepadata->maxsepacutsround + sepadata->oldncuts - sepadata->ncuts);
2515 for( j = graph.levelAdj[graph.nlevels+1]; j < graph.levelAdj[graph.nlevels+2]
2518 unsigned int ncyclevars;
2525 assert(graph.sourceAdj[j] < graph.targetAdj[j]);
2534 while( u != graph.sourceAdj[j] )
2536 assert(parentTree[u] != -1 && k <= graph.maxnodes);
2537 u = (
unsigned int) parentTree[u];
2543 for( k = 0; k < graph.nnodes; ++k )
2548 if( blocked[graph.targetAdj[j]] )
2553 graph.targetAdj[j], distance, queue, inQueue, parentTreeBackward, i, blocked) );
2556 if( parentTreeBackward[graph.targetAdj[j]] < 0 )
2562 for( k = 0; k < 2 * nbinvars; ++k )
2574 u = graph.targetAdj[j];
2577 while( success && u != i )
2580 pred[u] = (
unsigned int) parentTreeBackward[u];
2583 SCIP_CALL(
cleanCycle(scip, pred, incycle, incut, u, graph.targetAdj[j], nbinvars, &ncyclevars,
2584 sepadata->repaircycles, sepadata->allowmultiplecuts, &success) );
2586 assert(parentTreeBackward[u] >= 0 || u == i);
2589 u = (
unsigned int) parentTreeBackward[u];
2593 while( success && u != graph.sourceAdj[j] )
2596 pred[u] = (
unsigned int) parentTree[u];
2599 SCIP_CALL(
cleanCycle(scip, pred, incycle, incut, u, graph.targetAdj[j], nbinvars, &ncyclevars,
2600 sepadata->repaircycles, sepadata->allowmultiplecuts, &success) );
2603 u = (
unsigned int) parentTree[u];
2605 assert(!success || u == graph.sourceAdj[j]);
2610 pred[u] = graph.targetAdj[j];
2613 SCIP_CALL(
cleanCycle(scip, pred, incycle, incut, u, graph.targetAdj[j], nbinvars, &ncyclevars,
2614 sepadata->repaircycles, sepadata->allowmultiplecuts, &success) );
2621 unsigned int oldncuts;
2627 oldncuts = sepadata->ncuts;
2630 incut, vals, sepadata, &graphdata, result) );
2632 if(oldncuts < sepadata->ncuts)
2653 for( j = 0; j < nnewlevel; ++j )
2654 curlevel[j] = newlevel[j];
2655 ncurlevel = nnewlevel;
2659 && graph.nlevels < (
unsigned int) sepadata->maxnlevels
2660 && ncutsroot < (
unsigned int) sepadata->maxcutsroot
2661 && sepadata->ncuts - sepadata->oldncuts < (
unsigned int) sepadata->maxsepacutsround);
2667 if( sepadata->sortswitch ==
UNSORTED )
2669 if( i == graph.maxnodes )
2670 sepadata->lastroot = 0;
2672 sepadata->lastroot = (int) i;
2717 unsigned int maxarcs,
2718 unsigned int* arraysize,
2724 unsigned int additional;
2726 unsigned int oldarraysize;
2728 assert(scip != NULL);
2729 assert(arraysize != NULL);
2730 assert(graph != NULL);
2731 assert(graph->
head != NULL);
2732 assert(graph->
weight != NULL);
2733 assert(success != NULL);
2735 SCIPdebugMsg(scip,
"reallocating graph->head and graph->weight...\n");
2737 additional = (MIN(maxarcs, 2 * (*arraysize)) - (*arraysize)) * ((
int)
sizeof(*(graph->
head)));
2738 additional += (MIN(maxarcs, 2 * (*arraysize)) - (*arraysize)) * ((
int)
sizeof(*(graph->
weight)));
2749 if( memorylimit <= additional/1048576.0 ||
SCIPisStopped(scip) )
2756 oldarraysize = *arraysize;
2757 *arraysize = 2*(*arraysize);
2774 SCIPdebugMsg(scip,
"...memory limit exceeded - freeing all arrays\n");
2780 for( j = oldarraysize; j < MIN(maxarcs,(*arraysize)); ++j )
2797 unsigned int varsidx,
2798 unsigned int dijkindex,
2800 unsigned int nbinvars,
2801 unsigned int ncliques,
2803 unsigned int*
narcs,
2804 unsigned int maxarcs,
2807 unsigned int* arraysize,
2812 unsigned int neighindex;
2814 unsigned int ncliquevars;
2820 assert(scip != NULL);
2821 assert(sepadata != NULL);
2822 assert(vars != NULL);
2823 assert(graph != NULL);
2824 assert(graph->
head != NULL);
2825 assert(graph->
weight != NULL);
2826 assert(
narcs != NULL);
2827 assert(emptygraph != NULL);
2828 assert(arraysize != NULL);
2829 assert(success != NULL);
2833 assert(cliques != NULL || ncliques == 0);
2835 for( k = 0; k < ncliques; ++k )
2837 assert( cliques != NULL );
2844 assert(cliquevars != NULL || ncliquevars == 0);
2845 assert(cliquevals != NULL || ncliquevars == 0);
2848 for( m = 0; m < ncliquevars; ++m )
2852 assert( cliquevars != NULL && cliquevals != NULL );
2853 neighbor = cliquevars[m];
2856 assert(neighindex < nbinvars);
2859 if( neighindex == varsidx )
2873 tmp = (int)
SCIPfeasCeil(scip, sepadata->scale * (1 - vals[varsidx] - vals[neighindex] ));
2875 graph->
head[*
narcs] = neighindex + 2 * nbinvars;
2880 tmp = (int)
SCIPfeasCeil(scip, sepadata->scale * (1 - vals[varsidx] - (1 - vals[neighindex]) ));
2882 graph->
head[*
narcs] = neighindex + 3 * nbinvars;
2891 tmp = (int)
SCIPfeasCeil(scip, sepadata->scale * (1 - (1 - vals[varsidx]) - vals[neighindex] ));
2893 graph->
head[*
narcs] = neighindex + 2 * nbinvars;
2898 tmp = (int)
SCIPfeasCeil(scip, sepadata->scale * (1 - (1 - vals[varsidx]) - (1-vals[neighindex]) )) ;
2900 graph->
head[*
narcs] = neighindex + 3 * nbinvars;
2912 if( *arraysize == *
narcs )
2919 assert((*
narcs) < maxarcs);
2920 ++(graph->
outcnt[dijkindex]);
2922 *emptygraph =
FALSE;
2963 unsigned int* incut;
2970 unsigned int nbinvars;
2973 unsigned int ncliques;
2976 unsigned int arraysize;
2978 unsigned int maxarcs;
2979 unsigned int maxstarts;
2980 unsigned int startcounter;
2981 unsigned long long cutoff;
2983 unsigned int startnode;
2984 unsigned int endnode;
2985 unsigned long long* dist;
2987 unsigned int* entry;
2988 unsigned int* order;
2989 unsigned int dijkindex;
2993 unsigned int* pred2;
3001 assert(scip != NULL);
3002 assert(sepadata != NULL);
3003 assert(result != NULL);
3009 assert(nscipbinvars >= 0);
3010 assert(nscipintvars >= 0);
3011 assert(nscipimplvars >= 0);
3013 nintegral = nscipbinvars + nscipintvars + nscipimplvars;
3014 assert(scipvars != NULL || ((nscipbinvars == 0) && (nscipintvars == 0) && (nscipimplvars == 0) && (nintegral == 0)));
3018 for (k = 0; k < nscipbinvars; ++k)
3019 vars[k] = scipvars[k];
3021 nbinvars = (
unsigned int) nscipbinvars;
3022 for (k = nscipbinvars; k < nintegral; ++k)
3026 vars[nbinvars++] = scipvars[k];
3039 assert( vars != NULL );
3040 switch( sepadata->sortswitch )
3048 for( i = 0; i < nbinvars; ++i )
3057 for( i = 0; i < nbinvars; ++i )
3066 for( i = 0; i < nbinvars; ++i )
3069 vals[i] = MIN(1.0 - vals[i], vals[i]);
3078 for( i = 0; i < nbinvars; ++i )
3081 vals[i] = MIN(1.0 - vals[i], vals[i]);
3093 assert(vars != NULL);
3101 for( i = 0; i < nbinvars; ++i )
3108 for( i = nbinvars; i < 2*nbinvars; ++i )
3109 vals[i] = 1 - vals[i - nbinvars];
3112 graph.
nodes = 4 * nbinvars;
3134 arraysize = 100 * graph.
nodes;
3145 for( i = 0; i < MIN(arraysize, maxarcs); ++i )
3155 for( i = 0; i < graph.
nodes; ++i )
3163 for( dijkindex = 0; dijkindex < 2 * nbinvars; ++dijkindex )
3166 graph.
outcnt[dijkindex] = 0;
3169 if( dijkindex < nbinvars )
3176 i = dijkindex - nbinvars;
3179 assert(i < nbinvars);
3192 &
narcs, maxarcs, original, &emptygraph, &arraysize, &success) );
3200 if( sepadata->addselfarcs && graph.
outcnt[dijkindex] > 0 )
3205 assert(dijkindex < nbinvars);
3206 graph.
head[
narcs] = dijkindex + 3*nbinvars;
3211 assert(dijkindex >= nbinvars && dijkindex < 2*nbinvars);
3212 graph.
head[
narcs] = dijkindex + nbinvars;
3224 if( arraysize ==
narcs )
3230 assert(
narcs < maxarcs);
3231 ++(graph.
outcnt[dijkindex]);
3238 if( arraysize ==
narcs )
3244 assert(
narcs < maxarcs);
3252 for( i = 0; i < 2*nbinvars; ++i )
3255 graph.
outcnt[2 * nbinvars + i] = 0;
3261 assert(graph.
head[j] >= 2*nbinvars && graph.
head[j] < 4*nbinvars);
3267 if( arraysize ==
narcs )
3274 assert(
narcs < maxarcs);
3275 ++(graph.
outcnt[2*nbinvars+i]);
3283 if( arraysize ==
narcs )
3290 assert(
narcs < maxarcs);
3301 #ifdef SCIP_ODDCYCLE_WRITEGRAPH 3316 maxstarts = (
unsigned int)
SCIPceil(scip, sepadata->offsettestvars + (0.02 * nbinvars * sepadata->percenttestvars));
3324 cutoff = (
unsigned long long) (0.5 * sepadata->scale);
3325 for( i = (
unsigned int) sepadata->lastroot; i < 2 * nbinvars
3326 && startcounter < maxstarts
3327 && sepadata->ncuts - sepadata->oldncuts < (
unsigned int) sepadata->maxsepacutsround
3330 unsigned int ncyclevars;
3346 endnode = i + 2 * nbinvars;
3351 if( incut[startnode] && ! sepadata->multiplecuts )
3356 if ( sepadata->allowmultiplecuts )
3359 (
void)
dijkstraPairCutoff(&graph, startnode, endnode, cutoff, dist, pred, entry, order);
3366 if ( dist[endnode] >= cutoff )
3374 for( j = 0; j < 2 * nbinvars; ++j )
3381 edgedirection =
TRUE;
3385 for( dijkindex = endnode; dijkindex != startnode && success; dijkindex = pred[dijkindex], edgedirection = !edgedirection )
3390 assert(dijkindex >= 2 * nbinvars && dijkindex < 4 * nbinvars);
3391 assert(pred[dijkindex] < 2*nbinvars);
3393 pred2[dijkindex - 2 * nbinvars] = pred[dijkindex];
3399 SCIP_CALL(
cleanCycle(scip, pred2, incycle, incut, dijkindex-2*nbinvars, endnode-2*nbinvars, nbinvars,
3400 &ncyclevars, sepadata->repaircycles, sepadata->allowmultiplecuts, &success) );
3405 assert(dijkindex < 2 * nbinvars);
3406 assert(pred[dijkindex] >= 2 * nbinvars && pred[dijkindex] < 4 * nbinvars);
3408 pred2[dijkindex] = pred[dijkindex] - 2 * nbinvars;
3414 SCIP_CALL(
cleanCycle(scip, pred2, incycle, incut, dijkindex, endnode-2*nbinvars, nbinvars, &ncyclevars,
3415 sepadata->repaircycles, sepadata->allowmultiplecuts, &success) );
3428 SCIP_CALL(
generateOddCycleCut(scip, sepa, sol, vars, nbinvars, startnode, pred2, ncyclevars, incut, vals, sepadata, &graphdata, result) );
3439 if( sepadata->sortswitch ==
UNSORTED )
3441 if( i == 2 * nbinvars )
3442 sepadata->lastroot = 0;
3444 sepadata->lastroot = (int) i;
3474 assert(scip != NULL);
3475 assert(sepa != NULL);
3492 assert(sepadata != NULL);
3508 assert(sepadata != NULL);
3510 sepadata->ncuts = 0;
3511 sepadata->oldncuts = 0;
3512 sepadata->nliftedcuts = 0;
3513 sepadata->lastroot = 0;
3525 assert(sepa != NULL);
3528 assert(sepadata != NULL);
3530 sepadata->nunsucessfull = 0;
3531 sepadata->lastnode = -1;
3551 assert(sepadata != NULL);
3557 if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
3558 || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
3564 SCIPdebugMsg(scip,
"skipping separator: not enough binary variables\n");
3571 SCIPdebugMsg(scip,
"skipping separator: not enough fractional variables\n");
3578 SCIPdebugMsg(scip,
"skipping separator: not enough implications present\n");
3589 sepadata->nunsucessfull = 0;
3594 if ( sepadata->nunsucessfull > sepadata->maxunsucessfull )
3596 SCIPdebugMsg(scip,
"skipping separator: number of unsucessfull calls = %d.\n", sepadata->nunsucessfull);
3602 sepadata->oldncuts = sepadata->ncuts;
3603 SCIPdebug( oldnliftedcuts = sepadata->nliftedcuts; )
3606 sepadata->maxsepacutsround = sepadata->maxsepacutsroot;
3608 sepadata->maxsepacutsround = sepadata->maxsepacuts;
3611 if( sepadata->usegls )
3613 SCIPdebugMsg(scip,
"using GLS method for finding odd cycles\n");
3618 SCIPdebugMsg(scip,
"using level graph heuristic for finding odd cycles\n");
3622 if( sepadata->ncuts - sepadata->oldncuts > 0 )
3624 SCIPdebugMsg(scip,
"added %u cuts (%d allowed), %d lifted.\n", sepadata->ncuts - sepadata->oldncuts,
3625 sepadata->maxsepacutsround, sepadata->nliftedcuts - oldnliftedcuts);
3626 sepadata->nunsucessfull = 0;
3630 SCIPdebugMsg(scip,
"no cuts added (%d allowed)\n", sepadata->maxsepacutsround);
3631 ++sepadata->nunsucessfull;
3653 sepadata->nunsucessfull = 0;
3654 sepadata->lastnode = -1;
3659 sepaExeclpOddcycle, NULL,
3662 assert(sepa != NULL);
3672 "should the search method by Groetschel, Lovasz, Schrijver be used? Otherwise use levelgraph method by Hoffman, Padberg.",
3675 "should odd cycle cuts be lifted?",
3678 "maximal number of oddcycle cuts separated per separation round",
3681 "maximal number of oddcycle cuts separated per separation round in the root node",
3686 "maximal number of oddcycle separation rounds per node (-1: unlimited)",
3689 "maximal number of oddcycle separation rounds in the root node (-1: unlimited)",
3692 "factor for scaling of the arc-weights",
3695 "add links between a variable and its negated",
3698 "try to repair violated cycles with double appearance of a variable",
3701 "separate triangles found as 3-cycles or repaired larger cycles",
3704 "even if a variable is already covered by a cut, still try it as start node for a cycle search",
3707 "even if a variable is already covered by a cut, still allow another cut to cover it too",
3710 "choose lifting candidate by coef*lpvalue or only by coef",
3713 "calculate lifting coefficient of every candidate in every step (or only if its chosen)",
3716 "use sorted variable array (unsorted(0),maxlp(1),minlp(2),maxfrac(3),minfrac(4))",
3719 "sort level of the root neighbors by fractionality (maxfrac)",
3722 "percentage of variables to try the chosen method on [0-100]",
3725 "offset of variables to try the chosen method on (additional to the percentage of testvars)",
3728 "percentage of nodes allowed in the same level of the level graph [0-100]",
3731 "offset of nodes allowed in the same level of the level graph (additional to the percentage of levelnodes)",
3734 "maximal number of levels in level graph",
3737 "maximal number of oddcycle cuts generated per chosen variable as root of the level graph",
3740 "maximal number of oddcycle cuts generated in every level of the level graph",
3743 "minimal weight on an edge (in level graph or bipartite graph)",
3746 "number of unsuccessful calls at current node",
3749 "maximal number of other cuts s.t. separation is applied (-1 for direct call)",
enum SCIP_Result SCIP_RESULT
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 SCIP_DECL_SEPAEXECLP(sepaExeclpOddcycle)
static SCIP_RETCODE separateHeur(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_RESULT *result)
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
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)
Definitions for Disjkstra's shortest path algorithm.
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
DIJKSTRA_GRAPH * dijkstragraph
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
#define DEFAULT_MAXROUNDSROOT
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
#define DEFAULT_LPLIFTCOEF
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)
void SCIPsortDownRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
void SCIPsplitFilename(char *filename, char **path, char **name, char **extension, char **compression)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
#define DEFAULT_MAXSEPACUTSROOT
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
#define DEFAULT_MULTIPLECUTS
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
#define DEFAULT_OFFSETNODESLEVEL
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
enum SCIP_Retcode SCIP_RETCODE
SCIP_Real SCIPsepaGetTime(SCIP_SEPA *sepa)
int SCIPvarGetProbindex(SCIP_VAR *var)
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)
#define SCIPfreeBlockMemory(scip, ptr)
#define DEFAULT_MAXPERNODESLEVEL
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)
int SCIPgetNCutsFoundRound(SCIP *scip)
#define DEFAULT_SORTSWITCH
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
int SCIPgetNLPBranchCands(SCIP *scip)
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
#define DEFAULT_MAXSEPACUTS
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)
#define SEPA_MAXBOUNDDIST
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
static SCIP_DECL_SEPAINIT(sepaInitOddcycle)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
#define DEFAULT_ADDSELFARCS
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)
const char * SCIPgetProbName(SCIP *scip)
#define DEFAULT_ALLOWMULTIPLECUTS
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
#define DEFAULT_INCLUDETRIANGLES
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
static SCIP_DECL_SEPACOPY(sepaCopyOddcycle)
static SCIP_RETCODE separateGLS(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_RESULT *result)
#define DEFAULT_SORTROOTNEIGHBORS
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 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)
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
const char * SCIPvarGetName(SCIP_VAR *var)
#define DEFAULT_MAXREFERENCE
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
#define DEFAULT_REPAIRCYCLES
DIJKSTRA_Bool dijkstraGraphIsValid(const DIJKSTRA_GRAPH *G)
SCIP_RETCODE SCIPsetSepaInitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAINITSOL((*sepainitsol)))
static SCIP_DECL_SEPAINITSOL(sepaInitsolOddcycle)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
#define DEFAULT_MAXCUTSROOT
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)
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)
#define SCIPallocBufferArray(scip, ptr, num)
#define DEFAULT_PERCENTTESTVARS
public data structures and miscellaneous methods
SCIP_RETCODE SCIPchgRowRhs(SCIP *scip, SCIP_ROW *row, SCIP_Real rhs)
#define DEFAULT_MAXUNSUCESSFULL
int SCIPgetDepth(SCIP *scip)
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
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)
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)
SCIP_RETCODE SCIPwriteCliqueGraph(SCIP *scip, const char *fname, SCIP_Bool writenodeweights)
#define DEFAULT_SCALEFACTOR
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
int SCIPgetNBinVars(SCIP *scip)
#define DEFAULT_MAXNLEVELS
static SCIP_Bool isNeighbor(SCIP_VAR **vars, unsigned int nbinvars, GRAPHDATA *graphdata, unsigned int a, unsigned int b)
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_DECL_SEPAFREE(sepaFreeOddcycle)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
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 checkArraySizesGLS(SCIP *scip, unsigned int maxarcs, unsigned int *arraysize, DIJKSTRA_GRAPH *graph, SCIP_Bool *success)
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
SCIP_RETCODE SCIPsetSepaInit(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAINIT((*sepainit)))
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
void SCIProwChgRank(SCIP_ROW *row, int rank)
#define DEFAULT_RECALCLIFTCOEF
int SCIPgetNCliques(SCIP *scip)
int SCIPgetNImplications(SCIP *scip)
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
SCIP_Bool SCIPisStopped(SCIP *scip)
#define DEFAULT_OFFSETTESTVARS
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
#define DEFAULT_CUTTHRESHOLD
void SCIPsortRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
static SCIP_RETCODE blockRootPath(SCIP *scip, LEVELGRAPH *graph, unsigned int startnode, SCIP_Bool *inlevelgraph, SCIP_Bool *blocked, int *parentTree, unsigned int root)
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
#define BMSclearMemoryArray(ptr, num)
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)
SCIP_RETCODE SCIPincludeSepaOddcycle(SCIP *scip)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
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_LIFTODDCYCLES
SCIP_Longint SCIPgetNLPs(SCIP *scip)
#define DEFAULT_MAXCUTSLEVEL
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
static SCIP_RETCODE findShortestPathToRoot(SCIP *scip, int scale, LEVELGRAPH *graph, unsigned int startnode, unsigned int *distance, unsigned int *queue, SCIP_Bool *inQueue, int *parentTree)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
#define DEFAULT_MAXROUNDS
struct SCIP_SepaData SCIP_SEPADATA
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)
#define SCIPreallocBufferArray(scip, ptr, num)