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 )
2839 trafolbs[v] = lb * trafolinvals[v];
2844 trafoubs[v] = ub * trafolinvals[v];
2848 for (v = 0; v < nsos1vars; ++v)
2849 varindincons[v] = -1;
2852 for (v = 0; v < ntrafolinvars; ++v)
2859 varindincons[node] = v;
2867 for (i = 0; i < ntrafolinvars; ++i)
2868 coveredvars[i] =
FALSE;
2877 for (v = 0; v < ntrafolinvars; ++v)
2880 if ( ! coveredvars[v] )
2883 SCIP_CALL(
computeVarsCoverSOS1(scip, conflictgraph, conflictgraphlin, trafolinvars, coveredvars, cliquecovers[ncliquecovers], &(cliquecoversizes[ncliquecovers]), v,
FALSE) );
2893 for (v = 0; v < ntrafolinvars; ++v)
2910 for (s = 0; s < nsucc; ++s)
2915 if ( varindincons[succnode] == -1 )
2918 varindincons[succnode] = -2;
2930 for (i = 0; i < ncliquecovers; ++i)
2932 for (j = 0; j < cliquecoversizes[i]; ++j)
2934 int ind = cliquecovers[i][j];
2936 varincover[ind] = i;
2937 cliquecovervals[j] = trafoubs[ind];
2943 for (v = 0; v < ntrafolinvars + nsos1linvars; ++v)
2957 int ninftynonzero = 0;
2961 if ( v < ntrafolinvars )
2963 var = trafolinvars[v];
2964 trafoubv = trafoubs[v];
2968 assert( v >= ntrafolinvars );
2969 var = sos1linvars[v-ntrafolinvars];
2979 newboundnonzero = trafolhs;
2980 newboundnores = trafolhs;
2982 assert( nodev < nsos1vars );
2985 for (w = 0; w < nsos1vars; ++w)
2986 implnodes[w] =
FALSE;
2990 for (i = 0; i < ncliquecovers; ++i)
2995 assert( cliquecoversizes[i] > 0 );
2997 indcliq = cliquecovers[i][0];
2998 assert( 0 <= indcliq && indcliq < ntrafolinvars );
3006 newboundnores -= trafoubs[indcliq];
3008 else if ( cliquecoversizes[i] > 1 )
3010 assert( 0 <= cliquecovers[i][1] && cliquecovers[i][1] < ntrafolinvars );
3014 newboundnores -= trafoubs[cliquecovers[i][1]];
3018 for (j = 0; j < cliquecoversizes[i]; ++j)
3020 indcliq = cliquecovers[i][j];
3021 assert( 0 <= indcliq && indcliq < ntrafolinvars );
3024 assert( nodecliq < nsos1vars );
3034 newboundnonzero -= trafoubs[indcliq];
3041 assert( ninftynonzero == 0 || inftynores );
3044 if ( ninftynonzero == 0 && v < ntrafolinvars )
3046 linval = trafolinvals[v];
3053 newbound = newboundnonzero;
3055 newbound =
MIN(0, newboundnonzero);
3068 newbound =
SCIPceil(scip, newbound);
3071 assert( ! infeasible );
3092 assert( ! infeasible );
3103 SCIP_CALL(
updateImplicationGraphSOS1(scip, conshdlrdata, conflictgraph, adjacencymatrix, implgraph, implhash, implnodes, totalvars, cliquecovers, cliquecoversizes, varincover,
3104 trafolinvars, trafolinvals, ntrafolinvars, trafoubs, var, trafoubv, newboundnonzero, ninftynonzero,
TRUE, nchgbds, &update, &infeasible) );
3111 if ( *cutoff ==
TRUE )
3115 for (j = ncliquecovers-1; j >= 0; --j)
3129 for (i = 0; i < ncliquecovers; ++i)
3131 for (j = 0; j < cliquecoversizes[i]; ++j)
3133 int ind = cliquecovers[i][j];
3135 varincover[ind] = i;
3136 cliquecovervals[j] = trafolbs[ind];
3138 SCIPsortRealInt(cliquecovervals, cliquecovers[i], cliquecoversizes[i]);
3143 for (v = 0; v < ntrafolinvars + nsos1linvars; ++v)
3157 int ninftynonzero = 0;
3161 if ( v < ntrafolinvars )
3163 var = trafolinvars[v];
3164 trafolbv = trafolbs[v];
3168 assert( v-ntrafolinvars >= 0 );
3169 var = sos1linvars[v-ntrafolinvars];
3177 newboundnonzero = traforhs;
3178 newboundnores = traforhs;
3180 assert( nodev < nsos1vars );
3183 for (w = 0; w < nsos1vars; ++w)
3184 implnodes[w] =
FALSE;
3188 for (i = 0; i < ncliquecovers; ++i)
3193 assert( cliquecoversizes[i] > 0 );
3195 indcliq = cliquecovers[i][0];
3196 assert( 0 <= indcliq && indcliq < ntrafolinvars );
3205 newboundnores -= trafolbs[indcliq];
3207 else if ( cliquecoversizes[i] > 1 )
3209 assert( 0 <= cliquecovers[i][1] && cliquecovers[i][1] < ntrafolinvars );
3213 newboundnores -= trafolbs[cliquecovers[i][1]];
3217 for (j = 0; j < cliquecoversizes[i]; ++j)
3219 indcliq = cliquecovers[i][j];
3220 assert( 0 <= indcliq && indcliq < ntrafolinvars );
3223 assert( nodecliq < nsos1vars );
3234 newboundnonzero -= trafolbs[indcliq];
3241 assert( ninftynonzero == 0 || inftynores );
3245 if ( ninftynonzero == 0 && v < ntrafolinvars )
3247 linval = trafolinvals[v];
3254 newbound = newboundnonzero;
3256 newbound =
MAX(0, newboundnonzero);
3273 assert( ! infeasible );
3291 newbound =
SCIPceil(scip, newbound);
3294 assert( ! infeasible );
3305 SCIP_CALL(
updateImplicationGraphSOS1(scip, conshdlrdata, conflictgraph, adjacencymatrix, implgraph, implhash, implnodes, totalvars, cliquecovers, cliquecoversizes, varincover,
3306 trafolinvars, trafolinvals, ntrafolinvars, trafolbs, var, trafolbv, newboundnonzero, ninftynonzero,
FALSE, nchgbds, &update, &infeasible) );
3315 for (j = ncliquecovers-1; j >= 0; --j)
3323 if ( *cutoff ==
TRUE )
3377 for (i = 0; i < nsos1vars; ++i)
3386 totalvars[ntotalvars++] = var;
3389 for (i = 0; i < nprobvars; ++i)
3399 totalvars[ntotalvars++] = var;
3407 updateconfl =
FALSE;
3408 for (j = 0; (j < conshdlrdata->maxtightenbds || conshdlrdata->maxtightenbds == -1 ) && ! cutoff; ++j)
3413 nchgbdssave = *nchgbds;
3415 assert( ntotalvars > 0 );
3416 SCIP_CALL(
tightenVarsBoundsSOS1(scip, conshdlrdata, conflictgraph, implgraph, implhash, adjacencymatrix, totalvars, ntotalvars, nsos1vars, nchgbds, &implupdate, &cutoff) );
3417 if ( *nchgbds > nchgbdssave )
3423 else if ( implupdate )
3430 if ( updateconfl && conshdlrdata->perfimplanalysis && ! cutoff )
3445 naddconsssave = *naddconss;
3446 for (i = 0; i < nsos1vars; ++i)
3451 for (j = 0; j < nsos1vars; ++j)
3452 implnodes[j] =
FALSE;
3453 for (j = 0; j < ntotalvars; ++j)
3460 SCIP_CALL(
performImplicationGraphAnalysis(scip, conshdlrdata, conflictgraph, totalvars, implgraph, implhash, adjacencymatrix, i, i, impllbs, implubs, implnodes, naddconss, &probingdepth, &infeasible) );
3469 SCIPdebugMsg(scip,
"fixed variable %s with lower bound %f and upper bound %f to zero\n",
3479 if ( *naddconss > naddconsssave )
3496 for (j = ntotalvars-1; j >= 0; --j)
3505 for (s = nsucc-1; s >= 0; --s)
3528 assert( scip !=
NULL );
3529 assert( cons !=
NULL );
3530 assert( consdata !=
NULL );
3531 assert( cutoff !=
NULL );
3532 assert( ngen !=
NULL );
3537 if ( consdata->nfixednonzeros > 1 )
3539 SCIPdebugMsg(scip,
"the node is infeasible, more than 1 variable is fixed to be nonzero.\n");
3546 if ( consdata->nfixednonzeros == 1 )
3553 int firstFixedNonzero;
3557 firstFixedNonzero = -1;
3558 nvars = consdata->nvars;
3559 vars = consdata->vars;
3560 assert( vars !=
NULL );
3563 for (j = 0; j < nvars; ++j)
3567 firstFixedNonzero = j;
3571 assert( firstFixedNonzero >= 0 );
3573 SCIPdebugMsg(scip,
"variable <%s> is fixed nonzero, fixing other variables to 0.\n",
SCIPvarGetName(vars[firstFixedNonzero]));
3577 for (j = 0; j < firstFixedNonzero; ++j)
3581 assert( ! infeasible );
3582 allVarFixed = allVarFixed && success;
3588 for (j = firstFixedNonzero+1; j < nvars; ++j)
3592 assert( ! infeasible );
3593 allVarFixed = allVarFixed && success;
3634 assert( scip !=
NULL );
3635 assert( conflictgraph !=
NULL );
3636 assert( cutoff !=
NULL );
3637 assert( ngen !=
NULL );
3638 assert( node >= 0 );
3641 inferinfo = -node - 1;
3649 for (s = 0; s < nsucc; ++s)
3682 if ( implprop && implgraph !=
NULL )
3687 SCIP_NODEDATA* nodedbgdata;
3695 if ( succdatas !=
NULL )
3699 for (s = 0; s < nsucc; ++s)
3706 assert( nodedata !=
NULL );
3707 succdata = succdatas[s];
3708 assert( succdata !=
NULL );
3709 var = nodedata->var;
3710 assert( var !=
NULL );
3783 assert( scip !=
NULL );
3784 assert( conshdlrdata !=
NULL );
3785 assert( conflictgraph !=
NULL );
3786 assert( conshdlrdata->implgraph ==
NULL );
3787 assert( conshdlrdata->nimplnodes == 0 );
3788 assert( cutoff !=
NULL );
3789 assert( nchgbds !=
NULL );
3795 if ( conshdlrdata->maxsosadjacency != -1 && nsos1vars > conshdlrdata->maxsosadjacency )
3798 SCIPdebugMsg(scip,
"Implication graph was not created since number of SOS1 variables (%d) is larger than %d.\n", nsos1vars, conshdlrdata->maxsosadjacency);
3821 for (i = 0; i < nsos1vars; ++i)
3830 implvars[nimplnodes++] = var;
3833 for (i = 0; i < nprobvars; ++i)
3843 implvars[nimplnodes++] = var;
3846 conshdlrdata->nimplnodes = nimplnodes;
3849 for (i = 0; i < nimplnodes; ++i)
3855 nodedata->var = implvars[i];
3865 for (i = 0; i < nsos1vars; ++i)
3869 for (i = 0; i < nsos1vars; ++i)
3871 for (j = 0; j < i+1; ++j)
3872 adjacencymatrix[i][j] = 0;
3875 for (i = 0; i < nsos1vars; ++i)
3882 for (j = 0; j < nsucc; ++j)
3885 adjacencymatrix[i][succ[j]] = 1;
3892 for (j = 0; (j < maxrounds || maxrounds == -1 ); ++j)
3897 nchgbdssave = *nchgbds;
3899 assert( nimplnodes > 0 );
3900 SCIP_CALL(
tightenVarsBoundsSOS1(scip, conshdlrdata, conflictgraph, conshdlrdata->implgraph, implhash, adjacencymatrix, implvars, nimplnodes, nsos1vars, nchgbds, &implupdate, cutoff) );
3901 if ( *cutoff || ( ! implupdate && ! ( *nchgbds > nchgbdssave ) ) )
3906 for (i = nsos1vars-1; i >= 0; --i)
3919 else if ( *nchgbds > 0 )
3921 SCIPdebugMsg(scip,
"found %d bound changes\n", *nchgbds);
3925 assert( conshdlrdata->implgraph !=
NULL );
3940 assert( scip !=
NULL );
3941 assert( conshdlrdata !=
NULL );
3944 if ( conshdlrdata->implgraph ==
NULL )
3946 assert( conshdlrdata->nimplnodes == 0 );
3951 for (j = conshdlrdata->nimplnodes-1; j >= 0; --j)
3960 for (s = nsucc-1; s >= 0; --s)
3962 assert( succdatas[s] !=
NULL );
3968 for (j = conshdlrdata->nimplnodes-1; j >= 0; --j)
3972 assert( nodedata !=
NULL );
3979 conshdlrdata->nimplnodes = 0;
4006 assert( conflictgraph !=
NULL );
4007 assert( verticesarefixed !=
NULL );
4008 assert( coververtices !=
NULL );
4009 assert( ncoververtices !=
NULL );
4011 *ncoververtices = 0;
4014 if ( neightocover ==
NULL )
4016 assert( nneightocover == 0 );
4022 nsucc1 = nneightocover;
4023 succ1 = neightocover;
4027 for (s = 0; s < nsucc1; ++s)
4029 int succvertex1 = succ1[s];
4031 if ( ! verticesarefixed[succvertex1] )
4042 if ( *ncoververtices == 0 )
4044 for (j = 0; j < nsucc2; ++j)
4046 succvertex2 = succ2[j];
4047 if ( ! verticesarefixed[succvertex2] )
4048 coververtices[(*ncoververtices)++] = succvertex2;
4058 for (v = 0; v < *ncoververtices; ++v)
4061 for (j = k; j < nsucc2; ++j)
4063 succvertex2 = succ2[j];
4064 if ( succvertex2 > coververtices[v] )
4070 else if ( succvertex2 == coververtices[v] )
4073 coververtices[vv++] = succvertex2;
4080 *ncoververtices = vv;
4087 for (s = 0; s < *ncoververtices; ++s)
4089 assert( *ncoververtices <= 1 || coververtices[*ncoververtices - 1] > coververtices[*ncoververtices - 2] );
4117 assert( scip !=
NULL );
4118 assert( conflictgraph !=
NULL );
4119 assert( verticesarefixed !=
NULL );
4120 assert( ! verticesarefixed[branchvertex] );
4121 assert( fixingsnode1 !=
NULL );
4122 assert( fixingsnode2 !=
NULL );
4123 assert( nfixingsnode1 !=
NULL );
4124 assert( nfixingsnode2 !=
NULL );
4141 for (j = 0; j < nsucc; ++j)
4145 assert( ! verticesarefixed[succ[j]] );
4146 fixingsnode1[(*nfixingsnode1)++] = succ[j];
4151 if ( *nfixingsnode1 > 0 )
4154 SCIP_CALL(
getCoverVertices(conflictgraph, verticesarefixed, branchvertex, fixingsnode1, *nfixingsnode1, fixingsnode2, nfixingsnode2) );
4157 SCIP_CALL(
getCoverVertices(conflictgraph, verticesarefixed, branchvertex, fixingsnode2, *nfixingsnode2, fixingsnode1, nfixingsnode1) );
4159 for (j = 0; j < *nfixingsnode2; ++j)
4170 for (j = 0; j < *nfixingsnode1; ++j)
4178 takeallsucc =
FALSE;
4187 for (j = 0; j < nsucc; ++j)
4189 if ( ! verticesarefixed[succ[j]] )
4190 fixingsnode1[(*nfixingsnode1)++] = succ[j];
4196 SCIP_CALL(
getCoverVertices(conflictgraph, verticesarefixed, branchvertex, fixingsnode1, *nfixingsnode1, fixingsnode2, nfixingsnode2) );
4201 fixingsnode2[0] = branchvertex;
4223 int* vertexbestprior,
4230 assert( scip !=
NULL );
4231 assert( conshdlrdata !=
NULL );
4232 assert( conflictgraph !=
NULL );
4233 assert( verticesarefixed !=
NULL );
4234 assert( fixingsnode1 !=
NULL );
4235 assert( fixingsnode2 !=
NULL );
4236 assert( relsolfeas !=
NULL );
4240 for (i = 0; i < nsos1vars; ++i)
4261 assert( ! verticesarefixed[i] );
4265 for (j = 0; j < nfixingsnode1; ++j)
4276 for (j = 0; j < nfixingsnode2; ++j)
4286 if ( iszero1 || iszero2 )
4289 prior = sum1 * sum2;
4292 if ( branchpriors !=
NULL )
4293 branchpriors[i] = prior;
4294 if ( bestprior < prior )
4298 if ( vertexbestprior !=
NULL )
4299 *vertexbestprior = i;
4306 *relsolfeas =
FALSE;
4325 int* ndomainfixings,
4334 assert( scip !=
NULL );
4335 assert( conflictgraph !=
NULL );
4336 assert( fixingsexec !=
NULL );
4337 assert( nfixingsop > 0 );
4338 assert( fixingsop !=
NULL );
4339 assert( nfixingsop > 0 );
4340 assert( inititer >= -1 );
4341 assert( domainfixings !=
NULL );
4342 assert( ndomainfixings !=
NULL );
4343 assert( *ndomainfixings >= 0 );
4344 assert( infeasible !=
NULL );
4345 assert( objval !=
NULL );
4346 assert( lperror !=
NULL );
4350 *infeasible =
FALSE;
4356 if ( fixnonzero && nfixingsop == 1 )
4396 for (i = 0; i < nfixingsexec && ! *infeasible; ++i)
4410 if ( ! *infeasible )
4436 for (i = 0; i < nfixingsop; ++i)
4437 domainfixings[(*ndomainfixings)++] = fixingsop[i];
4468 int* vertexbestprior,
4475 int* indsos1vars =
NULL;
4476 int* domainfixings =
NULL;
4483 int lastscorechange;
4492 assert( scip !=
NULL );
4493 assert( conshdlrdata !=
NULL );
4494 assert( conflictgraph !=
NULL );
4495 assert( verticesarefixed !=
NULL );
4496 assert( fixingsnode1 !=
NULL );
4497 assert( fixingsnode2 !=
NULL );
4498 assert( vertexbestprior !=
NULL );
4499 assert( result !=
NULL );
4506 bipbranch, fixingsnode1, fixingsnode2, branchpriors,
NULL, &relsolfeas) );
4511 SCIPdebugMsg(scip,
"all the SOS1 constraints are feasible.\n");
4525 for (j = 0; j < nsos1vars; ++j)
4538 nlpiterations = 1000;
4545 if ( conshdlrdata->nstrongiter == -2 )
4547 inititer = (int)(2*nlpiterations / nlps);
4549 inititer =
MAX(inititer, 10);
4550 inititer =
MIN(inititer, 500);
4553 inititer = conshdlrdata->nstrongiter;
4560 lastscorechange = -1;
4561 *vertexbestprior = indsos1vars[0];
4565 maxfailures = nstrongrounds;
4568 for (j = 0; j < nstrongrounds; ++j)
4573 testvertex = indsos1vars[j];
4586 assert( ! verticesarefixed[testvertex] );
4587 SCIP_CALL(
getBranchingVerticesSOS1(scip, conflictgraph, sol, verticesarefixed, bipbranch, testvertex, fixingsnode1, &nfixingsnode1, fixingsnode2, &nfixingsnode2) );
4591 inititer, conshdlrdata->fixnonzero, domainfixings, &ndomainfixings, &infeasible1, &objval1, &lperror) );
4597 inititer,
FALSE, domainfixings, &ndomainfixings, &infeasible2, &objval2, &lperror) );
4602 if ( infeasible1 && infeasible2 )
4616 else if ( ! infeasible1 && ! infeasible2 )
4619 if ( ndomainfixings == 0 )
4626 *vertexbestprior = testvertex;
4627 *bestobjval1 = objval1;
4628 *bestobjval2 = objval2;
4630 lastscorechange = j;
4632 else if ( j - lastscorechange > maxfailures )
4640 if ( ndomainfixings > 0 )
4645 for (i = 0; i < ndomainfixings; ++i)
4648 assert( ! infeasible );
4651 SCIPdebugMsg(scip,
"found %d domain fixings.\n", ndomainfixings);
4690 int* extensions =
NULL;
4691 int nextensions = 0;
4695 assert( scip !=
NULL );
4696 assert( conflictgraph !=
NULL );
4697 assert( cons !=
NULL );
4698 assert( feas !=
NULL );
4704 var = nodedata->var;
4709 if ( boundvar ==
NULL )
4729 else if ( boundvar == nodedata->ubboundvar )
4735 ub = nodedata->ubboundcoef;
4744 lb = nodedata->lbboundcoef;
4753 *feas += coef * solval;
4763 assert( nsucc > 0 );
4769 for (s = 0; s < nsucc; ++s)
4770 extensions[s] = succ[s];
4771 nextensions = nsucc;
4777 while ( nextensions > 0 )
4794 assert( extensions !=
NULL );
4795 for (s = 0; s < nextensions; ++s)
4797 ext = extensions[s];
4801 bestbigMval = bigMval;
4806 assert( bestindex != -1 );
4810 var = nodedata->var;
4813 if ( boundvar ==
NULL )
4833 else if ( boundvar == nodedata->ubboundvar )
4839 ub = nodedata->ubboundcoef;
4848 lb = nodedata->lbboundcoef;
4856 *feas += coef * solval;
4862 assert( extensions !=
NULL );
4865 for (s = 0; s < nextensions; ++s)
4868 extensions[nextensionsnew++] = extensions[s];
4870 nextensions = nextensionsnew;
4881 if ( boundvar ==
NULL )
4915 assert( scip !=
NULL );
4916 assert( node !=
NULL );
4917 assert( conshdlrdata !=
NULL );
4918 assert( conflictgraph !=
NULL );
4919 assert( verticesarefixed !=
NULL );
4920 assert( fixingsnode1 !=
NULL );
4921 assert( fixingsnode2 !=
NULL );
4922 assert( naddedconss !=
NULL );
4926 if ( nfixingsnode2 > 1 )
4952 for (i = 0; i < nsos1vars; ++i)
4953 mark[i] = (verticesarefixed[i]);
4956 for (i = 0; i < nfixingsnode1; ++i)
4958 assert( nfixingsnode1 <= 1 || (fixingsnode1[nfixingsnode1 - 1] > fixingsnode1[nfixingsnode1 - 2]) );
4959 mark[fixingsnode1[i]] =
TRUE;
4963 for (i = 0; i < nfixingsnode2; ++i)
4965 assert( nfixingsnode2 <= 1 || (fixingsnode2[nfixingsnode2 - 1] > fixingsnode2[nfixingsnode2 - 2]) );
4966 mark[fixingsnode2[i]] =
TRUE;
4971 for (i = 0; i < nfixingsnode2; ++i)
4976 for (s = 0; s < nsucc; ++s)
4978 int succnode = succ[s];
4980 if ( ! mark[succnode] )
4982 mark[succnode] =
TRUE;
4983 succarray[nsuccarray++] = succnode;
4992 for (i = 0; i < nsos1vars; ++i)
4996 for (i = 0; i < nfixingsnode2; ++i)
4997 mark[fixingsnode2[i]] =
TRUE;
5000 for (i = 0; i < nsuccarray; ++i)
5007 vertex1 = succarray[i];
5019 for (s = 0; s < nsucc; ++s)
5021 if ( mark[succ[s]] )
5023 fixingsnode21[nfixingsnode21++] = succ[s];
5024 assert( nfixingsnode21 == 1 || (fixingsnode21[nfixingsnode21 - 1] > fixingsnode21[nfixingsnode21 - 2]) );
5029 if ( nfixingsnode21 == nfixingsnode2 )
5034 assert( ! infeasible );
5040 assert ( nfixingsnode22 + nfixingsnode21 == nfixingsnode2 );
5043 SCIP_CALL(
getCoverVertices(conflictgraph, verticesarefixed, -1, fixingsnode22, nfixingsnode22, coverarray, &ncoverarray) );
5047 for (j = 0; j < ncoverarray; ++j)
5051 vertex2 = coverarray[j];
5052 assert( vertex2 != vertex1 );
5055 if ( vertex2 < vertex1 )
5083 assert( nodedata !=
NULL );
5084 boundvar1 = nodedata->ubboundvar;
5085 lbboundcoef1 = nodedata->lbboundcoef;
5086 ubboundcoef1 = nodedata->ubboundcoef;
5088 assert( nodedata !=
NULL );
5089 boundvar2 = nodedata->ubboundvar;
5090 lbboundcoef2 = nodedata->lbboundcoef;
5091 ubboundcoef2 = nodedata->ubboundcoef;
5097 if ( conshdlrdata->addextendedbds )
5099 if ( localconflicts ==
NULL )
5102 localconflicts = conshdlrdata->localconflicts;
5116 conshdlrdata->isconflocal =
TRUE;
5156 feas += solval1/ubboundcoef1;
5162 feas += solval1/lbboundcoef1;
5169 feas += solval2/ubboundcoef2;
5175 feas += solval2/lbboundcoef2;
5180 if (
SCIPisGT(scip, feas, conshdlrdata->addcompsfeas) )
5184 SCIP_CALL(
SCIPcreateConsSOS1(scip, &conssos1, name, 0,
NULL,
NULL,
TRUE,
TRUE,
TRUE,
FALSE,
TRUE,
5209 SCIP_CALL(
SCIPcreateConsLinear(scip, &conssos1, name, 0,
NULL,
NULL, -
SCIPinfinity(scip), 0.0,
TRUE,
FALSE,
TRUE,
FALSE,
FALSE,
5218 SCIP_CALL(
SCIPcreateConsLinear(scip, &conssos1, name, 0,
NULL,
NULL, -
SCIPinfinity(scip), 1.0,
TRUE,
FALSE,
TRUE,
FALSE,
FALSE,
5226 if (
SCIPisGT(scip, feas, conshdlrdata->addbdsfeas ) )
5237 if ( conshdlrdata->maxaddcomps >= 0 && *naddedconss > conshdlrdata->maxaddcomps )
5245 if ( conshdlrdata->maxaddcomps >= 0 && *naddedconss > conshdlrdata->maxaddcomps )
5271 for (j = 0; j < nsos1vars; ++j)
5333 int* fixingsnode1 =
NULL;
5334 int* fixingsnode2 =
NULL;
5356 assert( scip !=
NULL );
5357 assert( conshdlrdata !=
NULL );
5358 assert( conshdlr !=
NULL );
5359 assert( conss !=
NULL );
5360 assert( result !=
NULL );
5366 nsos1vars = conshdlrdata->nsos1vars;
5369 conflictgraph = conshdlrdata->conflictgraph;
5370 assert( ! conshdlrdata->isconflocal );
5373 for (c = 0; c < nconss; ++c)
5380 assert( cons !=
NULL );
5382 assert( consdata !=
NULL );
5385 if ( consdata->nvars < 2 )
5402 assert( ngen == 0 );
5405 if ( consdata->local )
5412 if ( conshdlrdata->localconflicts ==
NULL )
5417 vars = consdata->vars;
5418 nvars = consdata->nvars;
5419 for (i = 0; i < nvars-1; ++i)
5425 assert( indi >= 0 );
5429 for (j = i+1; j < nvars; ++j)
5433 assert( indj >= 0 );
5445 conshdlrdata->isconflocal =
TRUE;
5455 if ( conshdlrdata->isconflocal )
5457 for (j = 0; j < nsos1vars; ++j)
5473 if ( conshdlrdata->isconflocal )
5476 conshdlrdata->isconflocal =
FALSE;
5484 for (j = 0; j < nsos1vars; ++j)
5494 verticesarefixed[j] =
TRUE;
5496 verticesarefixed[j] =
FALSE;
5500 if ( conshdlrdata->branchingrule ==
'b' )
5504 if ( conshdlrdata->nstrongrounds >= 0 )
5505 nstrongrounds =
MIN(conshdlrdata->nstrongrounds, nsos1vars);
5515 nstrongrounds =
MIN(nsos1vars, nstrongrounds);
5528 if ( nstrongrounds == 0 )
5533 SCIP_CALL(
getBranchingPrioritiesSOS1(scip, conshdlrdata, conflictgraph, sol, nsos1vars, verticesarefixed, bipbranch, fixingsnode1, fixingsnode2,
NULL, &branchvertex, &relsolfeas) );
5538 SCIPdebugMsg(scip,
"all the SOS1 constraints are feasible.\n");
5544 if ( conshdlrdata->isconflocal )
5547 conshdlrdata->isconflocal =
FALSE;
5562 fixingsnode1, fixingsnode2, &branchvertex, &bestobjval1, &bestobjval2, result) );
5567 if ( conshdlrdata->isconflocal )
5570 conshdlrdata->isconflocal =
FALSE;
5583 if ( ! conshdlrdata->branchsos )
5586 if ( conshdlrdata->isconflocal )
5589 conshdlrdata->isconflocal =
FALSE;
5599 SCIPerrorMessage(
"Incompatible parameter setting: branchsos can only be set to false if all SOS1 variables are binary.\n");
5607 assert( branchvertex >= 0 && branchvertex < nsos1vars );
5608 assert( ! verticesarefixed[branchvertex] );
5609 SCIP_CALL(
getBranchingVerticesSOS1(scip, conflictgraph, sol, verticesarefixed, bipbranch, branchvertex, fixingsnode1, &nfixingsnode1, fixingsnode2, &nfixingsnode2) );
5614 for (j = 0; j < nfixingsnode1; ++j)
5623 objest = objest/((
SCIP_Real) nfixingsnode1);
5629 if ( conshdlrdata->fixnonzero && nfixingsnode2 == 1 )
5668 for (j = 0; j < nfixingsnode1; ++j)
5672 assert( ! infeasible );
5678 for (j = 0; j < nfixingsnode2; ++j)
5688 objest = objest/((
SCIP_Real) nfixingsnode2);
5694 for (j = 0; j < nfixingsnode2; ++j)
5697 assert( ! infeasible );
5702 if ( conshdlrdata->addcomps && ( conshdlrdata->addcompsdepth == -1 || conshdlrdata->addcompsdepth >=
SCIPgetDepth(scip) ) )
5706 assert( ! conshdlrdata->fixnonzero );
5710 nsos1vars, verticesarefixed, fixingsnode1, nfixingsnode1, fixingsnode2, nfixingsnode2, &naddedconss,
TRUE) );
5712 if ( naddedconss == 0 )
5716 nsos1vars, verticesarefixed, fixingsnode2, nfixingsnode2, fixingsnode1, nfixingsnode1, &naddedconss,
TRUE) );
5721 if ( nstrongrounds > 0 )
5728 if ( conshdlrdata->isconflocal )
5731 conshdlrdata->isconflocal =
FALSE;
5796 assert( scip !=
NULL );
5797 assert( conshdlr !=
NULL );
5798 assert( conss !=
NULL );
5799 assert( result !=
NULL );
5809 assert( conshdlrdata !=
NULL );
5812 for (c = 0; c < nconss; ++c)
5822 assert( cons !=
NULL );
5824 assert( consdata !=
NULL );
5828 nvars = consdata->nvars;
5829 vars = consdata->vars;
5848 assert( ngen == 0 );
5852 for (j = 0; j < nvars; ++j)
5858 if ( conshdlrdata->branchnonzeros )
5862 if ( conshdlrdata->branchweight )
5865 if ( consdata->weights[j] > weight )
5866 weight = consdata->weights[j];
5875 if ( cnt > 1 && weight > maxWeight )
5883 if ( branchCons ==
NULL )
5885 SCIPdebugMsg(scip,
"All SOS1 constraints are feasible.\n");
5890 if ( ! conshdlrdata->branchsos )
5895 for (j = 0; j < consdata->nvars; ++j)
5901 if ( j == consdata->nvars )
5908 SCIPerrorMessage(
"Incompatible parameter setting: branchsos can only be set to false if all SOS1 variables are binary.\n");
5916 assert( consdata !=
NULL );
5917 nvars = consdata->nvars;
5918 vars = consdata->vars;
5932 assert( ! infeasible );
5936 assert( ! infeasible );
5956 for (j = 0; j < nvars; ++j)
5968 w = weight1/weight2;
5971 assert( 0 <= ind && ind < nvars-1 );
5979 for (j = 0; j <= ind; ++j)
5989 for (j = 0; j <= ind; ++j)
5992 assert( ! infeasible );
5998 for (j = ind+1; j < nvars; ++j)
6004 objest = objest/((
SCIP_Real) (nvars - ind - 1));
6008 for (j = ind+1; j < nvars; ++j)
6011 assert( ! infeasible );
6034 assert( scip !=
NULL );
6035 assert( conshdlr !=
NULL );
6036 assert( conss !=
NULL );
6037 assert( result !=
NULL );
6041 assert( conshdlrdata !=
NULL );
6043 if ( conshdlrdata->addcomps && conshdlrdata->fixnonzero )
6045 SCIPerrorMessage(
"Incompatible parameter setting: addcomps = TRUE and fixnonzero = TRUE.\n");
6049 if ( conshdlrdata->fixnonzero && ( conshdlrdata->branchingrule ==
'b' || conshdlrdata->branchingrule ==
's' ) )
6051 SCIPerrorMessage(
"Incompatible parameter setting: nonzero fixing is not compatible with bipartite or sos1 branching.\n");
6055 if ( conshdlrdata->branchingrule ==
's' && conshdlrdata->nstrongrounds != 0 )
6057 SCIPerrorMessage(
"Strong branching is not available for SOS1 branching.\n");
6061 if ( conshdlrdata->branchingrule ==
's' || conshdlrdata->switchsos1branch )
6068 if ( conshdlrdata->branchingrule !=
'n' && conshdlrdata->branchingrule !=
'b' )
6070 SCIPerrorMessage(
"branching rule %c unknown\n", conshdlrdata->branchingrule);
6102 for (j = 0; j < nsos1vars; ++j)
6109 for (j = 0; j < nsos1vars; ++j)
6119 for (i = 0; i < nsucc; ++i)
6136 tcliquedata = conshdlrdata->tcliquedata;
6139 tcliquedata->
scip = scip;
6144 tcliquedata->
ncuts = 0;
6145 tcliquedata->
nboundcuts = conshdlrdata->nboundcuts;
6147 tcliquedata->
maxboundcuts = conshdlrdata->maxboundcutsroot;
6169 for (j = 0; j < nsos1vars; ++j)
6180 if ( conshdlrdata->strthenboundcuts )
6187 if ( conshdlrdata->strthenboundcuts )
6200 nodeweight =
REALABS( solval/bound ) * scaleval;
6224 assert( scip !=
NULL );
6225 assert( tcliquedata !=
NULL );
6226 assert( success !=
NULL);
6227 assert( cutoff !=
NULL );
6233 if ( rowlb !=
NULL )
6244 ++tcliquedata->
ncuts;
6250 if ( rowub !=
NULL )
6261 ++tcliquedata->
ncuts;
6300 const char* nameext,
6313 assert( scip !=
NULL );
6314 assert( conshdlr !=
NULL );
6315 assert( conflictgraph !=
NULL );
6316 assert( ! local || ! global );
6317 assert( nodes !=
NULL );
6324 if ( rowub !=
NULL )
6333 useboundvar = strengthen;
6334 for (j = 0; j <
nnodes; ++j)
6341 assert( nodedata !=
NULL );
6342 var = nodedata->var;
6343 assert( var !=
NULL );
6346 if ( ! useboundvar || nodedata->ubboundvar ==
NULL )
6348 useboundvar =
FALSE;
6369 if ( ubboundvar ==
NULL )
6371 ubboundvar = nodedata->ubboundvar;
6372 val = nodedata->ubboundcoef;
6375 else if ( ubboundvar == nodedata->ubboundvar )
6376 val = nodedata->ubboundcoef;
6379 useboundvar =
FALSE;
6401 vals[cnt++] = 1.0/val;
6406 if ( j == nnodes && cnt >= 2 )
6416 rhs = rhs * vals[0] * vals[1];
6417 assert( (! useboundvar && cnt == 2 ) || (useboundvar && cnt == 3 ) );
6423 vars[cnt] = ubboundvar;
6425 assert(ubboundvar !=
NULL );
6446 if ( rowlb !=
NULL )
6456 useboundvar = strengthen;
6457 for (j = 0; j <
nnodes; ++j)
6464 assert( nodedata !=
NULL );
6465 var = nodedata->var;
6466 assert( var !=
NULL );
6469 if ( ! useboundvar || nodedata->lbboundvar ==
NULL )
6471 useboundvar =
FALSE;
6492 if ( lbboundvar ==
NULL )
6494 lbboundvar = nodedata->lbboundvar;
6495 val = nodedata->lbboundcoef;
6498 else if (
SCIPvarCompare(lbboundvar, nodedata->lbboundvar) == 0 )
6500 val = nodedata->lbboundcoef;
6504 useboundvar =
FALSE;
6526 vals[cnt++] = 1.0/val;
6531 if ( j == nnodes && cnt >= 2 )
6541 rhs = rhs * vals[0] * vals[1];
6542 assert( (! useboundvar && cnt == 2 ) || (useboundvar && cnt == 3 ) );
6548 vars[cnt] = lbboundvar;
6550 assert(lbboundvar !=
NULL );
6585 assert( acceptsol !=
NULL );
6586 assert( stopsolving !=
NULL );
6591 *stopsolving =
FALSE;
6594 minweightinc = (cliqueweight - *minweight)/10;
6595 minweightinc =
MAX(minweightinc, 1);
6596 *minweight += minweightinc;
6599 if( cliqueweight > tcliquedata->
scaleval )
6610 scip = tcliquedata->
scip;
6611 sol = tcliquedata->
sol;
6612 assert( scip !=
NULL );
6615 unscaledweight = 0.0;
6616 for( i = 0; i < ncliquenodes; i++ )
6618 node = cliquenodes[i];
6642 unscaledweight +=
REALABS( solval/bound );
6672 if ( rowlb !=
NULL )
6681 if ( rowub !=
NULL )
6694 SCIPdebugMsg(scip,
" -> found bound cut corresponding to clique (act=%g)\n", unscaledweight);
6704 *stopsolving =
TRUE;
6708 *stopsolving =
TRUE;
6733 int maxtreenodes = 10000;
6734 int maxzeroextensions = 1000;
6735 int backtrackfreq = 1000;
6740 assert( scip !=
NULL );
6741 assert( conshdlr !=
NULL );
6742 assert( conshdlrdata !=
NULL );
6743 assert( ngen !=
NULL );
6747 assert( conflictgraph !=
NULL );
6753 tcliquedata = conshdlrdata->tcliquedata;
6756 tcliquedata->
sol = sol;
6757 tcliquedata->
ncuts = 0;
6767 tcliqueMaxClique(tcliqueGetNNodes, tcliqueGetWeights, tcliqueIsEdge, tcliqueSelectAdjnodes,
6768 conshdlrdata->tcliquegraph, tcliqueNewsolClique, tcliquedata,
6769 cliquenodes, &ncliquenodes, &cliqueweight, (
int)scaleval-1, (
int)scaleval+1,
6770 maxtreenodes, backtrackfreq, maxzeroextensions, -1, &ntreenodes, &tcliquestatus);
6776 *ngen = tcliquedata->
ncuts;
6779 *cutoff = tcliquedata->
cutoff;
6782 conshdlrdata->nboundcuts = tcliquedata->
nboundcuts;
6809 assert( scip !=
NULL );
6810 assert( conshdlr !=
NULL );
6811 assert( cons !=
NULL );
6815 assert( consdata !=
NULL );
6816 assert( consdata->vars !=
NULL );
6817 nvars = consdata->nvars;
6821 assert( conshdlrdata !=
NULL );
6828 for (j = 0; j < nvars; ++j)
6869 assert( scip !=
NULL );
6870 assert( conshdlrdata !=
NULL );
6871 assert( conss !=
NULL );
6875 for (c = 0; c < nconss; ++c)
6882 assert( conss !=
NULL );
6883 assert( conss[c] !=
NULL );
6885 assert( consdata !=
NULL );
6898 if ( consdata->local )
6905 if ( consdata->rowub ==
NULL || consdata->rowlb ==
NULL )
6908 (consdata->rowlb ==
NULL) ? &consdata->rowlb :
NULL,
6909 (consdata->rowub == NULL) ? &consdata->rowub : NULL) );
6911 rowub = consdata->rowub;
6912 rowlb = consdata->rowlb;
6943 if ( rowlb !=
NULL )
6947 if ( rowub !=
NULL )
6953 if ( *cutoff || ( maxboundcuts >= 0 && cnt >= maxboundcuts ) )
6982 assert( scip !=
NULL);
6983 assert( conshdlrdata !=
NULL);
6984 assert( conshdlr !=
NULL);
6985 assert( ngen !=
NULL);
6986 assert( cutoff !=
NULL);
6992 if ( conshdlrdata->conflictgraph ==
NULL )
6996 implgraph = conshdlrdata->implgraph;
6999 if ( implgraph ==
NULL )
7006 SCIP_CALL(
initImplGraphSOS1(scip, conshdlrdata, conshdlrdata->conflictgraph, conshdlrdata->nsos1vars, conshdlrdata->maxtightenbds, &nchbds, cutoff, &success) );
7007 if ( *cutoff || ! success )
7009 implgraph = conshdlrdata->implgraph;
7016 nimplnodes = conshdlrdata->nimplnodes;
7017 assert( implgraph !=
NULL );
7018 assert( nimplnodes > 0);
7026 for (i = 0; i < nimplnodes && ! genbreak; ++i)
7038 assert( nodedata !=
NULL );
7039 var = nodedata->var;
7040 assert( var !=
NULL );
7048 for (s = 0; s < nsucc && ! genbreak; ++s)
7063 succdata = succdatas[s];
7064 assert( nodedata !=
NULL && succdata !=
NULL && nodedata->var !=
NULL );
7065 succvar = nodedata->var;
7077 bound1lower =
FALSE;
7082 for (k = 0; k < 2; ++k)
7090 impl = succdata->lbimpl;
7102 impl = succdata->ubimpl;
7116 bound2lower =
FALSE;
7119 lhsrhs = bound1 * bound2;
7122 if ( bound1lower == bound2lower )
7124 if (
SCIPisFeasGT(scip, solval * (bound2-impl) + solvalsucc * bound1, lhsrhs) )
7133 if (
SCIPisFeasLT(scip, solval * (bound2-impl) + solvalsucc * bound1, lhsrhs) )
7173 if ( maxcuts >= 0 && *ngen > maxcuts )
7204 assert( scip !=
NULL );
7205 assert( conshdlr !=
NULL );
7206 assert( conss !=
NULL );
7207 assert( result !=
NULL );
7222 assert( conshdlrdata !=
NULL );
7229 if ( conshdlrdata->boundcutsfreq >= 0 && ( (conshdlrdata->boundcutsfreq == 0 && depth == 0) || (conshdlrdata->boundcutsfreq > 0 && depth % conshdlrdata->boundcutsfreq == 0)) )
7236 maxboundcuts = conshdlrdata->maxboundcutsroot;
7238 maxboundcuts = conshdlrdata->maxboundcuts;
7240 if ( maxboundcuts >= 1 )
7243 if( conshdlrdata->boundcutsfromsos1 || conshdlrdata->switchcutsfromsos1 )
7256 if( conshdlrdata->boundcutsfromgraph && ! conshdlrdata->switchcutsfromsos1 )
7271 SCIPdebugMsg(scip,
"Separated %d bound (clique) inequalities.\n", ngen);
7276 if ( conshdlrdata->implcutsfreq >= 0 && ( (conshdlrdata->implcutsfreq == 0 && depth == 0) || (conshdlrdata->implcutsfreq > 0 && depth % conshdlrdata->implcutsfreq == 0)) )
7283 maximplcuts = conshdlrdata->maximplcutsroot;
7285 maximplcuts = conshdlrdata->maximplcuts;
7288 if ( maximplcuts >= 1 )
7302 SCIPdebugMsg(scip,
"Separated %d implied bound inequalities.\n", ngen);
7331 assert( scip !=
NULL );
7332 assert( conflictgraph !=
NULL );
7333 assert( indicatorzero !=
NULL );
7334 assert( weights !=
NULL );
7336 for (i = 0; i < nsos1vars; ++i)
7340 if( nsucc == 0 || indicatorzero[i] )
7354 for (j = 0; j < nsucc; ++j)
7361 sum +=
MIN(10E05, valsucc);
7371 val =
MIN(1e6, val);
7399 assert( scip !=
NULL );
7400 assert( conflictgraph !=
NULL );
7401 assert( mark !=
NULL );
7402 assert( indset !=
NULL );
7403 assert( cutoff !=
NULL );
7404 assert( cnt !=
NULL );
7412 for (j = 0; j < nsucc && !(*cutoff); ++j)
7417 assert( indset[succj] == 0 );
7439 if ( aggrnode >= 0 )
7444 if ( ! mark[aggrnode] )
7446 mark[aggrnode] =
TRUE;
7449 else if ( indset[aggrnode] == 1 )
7458 if ( indset[aggrnode] == 0 )
7461 if ( mark[aggrnode] )
7468 indset[aggrnode] = 1;
7469 mark[aggrnode] =
TRUE;
7490 if ( indset[negnode] == 1 )
7495 else if ( ! mark[negnode] )
7497 mark[negnode] =
TRUE;
7537 int* indscipvars =
NULL;
7543 assert( scip !=
NULL );
7544 assert( conflictgraph !=
NULL );
7545 assert( indicatorzero !=
NULL );
7546 assert( indset !=
NULL );
7554 for (i = 0; i < nsos1vars; ++i)
7562 for (i = 0; i < nsos1vars; ++i)
7566 if ( indset[i] == 0 )
7568 if( indicatorzero[i] )
7573 else if ( nsucc == 0 )
7595 for (i = 0; k < nsos1vars; ++i)
7597 assert( i < nsos1vars );
7599 ind = indscipvars[i];
7615 assert( k == nsos1vars );
7645 assert( scip !=
NULL );
7646 assert( conshdlr !=
NULL );
7647 assert( sol !=
NULL );
7648 assert( changed !=
NULL );
7650 *allroundable =
TRUE;
7655 assert( nsos1vars >= 0 );
7659 assert( conflictgraph !=
NULL );
7666 for (j = 0; j < nsos1vars; ++j)
7679 indicatorzero[j] =
TRUE;
7682 indicatorzero[j] =
FALSE;
7687 *allroundable =
FALSE;
7693 indicatorzero[j] =
TRUE;
7700 if ( ! (*allroundable) )
7711 for (j = 0; j < nsos1vars; ++j)
7713 if ( indset[j] == 0 )
7733 for (c = 0; c < nconss; ++c)
7737 assert( consdata !=
NULL );
7739 for (j = 0; j < consdata->nvars; ++j)
7773 assert( scip !=
NULL );
7774 assert( conshdlr !=
NULL );
7775 assert( sol !=
NULL );
7776 assert( changed !=
NULL );
7778 *allroundable =
TRUE;
7784 assert( nconss > 0 );
7787 for (c = 0; c < nconss && *allroundable; ++c)
7798 assert( cons !=
NULL );
7800 assert( consdata !=
NULL );
7802 nvars = consdata->nvars;
7803 vars = consdata->vars;
7806 for (j = 0; j < nvars; ++j)
7823 *allroundable =
FALSE;
7836 assert( ! varisfixed );
7854 if ( ! (*allroundable) )
7856 else if ( pos >= 0 )
7863 if ( *allroundable )
7865 for (c = 0; c < nconss; ++c)
7871 assert( consdata !=
NULL );
7873 for (j = 0; j < consdata->nvars; ++j)
7910 assert( scip !=
NULL );
7911 assert( conshdlr !=
NULL );
7912 assert( diveset !=
NULL );
7913 assert( success !=
NULL );
7924 for (v = 0; v < nsos1vars; ++v)
7966 &score, &roundup) );
7970 fixneigh = !fixneigh;
7982 if ( score > bestscore )
7989 bestvarfixneigh = fixneigh;
7993 assert( !(*success) || bestvar !=
NULL );
8001 assert( bestnode >= 0 && bestnode < nsos1vars );
8011 for (s = 0; s < nsucc; ++s)
8052 assert( scip !=
NULL );
8053 assert( conshdlr !=
NULL );
8054 assert( diveset !=
NULL );
8055 assert( success !=
NULL );
8064 for (c = 0; c < nconss; ++c)
8072 assert( consdata !=
NULL );
8074 nvars = consdata->nvars;
8075 vars = consdata->vars;
8078 for (j = 0; j < nvars && cnt < 2; ++j)
8095 for (j = 0; j < nvars; ++j)
8142 &score, &roundup) );
8158 if ( score > bestscore )
8165 bestvarfixcomp = fixcomp;
8170 assert( !(*success) || bestvar !=
NULL );
8179 assert( consdata !=
NULL );
8181 nvars = consdata->nvars;
8182 vars = consdata->vars;
8184 assert( bestcons >= 0 && bestcons < nconss );
8192 for (j = 0; j < nvars; ++j)
8227 assert( scip !=
NULL );
8228 assert( conshdlrdata !=
NULL );
8229 assert( var0 !=
NULL && var1 !=
NULL );
8253 if ( nodedata->lbboundvar ==
NULL )
8256 nodedata->lbboundvar = var1;
8257 nodedata->lbboundcoef = val;
8271 if ( nodedata->ubboundvar ==
NULL )
8274 nodedata->ubboundvar = var1;
8275 nodedata->ubboundcoef = val;
8308 assert( scip !=
NULL );
8309 assert( conflictgraph !=
NULL );
8310 assert( processed !=
NULL );
8311 assert( concomp !=
NULL );
8312 assert( nconcomp !=
NULL );
8313 assert( unique !=
NULL );
8315 processed[node] =
TRUE;
8316 concomp[(*nconcomp)++] = node;
8324 assert( nodedata !=
NULL );
8327 comparevar = nodedata->lbboundvar;
8329 comparevar = nodedata->ubboundvar;
8332 if ( boundvar ==
NULL )
8334 if ( comparevar !=
NULL )
8339 if ( comparevar ==
NULL )
8349 for (s = 0; s < nsucc; ++s)
8351 if ( ! processed[succ[s]] )
8377 assert( scip !=
NULL );
8378 assert( conflictgraph !=
NULL );
8383 for (j = 0; j < nsos1vars; ++j)
8384 processed[j] =
FALSE;
8387 for (j = 0; j < nsos1vars; ++j)
8390 if ( ! processed[j] )
8400 assert( nodedata !=
NULL );
8403 boundvar = nodedata->lbboundvar;
8405 boundvar = nodedata->ubboundvar;
8408 processed[j] =
TRUE;
8415 for (s = 0; s < nsucc; ++s)
8417 if ( ! processed[succ[s]] )
8424 if ( unique && boundvar !=
NULL )
8426 for (s = 0; s < nconcomp; ++s)
8429 assert( processed[concomp[s]] ==
TRUE );
8430 assert( nodedata !=
NULL );
8433 nodedata->lbboundcomp =
TRUE;
8435 nodedata->ubboundcomp =
TRUE;
8437 SCIPdebugMsg(scip,
"Found a connected component of size <%i> with unique bound variable.\n", nconcomp);
8464 for (c = 0; c < nlinconss; ++c)
8469 lincons = linconss[c];
8490 assert( var0 !=
NULL && var1 !=
NULL );
8539 if ( conshdlrdata->nsos1vars > 0 )
8541 for (c = 0; c < nconss && nonoverlap; ++c)
8549 assert( conss[c] !=
NULL );
8553 assert( consdata !=
NULL );
8556 nvars = consdata->nvars;
8557 vars = consdata->vars;
8560 for (i = 0; i < nvars; ++i)
8567 for (i = 0; i < nvars; ++i)
8571 assert( vars[i] !=
NULL );
8575 assert( node < conshdlrdata->nsos1vars );
8589 if ( conshdlrdata->autosos1branch )
8591 conshdlrdata->switchsos1branch =
TRUE;
8592 SCIPdebugMsg(scip,
"Switched to SOS1 branching, since the SOS1 constraints do not overlap\n");
8595 if ( conshdlrdata->autocutsfromsos1 )
8597 conshdlrdata->switchcutsfromsos1 =
TRUE;
8598 SCIPdebugMsg(scip,
"Switched to separating bound cuts from SOS1 constraints (and not from the conflict graph), since the SOS1 constraints do not overlap\n");
8619 if ( nsos1vars == 0 )
8624 if ( linconshdlr ==
NULL )
8661 assert( conshdlrdata !=
NULL );
8662 assert( nconss == 0 || conss !=
NULL );
8670 for (i = 0; i < ntotalvars; ++i)
8671 nodecreated[i] =
FALSE;
8675 for (c = 0; c < nconss; ++c)
8681 assert( conss[c] !=
NULL );
8685 assert( consdata !=
NULL );
8688 nvars = consdata->nvars;
8689 vars = consdata->vars;
8692 for (i = 0; i < nvars; ++i)
8704 assert( ind >= 0 && ind < ntotalvars );
8705 if ( ! nodecreated[ind] )
8707 nodecreated[ind] =
TRUE;
8708 nodeorig[ind] = cntsos;
8719 conshdlrdata->nsos1vars = 0;
8724 for (i = 0; i < ntotalvars; ++i)
8725 nodecreated[i] =
FALSE;
8735 for (c = 0; c < nconss; ++c)
8741 assert( conss[c] !=
NULL );
8745 assert( consdata !=
NULL );
8748 nvars = consdata->nvars;
8749 vars = consdata->vars;
8752 for (i = 0; i < nvars; ++i)
8765 if ( ! nodecreated[indi] )
8777 nodedata->var = var;
8778 nodedata->lbboundvar =
NULL;
8779 nodedata->ubboundvar =
NULL;
8780 nodedata->lbboundcoef = 0.0;
8781 nodedata->ubboundcoef = 0.0;
8782 nodedata->lbboundcomp =
FALSE;
8783 nodedata->ubboundcomp =
FALSE;
8789 nodecreated[indi] =
TRUE;
8794 for (j = i+1; j < nvars; ++j)
8819 conshdlrdata->nsos1vars = cntsos;
8826 for (j = 0; j < conshdlrdata->nsos1vars; ++j)
8847 if ( conshdlrdata->conflictgraph ==
NULL )
8849 assert( conshdlrdata->nsos1vars == 0 );
8854 assert( conshdlrdata->nsos1vars > 0 );
8855 for (j = 0; j < conshdlrdata->nsos1vars; ++j)
8860 assert( conshdlrdata->conflictgraph !=
NULL );
8862 assert( nodedata !=
NULL );
8870 assert( conshdlrdata->varhash !=
NULL );
8873 conshdlrdata->nsos1vars = 0;
8875 assert( conshdlrdata->varhash ==
NULL );
8876 assert( conshdlrdata->conflictgraph ==
NULL );
8888 assert( scip !=
NULL );
8889 assert( conshdlr !=
NULL );
8907 assert( scip !=
NULL );
8908 assert( conshdlr !=
NULL );
8912 assert(conshdlrdata !=
NULL);
8929 assert( scip !=
NULL );
8930 assert( conshdlr !=
NULL );
8934 assert( conshdlrdata !=
NULL );
8936 conshdlrdata->nsos1vars = 0;
8937 conshdlrdata->varhash =
NULL;
8947 if ( ( conshdlrdata->autosos1branch || conshdlrdata->autocutsfromsos1 )
8948 && ( ! conshdlrdata->switchsos1branch || ! conshdlrdata->switchcutsfromsos1 )
8959 if ( conshdlrdata->addcomps )
8965 if ( conshdlrdata->fixnonzerovars ==
NULL )
8967 conshdlrdata->maxnfixnonzerovars = conshdlrdata->nsos1vars;
8983 assert( scip !=
NULL );
8987 assert( conshdlrdata !=
NULL );
8990 for (c = 0; c < nconss; ++c)
8994 assert( conss !=
NULL );
8995 assert( conss[c] !=
NULL );
8997 assert( consdata !=
NULL );
9002 if ( consdata->rowub !=
NULL )
9007 if ( consdata->rowlb !=
NULL )
9014 if ( conshdlrdata->implgraph !=
NULL )
9018 assert( conshdlrdata->implgraph ==
NULL );
9021 if ( conshdlrdata->tcliquegraph !=
NULL )
9023 assert( conshdlrdata->tcliquedata !=
NULL );
9027 assert(conshdlrdata->tcliquegraph ==
NULL);
9028 assert(conshdlrdata->tcliquedata ==
NULL);
9032 conshdlrdata->nfixnonzerovars = 0;
9033 conshdlrdata->maxnfixnonzerovars = 0;
9036 if ( conshdlrdata->localconflicts !=
NULL )
9038 assert( conshdlrdata->localconflicts ==
NULL );
9042 assert( conshdlrdata->conflictgraph ==
NULL );
9052 assert( scip !=
NULL );
9053 assert( conshdlr !=
NULL );
9054 assert( cons !=
NULL );
9055 assert( consdata !=
NULL );
9068 assert( conshdlrdata !=
NULL );
9069 assert( conshdlrdata->eventhdlr !=
NULL );
9071 for (j = 0; j < (*consdata)->nvars; ++j)
9079 if ( (*consdata)->weights !=
NULL )
9085 if ( (*consdata)->rowub !=
NULL )
9089 if ( (*consdata)->rowlb !=
NULL )
9093 assert( (*consdata)->rowub ==
NULL );
9094 assert( (*consdata)->rowlb ==
NULL );
9112 assert( scip !=
NULL );
9113 assert( conshdlr !=
NULL );
9115 assert( sourcecons !=
NULL );
9116 assert( targetcons !=
NULL );
9120 assert( conshdlrdata !=
NULL );
9121 assert( conshdlrdata->eventhdlr !=
NULL );
9127 assert( sourcedata !=
NULL );
9128 assert( sourcedata->nvars > 0 );
9129 assert( sourcedata->nvars <= sourcedata->maxvars );
9132 if ( conshdlrdata->fixnonzerovars ==
NULL )
9141 consdata->nvars = sourcedata->nvars;
9142 consdata->maxvars = sourcedata->nvars;
9143 consdata->rowub =
NULL;
9144 consdata->rowlb =
NULL;
9145 consdata->nfixednonzeros = 0;
9146 consdata->local = sourcedata->local;
9149 if ( sourcedata->weights !=
NULL )
9154 consdata->weights =
NULL;
9156 for (j = 0; j < sourcedata->nvars; ++j)
9158 assert( sourcedata->vars[j] != 0 );
9163 ++(consdata->nfixednonzeros);
9176 for (j = 0; j < consdata->nvars; ++j)
9183 if ( consdata->nfixednonzeros > 0 )
9186 consdata->nfixednonzeros );
9209 assert( scip !=
NULL );
9210 assert( conshdlr !=
NULL );
9212 assert( result !=
NULL );
9215 assert( conshdlrdata !=
NULL );
9221 SCIPdebug( oldnfixedvars = *nfixedvars; )
9224 SCIPdebug( oldnupgdconss = *nupgdconss; )
9228 if( nconss > 0 && ( nrounds == 0 || nnewfixedvars > 0 || nnewaggrvars > 0 || nnewchgbds > 0 ) )
9242 assert( eventhdlr !=
NULL );
9248 conflictgraph = conshdlrdata->conflictgraph;
9249 nsos1vars = conshdlrdata->nsos1vars;
9250 if ( nsos1vars < 2 )
9257 if ( conshdlrdata->maxsosadjacency == -1 || nsos1vars <= conshdlrdata->maxsosadjacency )
9261 for (i = 0; i < nsos1vars; ++i)
9267 for (i = 0; i < nsos1vars; ++i)
9269 for (j = 0; j < i+1; ++j)
9270 adjacencymatrix[i][j] = 0;
9272 for (i = 0; i < nsos1vars; ++i)
9280 for (j = 0; j < nsucc; ++j)
9283 adjacencymatrix[i][succ[j]] = 1;
9289 SCIPdebugMsg(scip,
"Adjacency matrix was not created since number of SOS1 variables (%d) is larger than %d.\n", nsos1vars, conshdlrdata->maxsosadjacency);
9293 SCIP_CALL(
presolRoundConssSOS1(scip, eventhdlr, conshdlrdata, conflictgraph, adjacencymatrix, conss, nconss, nsos1vars, naddconss, ndelconss, nupgdconss, nfixedvars, &nremovedvars, result) );
9295 if ( adjacencymatrix !=
NULL )
9298 if ( conshdlrdata->maxtightenbds != 0 && *result !=
SCIP_CUTOFF )
9300 SCIP_CALL(
presolRoundVarsSOS1(scip, conshdlrdata, conflictgraph, adjacencymatrix, nsos1vars, nfixedvars, nchgbds, naddconss, result) );
9304 for (j = nsos1vars-1; j >= 0; --j)
9312 (*nchgcoefs) += nremovedvars;
9314 SCIPdebugMsg(scip,
"presolving fixed %d variables, changed %d bounds, removed %d variables, deleted %d constraints, and upgraded %d constraints.\n",
9315 *nfixedvars - oldnfixedvars, *nchgbds - oldnchgbds, nremovedvars, *ndelconss - oldndelconss, *nupgdconss - oldnupgdconss);
9327 assert( scip !=
NULL );
9328 assert( conshdlr !=
NULL );
9332 assert( conshdlrdata !=
NULL );
9334 *infeasible =
FALSE;
9337 if( conshdlrdata->boundcutsfromsos1 || conshdlrdata->switchcutsfromsos1 )
9350 assert( scip !=
NULL );
9351 assert( conshdlr !=
NULL );
9352 assert( conss !=
NULL );
9366 assert( scip !=
NULL );
9367 assert( conshdlr !=
NULL );
9368 assert( conss !=
NULL );
9382 assert( scip !=
NULL );
9383 assert( conshdlr !=
NULL );
9384 assert( conss !=
NULL );
9398 assert( scip !=
NULL );
9399 assert( conshdlr !=
NULL );
9400 assert( conss !=
NULL );
9414 assert( scip !=
NULL );
9415 assert( conshdlr !=
NULL );
9416 assert( conss !=
NULL );
9435 assert( scip !=
NULL );
9436 assert( conshdlr !=
NULL );
9439 assert( result !=
NULL );
9444 for (c = 0; c < nconss && (*result ==
SCIP_FEASIBLE || completely); ++c)
9451 assert( conss[c] !=
NULL );
9453 assert( consdata !=
NULL );
9457 for (j = 0; j < consdata->nvars; ++j)
9477 for (l = 0; l < consdata->nvars; ++l)
9506 assert( scip !=
NULL );
9507 assert( conshdlr !=
NULL );
9508 assert( conss !=
NULL );
9510 assert( result !=
NULL );
9523 assert( conshdlrdata !=
NULL );
9526 conflictgraph = conshdlrdata->conflictgraph;
9529 implgraph = conshdlrdata->implgraph;
9530 if ( implgraph ==
NULL && conshdlrdata->implprop && conflictgraph !=
NULL )
9538 SCIP_CALL(
initImplGraphSOS1(scip, conshdlrdata, conflictgraph, conshdlrdata->nsos1vars, conshdlrdata->maxtightenbds, &nchbds, &cutoff, &success) );
9540 conshdlrdata->implprop =
FALSE;
9547 else if ( nchbds > 0 )
9549 implgraph = conshdlrdata->implgraph;
9552 conshdlrdata->implprop =
FALSE;
9556 if ( conshdlrdata->conflictprop && conflictgraph !=
NULL )
9559 int nfixnonzerovars;
9562 assert( nconss > 0 );
9565 nfixnonzerovars = conshdlrdata->nfixnonzerovars;
9566 fixnonzerovars = conshdlrdata->fixnonzerovars;
9567 assert( fixnonzerovars !=
NULL );
9570 for (j = 0; j < nfixnonzerovars; ++j)
9574 var = fixnonzerovars[j];
9583 assert(
varGetNodeSOS1(conshdlrdata, var) < conshdlrdata->nsos1vars );
9602 conshdlrdata->nfixnonzerovars = 0;
9605 if ( conshdlrdata->sosconsprop || conflictgraph ==
NULL )
9610 for (c = 0; c < nconss; ++c)
9616 assert( conss[c] !=
NULL );
9619 assert( consdata !=
NULL );
9649 assert( scip !=
NULL );
9650 assert( cons !=
NULL );
9652 assert( infervar !=
NULL );
9653 assert( bdchgidx !=
NULL );
9654 assert( result !=
NULL );
9660 if ( inferinfo < 0 )
9664 assert( conshdlr !=
NULL );
9668 assert( conshdlrdata !=
NULL );
9669 assert( conshdlrdata->conflictgraph !=
NULL );
9670 assert( inferinfo >= -conshdlrdata->maxnfixnonzerovars );
9671 assert( inferinfo >= -conshdlrdata->nsos1vars );
9672 assert( inferinfo <= -1 );
9682 assert( consdata !=
NULL );
9683 assert( inferinfo < consdata->nvars );
9685 var = consdata->vars[inferinfo];
9687 assert( var !=
NULL );
9688 assert( var != infervar );
9728 assert( scip !=
NULL );
9729 assert( conshdlr !=
NULL );
9730 assert( cons !=
NULL );
9733 assert( consdata !=
NULL );
9737 vars = consdata->vars;
9738 nvars = consdata->nvars;
9739 assert( vars !=
NULL );
9741 for (j = 0; j < nvars; ++j)
9770 assert( scip !=
NULL );
9772 assert( cons !=
NULL );
9776 assert( consdata !=
NULL );
9778 for (j = 0; j < consdata->nvars; ++j)
9783 if ( consdata->weights ==
NULL )
9802 const char* consname;
9806 assert( scip !=
NULL );
9807 assert( sourcescip !=
NULL );
9808 assert( sourcecons !=
NULL );
9818 SCIPdebugMsg(scip,
"Copying SOS1 constraint <%s> ...\n", consname);
9821 assert( sourceconsdata !=
NULL );
9824 nvars = sourceconsdata->nvars;
9829 sourcevars = sourceconsdata->vars;
9830 assert( sourcevars !=
NULL );
9831 sourceweights = sourceconsdata->weights;
9832 assert( sourceweights !=
NULL );
9839 for( v = 0; v < nvars && *valid; ++v )
9841 SCIP_CALL(
SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &(targetvars[v]), varmap, consmap, global, valid) );
9848 initial, separate, enforce, check, propagate, local, dynamic, removable, stickingatnode) );
9868 assert(scip !=
NULL);
9869 assert(conshdlr !=
NULL);
9871 assert(cons !=
NULL);
9872 assert(success !=
NULL);
9878 SCIP_CALL(
SCIPcreateConsSOS1(scip, cons, name, 0,
NULL,
NULL, initial, separate, enforce, check, propagate, local, dynamic, removable, stickingatnode) );
9888 while ( *s !=
'\0' && *s !=
'(' )
9901 weight = strtod(s, &t);
9911 while ( *s !=
'\0' && ( isspace((
unsigned char)*s) || *s ==
',' || *s ==
')' ) )
9917 while ( *s !=
'\0' );
9930 assert(consdata !=
NULL);
9932 if( varssize < consdata->nvars )
9936 assert(vars !=
NULL);
9953 assert(consdata !=
NULL);
9955 (*nvars) = consdata->nvars;
9979 assert( eventhdlr !=
NULL );
9980 assert( eventdata !=
NULL );
9982 assert( event !=
NULL );
9985 assert( cons !=
NULL );
9987 assert( 0 <= consdata->nfixednonzeros && consdata->nfixednonzeros <= consdata->nvars );
9993 switch ( eventtype )
10000 assert( conshdlr !=
NULL );
10002 assert( conshdlrdata !=
NULL );
10005 assert( 0 <= conshdlrdata->nfixnonzerovars && conshdlrdata->nfixnonzerovars <=
SCIPgetNTotalVars(scip) );
10006 if ( conshdlrdata->nfixnonzerovars < conshdlrdata->maxnfixnonzerovars )
10008 assert( conshdlrdata->fixnonzerovars !=
NULL );
10010 conshdlrdata->fixnonzerovars[conshdlrdata->nfixnonzerovars++] =
SCIPeventGetVar(event);
10013 ++(consdata->nfixednonzeros);
10022 assert( conshdlr !=
NULL );
10024 assert( conshdlrdata !=
NULL );
10027 assert( 0 <= conshdlrdata->nfixnonzerovars && conshdlrdata->nfixnonzerovars <=
SCIPgetNTotalVars(scip) );
10028 if ( conshdlrdata->nfixnonzerovars < conshdlrdata->maxnfixnonzerovars )
10030 assert( conshdlrdata->fixnonzerovars !=
NULL );
10032 conshdlrdata->fixnonzerovars[conshdlrdata->nfixnonzerovars++] =
SCIPeventGetVar(event);
10035 ++(consdata->nfixednonzeros);
10042 --(consdata->nfixednonzeros);
10048 --(consdata->nfixednonzeros);
10055 assert( 0 <= consdata->nfixednonzeros && consdata->nfixednonzeros <= consdata->nvars );
10058 oldbound, newbound, consdata->nfixednonzeros);
10070 assert( scip !=
NULL );
10071 assert( conshdlr !=
NULL );
10073 assert( diveset !=
NULL );
10074 assert( success !=
NULL );
10075 assert( infeasible !=
NULL );
10077 *infeasible =
FALSE;
10086 assert( conshdlrdata !=
NULL );
10091 if ( conshdlrdata->switchsos1branch )
10116 conshdlrdata->branchsos =
TRUE;
10117 conshdlrdata->switchsos1branch =
FALSE;
10118 conshdlrdata->switchcutsfromsos1 =
FALSE;
10119 conshdlrdata->eventhdlr =
NULL;
10120 conshdlrdata->fixnonzerovars =
NULL;
10121 conshdlrdata->maxnfixnonzerovars = 0;
10122 conshdlrdata->nfixnonzerovars = 0;
10123 conshdlrdata->conflictgraph =
NULL;
10124 conshdlrdata->localconflicts =
NULL;
10125 conshdlrdata->isconflocal =
FALSE;
10126 conshdlrdata->implgraph =
NULL;
10127 conshdlrdata->nimplnodes = 0;
10128 conshdlrdata->nboundcuts = 0;
10129 conshdlrdata->tcliquegraph =
NULL;
10130 conshdlrdata->tcliquedata =
NULL;
10131 conshdlrdata->cntextsos1 = -1;
10132 conshdlrdata->varhash =
NULL;
10136 if ( conshdlrdata->eventhdlr ==
NULL )
10145 consEnfolpSOS1, consEnfopsSOS1, consCheckSOS1, consLockSOS1, conshdlrdata) );
10146 assert(conshdlr !=
NULL);
10171 "do not create an adjacency matrix if number of SOS1 variables is larger than predefined value (-1: no limit)",
10176 "maximal number of extensions that will be computed for each SOS1 constraint (-1: no limit)",
10180 "maximal number of bound tightening rounds per presolving round (-1: no limit)",
10184 "if TRUE then perform implication graph analysis (might add additional SOS1 constraints)",
10188 "number of recursive calls of implication graph analysis (-1: no limit)",
10193 "whether to use conflict graph propagation",
10197 "whether to use implication graph propagation",
10201 "whether to use SOS1 constraint propagation",
10206 "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)",
10210 "if TRUE then automatically switch to SOS1 branching if the SOS1 constraints do not overlap",
10214 "if neighborhood branching is used, then fix the branching variable (if positive in sign) to the value of the feasibility tolerance",
10218 "if TRUE then add complementarity constraints to the branching nodes (can be used in combination with neighborhood or bipartite branching)",
10222 "maximal number of complementarity constraints added per branching node (-1: no limit)",
10226 "minimal feasibility value for complementarity constraints in order to be added to the branching node",
10230 "minimal feasibility value for bound inequalities in order to be added to the branching node",
10234 "should added complementarity constraints be extended to SOS1 constraints to get tighter bound inequalities",
10238 "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",
10242 "Branch on SOS constraint with most number of nonzeros?",
10246 "Branch on SOS cons. with highest nonzero-variable weight for branching (needs branchnonzeros = false)?",
10250 "only add complementarity constraints to branching nodes for predefined depth (-1: no limit)",
10255 "maximal number of strong branching rounds to perform for each node (-1: auto); only available for neighborhood and bipartite branching",
10259 "maximal number LP iterations to perform for each strong branching round (-2: auto, -1: no limit)",
10264 "if TRUE separate bound inequalities from initial SOS1 constraints",
10268 "if TRUE separate bound inequalities from the conflict graph",
10272 "if TRUE then automatically switch to separating initial SOS1 constraints if the SOS1 constraints do not overlap",
10276 "frequency for separating bound cuts; zero means to separate only in the root node",
10280 "node depth of separating bound cuts (-1: no limit)",
10284 "maximal number of bound cuts separated per branching node",
10288 "maximal number of bound cuts separated per iteration in the root node",
10292 "if TRUE then bound cuts are strengthened in case bound variables are available",
10296 "frequency for separating implied bound cuts; zero means to separate only in the root node",
10300 "node depth of separating implied bound cuts (-1: no limit)",
10304 "maximal number of implied bound cuts separated per branching node",
10308 "maximal number of implied bound cuts separated per iteration in the root node",
10357 modifiable =
FALSE;
10361 if ( conshdlr ==
NULL )
10372 consdata->vars =
NULL;
10373 consdata->nvars = nvars;
10374 consdata->maxvars = nvars;
10375 consdata->rowub =
NULL;
10376 consdata->rowlb =
NULL;
10377 consdata->nfixednonzeros = transformed ? 0 : -1;
10378 consdata->weights =
NULL;
10379 consdata->local = local;
10386 if ( weights !=
NULL )
10397 assert( weights ==
NULL );
10401 for (v = 0; v < nvars; ++v)
10407 SCIP_CALL(
SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
10408 local, modifiable, dynamic, removable, stickingatnode) );
10412 for (v = nvars - 1; v >= 0; --v)
10421 assert( consdata->vars[v] !=
NULL );
10426 assert( conshdlrdata !=
NULL );
10452 SCIP_CALL(
SCIPcreateConsSOS1( scip, cons, name, nvars, vars, weights,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
FALSE,
FALSE,
FALSE,
FALSE) );
10469 assert( scip !=
NULL );
10470 assert( var !=
NULL );
10471 assert( cons !=
NULL );
10476 assert( conshdlr !=
NULL );
10484 assert( conshdlrdata !=
NULL );
10502 assert( scip !=
NULL );
10503 assert( var !=
NULL );
10504 assert( cons !=
NULL );
10509 assert( conshdlr !=
NULL );
10517 assert( conshdlrdata !=
NULL );
10533 assert( scip !=
NULL );
10534 assert( cons !=
NULL );
10544 assert( consdata !=
NULL );
10546 return consdata->nvars;
10558 assert( scip !=
NULL );
10559 assert( cons !=
NULL );
10569 assert( consdata !=
NULL );
10571 return consdata->vars;
10583 assert( scip !=
NULL );
10584 assert( cons !=
NULL );
10594 assert( consdata !=
NULL );
10596 return consdata->weights;
10619 assert( conshdlrdata !=
NULL );
10621 return conshdlrdata->conflictgraph;
10641 assert( conshdlrdata !=
NULL );
10643 return conshdlrdata->nsos1vars;
10655 assert( var !=
NULL );
10656 assert( conshdlr !=
NULL );
10665 assert( conshdlrdata !=
NULL );
10679 assert( conshdlr !=
NULL );
10680 assert( var !=
NULL );
10689 assert( conshdlrdata !=
NULL );
10691 if ( conshdlrdata->varhash ==
NULL )
10710 assert( conflictgraph !=
NULL );
10716 if ( nodedata ==
NULL )
10723 return nodedata->var;
10741 assert( scip !=
NULL );
10742 assert( conshdlr !=
NULL );
10743 assert( sol !=
NULL );
10744 assert( changed !=
NULL );
10745 assert( success !=
NULL );
10753 assert( conshdlrdata !=
NULL );
10757 allroundable =
FALSE;
10768 if ( conshdlrdata->switchsos1branch )
10777 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)