86 #define CONSHDLR_NAME "SOS1" 87 #define CONSHDLR_DESC "SOS1 constraint handler" 88 #define CONSHDLR_SEPAPRIORITY 1000 89 #define CONSHDLR_ENFOPRIORITY 100 90 #define CONSHDLR_CHECKPRIORITY -10 91 #define CONSHDLR_SEPAFREQ 10 92 #define CONSHDLR_PROPFREQ 1 93 #define CONSHDLR_EAGERFREQ 100 95 #define CONSHDLR_MAXPREROUNDS -1 96 #define CONSHDLR_DELAYSEPA FALSE 97 #define CONSHDLR_DELAYPROP FALSE 98 #define CONSHDLR_NEEDSCONS TRUE 99 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP 100 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM 103 #define DEFAULT_MAXSOSADJACENCY 10000 107 #define DEFAULT_MAXEXTENSIONS 1 108 #define DEFAULT_MAXTIGHTENBDS 5 109 #define DEFAULT_PERFIMPLANALYSIS FALSE 110 #define DEFAULT_DEPTHIMPLANALYSIS -1 113 #define DEFAULT_CONFLICTPROP TRUE 114 #define DEFAULT_IMPLPROP TRUE 115 #define DEFAULT_SOSCONSPROP FALSE 118 #define DEFAULT_BRANCHSTRATEGIES "nbs" 119 #define DEFAULT_BRANCHINGRULE 'n' 121 #define DEFAULT_AUTOSOS1BRANCH TRUE 122 #define DEFAULT_FIXNONZERO FALSE 124 #define DEFAULT_ADDCOMPS FALSE 126 #define DEFAULT_MAXADDCOMPS -1 127 #define DEFAULT_ADDCOMPSDEPTH 30 128 #define DEFAULT_ADDCOMPSFEAS -0.6 129 #define DEFAULT_ADDBDSFEAS 1.0 130 #define DEFAULT_ADDEXTENDEDBDS TRUE 133 #define DEFAULT_NSTRONGROUNDS 0 135 #define DEFAULT_NSTRONGITER 10000 138 #define DEFAULT_BOUNDCUTSFROMSOS1 FALSE 139 #define DEFAULT_BOUNDCUTSFROMGRAPH TRUE 140 #define DEFAULT_AUTOCUTSFROMSOS1 TRUE 141 #define DEFAULT_BOUNDCUTSFREQ 10 142 #define DEFAULT_BOUNDCUTSDEPTH 40 143 #define DEFAULT_MAXBOUNDCUTS 50 144 #define DEFAULT_MAXBOUNDCUTSROOT 150 145 #define DEFAULT_STRTHENBOUNDCUTS TRUE 146 #define DEFAULT_IMPLCUTSFREQ 0 147 #define DEFAULT_IMPLCUTSDEPTH 40 148 #define DEFAULT_MAXIMPLCUTS 50 149 #define DEFAULT_MAXIMPLCUTSROOT 150 152 #define EVENTHDLR_NAME "SOS1" 153 #define EVENTHDLR_DESC "bound change event handler for SOS1 constraints" 156 #define DIVINGCUTOFFVALUE 1e6 186 typedef struct SCIP_NodeData SCIP_NODEDATA;
215 struct SCIP_ConshdlrData
235 int maxnfixnonzerovars;
242 int depthimplanalysis;
276 int maxboundcutsroot;
300 assert( adjacencymatrix !=
NULL || conflictgraph !=
NULL );
303 if ( vertex1 == vertex2 )
307 if ( adjacencymatrix ==
NULL )
318 if ( nsucc1 < 1 || nsucc2 < 1 )
321 if ( nsucc1 > nsucc2 )
330 for (j = 0; j < nsucc1; ++j)
332 succvertex = succ[j];
333 if ( succvertex == vertex2 )
335 else if ( succvertex > vertex2 )
341 if ( vertex1 < vertex2 )
342 return adjacencymatrix[vertex2][vertex1];
344 return adjacencymatrix[vertex1][vertex2];
363 assert( scip !=
NULL );
364 assert( conflictgraph !=
NULL );
368 assert( var !=
NULL );
382 for (s = 0; s < nsucc; ++s)
385 assert( var !=
NULL );
409 assert( scip !=
NULL );
410 assert( conflictgraph !=
NULL );
457 assert( scip !=
NULL );
458 assert( conflictgraph !=
NULL );
463 assert( nodedata !=
NULL );
466 if ( nodedata->lbboundvar ==
NULL || ! nodedata->lbboundcomp )
469 return nodedata->lbboundcoef *
SCIPgetSolVal(scip, sol, nodedata->lbboundvar);
484 assert( scip !=
NULL );
485 assert( conflictgraph !=
NULL );
490 assert( nodedata !=
NULL );
493 if ( nodedata->ubboundvar ==
NULL || ! nodedata->ubboundcomp )
496 return nodedata->ubboundcoef *
SCIPgetSolVal(scip, sol, nodedata->ubboundvar);
507 assert( conshdlrdata !=
NULL );
524 assert( conshdlrdata !=
NULL );
526 assert( conshdlrdata->varhash !=
NULL );
567 SCIP_CALL(
SCIPcreateConsLinear(scip, &cons,
"branch", 1, &var, &val, 0.0, 0.0,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
602 assert( scip !=
NULL );
603 assert( var !=
NULL );
604 assert( infeasible !=
NULL );
605 assert( tightened !=
NULL );
630 for (i = 0; i < naggrvars; ++i)
635 allnonnegative =
FALSE;
640 if ( allnonnegative )
643 for (i = 0; i < naggrvars; ++i)
649 *tightened = *tightened || fixed;
697 *tightened = *tightened || tighten;
701 *tightened = *tightened || tighten;
719 assert( cons !=
NULL );
720 assert( var !=
NULL );
738 assert( cons !=
NULL );
739 assert( var !=
NULL );
757 assert( consdata !=
NULL );
758 assert( consdata->nvars <= consdata->maxvars );
760 if ( num > consdata->maxvars )
766 if ( reserveWeights )
768 consdata->maxvars = newsize;
770 assert( num <= consdata->maxvars );
790 assert( scip !=
NULL );
791 assert( cons !=
NULL );
792 assert( consdata !=
NULL );
793 assert( conshdlrdata !=
NULL );
794 assert( var !=
NULL );
799 assert( conshdlrdata->eventhdlr !=
NULL );
806 assert( consdata->nfixednonzeros >= 0 );
808 ++consdata->nfixednonzeros;
830 conflictgraph = conshdlrdata->conflictgraph;
831 if ( conflictgraph ==
NULL )
836 assert( node < conshdlrdata->nsos1vars );
843 SCIPdebugMsg(scip,
"Switched to SOS1 branching rule, since conflict graph could be infeasible.\n");
844 conshdlrdata->switchsos1branch =
TRUE;
850 if ( ! consdata->local )
856 vars = consdata->vars;
857 nvars = consdata->nvars;
859 for (v = 0; v < nvars; ++v)
863 if ( var == vars[v] )
868 assert( nodev < conshdlrdata->nsos1vars );
900 SCIPdebugMsg(scip,
"Switched to SOS1 branching rule, since conflict graph could be infeasible.\n");
901 conshdlrdata->switchsos1branch =
TRUE;
926 assert( var !=
NULL );
927 assert( cons !=
NULL );
928 assert( conshdlrdata !=
NULL );
931 assert( consdata !=
NULL );
933 if ( consdata->weights ==
NULL && consdata->maxvars > 0 )
947 assert( var !=
NULL );
951 assert( consdata->weights !=
NULL );
952 assert( consdata->maxvars >= consdata->nvars+1 );
955 for (pos = 0; pos < consdata->nvars; ++pos)
957 if ( consdata->weights[pos] > weight )
960 assert( 0 <= pos && pos <= consdata->nvars );
963 for (j = consdata->nvars; j > pos; --j)
965 consdata->vars[j] = consdata->vars[j-1];
966 consdata->weights[j] = consdata->weights[j-1];
970 consdata->vars[pos] = var;
971 consdata->weights[pos] = weight;
993 assert( var !=
NULL );
994 assert( cons !=
NULL );
995 assert( conshdlrdata !=
NULL );
998 assert( consdata !=
NULL );
1008 assert( var !=
NULL );
1014 consdata->vars[consdata->nvars] = var;
1015 assert( consdata->weights !=
NULL || consdata->nvars > 0 );
1016 if ( consdata->weights !=
NULL && consdata->nvars > 0 )
1017 consdata->weights[consdata->nvars] = consdata->weights[consdata->nvars-1] + 1.0;
1039 assert( 0 <= pos && pos < consdata->nvars );
1048 for (j = pos; j < consdata->nvars-1; ++j)
1050 consdata->vars[j] = consdata->vars[j+1];
1051 if ( consdata->weights !=
NULL )
1052 consdata->weights[j] = consdata->weights[j+1];
1094 int* workingsetnew =
NULL;
1105 assert( scip !=
NULL );
1106 assert( conshdlrdata !=
NULL );
1107 assert( adjacencymatrix !=
NULL );
1108 assert( vertexcliquegraph !=
NULL );
1109 assert( cons !=
NULL );
1110 assert( cliques !=
NULL );
1111 assert( cliquesizes !=
NULL );
1112 assert( newclique !=
NULL );
1113 assert( workingset !=
NULL );
1114 assert( maxextensions !=
NULL );
1115 assert( naddconss !=
NULL );
1116 assert( success !=
NULL );
1121 mincands = nworkingset;
1129 for (i = 0; i < nexts; ++i)
1131 int vertex = workingset[i];
1132 for (j = nexts; j < nworkingset; ++j)
1140 for (i = 0; i < nworkingset; ++i)
1145 vertex = workingset[i];
1148 for (j = nexts; j < nworkingset && cnt < mincands; ++j)
1150 if ( vertex != workingset[j] && !
isConnectedSOS1(adjacencymatrix,
NULL, vertex, workingset[j]) )
1160 if ( cnt < mincands )
1182 for (btriter = mincands + btriter; btriter >= 1; --btriter)
1184 assert( selpos >= 0);
1185 assert( fixvertex >= 0);
1188 selvertex = workingset[selpos];
1189 workingset[selpos] = workingset[nexts];
1190 workingset[nexts] = selvertex;
1194 for (j = 0 ; j < nexts; ++j)
1197 workingsetnew[nextsnew++] = workingset[j];
1199 nworkingsetnew = nextsnew;
1200 for (j = nexts + 1; j < nworkingset; ++j)
1203 workingsetnew[nworkingsetnew++] = workingset[j];
1206 newclique[cliquesizes[*ncliques]++] = selvertex;
1209 if ( nworkingsetnew == 0 )
1216 cliqueind = nsos1vars + *ncliques;
1219 assert( cliquesizes[*ncliques] >= 0 && cliquesizes[*ncliques] <= nsos1vars );
1220 assert( *ncliques <
MAX(1, conshdlrdata->maxextensions) * nconss );
1222 for (j = 0 ; j < cliquesizes[*ncliques]; ++j)
1226 cliques[*ncliques][j] = newclique[j];
1229 SCIPsortInt(cliques[*ncliques], cliquesizes[*ncliques]);
1232 (void)
SCIPsnprintf(consname,
SCIP_MAXSTRLEN,
"extsos1_%" SCIP_LONGINT_FORMAT, conshdlrdata->cntextsos1, conshdlrdata->cntextsos1);
1244 for (j = 0; j < consdata->nvars; ++j)
1254 ++(conshdlrdata->cntextsos1);
1256 cliquesizes[*ncliques] = cliquesizes[*ncliques-1];
1262 if ( *maxextensions <= 0 )
1268 else if ( nextsnew < nworkingsetnew )
1273 SCIP_CALL(
extensionOperatorSOS1(scip, conshdlrdata, adjacencymatrix, vertexcliquegraph, nsos1vars, nconss, cons, vars, weights,
FALSE, usebacktrack,
1274 cliques, ncliques, cliquesizes, newclique, workingsetnew, nworkingsetnew, nextsnew, pos, maxextensions, naddconss, success) );
1275 if ( *maxextensions <= 0 )
1285 assert( nworkingset >= nworkingsetnew );
1286 for (w = 0; w < nworkingsetnew; ++w)
1287 workingset[w] = workingsetnew[w];
1288 nworkingset = nworkingsetnew;
1292 SCIP_CALL(
extensionOperatorSOS1(scip, conshdlrdata, adjacencymatrix, vertexcliquegraph, nsos1vars, nconss, cons, vars, weights,
FALSE, usebacktrack,
1293 cliques, ncliques, cliquesizes, newclique, workingset, nworkingset, nextsnew, pos, maxextensions, naddconss, success) );
1294 assert( *maxextensions <= 0 );
1298 assert( workingsetnew !=
NULL );
1299 assert( workingset !=
NULL );
1302 --cliquesizes[*ncliques];
1310 for (j = nexts; j < nworkingset; ++j)
1312 assert( fixvertex != workingset[j] );
1347 assert( conflictgraphlin !=
NULL );
1348 assert( conflictgraphorig !=
NULL );
1349 assert( linvars !=
NULL );
1350 assert( posinlinvars !=
NULL );
1352 for (v = 1; v < nlinvars; ++v)
1357 if ( indexinsosvars >= 0 )
1362 for (s = 0; s < nsucc; ++s)
1364 assert( succ[s] >= 0 );
1365 indexinlinvars = posinlinvars[succ[s]];
1366 assert( indexinlinvars < nlinvars );
1368 if ( indexinlinvars >= 0 && indexinlinvars < v )
1401 assert( conflictgraph !=
NULL );
1402 assert( clique !=
NULL );
1403 assert( vars !=
NULL );
1404 assert( comsucc !=
NULL );
1405 assert( ncomsucc !=
NULL );
1412 assert(vars[0] !=
NULL );
1418 for (j = 0; j < nvars; ++j)
1420 for (i = k; i < nsucc; ++i)
1422 if ( succ[i] > clique[j] )
1427 else if ( succ[i] == clique[j] )
1433 comsucc[(*ncomsucc)++] = succ[i];
1438 for (v = 1; v < nvars; ++v)
1440 int ncomsuccsave = 0;
1443 assert(vars[v] !=
NULL );
1453 for (j = 0; j < *ncomsucc; ++j)
1455 for (i = k; i < nsucc; ++i)
1457 if ( succ[i] > comsucc[j] )
1462 else if ( succ[i] == comsucc[j] )
1464 comsucc[ncomsuccsave++] = succ[i];
1470 *ncomsucc = ncomsuccsave;
1496 assert( scip !=
NULL );
1497 assert( implgraph !=
NULL );
1498 assert( implnodes !=
NULL );
1499 assert( node >= 0 );
1500 assert( vars[node] !=
NULL );
1512 for (s = 0; s < nsucc; ++s)
1517 data = succdatas[s];
1521 assert( succdatas[s] !=
NULL );
1524 assert( sos1node == succnode );
1525 implnodes[sos1node] =
TRUE;
1565 int lastFixedNonzero;
1568 assert( scip !=
NULL );
1569 assert( cons !=
NULL );
1570 assert( consdata !=
NULL );
1571 assert( eventhdlr !=
NULL );
1572 assert( cutoff !=
NULL );
1573 assert( success !=
NULL );
1574 assert( ndelconss !=
NULL );
1575 assert( nfixedvars !=
NULL );
1576 assert( nremovedvars !=
NULL );
1578 *substituted =
FALSE;
1586 lastFixedNonzero = -1;
1587 allvarsbinary =
TRUE;
1588 vars = consdata->vars;
1591 while ( j < consdata->nvars )
1620 *substituted =
TRUE;
1624 for (l = j+1; l < consdata->nvars; ++l)
1627 if ( vars[j] == vars[l] )
1650 lastFixedNonzero = j;
1664 allvarsbinary =
FALSE;
1671 if ( consdata->nvars < 2 )
1684 if ( nfixednonzeros > 1 )
1686 SCIPdebugMsg(scip,
"The problem is infeasible: more than one variable has bounds that keep it from being 0.\n");
1687 assert( lastFixedNonzero >= 0 );
1693 if ( nfixednonzeros == 1 )
1695 assert( lastFixedNonzero >= 0 );
1698 for (j = 0; j < consdata->nvars; ++j)
1700 if ( j != lastFixedNonzero )
1790 int** cliques =
NULL;
1792 int* cliquesizes =
NULL;
1793 int* newclique =
NULL;
1794 int* indconss =
NULL;
1795 int* lengthconss =
NULL;
1796 int* comsucc =
NULL;
1801 assert( scip !=
NULL );
1802 assert( eventhdlr !=
NULL );
1803 assert( conshdlrdata !=
NULL );
1804 assert( conflictgraph !=
NULL );
1805 assert( conss !=
NULL );
1806 assert( naddconss !=
NULL );
1807 assert( ndelconss !=
NULL );
1808 assert( nupgdconss !=
NULL );
1809 assert( nfixedvars !=
NULL );
1810 assert( nremovedvars !=
NULL );
1811 assert( result !=
NULL );
1814 csize =
MAX(1, conshdlrdata->maxextensions) * nconss;
1828 for (c = 0; c < nconss; ++c)
1833 assert( consdata !=
NULL );
1836 lengthconss[c] = consdata->nvars;
1841 for (iter = 0; iter < nconss; ++iter)
1848 int savennupgdconss;
1856 assert( conss !=
NULL );
1857 assert( conss[c] !=
NULL );
1861 assert( consdata !=
NULL );
1862 assert( consdata->nvars >= 0 );
1863 assert( consdata->nvars <= consdata->maxvars );
1865 assert( ncliques < csize );
1867 savendelconss = *ndelconss;
1868 savennupgdconss = *nupgdconss;
1871 SCIP_CALL(
presolRoundConsSOS1(scip, cons, consdata, eventhdlr, &substituted, &cutoff, &success, ndelconss, nupgdconss, nfixedvars, nremovedvars) );
1879 if ( *ndelconss > savendelconss || *nupgdconss > savennupgdconss || substituted )
1889 nvars = consdata->nvars;
1892 vars = consdata->vars;
1894 if ( nvars > 1 && conshdlrdata->maxextensions != 0 )
1903 for (j = 0; j < nvars; ++j)
1907 if ( varprobind >= 0 )
1908 newclique[cliquesize++] = varprobind;
1911 if ( cliquesize > 1 )
1913 cliquesizes[ncliques] = cliquesize;
1925 varprobind = newclique[0];
1930 for (j = 0; j < ncomsucc; ++j)
1933 assert( j == 0 || succ[j] > succ[j-1] );
1934 comsucc[j] = succ[j];
1938 for (v = 1; v < cliquesize && ncomsucc > 0; ++v)
1940 varprobind = newclique[v];
1945 assert( succ !=
NULL || nsucc == 0 );
1968 if ( conshdlrdata->maxextensions != 0 && adjacencymatrix !=
NULL )
1977 maxextensions = conshdlrdata->maxextensions;
1980 TRUE, (maxextensions <= 1) ?
FALSE :
TRUE, cliques, &ncliques, cliquesizes, newclique, comsucc, ncomsucc, 0, -1, &maxextensions,
1981 naddconss, &extended) );
1996 cliqueind = nsos1vars + ncliques;
1999 assert( cliquesize >= 0 && cliquesize <= nsos1vars );
2000 assert( ncliques < csize );
2002 for (j = 0; j < cliquesize; ++j)
2004 cliques[ncliques][j] = newclique[j];
2016 for (c = ncliques-1; c >= 0; --c)
2066 if ( conshdlrdata->depthimplanalysis >= 0 && *probingdepth >= conshdlrdata->depthimplanalysis )
2075 for (s = 0; s < nsucc; ++s)
2094 impllbs[succnode] = 0;
2095 implubs[succnode] = 0;
2106 if ( givennode > succnode )
2107 adjacencymatrix[givennode][succnode] = 1;
2109 adjacencymatrix[succnode][givennode] = 1;
2117 SCIP_CALL(
SCIPcreateConsSOS1(scip, &soscons, namesos, 0,
NULL,
NULL,
TRUE,
TRUE,
TRUE,
FALSE,
TRUE,
2141 for (s = 0; s < nsucc; ++s)
2144 int oldprobingdepth;
2147 data = succdatas[s];
2148 oldprobingdepth = *probingdepth;
2151 if (
SCIPisFeasLT(scip, impllbs[succnode], data->lbimpl) )
2153 impllbs[succnode] = data->lbimpl;
2160 implnodes[succnode] =
TRUE;
2161 SCIP_CALL(
performImplicationGraphAnalysis(scip, conshdlrdata, conflictgraph, totalvars, implgraph, implhash, adjacencymatrix, givennode, succnode, impllbs, implubs, implnodes, naddconss, probingdepth, infeasible) );
2162 *probingdepth = oldprobingdepth;
2171 if (
SCIPisFeasGT(scip, implubs[succnode], data->ubimpl) )
2173 implubs[succnode] = data->ubimpl;
2180 implnodes[succnode] =
TRUE;
2181 SCIP_CALL(
performImplicationGraphAnalysis(scip, conshdlrdata, conflictgraph, totalvars, implgraph, implhash, adjacencymatrix, givennode, succnode, impllbs, implubs, implnodes, naddconss, probingdepth, infeasible) );
2182 *probingdepth = oldprobingdepth;
2214 for (s = 0; s < nsucc; ++s)
2216 if ( implnodes[succ[s]] )
2250 assert( scip !=
NULL );
2251 assert( implgraph !=
NULL );
2252 assert( implhash !=
NULL );
2253 assert( totalvars !=
NULL );
2254 assert( varv !=
NULL );
2255 assert( varw !=
NULL );
2268 if ( infeasible1 || infeasible2 )
2274 if ( tightened1 || tightened2 )
2291 for (s = 0; s < nsucc; ++s)
2293 if ( succ[s] == indw )
2295 data = succdatas[s];
2296 assert( data !=
NULL );
2297 if ( lower &&
SCIPisFeasLT(scip, data->lbimpl, newbound) )
2300 data->lbimpl =
SCIPceil(scip, newbound);
2302 data->lbimpl = newbound;
2307 else if ( ! lower &&
SCIPisFeasGT(scip, data->ubimpl, newbound) )
2310 data->ubimpl =
SCIPfloor(scip, newbound);
2312 data->ubimpl = newbound;
2324 assert( data ==
NULL );
2328 data->lbimpl = newbound;
2335 data->ubimpl = newbound;
2362 int* cliquecoversizes,
2381 assert( update !=
NULL );
2385 *infeasible =
FALSE;
2393 for (w = 0; w < nvars; ++w)
2395 int newninftynonzero;
2402 newninftynonzero = ninftynonzero;
2416 implbound = boundnonzero -
bound;
2417 ind = varincover[w];
2418 assert( cliquecoversizes[ind] > 0 );
2421 for (j = 0; j < cliquecoversizes[ind]; ++j)
2423 indcliq = cliquecovers[ind][j];
2424 assert( 0 <= indcliq && indcliq < nvars );
2434 implbound += bounds[w];
2439 else if ( implcoverw )
2444 implbound -= bounds[indcliq];
2457 if ( ! implinfty && newninftynonzero == 0 )
2471 newbound = implbound / coef;
2478 SCIP_CALL(
updateArcData(scip, implgraph, implhash, totalvars, var, vars[w], lb, ub, newbound,
TRUE, nchgbds, update, infeasible) );
2482 SCIP_CALL(
updateArcData(scip, implgraph, implhash, totalvars, var, vars[w], lb, ub, newbound,
FALSE, nchgbds, update, infeasible) );
2489 SCIP_CALL(
updateArcData(scip, implgraph, implhash, totalvars, var, vars[w], lb, ub, newbound,
FALSE, nchgbds, update, infeasible) );
2493 SCIP_CALL(
updateArcData(scip, implgraph, implhash, totalvars, var, vars[w], lb, ub, newbound,
TRUE, nchgbds, update, infeasible) );
2526 assert( conflictgraphlin !=
NULL );
2527 assert( linvars !=
NULL );
2528 assert( coveredvars !=
NULL );
2529 assert( clique !=
NULL );
2530 assert( cliquesize !=
NULL );
2532 assert( ! coveredvars[v] );
2542 int nextensions = 0;
2553 for (s = 0; s < nsucc; ++s)
2556 if ( ! coveredvars[succnode] )
2557 extensions[nextensions++] = succ[s];
2561 while ( nextensions > 0 )
2565 if ( considersolvals )
2573 for (s = 0; s < nextensions; ++s)
2578 bestbigMval = bigMval;
2579 bestindex = extensions[s];
2584 bestindex = extensions[0];
2586 assert( bestindex != -1 );
2589 clique[(*cliquesize)++] = bestindex;
2593 for (s = 0; s < nextensions; ++s)
2595 if ( s != bestindex &&
isConnectedSOS1(
NULL, conflictgraphlin, bestindex, extensions[s]) )
2596 extensions[nextensionsnew++] = extensions[s];
2598 nextensions = nextensionsnew;
2606 for (s = 0; s < *cliquesize; ++s)
2612 assert( ! coveredvars[ind] );
2613 coveredvars[ind] =
TRUE;
2643 int* varindincons =
NULL;
2646 int ntrafolinvars = 0;
2657 assert( scip !=
NULL );
2658 assert( conflictgraph !=
NULL );
2659 assert( adjacencymatrix !=
NULL );
2660 assert( nchgbds !=
NULL );
2661 assert( cutoff !=
NULL );
2664 *implupdate =
FALSE;
2668 if ( conshdlrlinear ==
NULL )
2684 for (c = 0; c < nlinearconss + nsos1vars && ! (*cutoff); ++c)
2687 int** cliquecovers =
NULL;
2688 int* cliquecoversizes =
NULL;
2691 int* varincover =
NULL;
2698 if ( c < nlinearconss )
2715 if ( noriglinvars < 1 )
2717 assert( origlinvars !=
NULL );
2718 assert( origlinvals !=
NULL );
2723 ntrafolinvars = noriglinvars;
2728 if( requiredsize > ntrafolinvars )
2734 assert( requiredsize <= ntrafolinvars );
2736 trafolhs = origlhs - constant;
2737 traforhs = origrhs - constant;
2755 trafolinvars[1] = var;
2756 trafolinvals[1] = -1.0;
2757 trafolhs = -constant;
2758 traforhs = -constant;
2777 for (v = 0; v < nagrvars; ++v)
2779 trafolinvars[v] = agrvars[v];
2780 trafolinvals[v] = scalars[v];
2782 trafolinvars[nagrvars] = var;
2783 trafolinvals[nagrvars] = -1.0;
2784 trafolhs = -constant;
2785 traforhs = -constant;
2786 ntrafolinvars = nagrvars + 1;
2800 trafolinvars[0] = negvar;
2801 trafolinvars[1] = var;
2802 trafolinvals[0] = 1.0;
2803 trafolinvals[1] = 1.0;
2812 if ( ntrafolinvars == 0 )
2820 for (v = 0; v < ntrafolinvars; ++v)
2825 if ( trafolinvals[v] < 0.0 )
2837 trafolbs[v] = lb * trafolinvals[v];
2842 trafoubs[v] = ub * trafolinvals[v];
2846 for (v = 0; v < nsos1vars; ++v)
2847 varindincons[v] = -1;
2850 for (v = 0; v < ntrafolinvars; ++v)
2857 varindincons[node] = v;
2865 for (i = 0; i < ntrafolinvars; ++i)
2866 coveredvars[i] =
FALSE;
2875 for (v = 0; v < ntrafolinvars; ++v)
2878 if ( ! coveredvars[v] )
2881 SCIP_CALL(
computeVarsCoverSOS1(scip, conflictgraph, conflictgraphlin, trafolinvars, coveredvars, cliquecovers[ncliquecovers], &(cliquecoversizes[ncliquecovers]), v,
FALSE) );
2891 for (v = 0; v < ntrafolinvars; ++v)
2908 for (s = 0; s < nsucc; ++s)
2913 if ( varindincons[succnode] == -1 )
2916 varindincons[succnode] = -2;
2928 for (i = 0; i < ncliquecovers; ++i)
2930 for (j = 0; j < cliquecoversizes[i]; ++j)
2932 int ind = cliquecovers[i][j];
2934 varincover[ind] = i;
2935 cliquecovervals[j] = trafoubs[ind];
2941 for (v = 0; v < ntrafolinvars + nsos1linvars; ++v)
2955 int ninftynonzero = 0;
2959 if ( v < ntrafolinvars )
2961 var = trafolinvars[v];
2962 trafoubv = trafoubs[v];
2966 assert( v >= ntrafolinvars );
2967 var = sos1linvars[v-ntrafolinvars];
2977 newboundnonzero = trafolhs;
2978 newboundnores = trafolhs;
2980 assert( nodev < nsos1vars );
2983 for (w = 0; w < nsos1vars; ++w)
2984 implnodes[w] =
FALSE;
2988 for (i = 0; i < ncliquecovers; ++i)
2993 assert( cliquecoversizes[i] > 0 );
2995 indcliq = cliquecovers[i][0];
2996 assert( 0 <= indcliq && indcliq < ntrafolinvars );
3004 newboundnores -= trafoubs[indcliq];
3006 else if ( cliquecoversizes[i] > 1 )
3008 assert( 0 <= cliquecovers[i][1] && cliquecovers[i][1] < ntrafolinvars );
3012 newboundnores -= trafoubs[cliquecovers[i][1]];
3016 for (j = 0; j < cliquecoversizes[i]; ++j)
3018 indcliq = cliquecovers[i][j];
3019 assert( 0 <= indcliq && indcliq < ntrafolinvars );
3022 assert( nodecliq < nsos1vars );
3032 newboundnonzero -= trafoubs[indcliq];
3039 assert( ninftynonzero == 0 || inftynores );
3042 if ( ninftynonzero == 0 && v < ntrafolinvars )
3044 linval = trafolinvals[v];
3051 newbound = newboundnonzero;
3053 newbound =
MIN(0, newboundnonzero);
3066 newbound =
SCIPceil(scip, newbound);
3069 assert( ! infeasible );
3090 assert( ! infeasible );
3101 SCIP_CALL(
updateImplicationGraphSOS1(scip, conshdlrdata, conflictgraph, adjacencymatrix, implgraph, implhash, implnodes, totalvars, cliquecovers, cliquecoversizes, varincover,
3102 trafolinvars, trafolinvals, ntrafolinvars, trafoubs, var, trafoubv, newboundnonzero, ninftynonzero,
TRUE, nchgbds, &update, &infeasible) );
3109 if ( *cutoff ==
TRUE )
3113 for (j = ncliquecovers-1; j >= 0; --j)
3127 for (i = 0; i < ncliquecovers; ++i)
3129 for (j = 0; j < cliquecoversizes[i]; ++j)
3131 int ind = cliquecovers[i][j];
3133 varincover[ind] = i;
3134 cliquecovervals[j] = trafolbs[ind];
3136 SCIPsortRealInt(cliquecovervals, cliquecovers[i], cliquecoversizes[i]);
3141 for (v = 0; v < ntrafolinvars + nsos1linvars; ++v)
3155 int ninftynonzero = 0;
3159 if ( v < ntrafolinvars )
3161 var = trafolinvars[v];
3162 trafolbv = trafolbs[v];
3166 assert( v-ntrafolinvars >= 0 );
3167 var = sos1linvars[v-ntrafolinvars];
3175 newboundnonzero = traforhs;
3176 newboundnores = traforhs;
3178 assert( nodev < nsos1vars );
3181 for (w = 0; w < nsos1vars; ++w)
3182 implnodes[w] =
FALSE;
3186 for (i = 0; i < ncliquecovers; ++i)
3191 assert( cliquecoversizes[i] > 0 );
3193 indcliq = cliquecovers[i][0];
3194 assert( 0 <= indcliq && indcliq < ntrafolinvars );
3203 newboundnores -= trafolbs[indcliq];
3205 else if ( cliquecoversizes[i] > 1 )
3207 assert( 0 <= cliquecovers[i][1] && cliquecovers[i][1] < ntrafolinvars );
3211 newboundnores -= trafolbs[cliquecovers[i][1]];
3215 for (j = 0; j < cliquecoversizes[i]; ++j)
3217 indcliq = cliquecovers[i][j];
3218 assert( 0 <= indcliq && indcliq < ntrafolinvars );
3221 assert( nodecliq < nsos1vars );
3232 newboundnonzero -= trafolbs[indcliq];
3239 assert( ninftynonzero == 0 || inftynores );
3243 if ( ninftynonzero == 0 && v < ntrafolinvars )
3245 linval = trafolinvals[v];
3252 newbound = newboundnonzero;
3254 newbound =
MAX(0, newboundnonzero);
3271 assert( ! infeasible );
3289 newbound =
SCIPceil(scip, newbound);
3292 assert( ! infeasible );
3303 SCIP_CALL(
updateImplicationGraphSOS1(scip, conshdlrdata, conflictgraph, adjacencymatrix, implgraph, implhash, implnodes, totalvars, cliquecovers, cliquecoversizes, varincover,
3304 trafolinvars, trafolinvals, ntrafolinvars, trafolbs, var, trafolbv, newboundnonzero, ninftynonzero,
FALSE, nchgbds, &update, &infeasible) );
3313 for (j = ncliquecovers-1; j >= 0; --j)
3321 if ( *cutoff ==
TRUE )
3375 for (i = 0; i < nsos1vars; ++i)
3384 totalvars[ntotalvars++] = var;
3387 for (i = 0; i < nprobvars; ++i)
3397 totalvars[ntotalvars++] = var;
3405 updateconfl =
FALSE;
3406 for (j = 0; (j < conshdlrdata->maxtightenbds || conshdlrdata->maxtightenbds == -1 ) && ! cutoff; ++j)
3411 nchgbdssave = *nchgbds;
3413 assert( ntotalvars > 0 );
3414 SCIP_CALL(
tightenVarsBoundsSOS1(scip, conshdlrdata, conflictgraph, implgraph, implhash, adjacencymatrix, totalvars, ntotalvars, nsos1vars, nchgbds, &implupdate, &cutoff) );
3415 if ( *nchgbds > nchgbdssave )
3421 else if ( implupdate )
3428 if ( updateconfl && conshdlrdata->perfimplanalysis && ! cutoff )
3443 naddconsssave = *naddconss;
3444 for (i = 0; i < nsos1vars; ++i)
3449 for (j = 0; j < nsos1vars; ++j)
3450 implnodes[j] =
FALSE;
3451 for (j = 0; j < ntotalvars; ++j)
3458 SCIP_CALL(
performImplicationGraphAnalysis(scip, conshdlrdata, conflictgraph, totalvars, implgraph, implhash, adjacencymatrix, i, i, impllbs, implubs, implnodes, naddconss, &probingdepth, &infeasible) );
3467 SCIPdebugMsg(scip,
"fixed variable %s with lower bound %f and upper bound %f to zero\n",
3477 if ( *naddconss > naddconsssave )
3494 for (j = ntotalvars-1; j >= 0; --j)
3503 for (s = nsucc-1; s >= 0; --s)
3526 assert( scip !=
NULL );
3527 assert( cons !=
NULL );
3528 assert( consdata !=
NULL );
3529 assert( cutoff !=
NULL );
3530 assert( ngen !=
NULL );
3535 if ( consdata->nfixednonzeros > 1 )
3537 SCIPdebugMsg(scip,
"the node is infeasible, more than 1 variable is fixed to be nonzero.\n");
3544 if ( consdata->nfixednonzeros == 1 )
3551 int firstFixedNonzero;
3555 firstFixedNonzero = -1;
3556 nvars = consdata->nvars;
3557 vars = consdata->vars;
3558 assert( vars !=
NULL );
3561 for (j = 0; j < nvars; ++j)
3565 firstFixedNonzero = j;
3569 assert( firstFixedNonzero >= 0 );
3571 SCIPdebugMsg(scip,
"variable <%s> is fixed nonzero, fixing other variables to 0.\n",
SCIPvarGetName(vars[firstFixedNonzero]));
3575 for (j = 0; j < firstFixedNonzero; ++j)
3579 assert( ! infeasible );
3580 allVarFixed = allVarFixed && success;
3586 for (j = firstFixedNonzero+1; j < nvars; ++j)
3590 assert( ! infeasible );
3591 allVarFixed = allVarFixed && success;
3632 assert( scip !=
NULL );
3633 assert( conflictgraph !=
NULL );
3634 assert( cutoff !=
NULL );
3635 assert( ngen !=
NULL );
3636 assert( node >= 0 );
3639 inferinfo = -node - 1;
3647 for (s = 0; s < nsucc; ++s)
3680 if ( implprop && implgraph !=
NULL )
3685 SCIP_NODEDATA* nodedbgdata;
3693 if ( succdatas !=
NULL )
3697 for (s = 0; s < nsucc; ++s)
3704 assert( nodedata !=
NULL );
3705 succdata = succdatas[s];
3706 assert( succdata !=
NULL );
3707 var = nodedata->var;
3708 assert( var !=
NULL );
3781 assert( scip !=
NULL );
3782 assert( conshdlrdata !=
NULL );
3783 assert( conflictgraph !=
NULL );
3784 assert( conshdlrdata->implgraph ==
NULL );
3785 assert( conshdlrdata->nimplnodes == 0 );
3786 assert( cutoff !=
NULL );
3787 assert( nchgbds !=
NULL );
3793 if ( conshdlrdata->maxsosadjacency != -1 && nsos1vars > conshdlrdata->maxsosadjacency )
3796 SCIPdebugMsg(scip,
"Implication graph was not created since number of SOS1 variables (%d) is larger than %d.\n", nsos1vars, conshdlrdata->maxsosadjacency);
3819 for (i = 0; i < nsos1vars; ++i)
3828 implvars[nimplnodes++] = var;
3831 for (i = 0; i < nprobvars; ++i)
3841 implvars[nimplnodes++] = var;
3844 conshdlrdata->nimplnodes = nimplnodes;
3847 for (i = 0; i < nimplnodes; ++i)
3853 nodedata->var = implvars[i];
3863 for (i = 0; i < nsos1vars; ++i)
3867 for (i = 0; i < nsos1vars; ++i)
3869 for (j = 0; j < i+1; ++j)
3870 adjacencymatrix[i][j] = 0;
3873 for (i = 0; i < nsos1vars; ++i)
3880 for (j = 0; j < nsucc; ++j)
3883 adjacencymatrix[i][succ[j]] = 1;
3890 for (j = 0; (j < maxrounds || maxrounds == -1 ); ++j)
3895 nchgbdssave = *nchgbds;
3897 assert( nimplnodes > 0 );
3898 SCIP_CALL(
tightenVarsBoundsSOS1(scip, conshdlrdata, conflictgraph, conshdlrdata->implgraph, implhash, adjacencymatrix, implvars, nimplnodes, nsos1vars, nchgbds, &implupdate, cutoff) );
3899 if ( *cutoff || ( ! implupdate && ! ( *nchgbds > nchgbdssave ) ) )
3904 for (i = nsos1vars-1; i >= 0; --i)
3917 else if ( *nchgbds > 0 )
3919 SCIPdebugMsg(scip,
"found %d bound changes\n", *nchgbds);
3923 assert( conshdlrdata->implgraph !=
NULL );
3938 assert( scip !=
NULL );
3939 assert( conshdlrdata !=
NULL );
3942 if ( conshdlrdata->implgraph ==
NULL )
3944 assert( conshdlrdata->nimplnodes == 0 );
3949 for (j = conshdlrdata->nimplnodes-1; j >= 0; --j)
3958 for (s = nsucc-1; s >= 0; --s)
3960 assert( succdatas[s] !=
NULL );
3966 for (j = conshdlrdata->nimplnodes-1; j >= 0; --j)
3970 assert( nodedata !=
NULL );
3977 conshdlrdata->nimplnodes = 0;
4004 assert( conflictgraph !=
NULL );
4005 assert( verticesarefixed !=
NULL );
4006 assert( coververtices !=
NULL );
4007 assert( ncoververtices !=
NULL );
4009 *ncoververtices = 0;
4012 if ( neightocover ==
NULL )
4014 assert( nneightocover == 0 );
4020 nsucc1 = nneightocover;
4021 succ1 = neightocover;
4025 for (s = 0; s < nsucc1; ++s)
4027 int succvertex1 = succ1[s];
4029 if ( ! verticesarefixed[succvertex1] )
4040 if ( *ncoververtices == 0 )
4042 for (j = 0; j < nsucc2; ++j)
4044 succvertex2 = succ2[j];
4045 if ( ! verticesarefixed[succvertex2] )
4046 coververtices[(*ncoververtices)++] = succvertex2;
4056 for (v = 0; v < *ncoververtices; ++v)
4059 for (j = k; j < nsucc2; ++j)
4061 succvertex2 = succ2[j];
4062 if ( succvertex2 > coververtices[v] )
4068 else if ( succvertex2 == coververtices[v] )
4071 coververtices[vv++] = succvertex2;
4078 *ncoververtices = vv;
4085 for (s = 0; s < *ncoververtices; ++s)
4087 assert( *ncoververtices <= 1 || coververtices[*ncoververtices - 1] > coververtices[*ncoververtices - 2] );
4115 assert( scip !=
NULL );
4116 assert( conflictgraph !=
NULL );
4117 assert( verticesarefixed !=
NULL );
4118 assert( ! verticesarefixed[branchvertex] );
4119 assert( fixingsnode1 !=
NULL );
4120 assert( fixingsnode2 !=
NULL );
4121 assert( nfixingsnode1 !=
NULL );
4122 assert( nfixingsnode2 !=
NULL );
4139 for (j = 0; j < nsucc; ++j)
4143 assert( ! verticesarefixed[succ[j]] );
4144 fixingsnode1[(*nfixingsnode1)++] = succ[j];
4149 if ( *nfixingsnode1 > 0 )
4152 SCIP_CALL(
getCoverVertices(conflictgraph, verticesarefixed, branchvertex, fixingsnode1, *nfixingsnode1, fixingsnode2, nfixingsnode2) );
4155 SCIP_CALL(
getCoverVertices(conflictgraph, verticesarefixed, branchvertex, fixingsnode2, *nfixingsnode2, fixingsnode1, nfixingsnode1) );
4157 for (j = 0; j < *nfixingsnode2; ++j)
4168 for (j = 0; j < *nfixingsnode1; ++j)
4176 takeallsucc =
FALSE;
4185 for (j = 0; j < nsucc; ++j)
4187 if ( ! verticesarefixed[succ[j]] )
4188 fixingsnode1[(*nfixingsnode1)++] = succ[j];
4194 SCIP_CALL(
getCoverVertices(conflictgraph, verticesarefixed, branchvertex, fixingsnode1, *nfixingsnode1, fixingsnode2, nfixingsnode2) );
4199 fixingsnode2[0] = branchvertex;
4221 int* vertexbestprior,
4228 assert( scip !=
NULL );
4229 assert( conshdlrdata !=
NULL );
4230 assert( conflictgraph !=
NULL );
4231 assert( verticesarefixed !=
NULL );
4232 assert( fixingsnode1 !=
NULL );
4233 assert( fixingsnode2 !=
NULL );
4234 assert( relsolfeas !=
NULL );
4238 for (i = 0; i < nsos1vars; ++i)
4259 assert( ! verticesarefixed[i] );
4263 for (j = 0; j < nfixingsnode1; ++j)
4274 for (j = 0; j < nfixingsnode2; ++j)
4284 if ( iszero1 || iszero2 )
4287 prior = sum1 * sum2;
4290 if ( branchpriors !=
NULL )
4291 branchpriors[i] = prior;
4292 if ( bestprior < prior )
4296 if ( vertexbestprior !=
NULL )
4297 *vertexbestprior = i;
4304 *relsolfeas =
FALSE;
4323 int* ndomainfixings,
4332 assert( scip !=
NULL );
4333 assert( conflictgraph !=
NULL );
4334 assert( fixingsexec !=
NULL );
4335 assert( nfixingsop > 0 );
4336 assert( fixingsop !=
NULL );
4337 assert( nfixingsop > 0 );
4338 assert( inititer >= -1 );
4339 assert( domainfixings !=
NULL );
4340 assert( ndomainfixings !=
NULL );
4341 assert( *ndomainfixings >= 0 );
4342 assert( infeasible !=
NULL );
4343 assert( objval !=
NULL );
4344 assert( lperror !=
NULL );
4348 *infeasible =
FALSE;
4354 if ( fixnonzero && nfixingsop == 1 )
4394 for (i = 0; i < nfixingsexec && ! *infeasible; ++i)
4408 if ( ! *infeasible )
4434 for (i = 0; i < nfixingsop; ++i)
4435 domainfixings[(*ndomainfixings)++] = fixingsop[i];
4466 int* vertexbestprior,
4473 int* indsos1vars =
NULL;
4474 int* domainfixings =
NULL;
4481 int lastscorechange;
4490 assert( scip !=
NULL );
4491 assert( conshdlrdata !=
NULL );
4492 assert( conflictgraph !=
NULL );
4493 assert( verticesarefixed !=
NULL );
4494 assert( fixingsnode1 !=
NULL );
4495 assert( fixingsnode2 !=
NULL );
4496 assert( vertexbestprior !=
NULL );
4497 assert( result !=
NULL );
4504 bipbranch, fixingsnode1, fixingsnode2, branchpriors,
NULL, &relsolfeas) );
4509 SCIPdebugMsg(scip,
"all the SOS1 constraints are feasible.\n");
4523 for (j = 0; j < nsos1vars; ++j)
4536 nlpiterations = 1000;
4543 if ( conshdlrdata->nstrongiter == -2 )
4545 inititer = (int)(2*nlpiterations / nlps);
4547 inititer =
MAX(inititer, 10);
4548 inititer =
MIN(inititer, 500);
4551 inititer = conshdlrdata->nstrongiter;
4558 lastscorechange = -1;
4559 *vertexbestprior = indsos1vars[0];
4563 maxfailures = nstrongrounds;
4566 for (j = 0; j < nstrongrounds; ++j)
4571 testvertex = indsos1vars[j];
4584 assert( ! verticesarefixed[testvertex] );
4585 SCIP_CALL(
getBranchingVerticesSOS1(scip, conflictgraph, sol, verticesarefixed, bipbranch, testvertex, fixingsnode1, &nfixingsnode1, fixingsnode2, &nfixingsnode2) );
4589 inititer, conshdlrdata->fixnonzero, domainfixings, &ndomainfixings, &infeasible1, &objval1, &lperror) );
4595 inititer,
FALSE, domainfixings, &ndomainfixings, &infeasible2, &objval2, &lperror) );
4600 if ( infeasible1 && infeasible2 )
4614 else if ( ! infeasible1 && ! infeasible2 )
4617 if ( ndomainfixings == 0 )
4624 *vertexbestprior = testvertex;
4625 *bestobjval1 = objval1;
4626 *bestobjval2 = objval2;
4628 lastscorechange = j;
4630 else if ( j - lastscorechange > maxfailures )
4638 if ( ndomainfixings > 0 )
4643 for (i = 0; i < ndomainfixings; ++i)
4646 assert( ! infeasible );
4649 SCIPdebugMsg(scip,
"found %d domain fixings.\n", ndomainfixings);
4688 int* extensions =
NULL;
4689 int nextensions = 0;
4693 assert( scip !=
NULL );
4694 assert( conflictgraph !=
NULL );
4695 assert( cons !=
NULL );
4696 assert( feas !=
NULL );
4702 var = nodedata->var;
4707 if ( boundvar ==
NULL )
4727 else if ( boundvar == nodedata->ubboundvar )
4733 ub = nodedata->ubboundcoef;
4742 lb = nodedata->lbboundcoef;
4751 *feas += coef * solval;
4761 assert( nsucc > 0 );
4767 for (s = 0; s < nsucc; ++s)
4768 extensions[s] = succ[s];
4769 nextensions = nsucc;
4775 while ( nextensions > 0 )
4792 assert( extensions !=
NULL );
4793 for (s = 0; s < nextensions; ++s)
4795 ext = extensions[s];
4799 bestbigMval = bigMval;
4804 assert( bestindex != -1 );
4808 var = nodedata->var;
4811 if ( boundvar ==
NULL )
4831 else if ( boundvar == nodedata->ubboundvar )
4837 ub = nodedata->ubboundcoef;
4846 lb = nodedata->lbboundcoef;
4854 *feas += coef * solval;
4860 assert( extensions !=
NULL );
4863 for (s = 0; s < nextensions; ++s)
4866 extensions[nextensionsnew++] = extensions[s];
4868 nextensions = nextensionsnew;
4879 if ( boundvar ==
NULL )
4913 assert( scip !=
NULL );
4914 assert( node !=
NULL );
4915 assert( conshdlrdata !=
NULL );
4916 assert( conflictgraph !=
NULL );
4917 assert( verticesarefixed !=
NULL );
4918 assert( fixingsnode1 !=
NULL );
4919 assert( fixingsnode2 !=
NULL );
4920 assert( naddedconss !=
NULL );
4924 if ( nfixingsnode2 > 1 )
4950 for (i = 0; i < nsos1vars; ++i)
4951 mark[i] = (verticesarefixed[i]);
4954 for (i = 0; i < nfixingsnode1; ++i)
4956 assert( nfixingsnode1 <= 1 || (fixingsnode1[nfixingsnode1 - 1] > fixingsnode1[nfixingsnode1 - 2]) );
4957 mark[fixingsnode1[i]] =
TRUE;
4961 for (i = 0; i < nfixingsnode2; ++i)
4963 assert( nfixingsnode2 <= 1 || (fixingsnode2[nfixingsnode2 - 1] > fixingsnode2[nfixingsnode2 - 2]) );
4964 mark[fixingsnode2[i]] =
TRUE;
4969 for (i = 0; i < nfixingsnode2; ++i)
4974 for (s = 0; s < nsucc; ++s)
4976 int succnode = succ[s];
4978 if ( ! mark[succnode] )
4980 mark[succnode] =
TRUE;
4981 succarray[nsuccarray++] = succnode;
4990 for (i = 0; i < nsos1vars; ++i)
4994 for (i = 0; i < nfixingsnode2; ++i)
4995 mark[fixingsnode2[i]] =
TRUE;
4998 for (i = 0; i < nsuccarray; ++i)
5005 vertex1 = succarray[i];
5017 for (s = 0; s < nsucc; ++s)
5019 if ( mark[succ[s]] )
5021 fixingsnode21[nfixingsnode21++] = succ[s];
5022 assert( nfixingsnode21 == 1 || (fixingsnode21[nfixingsnode21 - 1] > fixingsnode21[nfixingsnode21 - 2]) );
5027 if ( nfixingsnode21 == nfixingsnode2 )
5032 assert( ! infeasible );
5038 assert ( nfixingsnode22 + nfixingsnode21 == nfixingsnode2 );
5041 SCIP_CALL(
getCoverVertices(conflictgraph, verticesarefixed, -1, fixingsnode22, nfixingsnode22, coverarray, &ncoverarray) );
5045 for (j = 0; j < ncoverarray; ++j)
5049 vertex2 = coverarray[j];
5050 assert( vertex2 != vertex1 );
5053 if ( vertex2 < vertex1 )
5081 assert( nodedata !=
NULL );
5082 boundvar1 = nodedata->ubboundvar;
5083 lbboundcoef1 = nodedata->lbboundcoef;
5084 ubboundcoef1 = nodedata->ubboundcoef;
5086 assert( nodedata !=
NULL );
5087 boundvar2 = nodedata->ubboundvar;
5088 lbboundcoef2 = nodedata->lbboundcoef;
5089 ubboundcoef2 = nodedata->ubboundcoef;
5095 if ( conshdlrdata->addextendedbds )
5097 if ( localconflicts ==
NULL )
5100 localconflicts = conshdlrdata->localconflicts;
5114 conshdlrdata->isconflocal =
TRUE;
5154 feas += solval1/ubboundcoef1;
5160 feas += solval1/lbboundcoef1;
5167 feas += solval2/ubboundcoef2;
5173 feas += solval2/lbboundcoef2;
5178 if (
SCIPisGT(scip, feas, conshdlrdata->addcompsfeas) )
5182 SCIP_CALL(
SCIPcreateConsSOS1(scip, &conssos1, name, 0,
NULL,
NULL,
TRUE,
TRUE,
TRUE,
FALSE,
TRUE,
5207 SCIP_CALL(
SCIPcreateConsLinear(scip, &conssos1, name, 0,
NULL,
NULL, -
SCIPinfinity(scip), 0.0,
TRUE,
FALSE,
TRUE,
FALSE,
FALSE,
5216 SCIP_CALL(
SCIPcreateConsLinear(scip, &conssos1, name, 0,
NULL,
NULL, -
SCIPinfinity(scip), 1.0,
TRUE,
FALSE,
TRUE,
FALSE,
FALSE,
5224 if (
SCIPisGT(scip, feas, conshdlrdata->addbdsfeas ) )
5235 if ( conshdlrdata->maxaddcomps >= 0 && *naddedconss > conshdlrdata->maxaddcomps )
5243 if ( conshdlrdata->maxaddcomps >= 0 && *naddedconss > conshdlrdata->maxaddcomps )
5269 for (j = 0; j < nsos1vars; ++j)
5331 int* fixingsnode1 =
NULL;
5332 int* fixingsnode2 =
NULL;
5354 assert( scip !=
NULL );
5355 assert( conshdlrdata !=
NULL );
5356 assert( conshdlr !=
NULL );
5357 assert( conss !=
NULL );
5358 assert( result !=
NULL );
5364 nsos1vars = conshdlrdata->nsos1vars;
5367 conflictgraph = conshdlrdata->conflictgraph;
5368 assert( ! conshdlrdata->isconflocal );
5371 for (c = 0; c < nconss; ++c)
5378 assert( cons !=
NULL );
5380 assert( consdata !=
NULL );
5383 if ( consdata->nvars < 2 )
5400 assert( ngen == 0 );
5403 if ( consdata->local )
5410 if ( conshdlrdata->localconflicts ==
NULL )
5415 vars = consdata->vars;
5416 nvars = consdata->nvars;
5417 for (i = 0; i < nvars-1; ++i)
5423 assert( indi >= 0 );
5427 for (j = i+1; j < nvars; ++j)
5431 assert( indj >= 0 );
5443 conshdlrdata->isconflocal =
TRUE;
5453 if ( conshdlrdata->isconflocal )
5455 for (j = 0; j < nsos1vars; ++j)
5471 if ( conshdlrdata->isconflocal )
5474 conshdlrdata->isconflocal =
FALSE;
5482 for (j = 0; j < nsos1vars; ++j)
5492 verticesarefixed[j] =
TRUE;
5494 verticesarefixed[j] =
FALSE;
5498 if ( conshdlrdata->branchingrule ==
'b' )
5502 if ( conshdlrdata->nstrongrounds >= 0 )
5503 nstrongrounds =
MIN(conshdlrdata->nstrongrounds, nsos1vars);
5513 nstrongrounds =
MIN(nsos1vars, nstrongrounds);
5526 if ( nstrongrounds == 0 )
5531 SCIP_CALL(
getBranchingPrioritiesSOS1(scip, conshdlrdata, conflictgraph, sol, nsos1vars, verticesarefixed, bipbranch, fixingsnode1, fixingsnode2,
NULL, &branchvertex, &relsolfeas) );
5536 SCIPdebugMsg(scip,
"all the SOS1 constraints are feasible.\n");
5542 if ( conshdlrdata->isconflocal )
5545 conshdlrdata->isconflocal =
FALSE;
5560 fixingsnode1, fixingsnode2, &branchvertex, &bestobjval1, &bestobjval2, result) );
5565 if ( conshdlrdata->isconflocal )
5568 conshdlrdata->isconflocal =
FALSE;
5581 if ( ! conshdlrdata->branchsos )
5584 if ( conshdlrdata->isconflocal )
5587 conshdlrdata->isconflocal =
FALSE;
5597 SCIPerrorMessage(
"Incompatible parameter setting: branchsos can only be set to false if all SOS1 variables are binary.\n");
5605 assert( branchvertex >= 0 && branchvertex < nsos1vars );
5606 assert( ! verticesarefixed[branchvertex] );
5607 SCIP_CALL(
getBranchingVerticesSOS1(scip, conflictgraph, sol, verticesarefixed, bipbranch, branchvertex, fixingsnode1, &nfixingsnode1, fixingsnode2, &nfixingsnode2) );
5612 for (j = 0; j < nfixingsnode1; ++j)
5621 objest = objest/((
SCIP_Real) nfixingsnode1);
5627 if ( conshdlrdata->fixnonzero && nfixingsnode2 == 1 )
5666 for (j = 0; j < nfixingsnode1; ++j)
5670 assert( ! infeasible );
5676 for (j = 0; j < nfixingsnode2; ++j)
5686 objest = objest/((
SCIP_Real) nfixingsnode2);
5692 for (j = 0; j < nfixingsnode2; ++j)
5695 assert( ! infeasible );
5700 if ( conshdlrdata->addcomps && ( conshdlrdata->addcompsdepth == -1 || conshdlrdata->addcompsdepth >=
SCIPgetDepth(scip) ) )
5704 assert( ! conshdlrdata->fixnonzero );
5708 nsos1vars, verticesarefixed, fixingsnode1, nfixingsnode1, fixingsnode2, nfixingsnode2, &naddedconss,
TRUE) );
5710 if ( naddedconss == 0 )
5714 nsos1vars, verticesarefixed, fixingsnode2, nfixingsnode2, fixingsnode1, nfixingsnode1, &naddedconss,
TRUE) );
5719 if ( nstrongrounds > 0 )
5726 if ( conshdlrdata->isconflocal )
5729 conshdlrdata->isconflocal =
FALSE;
5794 assert( scip !=
NULL );
5795 assert( conshdlr !=
NULL );
5796 assert( conss !=
NULL );
5797 assert( result !=
NULL );
5807 assert( conshdlrdata !=
NULL );
5810 for (c = 0; c < nconss; ++c)
5820 assert( cons !=
NULL );
5822 assert( consdata !=
NULL );
5826 nvars = consdata->nvars;
5827 vars = consdata->vars;
5846 assert( ngen == 0 );
5850 for (j = 0; j < nvars; ++j)
5856 if ( conshdlrdata->branchnonzeros )
5860 if ( conshdlrdata->branchweight )
5863 if ( consdata->weights[j] > weight )
5864 weight = consdata->weights[j];
5873 if ( cnt > 1 && weight > maxWeight )
5881 if ( branchCons ==
NULL )
5883 SCIPdebugMsg(scip,
"All SOS1 constraints are feasible.\n");
5888 if ( ! conshdlrdata->branchsos )
5893 for (j = 0; j < consdata->nvars; ++j)
5899 if ( j == consdata->nvars )
5906 SCIPerrorMessage(
"Incompatible parameter setting: branchsos can only be set to false if all SOS1 variables are binary.\n");
5914 assert( consdata !=
NULL );
5915 nvars = consdata->nvars;
5916 vars = consdata->vars;
5930 assert( ! infeasible );
5934 assert( ! infeasible );
5954 for (j = 0; j < nvars; ++j)
5966 w = weight1/weight2;
5969 assert( 0 <= ind && ind < nvars-1 );
5977 for (j = 0; j <= ind; ++j)
5987 for (j = 0; j <= ind; ++j)
5990 assert( ! infeasible );
5996 for (j = ind+1; j < nvars; ++j)
6002 objest = objest/((
SCIP_Real) (nvars - ind - 1));
6006 for (j = ind+1; j < nvars; ++j)
6009 assert( ! infeasible );
6032 assert( scip !=
NULL );
6033 assert( conshdlr !=
NULL );
6034 assert( conss !=
NULL );
6035 assert( result !=
NULL );
6039 assert( conshdlrdata !=
NULL );
6041 if ( conshdlrdata->addcomps && conshdlrdata->fixnonzero )
6043 SCIPerrorMessage(
"Incompatible parameter setting: addcomps = TRUE and fixnonzero = TRUE.\n");
6047 if ( conshdlrdata->fixnonzero && ( conshdlrdata->branchingrule ==
'b' || conshdlrdata->branchingrule ==
's' ) )
6049 SCIPerrorMessage(
"Incompatible parameter setting: nonzero fixing is not compatible with bipartite or sos1 branching.\n");
6053 if ( conshdlrdata->branchingrule ==
's' && conshdlrdata->nstrongrounds != 0 )
6055 SCIPerrorMessage(
"Strong branching is not available for SOS1 branching.\n");
6059 if ( conshdlrdata->branchingrule ==
's' || conshdlrdata->switchsos1branch )
6066 if ( conshdlrdata->branchingrule !=
'n' && conshdlrdata->branchingrule !=
'b' )
6068 SCIPerrorMessage(
"branching rule %c unknown\n", conshdlrdata->branchingrule);
6100 for (j = 0; j < nsos1vars; ++j)
6107 for (j = 0; j < nsos1vars; ++j)
6117 for (i = 0; i < nsucc; ++i)
6134 tcliquedata = conshdlrdata->tcliquedata;
6137 tcliquedata->
scip = scip;
6142 tcliquedata->
ncuts = 0;
6143 tcliquedata->
nboundcuts = conshdlrdata->nboundcuts;
6145 tcliquedata->
maxboundcuts = conshdlrdata->maxboundcutsroot;
6167 for (j = 0; j < nsos1vars; ++j)
6178 if ( conshdlrdata->strthenboundcuts )
6185 if ( conshdlrdata->strthenboundcuts )
6198 nodeweight =
REALABS( solval/bound ) * scaleval;
6222 assert( scip !=
NULL );
6223 assert( tcliquedata !=
NULL );
6224 assert( success !=
NULL);
6225 assert( cutoff !=
NULL );
6231 if ( rowlb !=
NULL )
6242 ++tcliquedata->
ncuts;
6248 if ( rowub !=
NULL )
6259 ++tcliquedata->
ncuts;
6298 const char* nameext,
6311 assert( scip !=
NULL );
6312 assert( conshdlr !=
NULL );
6313 assert( conflictgraph !=
NULL );
6314 assert( ! local || ! global );
6315 assert( nodes !=
NULL );
6322 if ( rowub !=
NULL )
6331 useboundvar = strengthen;
6332 for (j = 0; j <
nnodes; ++j)
6339 assert( nodedata !=
NULL );
6340 var = nodedata->var;
6341 assert( var !=
NULL );
6344 if ( ! useboundvar || nodedata->ubboundvar ==
NULL )
6346 useboundvar =
FALSE;
6367 if ( ubboundvar ==
NULL )
6369 ubboundvar = nodedata->ubboundvar;
6370 val = nodedata->ubboundcoef;
6373 else if ( ubboundvar == nodedata->ubboundvar )
6374 val = nodedata->ubboundcoef;
6377 useboundvar =
FALSE;
6399 vals[cnt++] = 1.0/val;
6404 if ( j == nnodes && cnt >= 2 )
6414 rhs = rhs * vals[0] * vals[1];
6415 assert( (! useboundvar && cnt == 2 ) || (useboundvar && cnt == 3 ) );
6421 vars[cnt] = ubboundvar;
6423 assert(ubboundvar !=
NULL );
6444 if ( rowlb !=
NULL )
6454 useboundvar = strengthen;
6455 for (j = 0; j <
nnodes; ++j)
6462 assert( nodedata !=
NULL );
6463 var = nodedata->var;
6464 assert( var !=
NULL );
6467 if ( ! useboundvar || nodedata->lbboundvar ==
NULL )
6469 useboundvar =
FALSE;
6490 if ( lbboundvar ==
NULL )
6492 lbboundvar = nodedata->lbboundvar;
6493 val = nodedata->lbboundcoef;
6496 else if (
SCIPvarCompare(lbboundvar, nodedata->lbboundvar) == 0 )
6498 val = nodedata->lbboundcoef;
6502 useboundvar =
FALSE;
6524 vals[cnt++] = 1.0/val;
6529 if ( j == nnodes && cnt >= 2 )
6539 rhs = rhs * vals[0] * vals[1];
6540 assert( (! useboundvar && cnt == 2 ) || (useboundvar && cnt == 3 ) );
6546 vars[cnt] = lbboundvar;
6548 assert(lbboundvar !=
NULL );
6583 assert( acceptsol !=
NULL );
6584 assert( stopsolving !=
NULL );
6589 *stopsolving =
FALSE;
6592 minweightinc = (cliqueweight - *minweight)/10;
6593 minweightinc =
MAX(minweightinc, 1);
6594 *minweight += minweightinc;
6597 if( cliqueweight > tcliquedata->
scaleval )
6608 scip = tcliquedata->
scip;
6609 sol = tcliquedata->
sol;
6610 assert( scip !=
NULL );
6613 unscaledweight = 0.0;
6614 for( i = 0; i < ncliquenodes; i++ )
6616 node = cliquenodes[i];
6640 unscaledweight +=
REALABS( solval/bound );
6670 if ( rowlb !=
NULL )
6679 if ( rowub !=
NULL )
6692 SCIPdebugMsg(scip,
" -> found bound cut corresponding to clique (act=%g)\n", unscaledweight);
6702 *stopsolving =
TRUE;
6706 *stopsolving =
TRUE;
6731 int maxtreenodes = 10000;
6732 int maxzeroextensions = 1000;
6733 int backtrackfreq = 1000;
6738 assert( scip !=
NULL );
6739 assert( conshdlr !=
NULL );
6740 assert( conshdlrdata !=
NULL );
6741 assert( ngen !=
NULL );
6745 assert( conflictgraph !=
NULL );
6751 tcliquedata = conshdlrdata->tcliquedata;
6754 tcliquedata->
sol = sol;
6755 tcliquedata->
ncuts = 0;
6765 tcliqueMaxClique(tcliqueGetNNodes, tcliqueGetWeights, tcliqueIsEdge, tcliqueSelectAdjnodes,
6766 conshdlrdata->tcliquegraph, tcliqueNewsolClique, tcliquedata,
6767 cliquenodes, &ncliquenodes, &cliqueweight, (
int)scaleval-1, (
int)scaleval+1,
6768 maxtreenodes, backtrackfreq, maxzeroextensions, -1, &ntreenodes, &tcliquestatus);
6774 *ngen = tcliquedata->
ncuts;
6777 *cutoff = tcliquedata->
cutoff;
6780 conshdlrdata->nboundcuts = tcliquedata->
nboundcuts;
6807 assert( scip !=
NULL );
6808 assert( conshdlr !=
NULL );
6809 assert( cons !=
NULL );
6813 assert( consdata !=
NULL );
6814 assert( consdata->vars !=
NULL );
6815 nvars = consdata->nvars;
6819 assert( conshdlrdata !=
NULL );
6826 for (j = 0; j < nvars; ++j)
6867 assert( scip !=
NULL );
6868 assert( conshdlrdata !=
NULL );
6869 assert( conss !=
NULL );
6873 for (c = 0; c < nconss; ++c)
6880 assert( conss !=
NULL );
6881 assert( conss[c] !=
NULL );
6883 assert( consdata !=
NULL );
6896 if ( consdata->local )
6903 if ( consdata->rowub ==
NULL || consdata->rowlb ==
NULL )
6906 (consdata->rowlb ==
NULL) ? &consdata->rowlb :
NULL,
6907 (consdata->rowub == NULL) ? &consdata->rowub : NULL) );
6909 rowub = consdata->rowub;
6910 rowlb = consdata->rowlb;
6941 if ( rowlb !=
NULL )
6945 if ( rowub !=
NULL )
6951 if ( *cutoff || ( maxboundcuts >= 0 && cnt >= maxboundcuts ) )
6980 assert( scip !=
NULL);
6981 assert( conshdlrdata !=
NULL);
6982 assert( conshdlr !=
NULL);
6983 assert( ngen !=
NULL);
6984 assert( cutoff !=
NULL);
6990 if ( conshdlrdata->conflictgraph ==
NULL )
6994 implgraph = conshdlrdata->implgraph;
6997 if ( implgraph ==
NULL )
7004 SCIP_CALL(
initImplGraphSOS1(scip, conshdlrdata, conshdlrdata->conflictgraph, conshdlrdata->nsos1vars, conshdlrdata->maxtightenbds, &nchbds, cutoff, &success) );
7005 if ( *cutoff || ! success )
7007 implgraph = conshdlrdata->implgraph;
7014 nimplnodes = conshdlrdata->nimplnodes;
7015 assert( implgraph !=
NULL );
7016 assert( nimplnodes > 0);
7024 for (i = 0; i < nimplnodes && ! genbreak; ++i)
7036 assert( nodedata !=
NULL );
7037 var = nodedata->var;
7038 assert( var !=
NULL );
7046 for (s = 0; s < nsucc && ! genbreak; ++s)
7061 succdata = succdatas[s];
7062 assert( nodedata !=
NULL && succdata !=
NULL && nodedata->var !=
NULL );
7063 succvar = nodedata->var;
7075 bound1lower =
FALSE;
7080 for (k = 0; k < 2; ++k)
7088 impl = succdata->lbimpl;
7100 impl = succdata->ubimpl;
7114 bound2lower =
FALSE;
7117 lhsrhs = bound1 * bound2;
7120 if ( bound1lower == bound2lower )
7122 if (
SCIPisFeasGT(scip, solval * (bound2-impl) + solvalsucc * bound1, lhsrhs) )
7131 if (
SCIPisFeasLT(scip, solval * (bound2-impl) + solvalsucc * bound1, lhsrhs) )
7171 if ( maxcuts >= 0 && *ngen > maxcuts )
7202 assert( scip !=
NULL );
7203 assert( conshdlr !=
NULL );
7204 assert( conss !=
NULL );
7205 assert( result !=
NULL );
7220 assert( conshdlrdata !=
NULL );
7227 if ( conshdlrdata->boundcutsfreq >= 0 && ( (conshdlrdata->boundcutsfreq == 0 && depth == 0) || (conshdlrdata->boundcutsfreq > 0 && depth % conshdlrdata->boundcutsfreq == 0)) )
7234 maxboundcuts = conshdlrdata->maxboundcutsroot;
7236 maxboundcuts = conshdlrdata->maxboundcuts;
7238 if ( maxboundcuts >= 1 )
7241 if( conshdlrdata->boundcutsfromsos1 || conshdlrdata->switchcutsfromsos1 )
7254 if( conshdlrdata->boundcutsfromgraph && ! conshdlrdata->switchcutsfromsos1 )
7269 SCIPdebugMsg(scip,
"Separated %d bound (clique) inequalities.\n", ngen);
7274 if ( conshdlrdata->implcutsfreq >= 0 && ( (conshdlrdata->implcutsfreq == 0 && depth == 0) || (conshdlrdata->implcutsfreq > 0 && depth % conshdlrdata->implcutsfreq == 0)) )
7281 maximplcuts = conshdlrdata->maximplcutsroot;
7283 maximplcuts = conshdlrdata->maximplcuts;
7286 if ( maximplcuts >= 1 )
7300 SCIPdebugMsg(scip,
"Separated %d implied bound inequalities.\n", ngen);
7329 assert( scip !=
NULL );
7330 assert( conflictgraph !=
NULL );
7331 assert( indicatorzero !=
NULL );
7332 assert( weights !=
NULL );
7334 for (i = 0; i < nsos1vars; ++i)
7338 if( nsucc == 0 || indicatorzero[i] )
7352 for (j = 0; j < nsucc; ++j)
7359 sum +=
MIN(10E05, valsucc);
7369 val =
MIN(1e6, val);
7397 assert( scip !=
NULL );
7398 assert( conflictgraph !=
NULL );
7399 assert( mark !=
NULL );
7400 assert( indset !=
NULL );
7401 assert( cutoff !=
NULL );
7402 assert( cnt !=
NULL );
7410 for (j = 0; j < nsucc && !(*cutoff); ++j)
7415 assert( indset[succj] == 0 );
7437 if ( aggrnode >= 0 )
7442 if ( ! mark[aggrnode] )
7444 mark[aggrnode] =
TRUE;
7447 else if ( indset[aggrnode] == 1 )
7456 if ( indset[aggrnode] == 0 )
7459 if ( mark[aggrnode] )
7466 indset[aggrnode] = 1;
7467 mark[aggrnode] =
TRUE;
7488 if ( indset[negnode] == 1 )
7493 else if ( ! mark[negnode] )
7495 mark[negnode] =
TRUE;
7535 int* indscipvars =
NULL;
7541 assert( scip !=
NULL );
7542 assert( conflictgraph !=
NULL );
7543 assert( indicatorzero !=
NULL );
7544 assert( indset !=
NULL );
7552 for (i = 0; i < nsos1vars; ++i)
7560 for (i = 0; i < nsos1vars; ++i)
7564 if ( indset[i] == 0 )
7566 if( indicatorzero[i] )
7571 else if ( nsucc == 0 )
7593 for (i = 0; k < nsos1vars; ++i)
7595 assert( i < nsos1vars );
7597 ind = indscipvars[i];
7613 assert( k == nsos1vars );
7643 assert( scip !=
NULL );
7644 assert( conshdlr !=
NULL );
7645 assert( sol !=
NULL );
7646 assert( changed !=
NULL );
7648 *allroundable =
TRUE;
7653 assert( nsos1vars >= 0 );
7657 assert( conflictgraph !=
NULL );
7664 for (j = 0; j < nsos1vars; ++j)
7677 indicatorzero[j] =
TRUE;
7680 indicatorzero[j] =
FALSE;
7685 *allroundable =
FALSE;
7691 indicatorzero[j] =
TRUE;
7698 if ( ! (*allroundable) )
7709 for (j = 0; j < nsos1vars; ++j)
7711 if ( indset[j] == 0 )
7731 for (c = 0; c < nconss; ++c)
7735 assert( consdata !=
NULL );
7737 for (j = 0; j < consdata->nvars; ++j)
7771 assert( scip !=
NULL );
7772 assert( conshdlr !=
NULL );
7773 assert( sol !=
NULL );
7774 assert( changed !=
NULL );
7776 *allroundable =
TRUE;
7782 assert( nconss > 0 );
7785 for (c = 0; c < nconss && *allroundable; ++c)
7796 assert( cons !=
NULL );
7798 assert( consdata !=
NULL );
7800 nvars = consdata->nvars;
7801 vars = consdata->vars;
7804 for (j = 0; j < nvars; ++j)
7821 *allroundable =
FALSE;
7834 assert( ! varisfixed );
7852 if ( ! (*allroundable) )
7854 else if ( pos >= 0 )
7861 if ( *allroundable )
7863 for (c = 0; c < nconss; ++c)
7869 assert( consdata !=
NULL );
7871 for (j = 0; j < consdata->nvars; ++j)
7908 assert( scip !=
NULL );
7909 assert( conshdlr !=
NULL );
7910 assert( diveset !=
NULL );
7911 assert( success !=
NULL );
7922 for (v = 0; v < nsos1vars; ++v)
7964 &score, &roundup) );
7968 fixneigh = !fixneigh;
7980 if ( score > bestscore )
7987 bestvarfixneigh = fixneigh;
7991 assert( !(*success) || bestvar !=
NULL );
7999 assert( bestnode >= 0 && bestnode < nsos1vars );
8009 for (s = 0; s < nsucc; ++s)
8050 assert( scip !=
NULL );
8051 assert( conshdlr !=
NULL );
8052 assert( diveset !=
NULL );
8053 assert( success !=
NULL );
8062 for (c = 0; c < nconss; ++c)
8070 assert( consdata !=
NULL );
8072 nvars = consdata->nvars;
8073 vars = consdata->vars;
8076 for (j = 0; j < nvars && cnt < 2; ++j)
8093 for (j = 0; j < nvars; ++j)
8140 &score, &roundup) );
8156 if ( score > bestscore )
8163 bestvarfixcomp = fixcomp;
8168 assert( !(*success) || bestvar !=
NULL );
8177 assert( consdata !=
NULL );
8179 nvars = consdata->nvars;
8180 vars = consdata->vars;
8182 assert( bestcons >= 0 && bestcons < nconss );
8190 for (j = 0; j < nvars; ++j)
8225 assert( scip !=
NULL );
8226 assert( conshdlrdata !=
NULL );
8227 assert( var0 !=
NULL && var1 !=
NULL );
8251 if ( nodedata->lbboundvar ==
NULL )
8254 nodedata->lbboundvar = var1;
8255 nodedata->lbboundcoef = val;
8269 if ( nodedata->ubboundvar ==
NULL )
8272 nodedata->ubboundvar = var1;
8273 nodedata->ubboundcoef = val;
8306 assert( scip !=
NULL );
8307 assert( conflictgraph !=
NULL );
8308 assert( processed !=
NULL );
8309 assert( concomp !=
NULL );
8310 assert( nconcomp !=
NULL );
8311 assert( unique !=
NULL );
8313 processed[node] =
TRUE;
8314 concomp[(*nconcomp)++] = node;
8322 assert( nodedata !=
NULL );
8325 comparevar = nodedata->lbboundvar;
8327 comparevar = nodedata->ubboundvar;
8330 if ( boundvar ==
NULL )
8332 if ( comparevar !=
NULL )
8337 if ( comparevar ==
NULL )
8347 for (s = 0; s < nsucc; ++s)
8349 if ( ! processed[succ[s]] )
8375 assert( scip !=
NULL );
8376 assert( conflictgraph !=
NULL );
8381 for (j = 0; j < nsos1vars; ++j)
8382 processed[j] =
FALSE;
8385 for (j = 0; j < nsos1vars; ++j)
8388 if ( ! processed[j] )
8398 assert( nodedata !=
NULL );
8401 boundvar = nodedata->lbboundvar;
8403 boundvar = nodedata->ubboundvar;
8406 processed[j] =
TRUE;
8413 for (s = 0; s < nsucc; ++s)
8415 if ( ! processed[succ[s]] )
8422 if ( unique && boundvar !=
NULL )
8424 for (s = 0; s < nconcomp; ++s)
8427 assert( processed[concomp[s]] ==
TRUE );
8428 assert( nodedata !=
NULL );
8431 nodedata->lbboundcomp =
TRUE;
8433 nodedata->ubboundcomp =
TRUE;
8435 SCIPdebugMsg(scip,
"Found a connected component of size <%i> with unique bound variable.\n", nconcomp);
8462 for (c = 0; c < nlinconss; ++c)
8467 lincons = linconss[c];
8488 assert( var0 !=
NULL && var1 !=
NULL );
8537 if ( conshdlrdata->nsos1vars > 0 )
8539 for (c = 0; c < nconss && nonoverlap; ++c)
8547 assert( conss[c] !=
NULL );
8551 assert( consdata !=
NULL );
8554 nvars = consdata->nvars;
8555 vars = consdata->vars;
8558 for (i = 0; i < nvars; ++i)
8565 for (i = 0; i < nvars; ++i)
8569 assert( vars[i] !=
NULL );
8573 assert( node < conshdlrdata->nsos1vars );
8587 if ( conshdlrdata->autosos1branch )
8589 conshdlrdata->switchsos1branch =
TRUE;
8590 SCIPdebugMsg(scip,
"Switched to SOS1 branching, since the SOS1 constraints do not overlap\n");
8593 if ( conshdlrdata->autocutsfromsos1 )
8595 conshdlrdata->switchcutsfromsos1 =
TRUE;
8596 SCIPdebugMsg(scip,
"Switched to separating bound cuts from SOS1 constraints (and not from the conflict graph), since the SOS1 constraints do not overlap\n");
8617 if ( nsos1vars == 0 )
8622 if ( linconshdlr ==
NULL )
8659 assert( conshdlrdata !=
NULL );
8660 assert( nconss == 0 || conss !=
NULL );
8668 for (i = 0; i < ntotalvars; ++i)
8669 nodecreated[i] =
FALSE;
8673 for (c = 0; c < nconss; ++c)
8679 assert( conss[c] !=
NULL );
8683 assert( consdata !=
NULL );
8686 nvars = consdata->nvars;
8687 vars = consdata->vars;
8690 for (i = 0; i < nvars; ++i)
8702 assert( ind >= 0 && ind < ntotalvars );
8703 if ( ! nodecreated[ind] )
8705 nodecreated[ind] =
TRUE;
8706 nodeorig[ind] = cntsos;
8717 conshdlrdata->nsos1vars = 0;
8722 for (i = 0; i < ntotalvars; ++i)
8723 nodecreated[i] =
FALSE;
8733 for (c = 0; c < nconss; ++c)
8739 assert( conss[c] !=
NULL );
8743 assert( consdata !=
NULL );
8746 nvars = consdata->nvars;
8747 vars = consdata->vars;
8750 for (i = 0; i < nvars; ++i)
8763 if ( ! nodecreated[indi] )
8775 nodedata->var = var;
8776 nodedata->lbboundvar =
NULL;
8777 nodedata->ubboundvar =
NULL;
8778 nodedata->lbboundcoef = 0.0;
8779 nodedata->ubboundcoef = 0.0;
8780 nodedata->lbboundcomp =
FALSE;
8781 nodedata->ubboundcomp =
FALSE;
8787 nodecreated[indi] =
TRUE;
8792 for (j = i+1; j < nvars; ++j)
8817 conshdlrdata->nsos1vars = cntsos;
8824 for (j = 0; j < conshdlrdata->nsos1vars; ++j)
8845 if ( conshdlrdata->conflictgraph ==
NULL )
8847 assert( conshdlrdata->nsos1vars == 0 );
8852 assert( conshdlrdata->nsos1vars > 0 );
8853 for (j = 0; j < conshdlrdata->nsos1vars; ++j)
8858 assert( conshdlrdata->conflictgraph !=
NULL );
8860 assert( nodedata !=
NULL );
8868 assert( conshdlrdata->varhash !=
NULL );
8871 conshdlrdata->nsos1vars = 0;
8873 assert( conshdlrdata->varhash ==
NULL );
8874 assert( conshdlrdata->conflictgraph ==
NULL );
8886 assert( scip !=
NULL );
8887 assert( conshdlr !=
NULL );
8905 assert( scip !=
NULL );
8906 assert( conshdlr !=
NULL );
8910 assert(conshdlrdata !=
NULL);
8927 assert( scip !=
NULL );
8928 assert( conshdlr !=
NULL );
8932 assert( conshdlrdata !=
NULL );
8934 conshdlrdata->nsos1vars = 0;
8935 conshdlrdata->varhash =
NULL;
8945 if ( ( conshdlrdata->autosos1branch || conshdlrdata->autocutsfromsos1 )
8946 && ( ! conshdlrdata->switchsos1branch || ! conshdlrdata->switchcutsfromsos1 )
8957 if ( conshdlrdata->addcomps )
8963 if ( conshdlrdata->fixnonzerovars ==
NULL )
8965 conshdlrdata->maxnfixnonzerovars = conshdlrdata->nsos1vars;
8981 assert( scip !=
NULL );
8985 assert( conshdlrdata !=
NULL );
8988 for (c = 0; c < nconss; ++c)
8992 assert( conss !=
NULL );
8993 assert( conss[c] !=
NULL );
8995 assert( consdata !=
NULL );
9000 if ( consdata->rowub !=
NULL )
9005 if ( consdata->rowlb !=
NULL )
9012 if ( conshdlrdata->implgraph !=
NULL )
9016 assert( conshdlrdata->implgraph ==
NULL );
9019 if ( conshdlrdata->tcliquegraph !=
NULL )
9021 assert( conshdlrdata->tcliquedata !=
NULL );
9025 assert(conshdlrdata->tcliquegraph ==
NULL);
9026 assert(conshdlrdata->tcliquedata ==
NULL);
9030 conshdlrdata->nfixnonzerovars = 0;
9031 conshdlrdata->maxnfixnonzerovars = 0;
9034 if ( conshdlrdata->localconflicts !=
NULL )
9036 assert( conshdlrdata->localconflicts ==
NULL );
9040 assert( conshdlrdata->conflictgraph ==
NULL );
9050 assert( scip !=
NULL );
9051 assert( conshdlr !=
NULL );
9052 assert( cons !=
NULL );
9053 assert( consdata !=
NULL );
9066 assert( conshdlrdata !=
NULL );
9067 assert( conshdlrdata->eventhdlr !=
NULL );
9069 for (j = 0; j < (*consdata)->nvars; ++j)
9077 if ( (*consdata)->weights !=
NULL )
9083 if ( (*consdata)->rowub !=
NULL )
9087 if ( (*consdata)->rowlb !=
NULL )
9091 assert( (*consdata)->rowub ==
NULL );
9092 assert( (*consdata)->rowlb ==
NULL );
9110 assert( scip !=
NULL );
9111 assert( conshdlr !=
NULL );
9113 assert( sourcecons !=
NULL );
9114 assert( targetcons !=
NULL );
9118 assert( conshdlrdata !=
NULL );
9119 assert( conshdlrdata->eventhdlr !=
NULL );
9125 assert( sourcedata !=
NULL );
9126 assert( sourcedata->nvars > 0 );
9127 assert( sourcedata->nvars <= sourcedata->maxvars );
9130 if ( conshdlrdata->fixnonzerovars ==
NULL )
9139 consdata->nvars = sourcedata->nvars;
9140 consdata->maxvars = sourcedata->nvars;
9141 consdata->rowub =
NULL;
9142 consdata->rowlb =
NULL;
9143 consdata->nfixednonzeros = 0;
9144 consdata->local = sourcedata->local;
9147 if ( sourcedata->weights !=
NULL )
9152 consdata->weights =
NULL;
9154 for (j = 0; j < sourcedata->nvars; ++j)
9156 assert( sourcedata->vars[j] != 0 );
9161 ++(consdata->nfixednonzeros);
9174 for (j = 0; j < consdata->nvars; ++j)
9181 if ( consdata->nfixednonzeros > 0 )
9184 consdata->nfixednonzeros );
9203 assert( scip !=
NULL );
9204 assert( conshdlr !=
NULL );
9206 assert( result !=
NULL );
9209 assert( conshdlrdata !=
NULL );
9215 SCIPdebug( oldnfixedvars = *nfixedvars; )
9218 SCIPdebug( oldnupgdconss = *nupgdconss; )
9222 if( nconss > 0 && ( nrounds == 0 || nnewfixedvars > 0 || nnewaggrvars > 0 || nnewchgbds > 0 ) )
9236 assert( eventhdlr !=
NULL );
9242 conflictgraph = conshdlrdata->conflictgraph;
9243 nsos1vars = conshdlrdata->nsos1vars;
9244 if ( nsos1vars < 2 )
9251 if ( conshdlrdata->maxsosadjacency == -1 || nsos1vars <= conshdlrdata->maxsosadjacency )
9255 for (i = 0; i < nsos1vars; ++i)
9261 for (i = 0; i < nsos1vars; ++i)
9263 for (j = 0; j < i+1; ++j)
9264 adjacencymatrix[i][j] = 0;
9266 for (i = 0; i < nsos1vars; ++i)
9274 for (j = 0; j < nsucc; ++j)
9277 adjacencymatrix[i][succ[j]] = 1;
9283 SCIPdebugMsg(scip,
"Adjacency matrix was not created since number of SOS1 variables (%d) is larger than %d.\n", nsos1vars, conshdlrdata->maxsosadjacency);
9287 SCIP_CALL(
presolRoundConssSOS1(scip, eventhdlr, conshdlrdata, conflictgraph, adjacencymatrix, conss, nconss, nsos1vars, naddconss, ndelconss, nupgdconss, nfixedvars, &nremovedvars, result) );
9289 if ( adjacencymatrix !=
NULL )
9292 if ( conshdlrdata->maxtightenbds != 0 && *result !=
SCIP_CUTOFF )
9294 SCIP_CALL(
presolRoundVarsSOS1(scip, conshdlrdata, conflictgraph, adjacencymatrix, nsos1vars, nfixedvars, nchgbds, naddconss, result) );
9298 for (j = nsos1vars-1; j >= 0; --j)
9306 (*nchgcoefs) += nremovedvars;
9308 SCIPdebugMsg(scip,
"presolving fixed %d variables, changed %d bounds, removed %d variables, deleted %d constraints, and upgraded %d constraints.\n",
9309 *nfixedvars - oldnfixedvars, *nchgbds - oldnchgbds, nremovedvars, *ndelconss - oldndelconss, *nupgdconss - oldnupgdconss);
9321 assert( scip !=
NULL );
9322 assert( conshdlr !=
NULL );
9326 assert( conshdlrdata !=
NULL );
9328 *infeasible =
FALSE;
9331 if( conshdlrdata->boundcutsfromsos1 || conshdlrdata->switchcutsfromsos1 )
9344 assert( scip !=
NULL );
9345 assert( conshdlr !=
NULL );
9346 assert( conss !=
NULL );
9360 assert( scip !=
NULL );
9361 assert( conshdlr !=
NULL );
9362 assert( conss !=
NULL );
9376 assert( scip !=
NULL );
9377 assert( conshdlr !=
NULL );
9378 assert( conss !=
NULL );
9392 assert( scip !=
NULL );
9393 assert( conshdlr !=
NULL );
9394 assert( conss !=
NULL );
9408 assert( scip !=
NULL );
9409 assert( conshdlr !=
NULL );
9410 assert( conss !=
NULL );
9429 assert( scip !=
NULL );
9430 assert( conshdlr !=
NULL );
9433 assert( result !=
NULL );
9438 for (c = 0; c < nconss && (*result ==
SCIP_FEASIBLE || completely); ++c)
9445 assert( conss[c] !=
NULL );
9447 assert( consdata !=
NULL );
9451 for (j = 0; j < consdata->nvars; ++j)
9471 for (l = 0; l < consdata->nvars; ++l)
9500 assert( scip !=
NULL );
9501 assert( conshdlr !=
NULL );
9502 assert( conss !=
NULL );
9504 assert( result !=
NULL );
9517 assert( conshdlrdata !=
NULL );
9520 conflictgraph = conshdlrdata->conflictgraph;
9523 implgraph = conshdlrdata->implgraph;
9524 if ( implgraph ==
NULL && conshdlrdata->implprop && conflictgraph !=
NULL )
9532 SCIP_CALL(
initImplGraphSOS1(scip, conshdlrdata, conflictgraph, conshdlrdata->nsos1vars, conshdlrdata->maxtightenbds, &nchbds, &cutoff, &success) );
9534 conshdlrdata->implprop =
FALSE;
9541 else if ( nchbds > 0 )
9543 implgraph = conshdlrdata->implgraph;
9546 conshdlrdata->implprop =
FALSE;
9550 if ( conshdlrdata->conflictprop && conflictgraph !=
NULL )
9553 int nfixnonzerovars;
9556 assert( nconss > 0 );
9559 nfixnonzerovars = conshdlrdata->nfixnonzerovars;
9560 fixnonzerovars = conshdlrdata->fixnonzerovars;
9561 assert( fixnonzerovars !=
NULL );
9564 for (j = 0; j < nfixnonzerovars; ++j)
9568 var = fixnonzerovars[j];
9577 assert(
varGetNodeSOS1(conshdlrdata, var) < conshdlrdata->nsos1vars );
9596 conshdlrdata->nfixnonzerovars = 0;
9599 if ( conshdlrdata->sosconsprop || conflictgraph ==
NULL )
9604 for (c = 0; c < nconss; ++c)
9610 assert( conss[c] !=
NULL );
9613 assert( consdata !=
NULL );
9643 assert( scip !=
NULL );
9644 assert( cons !=
NULL );
9646 assert( infervar !=
NULL );
9647 assert( bdchgidx !=
NULL );
9648 assert( result !=
NULL );
9654 if ( inferinfo < 0 )
9658 assert( conshdlr !=
NULL );
9662 assert( conshdlrdata !=
NULL );
9663 assert( conshdlrdata->conflictgraph !=
NULL );
9664 assert( inferinfo >= -conshdlrdata->maxnfixnonzerovars );
9665 assert( inferinfo >= -conshdlrdata->nsos1vars );
9666 assert( inferinfo <= -1 );
9676 assert( consdata !=
NULL );
9677 assert( inferinfo < consdata->nvars );
9679 var = consdata->vars[inferinfo];
9681 assert( var !=
NULL );
9682 assert( var != infervar );
9722 assert( scip !=
NULL );
9723 assert( conshdlr !=
NULL );
9724 assert( cons !=
NULL );
9727 assert( consdata !=
NULL );
9731 vars = consdata->vars;
9732 nvars = consdata->nvars;
9733 assert( vars !=
NULL );
9735 for (j = 0; j < nvars; ++j)
9764 assert( scip !=
NULL );
9766 assert( cons !=
NULL );
9770 assert( consdata !=
NULL );
9772 for (j = 0; j < consdata->nvars; ++j)
9777 if ( consdata->weights ==
NULL )
9796 const char* consname;
9800 assert( scip !=
NULL );
9801 assert( sourcescip !=
NULL );
9802 assert( sourcecons !=
NULL );
9812 SCIPdebugMsg(scip,
"Copying SOS1 constraint <%s> ...\n", consname);
9815 assert( sourceconsdata !=
NULL );
9818 nvars = sourceconsdata->nvars;
9823 sourcevars = sourceconsdata->vars;
9824 assert( sourcevars !=
NULL );
9825 sourceweights = sourceconsdata->weights;
9826 assert( sourceweights !=
NULL );
9833 for( v = 0; v < nvars && *valid; ++v )
9835 SCIP_CALL(
SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &(targetvars[v]), varmap, consmap, global, valid) );
9842 initial, separate, enforce, check, propagate, local, dynamic, removable, stickingatnode) );
9862 assert(scip !=
NULL);
9863 assert(conshdlr !=
NULL);
9865 assert(cons !=
NULL);
9866 assert(success !=
NULL);
9872 SCIP_CALL(
SCIPcreateConsSOS1(scip, cons, name, 0,
NULL,
NULL, initial, separate, enforce, check, propagate, local, dynamic, removable, stickingatnode) );
9882 while ( *s !=
'\0' && *s !=
'(' )
9895 weight = strtod(s, &t);
9905 while ( *s !=
'\0' && ( isspace((
unsigned char)*s) || *s ==
',' || *s ==
')' ) )
9911 while ( *s !=
'\0' );
9924 assert(consdata !=
NULL);
9926 if( varssize < consdata->nvars )
9930 assert(vars !=
NULL);
9947 assert(consdata !=
NULL);
9949 (*nvars) = consdata->nvars;
9973 assert( eventhdlr !=
NULL );
9974 assert( eventdata !=
NULL );
9976 assert( event !=
NULL );
9979 assert( cons !=
NULL );
9981 assert( 0 <= consdata->nfixednonzeros && consdata->nfixednonzeros <= consdata->nvars );
9987 switch ( eventtype )
9994 assert( conshdlr !=
NULL );
9996 assert( conshdlrdata !=
NULL );
9999 assert( 0 <= conshdlrdata->nfixnonzerovars && conshdlrdata->nfixnonzerovars <=
SCIPgetNTotalVars(scip) );
10000 if ( conshdlrdata->nfixnonzerovars < conshdlrdata->maxnfixnonzerovars )
10002 assert( conshdlrdata->fixnonzerovars !=
NULL );
10004 conshdlrdata->fixnonzerovars[conshdlrdata->nfixnonzerovars++] =
SCIPeventGetVar(event);
10007 ++(consdata->nfixednonzeros);
10016 assert( conshdlr !=
NULL );
10018 assert( conshdlrdata !=
NULL );
10021 assert( 0 <= conshdlrdata->nfixnonzerovars && conshdlrdata->nfixnonzerovars <=
SCIPgetNTotalVars(scip) );
10022 if ( conshdlrdata->nfixnonzerovars < conshdlrdata->maxnfixnonzerovars )
10024 assert( conshdlrdata->fixnonzerovars !=
NULL );
10026 conshdlrdata->fixnonzerovars[conshdlrdata->nfixnonzerovars++] =
SCIPeventGetVar(event);
10029 ++(consdata->nfixednonzeros);
10036 --(consdata->nfixednonzeros);
10042 --(consdata->nfixednonzeros);
10049 assert( 0 <= consdata->nfixednonzeros && consdata->nfixednonzeros <= consdata->nvars );
10052 oldbound, newbound, consdata->nfixednonzeros);
10064 assert( scip !=
NULL );
10065 assert( conshdlr !=
NULL );
10067 assert( diveset !=
NULL );
10068 assert( success !=
NULL );
10069 assert( infeasible !=
NULL );
10071 *infeasible =
FALSE;
10080 assert( conshdlrdata !=
NULL );
10085 if ( conshdlrdata->switchsos1branch )
10110 conshdlrdata->branchsos =
TRUE;
10111 conshdlrdata->switchsos1branch =
FALSE;
10112 conshdlrdata->switchcutsfromsos1 =
FALSE;
10113 conshdlrdata->eventhdlr =
NULL;
10114 conshdlrdata->fixnonzerovars =
NULL;
10115 conshdlrdata->maxnfixnonzerovars = 0;
10116 conshdlrdata->nfixnonzerovars = 0;
10117 conshdlrdata->conflictgraph =
NULL;
10118 conshdlrdata->localconflicts =
NULL;
10119 conshdlrdata->isconflocal =
FALSE;
10120 conshdlrdata->implgraph =
NULL;
10121 conshdlrdata->nimplnodes = 0;
10122 conshdlrdata->nboundcuts = 0;
10123 conshdlrdata->tcliquegraph =
NULL;
10124 conshdlrdata->tcliquedata =
NULL;
10125 conshdlrdata->cntextsos1 = -1;
10126 conshdlrdata->varhash =
NULL;
10130 if ( conshdlrdata->eventhdlr ==
NULL )
10139 consEnfolpSOS1, consEnfopsSOS1, consCheckSOS1, consLockSOS1, conshdlrdata) );
10140 assert(conshdlr !=
NULL);
10165 "do not create an adjacency matrix if number of SOS1 variables is larger than predefined value (-1: no limit)",
10170 "maximal number of extensions that will be computed for each SOS1 constraint (-1: no limit)",
10174 "maximal number of bound tightening rounds per presolving round (-1: no limit)",
10178 "if TRUE then perform implication graph analysis (might add additional SOS1 constraints)",
10182 "number of recursive calls of implication graph analysis (-1: no limit)",
10187 "whether to use conflict graph propagation",
10191 "whether to use implication graph propagation",
10195 "whether to use SOS1 constraint propagation",
10200 "which branching rule should be applied ? ('n': neighborhood, 'b': bipartite, 's': SOS1/clique) (note: in some cases an automatic switching to SOS1 branching is possible)",
10204 "if TRUE then automatically switch to SOS1 branching if the SOS1 constraints do not overlap",
10208 "if neighborhood branching is used, then fix the branching variable (if positive in sign) to the value of the feasibility tolerance",
10212 "if TRUE then add complementarity constraints to the branching nodes (can be used in combination with neighborhood or bipartite branching)",
10216 "maximal number of complementarity constraints added per branching node (-1: no limit)",
10220 "minimal feasibility value for complementarity constraints in order to be added to the branching node",
10224 "minimal feasibility value for bound inequalities in order to be added to the branching node",
10228 "should added complementarity constraints be extended to SOS1 constraints to get tighter bound inequalities",
10232 "Use SOS1 branching in enforcing (otherwise leave decision to branching rules)? This value can only be set to false if all SOS1 variables are binary",
10236 "Branch on SOS constraint with most number of nonzeros?",
10240 "Branch on SOS cons. with highest nonzero-variable weight for branching (needs branchnonzeros = false)?",
10244 "only add complementarity constraints to branching nodes for predefined depth (-1: no limit)",
10249 "maximal number of strong branching rounds to perform for each node (-1: auto); only available for neighborhood and bipartite branching",
10253 "maximal number LP iterations to perform for each strong branching round (-2: auto, -1: no limit)",
10258 "if TRUE separate bound inequalities from initial SOS1 constraints",
10262 "if TRUE separate bound inequalities from the conflict graph",
10266 "if TRUE then automatically switch to separating initial SOS1 constraints if the SOS1 constraints do not overlap",
10270 "frequency for separating bound cuts; zero means to separate only in the root node",
10274 "node depth of separating bound cuts (-1: no limit)",
10278 "maximal number of bound cuts separated per branching node",
10282 "maximal number of bound cuts separated per iteration in the root node",
10286 "if TRUE then bound cuts are strengthened in case bound variables are available",
10290 "frequency for separating implied bound cuts; zero means to separate only in the root node",
10294 "node depth of separating implied bound cuts (-1: no limit)",
10298 "maximal number of implied bound cuts separated per branching node",
10302 "maximal number of implied bound cuts separated per iteration in the root node",
10351 modifiable =
FALSE;
10355 if ( conshdlr ==
NULL )
10366 consdata->vars =
NULL;
10367 consdata->nvars = nvars;
10368 consdata->maxvars = nvars;
10369 consdata->rowub =
NULL;
10370 consdata->rowlb =
NULL;
10371 consdata->nfixednonzeros = transformed ? 0 : -1;
10372 consdata->weights =
NULL;
10373 consdata->local = local;
10380 if ( weights !=
NULL )
10391 assert( weights ==
NULL );
10395 for (v = 0; v < nvars; ++v)
10401 SCIP_CALL(
SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
10402 local, modifiable, dynamic, removable, stickingatnode) );
10406 for (v = nvars - 1; v >= 0; --v)
10415 assert( consdata->vars[v] !=
NULL );
10420 assert( conshdlrdata !=
NULL );
10446 SCIP_CALL(
SCIPcreateConsSOS1( scip, cons, name, nvars, vars, weights,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
FALSE,
FALSE,
FALSE,
FALSE) );
10463 assert( scip !=
NULL );
10464 assert( var !=
NULL );
10465 assert( cons !=
NULL );
10470 assert( conshdlr !=
NULL );
10478 assert( conshdlrdata !=
NULL );
10496 assert( scip !=
NULL );
10497 assert( var !=
NULL );
10498 assert( cons !=
NULL );
10503 assert( conshdlr !=
NULL );
10511 assert( conshdlrdata !=
NULL );
10527 assert( scip !=
NULL );
10528 assert( cons !=
NULL );
10538 assert( consdata !=
NULL );
10540 return consdata->nvars;
10552 assert( scip !=
NULL );
10553 assert( cons !=
NULL );
10563 assert( consdata !=
NULL );
10565 return consdata->vars;
10577 assert( scip !=
NULL );
10578 assert( cons !=
NULL );
10588 assert( consdata !=
NULL );
10590 return consdata->weights;
10613 assert( conshdlrdata !=
NULL );
10615 return conshdlrdata->conflictgraph;
10635 assert( conshdlrdata !=
NULL );
10637 return conshdlrdata->nsos1vars;
10649 assert( var !=
NULL );
10650 assert( conshdlr !=
NULL );
10659 assert( conshdlrdata !=
NULL );
10673 assert( conshdlr !=
NULL );
10674 assert( var !=
NULL );
10683 assert( conshdlrdata !=
NULL );
10685 if ( conshdlrdata->varhash ==
NULL )
10704 assert( conflictgraph !=
NULL );
10710 if ( nodedata ==
NULL )
10717 return nodedata->var;
10735 assert( scip !=
NULL );
10736 assert( conshdlr !=
NULL );
10737 assert( sol !=
NULL );
10738 assert( changed !=
NULL );
10739 assert( success !=
NULL );
10747 assert( conshdlrdata !=
NULL );
10751 allroundable =
FALSE;
10762 if ( conshdlrdata->switchsos1branch )
10771 if ( ! allroundable )
enum SCIP_Result SCIP_RESULT
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
#define DIVINGCUTOFFVALUE
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
void ** SCIPdigraphGetSuccessorsData(SCIP_DIGRAPH *digraph, int node)
static SCIP_RETCODE presolRoundConsSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *substituted, SCIP_Bool *cutoff, SCIP_Bool *success, int *ndelconss, int *nupgdconss, int *nfixedvars, int *nremovedvars)
static SCIP_RETCODE genConflictgraphLinearCons(SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraphlin, SCIP_DIGRAPH *conflictgraphorig, SCIP_VAR **linvars, int nlinvars, int *posinlinvars)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
SCIP_RETCODE SCIPflattenVarAggregationGraph(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
static SCIP_RETCODE enforceConssSOS1(SCIP *scip, SCIP_CONSHDLR *conshdlr, int nconss, SCIP_CONS **conss, SCIP_SOL *sol, SCIP_RESULT *result)
#define DEFAULT_MAXIMPLCUTS
static SCIP_RETCODE fixVariableZero(SCIP *scip, SCIP_VAR *var, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_Real SCIPfeastol(SCIP *scip)
enum TCLIQUE_Status TCLIQUE_STATUS
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define DEFAULT_MAXSOSADJACENCY
void tcliqueFree(TCLIQUE_GRAPH **tcliquegraph)
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
static SCIP_RETCODE detectVarboundSOS1(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var0, SCIP_VAR *var1, SCIP_Real val0, SCIP_Real val1)
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
SCIP_Real * SCIPvarGetMultaggrScalars(SCIP_VAR *var)
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
static SCIP_DECL_CONSENFOPS(consEnfopsSOS1)
static SCIP_RETCODE propVariableNonzero(SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_DIGRAPH *implgraph, SCIP_CONS *cons, int node, SCIP_Bool implprop, SCIP_Bool *cutoff, int *ngen)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE getDiveBdChgsSOS1constraints(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DIVESET *diveset, SCIP_SOL *sol, SCIP_Bool *success)
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
TCLIQUE_Bool tcliqueCreate(TCLIQUE_GRAPH **tcliquegraph)
static SCIP_DECL_CONSENFORELAX(consEnforelaxSOS1)
SCIP_VAR ** SCIPgetVarsSOS1(SCIP *scip, SCIP_CONS *cons)
#define CONSHDLR_PROPFREQ
static SCIP_DECL_CONSSEPALP(consSepalpSOS1)
struct TCLIQUE_Graph TCLIQUE_GRAPH
#define DEFAULT_ADDCOMPSFEAS
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
static SCIP_DECL_CONSINITLP(consInitlpSOS1)
static SCIP_DECL_CONSFREE(consFreeSOS1)
TCLIQUE_Bool tcliqueAddNode(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
static SCIP_RETCODE getDiveBdChgsSOS1conflictgraph(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DIVESET *diveset, SCIP_SOL *sol, SCIP_Bool *success)
static SCIP_RETCODE inferVariableZero(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, int inferinfo, SCIP_Bool *infeasible, SCIP_Bool *tightened, SCIP_Bool *success)
#define DEFAULT_MAXBOUNDCUTS
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
static SCIP_RETCODE cliqueGetCommonSuccessorsSOS1(SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, int *clique, SCIP_VAR **vars, int nvars, int *comsucc, int *ncomsucc)
static SCIP_RETCODE performStrongbranchSOS1(SCIP *scip, SCIP_DIGRAPH *conflictgraph, int *fixingsexec, int nfixingsexec, int *fixingsop, int nfixingsop, int inititer, SCIP_Bool fixnonzero, int *domainfixings, int *ndomainfixings, SCIP_Bool *infeasible, SCIP_Real *objval, SCIP_Bool *lperror)
SCIPInterval pow(const SCIPInterval &x, const SCIPInterval &y)
SCIP_RETCODE SCIPresetConsAge(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
SCIP_VAR ** SCIPvarGetMultaggrVars(SCIP_VAR *var)
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node)
SCIP_Real * SCIPgetWeightsSOS1(SCIP *scip, SCIP_CONS *cons)
static SCIP_RETCODE getSOS1Implications(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR **vars, SCIP_DIGRAPH *implgraph, SCIP_HASHMAP *implhash, SCIP_Bool *implnodes, int node)
SCIP_RETCODE SCIPchgVarLbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
static SCIP_RETCODE makeSOS1constraintsFeasible(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_Bool *changed, SCIP_Bool *allroundable)
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
#define CONSHDLR_MAXPREROUNDS
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
static SCIP_RETCODE propConsSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_Bool *cutoff, int *ngen)
SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
SCIP_RETCODE SCIPmakeSOS1sFeasible(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_Bool *changed, SCIP_Bool *success)
static SCIP_RETCODE extensionOperatorSOS1(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_Bool **adjacencymatrix, SCIP_DIGRAPH *vertexcliquegraph, int nsos1vars, int nconss, SCIP_CONS *cons, SCIP_VAR **vars, SCIP_Real *weights, SCIP_Bool firstcall, SCIP_Bool usebacktrack, int **cliques, int *ncliques, int *cliquesizes, int *newclique, int *workingset, int nworkingset, int nexts, int pos, int *maxextensions, int *naddconss, SCIP_Bool *success)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
static SCIP_Bool isImpliedZero(SCIP_DIGRAPH *conflictgraph, SCIP_Bool *implnodes, int node)
#define DEFAULT_ADDBDSFEAS
static SCIP_RETCODE updateArcData(SCIP *scip, SCIP_DIGRAPH *implgraph, SCIP_HASHMAP *implhash, SCIP_VAR **totalvars, SCIP_VAR *varv, SCIP_VAR *varw, SCIP_Real lb, SCIP_Real ub, SCIP_Real newbound, SCIP_Bool lower, int *nchgbds, SCIP_Bool *update, SCIP_Bool *infeasible)
static SCIP_Real nodeGetSolvalBinaryBigMSOS1(SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int node)
#define DEFAULT_CONFLICTPROP
static SCIP_DECL_CONSRESPROP(consRespropSOS1)
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
static SCIP_RETCODE deleteVarSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos)
#define CONSHDLR_EAGERFREQ
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
#define CONSHDLR_SEPAPRIORITY
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
static SCIP_Real nodeGetSolvalVarboundLbSOS1(SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int node)
static SCIP_RETCODE passConComponentVarbound(SCIP *scip, SCIP_DIGRAPH *conflictgraph, int node, SCIP_VAR *boundvar, SCIP_Bool checklb, SCIP_Bool *processed, int *concomp, int *nconcomp, SCIP_Bool *unique)
#define CONSHDLR_CHECKPRIORITY
SCIP_Real SCIPinfinity(SCIP *scip)
miscellaneous datastructures
int SCIPgetNSOS1Vars(SCIP_CONSHDLR *conshdlr)
int SCIPsnprintf(char *t, int len, const char *s,...)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
enum SCIP_Retcode SCIP_RETCODE
static SCIP_Real nodeGetSolvalVarboundUbSOS1(SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int node)
SCIP_Real SCIPvarGetNegationConstant(SCIP_VAR *var)
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_RETCODE SCIPaddVarLocks(SCIP *scip, SCIP_VAR *var, int nlocksdown, int nlocksup)
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
SCIP_RETCODE SCIPincludeConshdlrSOS1(SCIP *scip)
enum SCIP_Varstatus SCIP_VARSTATUS
static SCIP_RETCODE maxWeightIndSetHeuristic(SCIP *scip, SCIP_SOL *sol, SCIP_CONSHDLR *conshdlr, SCIP_DIGRAPH *conflictgraph, int nsos1vars, SCIP_Bool *indicatorzero, SCIP_Bool *indset)
#define CONSHDLR_ENFOPRIORITY
SCIP_Real SCIPvarGetAggrScalar(SCIP_VAR *var)
SCIP_Bool SCIPconsIsTransformed(SCIP_CONS *cons)
SCIP_RETCODE SCIPcomputeArraysIntersection(int *array1, int narray1, int *array2, int narray2, int *intersectarray, int *nintersectarray)
static SCIP_RETCODE separateSOS1(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, int nconss, SCIP_CONS **conss, SCIP_RESULT *result)
void SCIPsortDownIntInt(int *intarray1, int *intarray2, int len)
SCIP_RETCODE SCIPaddDiveBoundChange(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir, SCIP_Real value, SCIP_Bool preferred)
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
#define SCIPfreeBlockMemory(scip, ptr)
static SCIP_RETCODE resetConflictgraphSOS1(SCIP_DIGRAPH *conflictgraph, SCIP_DIGRAPH *localconflicts, int nsos1vars)
SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa)
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
static SCIP_RETCODE initConflictgraph(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS **conss, int nconss)
SCIP_RETCODE SCIPchgVarUbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
#define SCIPduplicateBufferArray(scip, ptr, source, num)
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define DEFAULT_ADDCOMPSDEPTH
static SCIP_DECL_CONSGETVARS(consGetVarsSOS1)
#define SCIPfreeBufferArray(scip, ptr)
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Constraint handler for the set partitioning / packing / covering constraints .
#define SCIPallocBlockMemory(scip, ptr)
SCIP_Bool SCIPisTransformed(SCIP *scip)
SCIP_VAR * SCIPvarGetNegationVar(SCIP_VAR *var)
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
#define SCIP_EVENTTYPE_BOUNDCHANGED
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
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_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
static SCIP_RETCODE getVectorOfWeights(SCIP *scip, SCIP_SOL *sol, SCIP_DIGRAPH *conflictgraph, int nsos1vars, SCIP_Bool *indicatorzero, SCIP_Real *weights)
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse)))
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
#define DEFAULT_IMPLCUTSDEPTH
static SCIP_DECL_CONSENFOLP(consEnfolpSOS1)
SCIP_Longint SCIPgetNDualResolveLPIterations(SCIP *scip)
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
#define SCIP_EVENTTYPE_LBRELAXED
int SCIPdigraphGetNNodes(SCIP_DIGRAPH *digraph)
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
SCIP_RETCODE SCIPdigraphCreate(SCIP_DIGRAPH **digraph, int nnodes)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
static SCIP_DECL_CONSINITSOL(consInitsolSOS1)
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
static SCIP_DECL_CONSLOCK(consLockSOS1)
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
static SCIP_DECL_EVENTEXEC(eventExecSOS1)
SCIP_Real SCIPeventGetNewbound(SCIP_EVENT *event)
static const NodeData nodedata[]
SCIP_RETCODE SCIPsetConshdlrGetDiveBdChgs(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETDIVEBDCHGS((*consgetdivebdchgs)))
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
int SCIPvarGetNodeSOS1(SCIP_CONSHDLR *conshdlr, SCIP_VAR *var)
TCLIQUE_Bool tcliqueAddEdge(TCLIQUE_GRAPH *tcliquegraph, int node1, int node2)
SCIP_RETCODE SCIPdigraphSetNSuccessors(SCIP_DIGRAPH *digraph, int node, int nsuccessors)
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
#define DEFAULT_NSTRONGITER
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define DEFAULT_IMPLCUTSFREQ
#define DEFAULT_SOSCONSPROP
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
static SCIP_DECL_CONSPRINT(consPrintSOS1)
#define CONSHDLR_DELAYSEPA
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
#define DEFAULT_AUTOCUTSFROMSOS1
SCIP_RETCODE SCIPaddVarSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real weight)
void tcliqueChangeWeight(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
void * SCIPdigraphGetNodeData(SCIP_DIGRAPH *digraph, int node)
static SCIP_RETCODE updateWeightsTCliquegraph(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, TCLIQUE_DATA *tcliquedata, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int nsos1vars)
SCIP_RETCODE SCIPgetProbvarSum(SCIP *scip, SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
#define SCIPfreeBufferArrayNull(scip, ptr)
static SCIP_DECL_CONSGETNVARS(consGetNVarsSOS1)
static SCIP_RETCODE generateBoundInequalityFromSOS1Cons(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_Bool local, SCIP_Bool global, SCIP_Bool strengthen, SCIP_Bool removable, SCIP_ROW **rowlb, SCIP_ROW **rowub)
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
void SCIPdigraphSetNodeData(SCIP_DIGRAPH *digraph, void *dataptr, int node)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
static SCIP_RETCODE sepaBoundInequalitiesFromGraph(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_SOL *sol, int maxboundcuts, int *ngen, SCIP_Bool *cutoff)
const char * SCIPconsGetName(SCIP_CONS *cons)
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
SCIP_Real SCIPvarGetAggrConstant(SCIP_VAR *var)
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
SCIP_RETCODE SCIPendProbing(SCIP *scip)
struct SCIP_EventData SCIP_EVENTDATA
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
static SCIP_RETCODE fixVariableZeroNode(SCIP *scip, SCIP_VAR *var, SCIP_NODE *node, SCIP_Bool *infeasible)
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
internal miscellaneous methods
#define SCIP_EVENTTYPE_UBRELAXED
void tcliqueMaxClique(TCLIQUE_GETNNODES((*getnnodes)), TCLIQUE_GETWEIGHTS((*getweights)), TCLIQUE_ISEDGE((*isedge)), TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, TCLIQUE_NEWSOL((*newsol)), TCLIQUE_DATA *tcliquedata, int *maxcliquenodes, int *nmaxcliquenodes, TCLIQUE_WEIGHT *maxcliqueweight, TCLIQUE_WEIGHT maxfirstnodeweight, TCLIQUE_WEIGHT minweight, int maxntreenodes, int backtrackfreq, int maxnzeroextensions, int fixednode, int *ntreenodes, TCLIQUE_STATUS *status)
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
static SCIP_RETCODE appendVarSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var)
static SCIP_RETCODE tightenVarsBoundsSOS1(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_DIGRAPH *implgraph, SCIP_HASHMAP *implhash, SCIP_Bool **adjacencymatrix, SCIP_VAR **totalvars, int ntotalvars, int nsos1vars, int *nchgbds, SCIP_Bool *implupdate, SCIP_Bool *cutoff)
#define SCIP_EVENTTYPE_LBTIGHTENED
#define DEFAULT_MAXADDCOMPS
int SCIPgetNTotalVars(SCIP *scip)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
static SCIP_RETCODE computeNodeDataSOS1(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int nsos1vars)
SCIP_RETCODE SCIPgetProbvarLinearSum(SCIP *scip, SCIP_VAR **vars, SCIP_Real *scalars, int *nvars, int varssize, SCIP_Real *constant, int *requiredsize, SCIP_Bool mergemultiples)
SCIP_Real SCIPvarGetMultaggrConstant(SCIP_VAR *var)
#define DEFAULT_DEPTHIMPLANALYSIS
static SCIP_RETCODE initsepaBoundInequalityFromSOS1Cons(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS **conss, int nconss, SCIP_SOL *sol, SCIP_Bool solvedinitlp, int maxboundcuts, int *ngen, SCIP_Bool *cutoff)
#define DEFAULT_BOUNDCUTSFROMSOS1
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
SCIP_RETCODE SCIPdigraphAddArc(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
SCIP_DIGRAPH * SCIPgetConflictgraphSOS1(SCIP_CONSHDLR *conshdlr)
SCIP_RETCODE SCIPaddCut(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut, SCIP_Bool forcecut, SCIP_Bool *infeasible)
struct SCIP_ConsData SCIP_CONSDATA
SCIP_Bool strthenboundcuts
SCIP_Bool SCIPdivesetSupportsType(SCIP_DIVESET *diveset, SCIP_DIVETYPE divetype)
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
#define DEFAULT_NSTRONGROUNDS
SCIP_RETCODE SCIPaddConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode)
SCIP_RETCODE SCIPcomputeArraysSetminus(int *array1, int narray1, int *array2, int narray2, int *setminusarray, int *nsetminusarray)
#define CONSHDLR_DELAYPROP
SCIP_Bool SCIPvarIsSOS1(SCIP_CONSHDLR *conshdlr, SCIP_VAR *var)
SCIP_RETCODE SCIPcreateConsSetpack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPappendVarSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
static SCIP_DECL_CONSPROP(consPropSOS1)
#define CONSHDLR_NEEDSCONS
static SCIP_RETCODE checkConComponentsVarbound(SCIP *scip, SCIP_DIGRAPH *conflictgraph, int nsos1vars, SCIP_Bool checklb)
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
public data structures and miscellaneous methods
#define DEFAULT_MAXBOUNDCUTSROOT
SCIP_RETCODE SCIPdigraphAddArcSafe(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
int SCIPdigraphGetNSuccessors(SCIP_DIGRAPH *digraph, int node)
static SCIP_RETCODE freeImplGraphSOS1(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata)
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
#define CONSHDLR_PROP_TIMING
#define DEFAULT_AUTOSOS1BRANCH
static SCIP_DECL_CONSSEPASOL(consSepasolSOS1)
static SCIP_DECL_CONSEXITSOL(consExitsolSOS1)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
static SCIP_RETCODE getBranchingDecisionStrongbranchSOS1(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int nsos1vars, SCIP_Real lpobjval, SCIP_Bool bipbranch, int nstrongrounds, SCIP_Bool *verticesarefixed, int *fixingsnode1, int *fixingsnode2, int *vertexbestprior, SCIP_Real *bestobjval1, SCIP_Real *bestobjval2, SCIP_RESULT *result)
static SCIP_DECL_CONSDELETE(consDeleteSOS1)
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
#define DEFAULT_MAXTIGHTENBDS
static SCIP_RETCODE enforceConflictgraph(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONSHDLR *conshdlr, int nconss, SCIP_CONS **conss, SCIP_SOL *sol, SCIP_RESULT *result)
SCIP_RETCODE SCIPcreateEmptyRowCons(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
int SCIPgetDepth(SCIP *scip)
SCIP_RETCODE SCIPupdateNodeLowerbound(SCIP *scip, SCIP_NODE *node, SCIP_Real newbound)
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
int SCIPdigraphGetNArcs(SCIP_DIGRAPH *digraph)
static SCIP_RETCODE freeConflictgraph(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata)
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
int SCIPvarCompare(SCIP_VAR *var1, SCIP_VAR *var2)
static SCIP_RETCODE addVarSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var, SCIP_Real weight)
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
static SCIP_RETCODE getBranchingVerticesSOS1(SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, SCIP_Bool *verticesarefixed, SCIP_Bool bipbranch, int branchvertex, int *fixingsnode1, int *nfixingsnode1, int *fixingsnode2, int *nfixingsnode2)
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
int SCIPgetNVarsSOS1(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPcalcNodeselPriority(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR branchdir, SCIP_Real targetvalue)
SCIP_VAR * SCIPnodeGetVarSOS1(SCIP_DIGRAPH *conflictgraph, int node)
SCIP_VAR * SCIPvarGetAggrVar(SCIP_VAR *var)
SCIP_Longint SCIPgetNDualResolveLPs(SCIP *scip)
#define DEFAULT_BOUNDCUTSDEPTH
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
#define BMScopyMemoryArray(ptr, source, num)
SCIPInterval log(const SCIPInterval &x)
SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
static SCIP_RETCODE performImplicationGraphAnalysis(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_VAR **totalvars, SCIP_DIGRAPH *implgraph, SCIP_HASHMAP *implhash, SCIP_Bool **adjacencymatrix, int givennode, int nonznode, SCIP_Real *impllbs, SCIP_Real *implubs, SCIP_Bool *implnodes, int *naddconss, int *probingdepth, SCIP_Bool *infeasible)
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
#define SCIP_EVENTTYPE_UBTIGHTENED
Constraint handler for linear constraints in their most general form, .
static SCIP_RETCODE initImplGraphSOS1(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, int nsos1vars, int maxrounds, int *nchgbds, SCIP_Bool *cutoff, SCIP_Bool *success)
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopySOS1)
int SCIPvarGetMultaggrNVars(SCIP_VAR *var)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
#define DEFAULT_BRANCHSTRATEGIES
SCIP_RETCODE SCIPinferVarLbCons(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_CONS *infercons, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
static SCIP_RETCODE initTCliquegraph(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, int nsos1vars)
static SCIP_RETCODE addBoundCutSepa(SCIP *scip, TCLIQUE_DATA *tcliquedata, SCIP_ROW *rowlb, SCIP_ROW *rowub, SCIP_Bool *success, SCIP_Bool *cutoff)
SCIP_Real SCIPcalcChildEstimate(SCIP *scip, SCIP_VAR *var, SCIP_Real targetvalue)
#define SCIP_MAXTREEDEPTH
#define CONSHDLR_SEPAFREQ
SCIP_RETCODE SCIPcreateConsBasicSOS1(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *weights)
static SCIP_DECL_CONSCOPY(consCopySOS1)
int SCIPgetNVars(SCIP *scip)
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
#define DEFAULT_BOUNDCUTSFROMGRAPH
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
#define DEFAULT_ADDEXTENDEDBDS
static SCIP_RETCODE getBoundConsFromVertices(SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int v1, int v2, SCIP_VAR *boundvar, SCIP_Bool extend, SCIP_CONS *cons, SCIP_Real *feas)
SCIP_Longint SCIPgetNNodeInitLPIterations(SCIP *scip)
SCIP_Longint SCIPgetNNodeInitLPs(SCIP *scip)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE addBranchingComplementaritiesSOS1(SCIP *scip, SCIP_NODE *node, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_DIGRAPH *localconflicts, SCIP_SOL *sol, int nsos1vars, SCIP_Bool *verticesarefixed, int *fixingsnode1, int nfixingsnode1, int *fixingsnode2, int nfixingsnode2, int *naddedconss, SCIP_Bool onlyviolsos1)
static SCIP_RETCODE makeSOS1conflictgraphFeasible(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_Bool *changed, SCIP_Bool *allroundable)
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
static const SCIP_Real scalars[]
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
SCIP_VAR ** SCIPgetVarsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
static SCIP_DECL_CONSPARSE(consParseSOS1)
SCIP_RETCODE SCIPinferVarUbCons(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_CONS *infercons, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
static SCIP_RETCODE checkSwitchNonoverlappingSOS1Methods(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_CONS **conss, int nconss)
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
static SCIP_RETCODE branchCons(SCIP *scip, SCIP_CONS *cons, SCIP_RESULT *result)
SCIP_Real SCIPeventGetOldbound(SCIP_EVENT *event)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
struct SCIP_SuccData SCIP_SUCCDATA
SCIP_VAR ** SCIPgetVars(SCIP *scip)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
static SCIP_RETCODE lockVariableSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
static SCIP_RETCODE sepaImplBoundCutsSOS1(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_SOL *sol, int maxcuts, int *ngen, SCIP_Bool *cutoff)
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
#define DEFAULT_MAXIMPLCUTSROOT
#define DEFAULT_BOUNDCUTSFREQ
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
#define DEFAULT_BRANCHINGRULE
constraint handler for SOS type 1 constraints
#define DEFAULT_FIXNONZERO
#define DEFAULT_PERFIMPLANALYSIS
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
static SCIP_RETCODE updateImplicationGraphSOS1(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_Bool **adjacencymatrix, SCIP_DIGRAPH *implgraph, SCIP_HASHMAP *implhash, SCIP_Bool *implnodes, SCIP_VAR **totalvars, int **cliquecovers, int *cliquecoversizes, int *varincover, SCIP_VAR **vars, SCIP_Real *coefs, int nvars, SCIP_Real *bounds, SCIP_VAR *var, SCIP_Real bound, SCIP_Real boundnonzero, int ninftynonzero, SCIP_Bool lower, int *nchgbds, SCIP_Bool *update, SCIP_Bool *infeasible)
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
#define SCIP_DIVETYPE_SOS1VARIABLE
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
static SCIP_RETCODE getCoverVertices(SCIP_DIGRAPH *conflictgraph, SCIP_Bool *verticesarefixed, int vertex, int *neightocover, int nneightocover, int *coververtices, int *ncoververtices)
void SCIPsortInt(int *intarray, int len)
static SCIP_RETCODE presolRoundVarsSOS1(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_Bool **adjacencymatrix, int nsos1vars, int *nfixedvars, int *nchgbds, int *naddconss, SCIP_RESULT *result)
static SCIP_DECL_CONSPRESOL(consPresolSOS1)
void SCIPsortRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
int SCIPvarGetIndex(SCIP_VAR *var)
SCIP_OBJSENSE SCIPgetObjsense(SCIP *scip)
static SCIP_RETCODE checkLinearConssVarboundSOS1(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS **linconss, int nlinconss)
static SCIP_RETCODE handleNewVariableSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var, SCIP_Bool transformed)
static SCIP_RETCODE consdataEnsurevarsSizeSOS1(SCIP *scip, SCIP_CONSDATA *consdata, int num, SCIP_Bool reserveWeights)
static SCIP_RETCODE unlockVariableSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
static SCIP_Bool varIsSOS1(SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var)
static SCIP_DECL_CONSCHECK(consCheckSOS1)
static SCIP_RETCODE presolRoundConssSOS1(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_Bool **adjacencymatrix, SCIP_CONS **conss, int nconss, int nsos1vars, int *naddconss, int *ndelconss, int *nupgdconss, int *nfixedvars, int *nremovedvars, SCIP_RESULT *result)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Real * SCIPgetValsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsSOS1(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *weights, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
TCLIQUE_Bool tcliqueFlush(TCLIQUE_GRAPH *tcliquegraph)
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
#define DEFAULT_STRTHENBOUNDCUTS
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
static SCIP_RETCODE markNeighborsMWISHeuristic(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DIGRAPH *conflictgraph, int node, SCIP_Bool *mark, SCIP_Bool *indset, int *cnt, SCIP_Bool *cutoff)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
SCIP_RETCODE SCIPgetDivesetScore(SCIP *scip, SCIP_DIVESET *diveset, SCIP_DIVETYPE divetype, SCIP_VAR *divecand, SCIP_Real divecandsol, SCIP_Real divecandfrac, SCIP_Real *candscore, SCIP_Bool *roundup)
SCIP_Bool SCIPvarIsTransformed(SCIP_VAR *var)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
static SCIP_RETCODE getBranchingPrioritiesSOS1(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *conflictgraph, SCIP_SOL *sol, int nsos1vars, SCIP_Bool *verticesarefixed, SCIP_Bool bipbranch, int *fixingsnode1, int *fixingsnode2, SCIP_Real *branchpriors, int *vertexbestprior, SCIP_Bool *relsolfeas)
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
#define CONSHDLR_PRESOLTIMING
void SCIPswapInts(int *value1, int *value2)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
static SCIP_DECL_CONSGETDIVEBDCHGS(consGetDiveBdChgsSOS1)
void SCIPdigraphFree(SCIP_DIGRAPH **digraph)
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol)))
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_RETCODE SCIPwriteVarName(SCIP *scip, FILE *file, SCIP_VAR *var, SCIP_Bool type)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
static TCLIQUE_NEWSOL(tcliqueNewsolClique)
static SCIP_RETCODE generateBoundInequalityFromSOS1Nodes(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DIGRAPH *conflictgraph, int *nodes, int nnodes, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool global, SCIP_Bool strengthen, SCIP_Bool removable, const char *nameext, SCIP_ROW **rowlb, SCIP_ROW **rowub)
static SCIP_RETCODE enforceSOS1(SCIP *scip, SCIP_CONSHDLR *conshdlr, int nconss, SCIP_CONS **conss, SCIP_SOL *sol, SCIP_RESULT *result)
#define DEFAULT_MAXEXTENSIONS
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
static SCIP_DECL_CONSTRANS(consTransSOS1)
int SCIPgetNVarsLinear(SCIP *scip, SCIP_CONS *cons)
static int varGetNodeSOS1(SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var)
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_DIGRAPH * conflictgraph
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPvarMayRoundUp(SCIP_VAR *var)
static SCIP_RETCODE computeVarsCoverSOS1(SCIP *scip, SCIP_DIGRAPH *conflictgraphroot, SCIP_DIGRAPH *conflictgraphlin, SCIP_VAR **linvars, SCIP_Bool *coveredvars, int *clique, int *cliquesize, int v, SCIP_Bool considersolvals)
static SCIP_Bool isConnectedSOS1(SCIP_Bool **adjacencymatrix, SCIP_DIGRAPH *conflictgraph, int vertex1, int vertex2)
SCIP_Bool SCIPvarMayRoundDown(SCIP_VAR *var)
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)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
static SCIP_Bool isViolatedSOS1(SCIP *scip, SCIP_DIGRAPH *conflictgraph, int node, SCIP_SOL *sol)
#define SCIPreallocBufferArray(scip, ptr, num)
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)