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 );
508 assert( var != NULL );
510 if ( conshdlrdata->varhash == NULL || !
SCIPhashmapExists(conshdlrdata->varhash, var) )
524 assert( conshdlrdata != NULL );
525 assert( var != 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;
718 assert( scip != NULL );
719 assert( cons != NULL );
720 assert( var != NULL );
737 assert( scip != 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)
1134 assert(
isConnectedSOS1(adjacencymatrix, NULL, vertex, workingset[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)
1196 if (
isConnectedSOS1(adjacencymatrix, NULL, selvertex, workingset[j]) )
1197 workingsetnew[nextsnew++] = workingset[j];
1199 nworkingsetnew = nextsnew;
1200 for (j = nexts + 1; j < nworkingset; ++j)
1202 if (
isConnectedSOS1(adjacencymatrix, NULL, selvertex, workingset[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] );
1313 if ( !
isConnectedSOS1(adjacencymatrix, NULL, 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 );
1422 for (j = 0; j < nvars; ++j)
1424 for (i = k; i < nsucc; ++i)
1426 if ( succ[i] > clique[j] )
1431 else if ( succ[i] == clique[j] )
1437 comsucc[(*ncomsucc)++] = succ[i];
1442 for (v = 1; v < nvars; ++v)
1444 int ncomsuccsave = 0;
1447 assert(vars[v] != NULL );
1457 for (j = 0; j < *ncomsucc; ++j)
1459 for (i = k; i < nsucc; ++i)
1461 if ( succ[i] > comsucc[j] )
1466 else if ( succ[i] == comsucc[j] )
1468 comsucc[ncomsuccsave++] = succ[i];
1474 *ncomsucc = ncomsuccsave;
1500 assert( scip != NULL );
1501 assert( implgraph != NULL );
1502 assert( implnodes != NULL );
1503 assert( node >= 0 );
1504 assert( vars[node] != NULL );
1516 for (s = 0; s < nsucc; ++s)
1521 data = succdatas[s];
1525 assert( succdatas[s] != NULL );
1528 assert( sos1node == succnode );
1529 implnodes[sos1node] =
TRUE;
1569 int lastFixedNonzero;
1572 assert( scip != NULL );
1573 assert( cons != NULL );
1574 assert( consdata != NULL );
1575 assert( eventhdlr != NULL );
1576 assert( cutoff != NULL );
1577 assert( success != NULL );
1578 assert( ndelconss != NULL );
1579 assert( nfixedvars != NULL );
1580 assert( nremovedvars != NULL );
1582 *substituted =
FALSE;
1590 lastFixedNonzero = -1;
1591 allvarsbinary =
TRUE;
1592 vars = consdata->vars;
1595 while ( j < consdata->nvars )
1624 *substituted =
TRUE;
1628 for (l = j+1; l < consdata->nvars; ++l)
1631 if ( vars[j] == vars[l] )
1654 lastFixedNonzero = j;
1668 allvarsbinary =
FALSE;
1675 if ( consdata->nvars < 2 )
1688 if ( nfixednonzeros > 1 )
1690 SCIPdebugMsg(scip,
"The problem is infeasible: more than one variable has bounds that keep it from being 0.\n");
1691 assert( lastFixedNonzero >= 0 );
1697 if ( nfixednonzeros == 1 )
1699 assert( lastFixedNonzero >= 0 );
1702 for (j = 0; j < consdata->nvars; ++j)
1704 if ( j != lastFixedNonzero )
1794 int** cliques = NULL;
1796 int* cliquesizes = NULL;
1797 int* newclique = NULL;
1798 int* indconss = NULL;
1799 int* lengthconss = NULL;
1800 int* comsucc = NULL;
1805 assert( scip != NULL );
1806 assert( eventhdlr != NULL );
1807 assert( conshdlrdata != NULL );
1808 assert( conflictgraph != NULL );
1809 assert( conss != NULL );
1810 assert( naddconss != NULL );
1811 assert( ndelconss != NULL );
1812 assert( nupgdconss != NULL );
1813 assert( nfixedvars != NULL );
1814 assert( nremovedvars != NULL );
1815 assert( result != NULL );
1818 csize =
MAX(1, conshdlrdata->maxextensions) * nconss;
1832 for (c = 0; c < nconss; ++c)
1837 assert( consdata != NULL );
1840 lengthconss[c] = consdata->nvars;
1845 for (iter = 0; iter < nconss; ++iter)
1852 int savennupgdconss;
1860 assert( conss != NULL );
1861 assert( conss[c] != NULL );
1865 assert( consdata != NULL );
1866 assert( consdata->nvars >= 0 );
1867 assert( consdata->nvars <= consdata->maxvars );
1869 assert( ncliques < csize );
1871 savendelconss = *ndelconss;
1872 savennupgdconss = *nupgdconss;
1875 SCIP_CALL(
presolRoundConsSOS1(scip, cons, consdata, eventhdlr, &substituted, &cutoff, &success, ndelconss, nupgdconss, nfixedvars, nremovedvars) );
1883 if ( *ndelconss > savendelconss || *nupgdconss > savennupgdconss || substituted )
1893 nvars = consdata->nvars;
1896 vars = consdata->vars;
1898 if ( nvars > 1 && conshdlrdata->maxextensions != 0 )
1907 for (j = 0; j < nvars; ++j)
1911 if ( varprobind >= 0 )
1912 newclique[cliquesize++] = varprobind;
1915 if ( cliquesize > 1 )
1917 cliquesizes[ncliques] = cliquesize;
1929 varprobind = newclique[0];
1934 for (j = 0; j < ncomsucc; ++j)
1937 assert( j == 0 || succ[j] > succ[j-1] );
1938 comsucc[j] = succ[j];
1942 for (v = 1; v < cliquesize && ncomsucc > 0; ++v)
1944 varprobind = newclique[v];
1949 assert( succ != NULL || nsucc == 0 );
1972 if ( conshdlrdata->maxextensions != 0 && adjacencymatrix != NULL )
1981 maxextensions = conshdlrdata->maxextensions;
1984 TRUE, (maxextensions <= 1) ?
FALSE :
TRUE, cliques, &ncliques, cliquesizes, newclique, comsucc, ncomsucc, 0, -1, &maxextensions,
1985 naddconss, &extended) );
2000 cliqueind = nsos1vars + ncliques;
2003 assert( cliquesize >= 0 && cliquesize <= nsos1vars );
2004 assert( ncliques < csize );
2006 for (j = 0; j < cliquesize; ++j)
2008 cliques[ncliques][j] = newclique[j];
2020 for (c = ncliques-1; c >= 0; --c)
2070 if ( conshdlrdata->depthimplanalysis >= 0 && *probingdepth >= conshdlrdata->depthimplanalysis )
2079 for (s = 0; s < nsucc; ++s)
2090 else if ( !
isConnectedSOS1(adjacencymatrix, NULL, givennode, succnode) )
2098 impllbs[succnode] = 0;
2099 implubs[succnode] = 0;
2110 if ( givennode > succnode )
2111 adjacencymatrix[givennode][succnode] = 1;
2113 adjacencymatrix[succnode][givennode] = 1;
2121 SCIP_CALL(
SCIPcreateConsSOS1(scip, &soscons, namesos, 0, NULL, NULL,
TRUE,
TRUE,
TRUE,
FALSE,
TRUE,
2145 for (s = 0; s < nsucc; ++s)
2148 int oldprobingdepth;
2151 data = succdatas[s];
2152 oldprobingdepth = *probingdepth;
2155 if (
SCIPisFeasLT(scip, impllbs[succnode], data->lbimpl) )
2157 impllbs[succnode] = data->lbimpl;
2164 implnodes[succnode] =
TRUE;
2165 SCIP_CALL(
performImplicationGraphAnalysis(scip, conshdlrdata, conflictgraph, totalvars, implgraph, implhash, adjacencymatrix, givennode, succnode, impllbs, implubs, implnodes, naddconss, probingdepth, infeasible) );
2166 *probingdepth = oldprobingdepth;
2175 if (
SCIPisFeasGT(scip, implubs[succnode], data->ubimpl) )
2177 implubs[succnode] = data->ubimpl;
2184 implnodes[succnode] =
TRUE;
2185 SCIP_CALL(
performImplicationGraphAnalysis(scip, conshdlrdata, conflictgraph, totalvars, implgraph, implhash, adjacencymatrix, givennode, succnode, impllbs, implubs, implnodes, naddconss, probingdepth, infeasible) );
2186 *probingdepth = oldprobingdepth;
2218 for (s = 0; s < nsucc; ++s)
2220 if ( implnodes[succ[s]] )
2254 assert( scip != NULL );
2255 assert( implgraph != NULL );
2256 assert( implhash != NULL );
2257 assert( totalvars != NULL );
2258 assert( varv != NULL );
2259 assert( varw != NULL );
2272 if ( infeasible1 || infeasible2 )
2278 if ( tightened1 || tightened2 )
2295 for (s = 0; s < nsucc; ++s)
2297 if ( succ[s] == indw )
2299 data = succdatas[s];
2300 assert( data != NULL );
2301 if ( lower &&
SCIPisFeasLT(scip, data->lbimpl, newbound) )
2304 data->lbimpl =
SCIPceil(scip, newbound);
2306 data->lbimpl = newbound;
2311 else if ( ! lower &&
SCIPisFeasGT(scip, data->ubimpl, newbound) )
2314 data->ubimpl =
SCIPfloor(scip, newbound);
2316 data->ubimpl = newbound;
2328 assert( data == NULL );
2332 data->lbimpl = newbound;
2339 data->ubimpl = newbound;
2366 int* cliquecoversizes,
2385 assert( update != NULL );
2389 *infeasible =
FALSE;
2397 for (w = 0; w < nvars; ++w)
2399 int newninftynonzero;
2406 newninftynonzero = ninftynonzero;
2409 if ( nodew < 0 || ( nodev != nodew && !
isConnectedSOS1(adjacencymatrix, NULL, nodev, nodew) && !
isImpliedZero(conflictgraph, implnodes, nodew) ) )
2420 implbound = boundnonzero -
bound;
2421 ind = varincover[w];
2422 assert( cliquecoversizes[ind] > 0 );
2425 for (j = 0; j < cliquecoversizes[ind]; ++j)
2427 indcliq = cliquecovers[ind][j];
2428 assert( 0 <= indcliq && indcliq < nvars );
2433 if ( nodecliq < 0 || (!
isConnectedSOS1(adjacencymatrix, NULL, nodev, nodecliq) && !
isImpliedZero(conflictgraph, implnodes, nodecliq) ) )
2438 implbound += bounds[w];
2443 else if ( implcoverw )
2448 implbound -= bounds[indcliq];
2461 if ( ! implinfty && newninftynonzero == 0 )
2475 newbound = implbound / coef;
2482 SCIP_CALL(
updateArcData(scip, implgraph, implhash, totalvars, var, vars[w], lb, ub, newbound,
TRUE, nchgbds, update, infeasible) );
2486 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,
FALSE, nchgbds, update, infeasible) );
2497 SCIP_CALL(
updateArcData(scip, implgraph, implhash, totalvars, var, vars[w], lb, ub, newbound,
TRUE, nchgbds, update, infeasible) );
2530 assert( conflictgraphlin != NULL );
2531 assert( linvars != NULL );
2532 assert( coveredvars != NULL );
2533 assert( clique != NULL );
2534 assert( cliquesize != NULL );
2536 assert( ! coveredvars[v] );
2546 int nextensions = 0;
2557 for (s = 0; s < nsucc; ++s)
2560 if ( ! coveredvars[succnode] )
2561 extensions[nextensions++] = succ[s];
2565 while ( nextensions > 0 )
2569 if ( considersolvals )
2577 for (s = 0; s < nextensions; ++s)
2582 bestbigMval = bigMval;
2583 bestindex = extensions[s];
2588 bestindex = extensions[0];
2590 assert( bestindex != -1 );
2593 clique[(*cliquesize)++] = bestindex;
2597 for (s = 0; s < nextensions; ++s)
2599 if ( s != bestindex &&
isConnectedSOS1(NULL, conflictgraphlin, bestindex, extensions[s]) )
2600 extensions[nextensionsnew++] = extensions[s];
2602 nextensions = nextensionsnew;
2610 for (s = 0; s < *cliquesize; ++s)
2616 assert( ! coveredvars[ind] );
2617 coveredvars[ind] =
TRUE;
2647 int* varindincons = NULL;
2650 int ntrafolinvars = 0;
2661 assert( scip != NULL );
2662 assert( conflictgraph != NULL );
2663 assert( adjacencymatrix != NULL );
2664 assert( nchgbds != NULL );
2665 assert( cutoff != NULL );
2668 *implupdate =
FALSE;
2672 if ( conshdlrlinear == NULL )
2688 for (c = 0; c < nlinearconss + nsos1vars && ! (*cutoff); ++c)
2691 int** cliquecovers = NULL;
2692 int* cliquecoversizes = NULL;
2695 int* varincover = NULL;
2702 if ( c < nlinearconss )
2719 if ( noriglinvars < 1 )
2721 assert( origlinvars != NULL );
2722 assert( origlinvals != NULL );
2727 ntrafolinvars = noriglinvars;
2732 if( requiredsize > ntrafolinvars )
2738 assert( requiredsize <= ntrafolinvars );
2740 trafolhs = origlhs - constant;
2741 traforhs = origrhs - constant;
2759 trafolinvars[1] = var;
2760 trafolinvals[1] = -1.0;
2761 trafolhs = -constant;
2762 traforhs = -constant;
2781 for (v = 0; v < nagrvars; ++v)
2783 trafolinvars[v] = agrvars[v];
2784 trafolinvals[v] = scalars[v];
2786 trafolinvars[nagrvars] = var;
2787 trafolinvals[nagrvars] = -1.0;
2788 trafolhs = -constant;
2789 traforhs = -constant;
2790 ntrafolinvars = nagrvars + 1;
2804 trafolinvars[0] = negvar;
2805 trafolinvars[1] = var;
2806 trafolinvals[0] = 1.0;
2807 trafolinvals[1] = 1.0;
2816 if ( ntrafolinvars == 0 )
2824 for (v = 0; v < ntrafolinvars; ++v)
2829 if ( trafolinvals[v] < 0.0 )
2843 trafolbs[v] = lb * trafolinvals[v];
2848 trafoubs[v] = ub * trafolinvals[v];
2852 for (v = 0; v < nsos1vars; ++v)
2853 varindincons[v] = -1;
2856 for (v = 0; v < ntrafolinvars; ++v)
2863 varindincons[node] = v;
2871 for (i = 0; i < ntrafolinvars; ++i)
2872 coveredvars[i] =
FALSE;
2881 for (v = 0; v < ntrafolinvars; ++v)
2884 if ( ! coveredvars[v] )
2887 SCIP_CALL(
computeVarsCoverSOS1(scip, conflictgraph, conflictgraphlin, trafolinvars, coveredvars, cliquecovers[ncliquecovers], &(cliquecoversizes[ncliquecovers]), v,
FALSE) );
2897 for (v = 0; v < ntrafolinvars; ++v)
2914 for (s = 0; s < nsucc; ++s)
2919 if ( varindincons[succnode] == -1 )
2922 varindincons[succnode] = -2;
2934 for (i = 0; i < ncliquecovers; ++i)
2936 for (j = 0; j < cliquecoversizes[i]; ++j)
2938 int ind = cliquecovers[i][j];
2940 varincover[ind] = i;
2941 cliquecovervals[j] = trafoubs[ind];
2947 for (v = 0; v < ntrafolinvars + nsos1linvars; ++v)
2961 int ninftynonzero = 0;
2965 if ( v < ntrafolinvars )
2967 var = trafolinvars[v];
2968 trafoubv = trafoubs[v];
2972 assert( v >= ntrafolinvars );
2973 var = sos1linvars[v-ntrafolinvars];
2983 newboundnonzero = trafolhs;
2984 newboundnores = trafolhs;
2986 assert( nodev < nsos1vars );
2989 for (w = 0; w < nsos1vars; ++w)
2990 implnodes[w] =
FALSE;
2994 for (i = 0; i < ncliquecovers; ++i)
2999 assert( cliquecoversizes[i] > 0 );
3001 indcliq = cliquecovers[i][0];
3002 assert( 0 <= indcliq && indcliq < ntrafolinvars );
3010 newboundnores -= trafoubs[indcliq];
3012 else if ( cliquecoversizes[i] > 1 )
3014 assert( 0 <= cliquecovers[i][1] && cliquecovers[i][1] < ntrafolinvars );
3018 newboundnores -= trafoubs[cliquecovers[i][1]];
3022 for (j = 0; j < cliquecoversizes[i]; ++j)
3024 indcliq = cliquecovers[i][j];
3025 assert( 0 <= indcliq && indcliq < ntrafolinvars );
3028 assert( nodecliq < nsos1vars );
3033 if ( nodev < 0 || nodecliq < 0 || (!
isConnectedSOS1(adjacencymatrix, NULL, nodev, nodecliq) && !
isImpliedZero(conflictgraph, implnodes, nodecliq) ) )
3038 newboundnonzero -= trafoubs[indcliq];
3045 assert( ninftynonzero == 0 || inftynores );
3048 if ( ninftynonzero == 0 && v < ntrafolinvars )
3050 linval = trafolinvals[v];
3057 newbound = newboundnonzero;
3059 newbound = MIN(0, newboundnonzero);
3072 newbound =
SCIPceil(scip, newbound);
3075 assert( ! infeasible );
3096 assert( ! infeasible );
3107 SCIP_CALL(
updateImplicationGraphSOS1(scip, conshdlrdata, conflictgraph, adjacencymatrix, implgraph, implhash, implnodes, totalvars, cliquecovers, cliquecoversizes, varincover,
3108 trafolinvars, trafolinvals, ntrafolinvars, trafoubs, var, trafoubv, newboundnonzero, ninftynonzero,
TRUE, nchgbds, &update, &infeasible) );
3115 if ( *cutoff ==
TRUE )
3119 for (j = ncliquecovers-1; j >= 0; --j)
3133 for (i = 0; i < ncliquecovers; ++i)
3135 for (j = 0; j < cliquecoversizes[i]; ++j)
3137 int ind = cliquecovers[i][j];
3139 varincover[ind] = i;
3140 cliquecovervals[j] = trafolbs[ind];
3142 SCIPsortRealInt(cliquecovervals, cliquecovers[i], cliquecoversizes[i]);
3147 for (v = 0; v < ntrafolinvars + nsos1linvars; ++v)
3161 int ninftynonzero = 0;
3165 if ( v < ntrafolinvars )
3167 var = trafolinvars[v];
3168 trafolbv = trafolbs[v];
3172 assert( v-ntrafolinvars >= 0 );
3173 var = sos1linvars[v-ntrafolinvars];
3181 newboundnonzero = traforhs;
3182 newboundnores = traforhs;
3184 assert( nodev < nsos1vars );
3187 for (w = 0; w < nsos1vars; ++w)
3188 implnodes[w] =
FALSE;
3192 for (i = 0; i < ncliquecovers; ++i)
3197 assert( cliquecoversizes[i] > 0 );
3199 indcliq = cliquecovers[i][0];
3200 assert( 0 <= indcliq && indcliq < ntrafolinvars );
3209 newboundnores -= trafolbs[indcliq];
3211 else if ( cliquecoversizes[i] > 1 )
3213 assert( 0 <= cliquecovers[i][1] && cliquecovers[i][1] < ntrafolinvars );
3217 newboundnores -= trafolbs[cliquecovers[i][1]];
3221 for (j = 0; j < cliquecoversizes[i]; ++j)
3223 indcliq = cliquecovers[i][j];
3224 assert( 0 <= indcliq && indcliq < ntrafolinvars );
3227 assert( nodecliq < nsos1vars );
3232 if ( nodev < 0 || nodecliq < 0 || (!
isConnectedSOS1(adjacencymatrix, NULL, nodev, nodecliq) && !
isImpliedZero(conflictgraph, implnodes, nodecliq) ) )
3238 newboundnonzero -= trafolbs[indcliq];
3245 assert( ninftynonzero == 0 || inftynores );
3249 if ( ninftynonzero == 0 && v < ntrafolinvars )
3251 linval = trafolinvals[v];
3258 newbound = newboundnonzero;
3260 newbound =
MAX(0, newboundnonzero);
3277 assert( ! infeasible );
3295 newbound =
SCIPceil(scip, newbound);
3298 assert( ! infeasible );
3309 SCIP_CALL(
updateImplicationGraphSOS1(scip, conshdlrdata, conflictgraph, adjacencymatrix, implgraph, implhash, implnodes, totalvars, cliquecovers, cliquecoversizes, varincover,
3310 trafolinvars, trafolinvals, ntrafolinvars, trafolbs, var, trafolbv, newboundnonzero, ninftynonzero,
FALSE, nchgbds, &update, &infeasible) );
3319 for (j = ncliquecovers-1; j >= 0; --j)
3327 if ( *cutoff ==
TRUE )
3381 for (i = 0; i < nsos1vars; ++i)
3390 totalvars[ntotalvars++] = var;
3393 for (i = 0; i < nprobvars; ++i)
3403 totalvars[ntotalvars++] = var;
3411 updateconfl =
FALSE;
3412 for (j = 0; (j < conshdlrdata->maxtightenbds || conshdlrdata->maxtightenbds == -1 ) && ! cutoff; ++j)
3417 nchgbdssave = *nchgbds;
3419 assert( ntotalvars > 0 );
3420 SCIP_CALL(
tightenVarsBoundsSOS1(scip, conshdlrdata, conflictgraph, implgraph, implhash, adjacencymatrix, totalvars, ntotalvars, nsos1vars, nchgbds, &implupdate, &cutoff) );
3421 if ( *nchgbds > nchgbdssave )
3427 else if ( implupdate )
3434 if ( updateconfl && conshdlrdata->perfimplanalysis && ! cutoff )
3449 naddconsssave = *naddconss;
3450 for (i = 0; i < nsos1vars; ++i)
3455 for (j = 0; j < nsos1vars; ++j)
3456 implnodes[j] =
FALSE;
3457 for (j = 0; j < ntotalvars; ++j)
3464 SCIP_CALL(
performImplicationGraphAnalysis(scip, conshdlrdata, conflictgraph, totalvars, implgraph, implhash, adjacencymatrix, i, i, impllbs, implubs, implnodes, naddconss, &probingdepth, &infeasible) );
3473 SCIPdebugMsg(scip,
"fixed variable %s with lower bound %f and upper bound %f to zero\n",
3483 if ( *naddconss > naddconsssave )
3500 for (j = ntotalvars-1; j >= 0; --j)
3509 for (s = nsucc-1; s >= 0; --s)
3532 assert( scip != NULL );
3533 assert( cons != NULL );
3534 assert( consdata != NULL );
3535 assert( cutoff != NULL );
3536 assert( ngen != NULL );
3541 if ( consdata->nfixednonzeros > 1 )
3543 SCIPdebugMsg(scip,
"the node is infeasible, more than 1 variable is fixed to be nonzero.\n");
3550 if ( consdata->nfixednonzeros == 1 )
3557 int firstFixedNonzero;
3561 firstFixedNonzero = -1;
3562 nvars = consdata->nvars;
3563 vars = consdata->vars;
3564 assert( vars != NULL );
3567 for (j = 0; j < nvars; ++j)
3571 firstFixedNonzero = j;
3575 assert( firstFixedNonzero >= 0 );
3577 SCIPdebugMsg(scip,
"variable <%s> is fixed nonzero, fixing other variables to 0.\n",
SCIPvarGetName(vars[firstFixedNonzero]));
3581 for (j = 0; j < firstFixedNonzero; ++j)
3585 assert( ! infeasible );
3586 allVarFixed = allVarFixed && success;
3592 for (j = firstFixedNonzero+1; j < nvars; ++j)
3596 assert( ! infeasible );
3597 allVarFixed = allVarFixed && success;
3638 assert( scip != NULL );
3639 assert( conflictgraph != NULL );
3640 assert( cutoff != NULL );
3641 assert( ngen != NULL );
3642 assert( node >= 0 );
3645 inferinfo = -node - 1;
3653 for (s = 0; s < nsucc; ++s)
3686 if ( implprop && implgraph != NULL )
3691 SCIP_NODEDATA* nodedbgdata;
3699 if ( succdatas != NULL )
3703 for (s = 0; s < nsucc; ++s)
3710 assert( nodedata != NULL );
3711 succdata = succdatas[s];
3712 assert( succdata != NULL );
3713 var = nodedata->var;
3714 assert( var != NULL );
3787 assert( scip != NULL );
3788 assert( conshdlrdata != NULL );
3789 assert( conflictgraph != NULL );
3790 assert( conshdlrdata->implgraph == NULL );
3791 assert( conshdlrdata->nimplnodes == 0 );
3792 assert( cutoff != NULL );
3793 assert( nchgbds != NULL );
3799 if ( conshdlrdata->maxsosadjacency != -1 && nsos1vars > conshdlrdata->maxsosadjacency )
3802 SCIPdebugMsg(scip,
"Implication graph was not created since number of SOS1 variables (%d) is larger than %d.\n", nsos1vars, conshdlrdata->maxsosadjacency);
3825 for (i = 0; i < nsos1vars; ++i)
3834 implvars[nimplnodes++] = var;
3837 for (i = 0; i < nprobvars; ++i)
3847 implvars[nimplnodes++] = var;
3850 conshdlrdata->nimplnodes = nimplnodes;
3853 for (i = 0; i < nimplnodes; ++i)
3859 nodedata->var = implvars[i];
3869 for (i = 0; i < nsos1vars; ++i)
3873 for (i = 0; i < nsos1vars; ++i)
3875 for (j = 0; j < i+1; ++j)
3876 adjacencymatrix[i][j] = 0;
3879 for (i = 0; i < nsos1vars; ++i)
3886 for (j = 0; j < nsucc; ++j)
3889 adjacencymatrix[i][succ[j]] = 1;
3896 for (j = 0; (j < maxrounds || maxrounds == -1 ); ++j)
3901 nchgbdssave = *nchgbds;
3903 assert( nimplnodes > 0 );
3904 SCIP_CALL(
tightenVarsBoundsSOS1(scip, conshdlrdata, conflictgraph, conshdlrdata->implgraph, implhash, adjacencymatrix, implvars, nimplnodes, nsos1vars, nchgbds, &implupdate, cutoff) );
3905 if ( *cutoff || ( ! implupdate && ! ( *nchgbds > nchgbdssave ) ) )
3910 for (i = nsos1vars-1; i >= 0; --i)
3923 else if ( *nchgbds > 0 )
3925 SCIPdebugMsg(scip,
"found %d bound changes\n", *nchgbds);
3929 assert( conshdlrdata->implgraph != NULL );
3944 assert( scip != NULL );
3945 assert( conshdlrdata != NULL );
3948 if ( conshdlrdata->implgraph == NULL )
3950 assert( conshdlrdata->nimplnodes == 0 );
3955 for (j = conshdlrdata->nimplnodes-1; j >= 0; --j)
3964 for (s = nsucc-1; s >= 0; --s)
3966 assert( succdatas[s] != NULL );
3972 for (j = conshdlrdata->nimplnodes-1; j >= 0; --j)
3976 assert( nodedata != NULL );
3983 conshdlrdata->nimplnodes = 0;
4010 assert( conflictgraph != NULL );
4011 assert( verticesarefixed != NULL );
4012 assert( coververtices != NULL );
4013 assert( ncoververtices != NULL );
4015 *ncoververtices = 0;
4018 if ( neightocover == NULL )
4020 assert( nneightocover == 0 );
4026 nsucc1 = nneightocover;
4027 succ1 = neightocover;
4031 for (s = 0; s < nsucc1; ++s)
4033 int succvertex1 = succ1[s];
4035 if ( ! verticesarefixed[succvertex1] )
4046 if ( *ncoververtices == 0 )
4048 for (j = 0; j < nsucc2; ++j)
4050 succvertex2 = succ2[j];
4051 if ( ! verticesarefixed[succvertex2] )
4052 coververtices[(*ncoververtices)++] = succvertex2;
4062 for (v = 0; v < *ncoververtices; ++v)
4065 for (j = k; j < nsucc2; ++j)
4067 succvertex2 = succ2[j];
4068 if ( succvertex2 > coververtices[v] )
4074 else if ( succvertex2 == coververtices[v] )
4077 coververtices[vv++] = succvertex2;
4084 *ncoververtices = vv;
4091 for (s = 0; s < *ncoververtices; ++s)
4093 assert( *ncoververtices <= 1 || coververtices[*ncoververtices - 1] > coververtices[*ncoververtices - 2] );
4121 assert( scip != NULL );
4122 assert( conflictgraph != NULL );
4123 assert( verticesarefixed != NULL );
4124 assert( ! verticesarefixed[branchvertex] );
4125 assert( fixingsnode1 != NULL );
4126 assert( fixingsnode2 != NULL );
4127 assert( nfixingsnode1 != NULL );
4128 assert( nfixingsnode2 != NULL );
4145 for (j = 0; j < nsucc; ++j)
4149 assert( ! verticesarefixed[succ[j]] );
4150 fixingsnode1[(*nfixingsnode1)++] = succ[j];
4155 if ( *nfixingsnode1 > 0 )
4158 SCIP_CALL(
getCoverVertices(conflictgraph, verticesarefixed, branchvertex, fixingsnode1, *nfixingsnode1, fixingsnode2, nfixingsnode2) );
4161 SCIP_CALL(
getCoverVertices(conflictgraph, verticesarefixed, branchvertex, fixingsnode2, *nfixingsnode2, fixingsnode1, nfixingsnode1) );
4163 for (j = 0; j < *nfixingsnode2; ++j)
4174 for (j = 0; j < *nfixingsnode1; ++j)
4182 takeallsucc =
FALSE;
4191 for (j = 0; j < nsucc; ++j)
4193 if ( ! verticesarefixed[succ[j]] )
4194 fixingsnode1[(*nfixingsnode1)++] = succ[j];
4200 SCIP_CALL(
getCoverVertices(conflictgraph, verticesarefixed, branchvertex, fixingsnode1, *nfixingsnode1, fixingsnode2, nfixingsnode2) );
4205 fixingsnode2[0] = branchvertex;
4227 int* vertexbestprior,
4234 assert( scip != NULL );
4235 assert( conshdlrdata != NULL );
4236 assert( conflictgraph != NULL );
4237 assert( verticesarefixed != NULL );
4238 assert( fixingsnode1 != NULL );
4239 assert( fixingsnode2 != NULL );
4240 assert( relsolfeas != NULL );
4244 for (i = 0; i < nsos1vars; ++i)
4265 assert( ! verticesarefixed[i] );
4269 for (j = 0; j < nfixingsnode1; ++j)
4280 for (j = 0; j < nfixingsnode2; ++j)
4290 if ( iszero1 || iszero2 )
4293 prior = sum1 * sum2;
4296 if ( branchpriors != NULL )
4297 branchpriors[i] = prior;
4298 if ( bestprior < prior )
4302 if ( vertexbestprior != NULL )
4303 *vertexbestprior = i;
4310 *relsolfeas =
FALSE;
4329 int* ndomainfixings,
4338 assert( scip != NULL );
4339 assert( conflictgraph != NULL );
4340 assert( fixingsexec != NULL );
4341 assert( nfixingsop > 0 );
4342 assert( fixingsop != NULL );
4343 assert( nfixingsop > 0 );
4344 assert( inititer >= -1 );
4345 assert( domainfixings != NULL );
4346 assert( ndomainfixings != NULL );
4347 assert( *ndomainfixings >= 0 );
4348 assert( infeasible != NULL );
4349 assert( objval != NULL );
4350 assert( lperror != NULL );
4354 *infeasible =
FALSE;
4360 if ( fixnonzero && nfixingsop == 1 )
4400 for (i = 0; i < nfixingsexec && ! *infeasible; ++i)
4414 if ( ! *infeasible )
4440 for (i = 0; i < nfixingsop; ++i)
4441 domainfixings[(*ndomainfixings)++] = fixingsop[i];
4472 int* vertexbestprior,
4479 int* indsos1vars = NULL;
4480 int* domainfixings = NULL;
4487 int lastscorechange;
4496 assert( scip != NULL );
4497 assert( conshdlrdata != NULL );
4498 assert( conflictgraph != NULL );
4499 assert( verticesarefixed != NULL );
4500 assert( fixingsnode1 != NULL );
4501 assert( fixingsnode2 != NULL );
4502 assert( vertexbestprior != NULL );
4503 assert( result != NULL );
4510 bipbranch, fixingsnode1, fixingsnode2, branchpriors, NULL, &relsolfeas) );
4515 SCIPdebugMsg(scip,
"all the SOS1 constraints are feasible.\n");
4529 for (j = 0; j < nsos1vars; ++j)
4542 nlpiterations = 1000;
4549 if ( conshdlrdata->nstrongiter == -2 )
4551 inititer = (int)(2*nlpiterations / nlps);
4553 inititer =
MAX(inititer, 10);
4554 inititer = MIN(inititer, 500);
4557 inititer = conshdlrdata->nstrongiter;
4564 lastscorechange = -1;
4565 *vertexbestprior = indsos1vars[0];
4569 maxfailures = nstrongrounds;
4572 for (j = 0; j < nstrongrounds; ++j)
4577 testvertex = indsos1vars[j];
4590 assert( ! verticesarefixed[testvertex] );
4591 SCIP_CALL(
getBranchingVerticesSOS1(scip, conflictgraph, sol, verticesarefixed, bipbranch, testvertex, fixingsnode1, &nfixingsnode1, fixingsnode2, &nfixingsnode2) );
4595 inititer, conshdlrdata->fixnonzero, domainfixings, &ndomainfixings, &infeasible1, &objval1, &lperror) );
4601 inititer,
FALSE, domainfixings, &ndomainfixings, &infeasible2, &objval2, &lperror) );
4606 if ( infeasible1 && infeasible2 )
4620 else if ( ! infeasible1 && ! infeasible2 )
4623 if ( ndomainfixings == 0 )
4630 *vertexbestprior = testvertex;
4631 *bestobjval1 = objval1;
4632 *bestobjval2 = objval2;
4634 lastscorechange = j;
4636 else if ( j - lastscorechange > maxfailures )
4644 if ( ndomainfixings > 0 )
4649 for (i = 0; i < ndomainfixings; ++i)
4652 assert( ! infeasible );
4655 SCIPdebugMsg(scip,
"found %d domain fixings.\n", ndomainfixings);
4694 int* extensions = NULL;
4695 int nextensions = 0;
4699 assert( scip != NULL );
4700 assert( conflictgraph != NULL );
4701 assert( cons != NULL );
4702 assert( feas != NULL );
4708 var = nodedata->var;
4709 assert( boundvar == NULL ||
SCIPvarCompare(boundvar, nodedata->ubboundvar) == 0 );
4713 if ( boundvar == NULL )
4733 else if ( boundvar == nodedata->ubboundvar )
4739 ub = nodedata->ubboundcoef;
4748 lb = nodedata->lbboundcoef;
4757 *feas += coef * solval;
4767 assert( nsucc > 0 );
4773 for (s = 0; s < nsucc; ++s)
4774 extensions[s] = succ[s];
4775 nextensions = nsucc;
4781 while ( nextensions > 0 )
4798 assert( extensions != NULL );
4799 for (s = 0; s < nextensions; ++s)
4801 ext = extensions[s];
4805 bestbigMval = bigMval;
4810 assert( bestindex != -1 );
4814 var = nodedata->var;
4817 if ( boundvar == NULL )
4837 else if ( boundvar == nodedata->ubboundvar )
4843 ub = nodedata->ubboundcoef;
4852 lb = nodedata->lbboundcoef;
4860 *feas += coef * solval;
4866 assert( extensions != NULL );
4869 for (s = 0; s < nextensions; ++s)
4871 if ( s != bestindex &&
isConnectedSOS1(NULL, conflictgraph, bestindex, extensions[s]) )
4872 extensions[nextensionsnew++] = extensions[s];
4874 nextensions = nextensionsnew;
4885 if ( boundvar == NULL )
4919 assert( scip != NULL );
4920 assert( node != NULL );
4921 assert( conshdlrdata != NULL );
4922 assert( conflictgraph != NULL );
4923 assert( verticesarefixed != NULL );
4924 assert( fixingsnode1 != NULL );
4925 assert( fixingsnode2 != NULL );
4926 assert( naddedconss != NULL );
4930 if ( nfixingsnode2 > 1 )
4956 for (i = 0; i < nsos1vars; ++i)
4957 mark[i] = (verticesarefixed[i]);
4960 for (i = 0; i < nfixingsnode1; ++i)
4962 assert( nfixingsnode1 <= 1 || (fixingsnode1[nfixingsnode1 - 1] > fixingsnode1[nfixingsnode1 - 2]) );
4963 mark[fixingsnode1[i]] =
TRUE;
4967 for (i = 0; i < nfixingsnode2; ++i)
4969 assert( nfixingsnode2 <= 1 || (fixingsnode2[nfixingsnode2 - 1] > fixingsnode2[nfixingsnode2 - 2]) );
4970 mark[fixingsnode2[i]] =
TRUE;
4975 for (i = 0; i < nfixingsnode2; ++i)
4980 for (s = 0; s < nsucc; ++s)
4982 int succnode = succ[s];
4984 if ( ! mark[succnode] )
4986 mark[succnode] =
TRUE;
4987 succarray[nsuccarray++] = succnode;
4996 for (i = 0; i < nsos1vars; ++i)
5000 for (i = 0; i < nfixingsnode2; ++i)
5001 mark[fixingsnode2[i]] =
TRUE;
5004 for (i = 0; i < nsuccarray; ++i)
5011 vertex1 = succarray[i];
5023 for (s = 0; s < nsucc; ++s)
5025 if ( mark[succ[s]] )
5027 fixingsnode21[nfixingsnode21++] = succ[s];
5028 assert( nfixingsnode21 == 1 || (fixingsnode21[nfixingsnode21 - 1] > fixingsnode21[nfixingsnode21 - 2]) );
5033 if ( nfixingsnode21 == nfixingsnode2 )
5038 assert( ! infeasible );
5044 assert ( nfixingsnode22 + nfixingsnode21 == nfixingsnode2 );
5047 SCIP_CALL(
getCoverVertices(conflictgraph, verticesarefixed, -1, fixingsnode22, nfixingsnode22, coverarray, &ncoverarray) );
5051 for (j = 0; j < ncoverarray; ++j)
5055 vertex2 = coverarray[j];
5056 assert( vertex2 != vertex1 );
5059 if ( vertex2 < vertex1 )
5087 assert( nodedata != NULL );
5088 boundvar1 = nodedata->ubboundvar;
5089 lbboundcoef1 = nodedata->lbboundcoef;
5090 ubboundcoef1 = nodedata->ubboundcoef;
5092 assert( nodedata != NULL );
5093 boundvar2 = nodedata->ubboundvar;
5094 lbboundcoef2 = nodedata->lbboundcoef;
5095 ubboundcoef2 = nodedata->ubboundcoef;
5097 if ( boundvar1 != NULL && boundvar2 != NULL &&
SCIPvarCompare(boundvar1, boundvar2) == 0 )
5101 if ( conshdlrdata->addextendedbds )
5103 if ( localconflicts == NULL )
5106 localconflicts = conshdlrdata->localconflicts;
5120 conshdlrdata->isconflocal =
TRUE;
5160 feas += solval1/ubboundcoef1;
5166 feas += solval1/lbboundcoef1;
5173 feas += solval2/ubboundcoef2;
5179 feas += solval2/lbboundcoef2;
5184 if (
SCIPisGT(scip, feas, conshdlrdata->addcompsfeas) )
5188 SCIP_CALL(
SCIPcreateConsSOS1(scip, &conssos1, name, 0, NULL, NULL,
TRUE,
TRUE,
TRUE,
FALSE,
TRUE,
5213 SCIP_CALL(
SCIPcreateConsLinear(scip, &conssos1, name, 0, NULL, NULL, -
SCIPinfinity(scip), 0.0,
TRUE,
FALSE,
TRUE,
FALSE,
FALSE,
5222 SCIP_CALL(
SCIPcreateConsLinear(scip, &conssos1, name, 0, NULL, NULL, -
SCIPinfinity(scip), 1.0,
TRUE,
FALSE,
TRUE,
FALSE,
FALSE,
5230 if (
SCIPisGT(scip, feas, conshdlrdata->addbdsfeas ) )
5241 if ( conshdlrdata->maxaddcomps >= 0 && *naddedconss > conshdlrdata->maxaddcomps )
5249 if ( conshdlrdata->maxaddcomps >= 0 && *naddedconss > conshdlrdata->maxaddcomps )
5275 for (j = 0; j < nsos1vars; ++j)
5337 int* fixingsnode1 = NULL;
5338 int* fixingsnode2 = NULL;
5360 assert( scip != NULL );
5361 assert( conshdlrdata != NULL );
5362 assert( conshdlr != NULL );
5363 assert( conss != NULL );
5364 assert( result != NULL );
5370 nsos1vars = conshdlrdata->nsos1vars;
5373 conflictgraph = conshdlrdata->conflictgraph;
5374 assert( ! conshdlrdata->isconflocal );
5377 for (c = 0; c < nconss; ++c)
5384 assert( cons != NULL );
5386 assert( consdata != NULL );
5389 if ( consdata->nvars < 2 )
5406 assert( ngen == 0 );
5409 if ( consdata->local )
5416 if ( conshdlrdata->localconflicts == NULL )
5421 vars = consdata->vars;
5422 nvars = consdata->nvars;
5423 for (i = 0; i < nvars-1; ++i)
5435 for (j = i+1; j < nvars; ++j)
5453 conshdlrdata->isconflocal =
TRUE;
5463 if ( conshdlrdata->isconflocal )
5465 for (j = 0; j < nsos1vars; ++j)
5481 if ( conshdlrdata->isconflocal )
5484 conshdlrdata->isconflocal =
FALSE;
5492 for (j = 0; j < nsos1vars; ++j)
5502 verticesarefixed[j] =
TRUE;
5504 verticesarefixed[j] =
FALSE;
5508 if ( conshdlrdata->branchingrule ==
'b' )
5512 if ( conshdlrdata->nstrongrounds >= 0 )
5513 nstrongrounds = MIN(conshdlrdata->nstrongrounds, nsos1vars);
5523 nstrongrounds = MIN(nsos1vars, nstrongrounds);
5536 if ( nstrongrounds == 0 )
5541 SCIP_CALL(
getBranchingPrioritiesSOS1(scip, conshdlrdata, conflictgraph, sol, nsos1vars, verticesarefixed, bipbranch, fixingsnode1, fixingsnode2, NULL, &branchvertex, &relsolfeas) );
5546 SCIPdebugMsg(scip,
"all the SOS1 constraints are feasible.\n");
5552 if ( conshdlrdata->isconflocal )
5555 conshdlrdata->isconflocal =
FALSE;
5570 fixingsnode1, fixingsnode2, &branchvertex, &bestobjval1, &bestobjval2, result) );
5575 if ( conshdlrdata->isconflocal )
5578 conshdlrdata->isconflocal =
FALSE;
5591 if ( ! conshdlrdata->branchsos )
5594 if ( conshdlrdata->isconflocal )
5597 conshdlrdata->isconflocal =
FALSE;
5607 SCIPerrorMessage(
"Incompatible parameter setting: branchsos can only be set to false if all SOS1 variables are binary.\n");
5615 assert( branchvertex >= 0 && branchvertex < nsos1vars );
5616 assert( ! verticesarefixed[branchvertex] );
5617 SCIP_CALL(
getBranchingVerticesSOS1(scip, conflictgraph, sol, verticesarefixed, bipbranch, branchvertex, fixingsnode1, &nfixingsnode1, fixingsnode2, &nfixingsnode2) );
5622 for (j = 0; j < nfixingsnode1; ++j)
5631 objest = objest/((
SCIP_Real) nfixingsnode1);
5637 if ( conshdlrdata->fixnonzero && nfixingsnode2 == 1 )
5676 for (j = 0; j < nfixingsnode1; ++j)
5680 assert( ! infeasible );
5686 for (j = 0; j < nfixingsnode2; ++j)
5696 objest = objest/((
SCIP_Real) nfixingsnode2);
5702 for (j = 0; j < nfixingsnode2; ++j)
5705 assert( ! infeasible );
5710 if ( conshdlrdata->addcomps && ( conshdlrdata->addcompsdepth == -1 || conshdlrdata->addcompsdepth >=
SCIPgetDepth(scip) ) )
5714 assert( ! conshdlrdata->fixnonzero );
5718 nsos1vars, verticesarefixed, fixingsnode1, nfixingsnode1, fixingsnode2, nfixingsnode2, &naddedconss,
TRUE) );
5720 if ( naddedconss == 0 )
5724 nsos1vars, verticesarefixed, fixingsnode2, nfixingsnode2, fixingsnode1, nfixingsnode1, &naddedconss,
TRUE) );
5729 if ( nstrongrounds > 0 )
5736 if ( conshdlrdata->isconflocal )
5739 conshdlrdata->isconflocal =
FALSE;
5804 assert( scip != NULL );
5805 assert( conshdlr != NULL );
5806 assert( conss != NULL );
5807 assert( result != NULL );
5817 assert( conshdlrdata != NULL );
5820 for (c = 0; c < nconss; ++c)
5830 assert( cons != NULL );
5832 assert( consdata != NULL );
5836 nvars = consdata->nvars;
5837 vars = consdata->vars;
5856 assert( ngen == 0 );
5860 for (j = 0; j < nvars; ++j)
5866 if ( conshdlrdata->branchnonzeros )
5870 if ( conshdlrdata->branchweight )
5873 if ( consdata->weights[j] > weight )
5874 weight = consdata->weights[j];
5883 if ( cnt > 1 && weight > maxWeight )
5891 if ( branchCons == NULL )
5893 SCIPdebugMsg(scip,
"All SOS1 constraints are feasible.\n");
5898 if ( ! conshdlrdata->branchsos )
5903 for (j = 0; j < consdata->nvars; ++j)
5909 if ( j == consdata->nvars )
5916 SCIPerrorMessage(
"Incompatible parameter setting: branchsos can only be set to false if all SOS1 variables are binary.\n");
5924 assert( consdata != NULL );
5925 nvars = consdata->nvars;
5926 vars = consdata->vars;
5940 assert( ! infeasible );
5944 assert( ! infeasible );
5964 for (j = 0; j < nvars; ++j)
5976 w = weight1/weight2;
5979 assert( 0 <= ind && ind < nvars-1 );
5987 for (j = 0; j <= ind; ++j)
5997 for (j = 0; j <= ind; ++j)
6000 assert( ! infeasible );
6006 for (j = ind+1; j < nvars; ++j)
6012 objest = objest/((
SCIP_Real) (nvars - ind - 1));
6016 for (j = ind+1; j < nvars; ++j)
6019 assert( ! infeasible );
6042 assert( scip != NULL );
6043 assert( conshdlr != NULL );
6044 assert( conss != NULL );
6045 assert( result != NULL );
6049 assert( conshdlrdata != NULL );
6051 if ( conshdlrdata->addcomps && conshdlrdata->fixnonzero )
6053 SCIPerrorMessage(
"Incompatible parameter setting: addcomps = TRUE and fixnonzero = TRUE.\n");
6057 if ( conshdlrdata->fixnonzero && ( conshdlrdata->branchingrule ==
'b' || conshdlrdata->branchingrule ==
's' ) )
6059 SCIPerrorMessage(
"Incompatible parameter setting: nonzero fixing is not compatible with bipartite or sos1 branching.\n");
6063 if ( conshdlrdata->branchingrule ==
's' && conshdlrdata->nstrongrounds != 0 )
6065 SCIPerrorMessage(
"Strong branching is not available for SOS1 branching.\n");
6069 if ( conshdlrdata->branchingrule ==
's' || conshdlrdata->switchsos1branch )
6076 if ( conshdlrdata->branchingrule !=
'n' && conshdlrdata->branchingrule !=
'b' )
6078 SCIPerrorMessage(
"branching rule %c unknown\n", conshdlrdata->branchingrule);
6110 for (j = 0; j < nsos1vars; ++j)
6117 for (j = 0; j < nsos1vars; ++j)
6127 for (i = 0; i < nsucc; ++i)
6144 tcliquedata = conshdlrdata->tcliquedata;
6147 tcliquedata->
scip = scip;
6148 tcliquedata->
sol = NULL;
6152 tcliquedata->
ncuts = 0;
6153 tcliquedata->
nboundcuts = conshdlrdata->nboundcuts;
6155 tcliquedata->
maxboundcuts = conshdlrdata->maxboundcutsroot;
6177 for (j = 0; j < nsos1vars; ++j)
6188 if ( conshdlrdata->strthenboundcuts )
6195 if ( conshdlrdata->strthenboundcuts )
6208 nodeweight =
REALABS( solval/bound ) * scaleval;
6232 assert( scip != NULL );
6233 assert( tcliquedata != NULL );
6234 assert( success != NULL);
6235 assert( cutoff != NULL );
6241 if ( rowlb != NULL )
6252 ++tcliquedata->
ncuts;
6258 if ( rowub != NULL )
6269 ++tcliquedata->
ncuts;
6308 const char* nameext,
6321 assert( scip != NULL );
6322 assert( conshdlr != NULL );
6323 assert( conflictgraph != NULL );
6324 assert( ! local || ! global );
6325 assert( nodes != NULL );
6332 if ( rowub != NULL )
6341 useboundvar = strengthen;
6342 for (j = 0; j <
nnodes; ++j)
6349 assert( nodedata != NULL );
6350 var = nodedata->var;
6351 assert( var != NULL );
6354 if ( ! useboundvar || nodedata->ubboundvar == NULL )
6356 useboundvar =
FALSE;
6377 if ( ubboundvar == NULL )
6379 ubboundvar = nodedata->ubboundvar;
6380 val = nodedata->ubboundcoef;
6383 else if ( ubboundvar == nodedata->ubboundvar )
6384 val = nodedata->ubboundcoef;
6387 useboundvar =
FALSE;
6409 vals[cnt++] = 1.0/val;
6414 if ( j == nnodes && cnt >= 2 )
6424 rhs = rhs * vals[0] * vals[1];
6425 assert( (! useboundvar && cnt == 2 ) || (useboundvar && cnt == 3 ) );
6431 vars[cnt] = ubboundvar;
6433 assert(ubboundvar != NULL );
6454 if ( rowlb != NULL )
6464 useboundvar = strengthen;
6465 for (j = 0; j <
nnodes; ++j)
6472 assert( nodedata != NULL );
6473 var = nodedata->var;
6474 assert( var != NULL );
6477 if ( ! useboundvar || nodedata->lbboundvar == NULL )
6479 useboundvar =
FALSE;
6500 if ( lbboundvar == NULL )
6502 lbboundvar = nodedata->lbboundvar;
6503 val = nodedata->lbboundcoef;
6506 else if (
SCIPvarCompare(lbboundvar, nodedata->lbboundvar) == 0 )
6508 val = nodedata->lbboundcoef;
6512 useboundvar =
FALSE;
6534 vals[cnt++] = 1.0/val;
6539 if ( j == nnodes && cnt >= 2 )
6549 rhs = rhs * vals[0] * vals[1];
6550 assert( (! useboundvar && cnt == 2 ) || (useboundvar && cnt == 3 ) );
6556 vars[cnt] = lbboundvar;
6558 assert(lbboundvar != NULL );
6593 assert( acceptsol != NULL );
6594 assert( stopsolving != NULL );
6595 assert( tcliquedata != NULL );
6599 *stopsolving =
FALSE;
6602 minweightinc = (cliqueweight - *minweight)/10;
6603 minweightinc =
MAX(minweightinc, 1);
6604 *minweight += minweightinc;
6607 if( cliqueweight > tcliquedata->
scaleval )
6618 scip = tcliquedata->
scip;
6619 sol = tcliquedata->
sol;
6620 assert( scip != NULL );
6623 unscaledweight = 0.0;
6624 for( i = 0; i < ncliquenodes; i++ )
6626 node = cliquenodes[i];
6650 unscaledweight +=
REALABS( solval/bound );
6680 if ( rowlb != NULL )
6689 if ( rowub != NULL )
6702 SCIPdebugMsg(scip,
" -> found bound cut corresponding to clique (act=%g)\n", unscaledweight);
6712 *stopsolving =
TRUE;
6716 *stopsolving =
TRUE;
6741 int maxtreenodes = 10000;
6742 int maxzeroextensions = 1000;
6743 int backtrackfreq = 1000;
6748 assert( scip != NULL );
6749 assert( conshdlr != NULL );
6750 assert( conshdlrdata != NULL );
6751 assert( ngen != NULL );
6755 assert( conflictgraph != NULL );
6761 tcliquedata = conshdlrdata->tcliquedata;
6764 tcliquedata->
sol = sol;
6765 tcliquedata->
ncuts = 0;
6775 tcliqueMaxClique(tcliqueGetNNodes, tcliqueGetWeights, tcliqueIsEdge, tcliqueSelectAdjnodes,
6776 conshdlrdata->tcliquegraph, tcliqueNewsolClique, tcliquedata,
6777 cliquenodes, &ncliquenodes, &cliqueweight, (
int)scaleval-1, (
int)scaleval+1,
6778 maxtreenodes, backtrackfreq, maxzeroextensions, -1, &ntreenodes, &tcliquestatus);
6784 *ngen = tcliquedata->
ncuts;
6787 *cutoff = tcliquedata->
cutoff;
6790 conshdlrdata->nboundcuts = tcliquedata->
nboundcuts;
6817 assert( scip != NULL );
6818 assert( conshdlr != NULL );
6819 assert( cons != NULL );
6823 assert( consdata != NULL );
6824 assert( consdata->vars != NULL );
6825 nvars = consdata->nvars;
6829 assert( conshdlrdata != NULL );
6836 for (j = 0; j < nvars; ++j)
6877 assert( scip != NULL );
6878 assert( conshdlrdata != NULL );
6879 assert( conss != NULL );
6883 for (c = 0; c < nconss; ++c)
6890 assert( conss != NULL );
6891 assert( conss[c] != NULL );
6893 assert( consdata != NULL );
6906 if ( consdata->local )
6913 if ( consdata->rowub == NULL || consdata->rowlb == NULL )
6916 (consdata->rowlb == NULL) ? &consdata->rowlb : NULL,
6917 (consdata->rowub == NULL) ? &consdata->rowub : NULL) );
6919 rowub = consdata->rowub;
6920 rowlb = consdata->rowlb;
6951 if ( rowlb != NULL )
6955 if ( rowub != NULL )
6961 if ( *cutoff || ( maxboundcuts >= 0 && cnt >= maxboundcuts ) )
6990 assert( scip != NULL);
6991 assert( conshdlrdata != NULL);
6992 assert( conshdlr != NULL);
6993 assert( ngen != NULL);
6994 assert( cutoff != NULL);
7000 if ( conshdlrdata->conflictgraph == NULL )
7004 implgraph = conshdlrdata->implgraph;
7007 if ( implgraph == NULL )
7014 SCIP_CALL(
initImplGraphSOS1(scip, conshdlrdata, conshdlrdata->conflictgraph, conshdlrdata->nsos1vars, conshdlrdata->maxtightenbds, &nchbds, cutoff, &success) );
7015 if ( *cutoff || ! success )
7017 implgraph = conshdlrdata->implgraph;
7024 nimplnodes = conshdlrdata->nimplnodes;
7025 assert( implgraph != NULL );
7026 assert( nimplnodes > 0);
7034 for (i = 0; i < nimplnodes && ! genbreak; ++i)
7046 assert( nodedata != NULL );
7047 var = nodedata->var;
7048 assert( var != NULL );
7056 for (s = 0; s < nsucc && ! genbreak; ++s)
7071 succdata = succdatas[s];
7072 assert( nodedata != NULL && succdata != NULL && nodedata->var != NULL );
7073 succvar = nodedata->var;
7085 bound1lower =
FALSE;
7090 for (k = 0; k < 2; ++k)
7098 impl = succdata->lbimpl;
7110 impl = succdata->ubimpl;
7124 bound2lower =
FALSE;
7127 lhsrhs = bound1 * bound2;
7130 if ( bound1lower == bound2lower )
7132 if (
SCIPisFeasGT(scip, solval * (bound2-impl) + solvalsucc * bound1, lhsrhs) )
7141 if (
SCIPisFeasLT(scip, solval * (bound2-impl) + solvalsucc * bound1, lhsrhs) )
7181 if ( maxcuts >= 0 && *ngen > maxcuts )
7212 assert( scip != NULL );
7213 assert( conshdlr != NULL );
7214 assert( conss != NULL );
7215 assert( result != NULL );
7230 assert( conshdlrdata != NULL );
7237 if ( conshdlrdata->boundcutsfreq >= 0 && ( (conshdlrdata->boundcutsfreq == 0 && depth == 0) || (conshdlrdata->boundcutsfreq > 0 && depth % conshdlrdata->boundcutsfreq == 0)) )
7244 maxboundcuts = conshdlrdata->maxboundcutsroot;
7246 maxboundcuts = conshdlrdata->maxboundcuts;
7248 if ( maxboundcuts >= 1 )
7251 if( conshdlrdata->boundcutsfromsos1 || conshdlrdata->switchcutsfromsos1 )
7264 if( conshdlrdata->boundcutsfromgraph && ! conshdlrdata->switchcutsfromsos1 )
7279 SCIPdebugMsg(scip,
"Separated %d bound (clique) inequalities.\n", ngen);
7284 if ( conshdlrdata->implcutsfreq >= 0 && ( (conshdlrdata->implcutsfreq == 0 && depth == 0) || (conshdlrdata->implcutsfreq > 0 && depth % conshdlrdata->implcutsfreq == 0)) )
7291 maximplcuts = conshdlrdata->maximplcutsroot;
7293 maximplcuts = conshdlrdata->maximplcuts;
7296 if ( maximplcuts >= 1 )
7310 SCIPdebugMsg(scip,
"Separated %d implied bound inequalities.\n", ngen);
7339 assert( scip != NULL );
7340 assert( conflictgraph != NULL );
7341 assert( indicatorzero != NULL );
7342 assert( weights != NULL );
7344 for (i = 0; i < nsos1vars; ++i)
7348 if( nsucc == 0 || indicatorzero[i] )
7362 for (j = 0; j < nsucc; ++j)
7369 sum += MIN(10E05, valsucc);
7379 val = MIN(1e6, val);
7407 assert( scip != NULL );
7408 assert( conflictgraph != NULL );
7409 assert( mark != NULL );
7410 assert( indset != NULL );
7411 assert( cutoff != NULL );
7412 assert( cnt != NULL );
7420 for (j = 0; j < nsucc && !(*cutoff); ++j)
7425 assert( indset[succj] == 0 );
7447 if ( aggrnode >= 0 )
7452 if ( ! mark[aggrnode] )
7454 mark[aggrnode] =
TRUE;
7457 else if ( indset[aggrnode] == 1 )
7466 if ( indset[aggrnode] == 0 )
7469 if ( mark[aggrnode] )
7476 indset[aggrnode] = 1;
7477 mark[aggrnode] =
TRUE;
7498 if ( indset[negnode] == 1 )
7503 else if ( ! mark[negnode] )
7505 mark[negnode] =
TRUE;
7545 int* indscipvars = NULL;
7551 assert( scip != NULL );
7552 assert( conflictgraph != NULL );
7553 assert( indicatorzero != NULL );
7554 assert( indset != NULL );
7562 for (i = 0; i < nsos1vars; ++i)
7570 for (i = 0; i < nsos1vars; ++i)
7574 if ( indset[i] == 0 )
7576 if( indicatorzero[i] )
7581 else if ( nsucc == 0 )
7603 for (i = 0; k < nsos1vars; ++i)
7605 assert( i < nsos1vars );
7607 ind = indscipvars[i];
7623 assert( k == nsos1vars );
7653 assert( scip != NULL );
7654 assert( conshdlr != NULL );
7655 assert( sol != NULL );
7656 assert( changed != NULL );
7658 *allroundable =
TRUE;
7663 assert( nsos1vars >= 0 );
7667 assert( conflictgraph != NULL );
7674 for (j = 0; j < nsos1vars; ++j)
7687 indicatorzero[j] =
TRUE;
7690 indicatorzero[j] =
FALSE;
7695 *allroundable =
FALSE;
7701 indicatorzero[j] =
TRUE;
7708 if ( ! (*allroundable) )
7719 for (j = 0; j < nsos1vars; ++j)
7721 if ( indset[j] == 0 )
7741 for (c = 0; c < nconss; ++c)
7745 assert( consdata != NULL );
7747 for (j = 0; j < consdata->nvars; ++j)
7781 assert( scip != NULL );
7782 assert( conshdlr != NULL );
7783 assert( sol != NULL );
7784 assert( changed != NULL );
7786 *allroundable =
TRUE;
7792 assert( nconss > 0 );
7795 for (c = 0; c < nconss && *allroundable; ++c)
7806 assert( cons != NULL );
7808 assert( consdata != NULL );
7810 nvars = consdata->nvars;
7811 vars = consdata->vars;
7814 for (j = 0; j < nvars; ++j)
7831 *allroundable =
FALSE;
7844 assert( ! varisfixed );
7862 if ( ! (*allroundable) )
7864 else if ( pos >= 0 )
7871 if ( *allroundable )
7873 for (c = 0; c < nconss; ++c)
7879 assert( consdata != NULL );
7881 for (j = 0; j < consdata->nvars; ++j)
7918 assert( scip != NULL );
7919 assert( conshdlr != NULL );
7920 assert( diveset != NULL );
7921 assert( success != NULL );
7932 for (v = 0; v < nsos1vars; ++v)
7974 &score, &roundup) );
7978 fixneigh = !fixneigh;
7990 if ( score > bestscore )
7997 bestvarfixneigh = fixneigh;
8001 assert( !(*success) || bestvar != NULL );
8009 assert( bestnode >= 0 && bestnode < nsos1vars );
8019 for (s = 0; s < nsucc; ++s)
8060 assert( scip != NULL );
8061 assert( conshdlr != NULL );
8062 assert( diveset != NULL );
8063 assert( success != NULL );
8072 for (c = 0; c < nconss; ++c)
8080 assert( consdata != NULL );
8082 nvars = consdata->nvars;
8083 vars = consdata->vars;
8086 for (j = 0; j < nvars && cnt < 2; ++j)
8103 for (j = 0; j < nvars; ++j)
8150 &score, &roundup) );
8166 if ( score > bestscore )
8173 bestvarfixcomp = fixcomp;
8178 assert( !(*success) || bestvar != NULL );
8187 assert( consdata != NULL );
8189 nvars = consdata->nvars;
8190 vars = consdata->vars;
8192 assert( bestcons >= 0 && bestcons < nconss );
8200 for (j = 0; j < nvars; ++j)
8235 assert( scip != NULL );
8236 assert( conshdlrdata != NULL );
8237 assert( var0 != NULL && var1 != NULL );
8261 if ( nodedata->lbboundvar == NULL )
8264 nodedata->lbboundvar = var1;
8265 nodedata->lbboundcoef = val;
8279 if ( nodedata->ubboundvar == NULL )
8282 nodedata->ubboundvar = var1;
8283 nodedata->ubboundcoef = val;
8316 assert( scip != NULL );
8317 assert( conflictgraph != NULL );
8318 assert( processed != NULL );
8319 assert( concomp != NULL );
8320 assert( nconcomp != NULL );
8321 assert( unique != NULL );
8323 processed[node] =
TRUE;
8324 concomp[(*nconcomp)++] = node;
8332 assert( nodedata != NULL );
8335 comparevar = nodedata->lbboundvar;
8337 comparevar = nodedata->ubboundvar;
8340 if ( boundvar == NULL )
8342 if ( comparevar != NULL )
8347 if ( comparevar == NULL )
8357 for (s = 0; s < nsucc; ++s)
8359 if ( ! processed[succ[s]] )
8385 assert( scip != NULL );
8386 assert( conflictgraph != NULL );
8391 for (j = 0; j < nsos1vars; ++j)
8392 processed[j] =
FALSE;
8395 for (j = 0; j < nsos1vars; ++j)
8398 if ( ! processed[j] )
8408 assert( nodedata != NULL );
8411 boundvar = nodedata->lbboundvar;
8413 boundvar = nodedata->ubboundvar;
8416 processed[j] =
TRUE;
8423 for (s = 0; s < nsucc; ++s)
8425 if ( ! processed[succ[s]] )
8432 if ( unique && boundvar != NULL )
8434 for (s = 0; s < nconcomp; ++s)
8437 assert( processed[concomp[s]] ==
TRUE );
8438 assert( nodedata != NULL );
8441 nodedata->lbboundcomp =
TRUE;
8443 nodedata->ubboundcomp =
TRUE;
8445 SCIPdebugMsg(scip,
"Found a connected component of size <%i> with unique bound variable.\n", nconcomp);
8472 for (c = 0; c < nlinconss; ++c)
8477 lincons = linconss[c];
8498 assert( var0 != NULL && var1 != NULL );
8547 if ( conshdlrdata->nsos1vars > 0 )
8549 for (c = 0; c < nconss && nonoverlap; ++c)
8557 assert( conss[c] != NULL );
8561 assert( consdata != NULL );
8564 nvars = consdata->nvars;
8565 vars = consdata->vars;
8568 for (i = 0; i < nvars; ++i)
8575 for (i = 0; i < nvars; ++i)
8579 assert( vars[i] != NULL );
8583 assert( node < conshdlrdata->nsos1vars );
8597 if ( conshdlrdata->autosos1branch )
8599 conshdlrdata->switchsos1branch =
TRUE;
8600 SCIPdebugMsg(scip,
"Switched to SOS1 branching, since the SOS1 constraints do not overlap\n");
8603 if ( conshdlrdata->autocutsfromsos1 )
8605 conshdlrdata->switchcutsfromsos1 =
TRUE;
8606 SCIPdebugMsg(scip,
"Switched to separating bound cuts from SOS1 constraints (and not from the conflict graph), since the SOS1 constraints do not overlap\n");
8627 if ( nsos1vars == 0 )
8632 if ( linconshdlr == NULL )
8669 assert( conshdlrdata != NULL );
8670 assert( nconss == 0 || conss != NULL );
8678 for (i = 0; i < ntotalvars; ++i)
8679 nodecreated[i] =
FALSE;
8683 for (c = 0; c < nconss; ++c)
8689 assert( conss[c] != NULL );
8693 assert( consdata != NULL );
8696 nvars = consdata->nvars;
8697 vars = consdata->vars;
8700 for (i = 0; i < nvars; ++i)
8712 assert( ind >= 0 && ind < ntotalvars );
8713 if ( ! nodecreated[ind] )
8715 nodecreated[ind] =
TRUE;
8716 nodeorig[ind] = cntsos;
8727 conshdlrdata->nsos1vars = 0;
8732 for (i = 0; i < ntotalvars; ++i)
8733 nodecreated[i] =
FALSE;
8743 for (c = 0; c < nconss; ++c)
8749 assert( conss[c] != NULL );
8753 assert( consdata != NULL );
8756 nvars = consdata->nvars;
8757 vars = consdata->vars;
8760 for (i = 0; i < nvars; ++i)
8773 if ( ! nodecreated[indi] )
8785 nodedata->var = var;
8786 nodedata->lbboundvar = NULL;
8787 nodedata->ubboundvar = NULL;
8788 nodedata->lbboundcoef = 0.0;
8789 nodedata->ubboundcoef = 0.0;
8790 nodedata->lbboundcomp =
FALSE;
8791 nodedata->ubboundcomp =
FALSE;
8797 nodecreated[indi] =
TRUE;
8802 for (j = i+1; j < nvars; ++j)
8827 conshdlrdata->nsos1vars = cntsos;
8834 for (j = 0; j < conshdlrdata->nsos1vars; ++j)
8855 if ( conshdlrdata->conflictgraph == NULL )
8857 assert( conshdlrdata->nsos1vars == 0 );
8862 assert( conshdlrdata->nsos1vars > 0 );
8863 for (j = 0; j < conshdlrdata->nsos1vars; ++j)
8868 assert( conshdlrdata->conflictgraph != NULL );
8870 assert( nodedata != NULL );
8878 assert( conshdlrdata->varhash != NULL );
8881 conshdlrdata->nsos1vars = 0;
8883 assert( conshdlrdata->varhash == NULL );
8884 assert( conshdlrdata->conflictgraph == NULL );
8896 assert( scip != NULL );
8897 assert( conshdlr != NULL );
8915 assert( scip != NULL );
8916 assert( conshdlr != NULL );
8920 assert(conshdlrdata != NULL);
8937 assert( scip != NULL );
8938 assert( conshdlr != NULL );
8942 assert( conshdlrdata != NULL );
8944 conshdlrdata->nsos1vars = 0;
8945 conshdlrdata->varhash = NULL;
8955 if ( ( conshdlrdata->autosos1branch || conshdlrdata->autocutsfromsos1 )
8956 && ( ! conshdlrdata->switchsos1branch || ! conshdlrdata->switchcutsfromsos1 )
8967 if ( conshdlrdata->addcomps )
8973 if ( conshdlrdata->fixnonzerovars == NULL )
8975 conshdlrdata->maxnfixnonzerovars = conshdlrdata->nsos1vars;
8991 assert( scip != NULL );
8992 assert( conshdlr != NULL );
8995 assert( conshdlrdata != NULL );
8998 for (c = 0; c < nconss; ++c)
9002 assert( conss != NULL );
9003 assert( conss[c] != NULL );
9005 assert( consdata != NULL );
9010 if ( consdata->rowub != NULL )
9015 if ( consdata->rowlb != NULL )
9022 if ( conshdlrdata->implgraph != NULL )
9026 assert( conshdlrdata->implgraph == NULL );
9029 if ( conshdlrdata->tcliquegraph != NULL )
9031 assert( conshdlrdata->tcliquedata != NULL );
9035 assert(conshdlrdata->tcliquegraph == NULL);
9036 assert(conshdlrdata->tcliquedata == NULL);
9040 conshdlrdata->nfixnonzerovars = 0;
9041 conshdlrdata->maxnfixnonzerovars = 0;
9044 if ( conshdlrdata->localconflicts != NULL )
9046 assert( conshdlrdata->localconflicts == NULL );
9050 assert( conshdlrdata->conflictgraph == NULL );
9060 assert( scip != NULL );
9061 assert( conshdlr != NULL );
9062 assert( cons != NULL );
9063 assert( consdata != NULL );
9076 assert( conshdlrdata != NULL );
9077 assert( conshdlrdata->eventhdlr != NULL );
9079 for (j = 0; j < (*consdata)->nvars; ++j)
9087 if ( (*consdata)->weights != NULL )
9093 if ( (*consdata)->rowub != NULL )
9097 if ( (*consdata)->rowlb != NULL )
9101 assert( (*consdata)->rowub == NULL );
9102 assert( (*consdata)->rowlb == NULL );
9120 assert( scip != NULL );
9121 assert( conshdlr != NULL );
9123 assert( sourcecons != NULL );
9124 assert( targetcons != NULL );
9128 assert( conshdlrdata != NULL );
9129 assert( conshdlrdata->eventhdlr != NULL );
9135 assert( sourcedata != NULL );
9136 assert( sourcedata->nvars > 0 );
9137 assert( sourcedata->nvars <= sourcedata->maxvars );
9140 if ( conshdlrdata->fixnonzerovars == NULL )
9149 consdata->nvars = sourcedata->nvars;
9150 consdata->maxvars = sourcedata->nvars;
9151 consdata->rowub = NULL;
9152 consdata->rowlb = NULL;
9153 consdata->nfixednonzeros = 0;
9154 consdata->local = sourcedata->local;
9157 if ( sourcedata->weights != NULL )
9162 consdata->weights = NULL;
9164 for (j = 0; j < sourcedata->nvars; ++j)
9166 assert( sourcedata->vars[j] != 0 );
9171 ++(consdata->nfixednonzeros);
9184 for (j = 0; j < consdata->nvars; ++j)
9191 if ( consdata->nfixednonzeros > 0 )
9194 consdata->nfixednonzeros );
9217 assert( scip != NULL );
9218 assert( conshdlr != NULL );
9220 assert( result != NULL );
9223 assert( conshdlrdata != NULL );
9229 SCIPdebug( oldnfixedvars = *nfixedvars; )
9232 SCIPdebug( oldnupgdconss = *nupgdconss; )
9236 if( nconss > 0 && ( nrounds == 0 || nnewfixedvars > 0 || nnewaggrvars > 0 || nnewchgbds > 0 ) )
9250 assert( eventhdlr != NULL );
9256 conflictgraph = conshdlrdata->conflictgraph;
9257 nsos1vars = conshdlrdata->nsos1vars;
9258 if ( nsos1vars < 2 )
9265 if ( conshdlrdata->maxsosadjacency == -1 || nsos1vars <= conshdlrdata->maxsosadjacency )
9269 for (i = 0; i < nsos1vars; ++i)
9275 for (i = 0; i < nsos1vars; ++i)
9277 for (j = 0; j < i+1; ++j)
9278 adjacencymatrix[i][j] = 0;
9280 for (i = 0; i < nsos1vars; ++i)
9288 for (j = 0; j < nsucc; ++j)
9291 adjacencymatrix[i][succ[j]] = 1;
9297 SCIPdebugMsg(scip,
"Adjacency matrix was not created since number of SOS1 variables (%d) is larger than %d.\n", nsos1vars, conshdlrdata->maxsosadjacency);
9301 SCIP_CALL(
presolRoundConssSOS1(scip, eventhdlr, conshdlrdata, conflictgraph, adjacencymatrix, conss, nconss, nsos1vars, naddconss, ndelconss, nupgdconss, nfixedvars, &nremovedvars, result) );
9303 if ( adjacencymatrix != NULL )
9306 if ( conshdlrdata->maxtightenbds != 0 && *result !=
SCIP_CUTOFF )
9308 SCIP_CALL(
presolRoundVarsSOS1(scip, conshdlrdata, conflictgraph, adjacencymatrix, nsos1vars, nfixedvars, nchgbds, naddconss, result) );
9312 for (j = nsos1vars-1; j >= 0; --j)
9320 (*nchgcoefs) += nremovedvars;
9322 SCIPdebugMsg(scip,
"presolving fixed %d variables, changed %d bounds, removed %d variables, deleted %d constraints, and upgraded %d constraints.\n",
9323 *nfixedvars - oldnfixedvars, *nchgbds - oldnchgbds, nremovedvars, *ndelconss - oldndelconss, *nupgdconss - oldnupgdconss);
9335 assert( scip != NULL );
9336 assert( conshdlr != NULL );
9340 assert( conshdlrdata != NULL );
9342 *infeasible =
FALSE;
9345 if( conshdlrdata->boundcutsfromsos1 || conshdlrdata->switchcutsfromsos1 )
9358 assert( scip != NULL );
9359 assert( conshdlr != NULL );
9360 assert( conss != NULL );
9362 assert( result != NULL );
9374 assert( scip != NULL );
9375 assert( conshdlr != NULL );
9376 assert( conss != NULL );
9378 assert( result != NULL );
9390 assert( scip != NULL );
9391 assert( conshdlr != NULL );
9392 assert( conss != NULL );
9394 assert( result != NULL );
9406 assert( scip != NULL );
9407 assert( conshdlr != NULL );
9408 assert( conss != NULL );
9410 assert( result != NULL );
9422 assert( scip != NULL );
9423 assert( conshdlr != NULL );
9424 assert( conss != NULL );
9426 assert( result != NULL );
9443 assert( scip != NULL );
9444 assert( conshdlr != NULL );
9445 assert( conss != NULL );
9447 assert( result != NULL );
9452 for (c = 0; c < nconss && (*result ==
SCIP_FEASIBLE || completely); ++c)
9459 assert( conss[c] != NULL );
9461 assert( consdata != NULL );
9465 for (j = 0; j < consdata->nvars; ++j)
9489 for (l = 0; l < consdata->nvars; ++l)
9518 assert( scip != NULL );
9519 assert( conshdlr != NULL );
9520 assert( conss != NULL );
9522 assert( result != NULL );
9535 assert( conshdlrdata != NULL );
9538 conflictgraph = conshdlrdata->conflictgraph;
9541 implgraph = conshdlrdata->implgraph;
9542 if ( implgraph == NULL && conshdlrdata->implprop && conflictgraph != NULL )
9550 SCIP_CALL(
initImplGraphSOS1(scip, conshdlrdata, conflictgraph, conshdlrdata->nsos1vars, conshdlrdata->maxtightenbds, &nchbds, &cutoff, &success) );
9552 conshdlrdata->implprop =
FALSE;
9559 else if ( nchbds > 0 )
9561 implgraph = conshdlrdata->implgraph;
9564 conshdlrdata->implprop =
FALSE;
9568 if ( conshdlrdata->conflictprop && conflictgraph != NULL )
9571 int nfixnonzerovars;
9574 assert( nconss > 0 );
9577 nfixnonzerovars = conshdlrdata->nfixnonzerovars;
9578 fixnonzerovars = conshdlrdata->fixnonzerovars;
9579 assert( fixnonzerovars != NULL );
9582 for (j = 0; j < nfixnonzerovars; ++j)
9586 var = fixnonzerovars[j];
9595 assert(
varGetNodeSOS1(conshdlrdata, var) < conshdlrdata->nsos1vars );
9614 conshdlrdata->nfixnonzerovars = 0;
9617 if ( conshdlrdata->sosconsprop || conflictgraph == NULL )
9622 for (c = 0; c < nconss; ++c)
9628 assert( conss[c] != NULL );
9631 assert( consdata != NULL );
9661 assert( scip != NULL );
9662 assert( cons != NULL );
9664 assert( infervar != NULL );
9665 assert( bdchgidx != NULL );
9666 assert( result != NULL );
9672 if ( inferinfo < 0 )
9676 assert( conshdlr != NULL );
9680 assert( conshdlrdata != NULL );
9681 assert( conshdlrdata->conflictgraph != NULL );
9682 assert( inferinfo >= -conshdlrdata->maxnfixnonzerovars );
9683 assert( inferinfo >= -conshdlrdata->nsos1vars );
9684 assert( inferinfo <= -1 );
9694 assert( consdata != NULL );
9695 assert( inferinfo < consdata->nvars );
9697 var = consdata->vars[inferinfo];
9699 assert( var != NULL );
9700 assert( var != infervar );
9740 assert( scip != NULL );
9741 assert( conshdlr != NULL );
9742 assert( cons != NULL );
9745 assert( consdata != NULL );
9749 vars = consdata->vars;
9750 nvars = consdata->nvars;
9751 assert( vars != NULL );
9753 for (j = 0; j < nvars; ++j)
9782 assert( scip != NULL );
9783 assert( conshdlr != NULL );
9784 assert( cons != NULL );
9788 assert( consdata != NULL );
9790 for (j = 0; j < consdata->nvars; ++j)
9795 if ( consdata->weights == NULL )
9814 const char* consname;
9818 assert( scip != NULL );
9819 assert( sourcescip != NULL );
9820 assert( sourcecons != NULL );
9830 SCIPdebugMsg(scip,
"Copying SOS1 constraint <%s> ...\n", consname);
9833 assert( sourceconsdata != NULL );
9836 nvars = sourceconsdata->nvars;
9841 sourcevars = sourceconsdata->vars;
9842 assert( sourcevars != NULL );
9843 sourceweights = sourceconsdata->weights;
9844 assert( sourceweights != NULL );
9851 for( v = 0; v < nvars && *valid; ++v )
9853 SCIP_CALL(
SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &(targetvars[v]), varmap, consmap, global, valid) );
9860 initial, separate, enforce, check, propagate, local, dynamic, removable, stickingatnode) );
9880 assert(scip != NULL);
9881 assert(conshdlr != NULL);
9883 assert(cons != NULL);
9884 assert(success != NULL);
9890 SCIP_CALL(
SCIPcreateConsSOS1(scip, cons, name, 0, NULL, NULL, initial, separate, enforce, check, propagate, local, dynamic, removable, stickingatnode) );
9900 while ( *s !=
'\0' && *s !=
'(' )
9913 weight = strtod(s, &t);
9923 while ( *s !=
'\0' && ( isspace((
unsigned char)*s) || *s ==
',' || *s ==
')' ) )
9929 while ( *s !=
'\0' );
9942 assert(consdata != NULL);
9944 if( varssize < consdata->nvars )
9948 assert(vars != NULL);
9965 assert(consdata != NULL);
9967 (*nvars) = consdata->nvars;
9991 assert( eventhdlr != NULL );
9992 assert( eventdata != NULL );
9994 assert( event != NULL );
9997 assert( cons != NULL );
9999 assert( 0 <= consdata->nfixednonzeros && consdata->nfixednonzeros <= consdata->nvars );
10005 switch ( eventtype )
10012 assert( conshdlr != NULL );
10014 assert( conshdlrdata != NULL );
10017 assert( 0 <= conshdlrdata->nfixnonzerovars && conshdlrdata->nfixnonzerovars <=
SCIPgetNTotalVars(scip) );
10018 if ( conshdlrdata->nfixnonzerovars < conshdlrdata->maxnfixnonzerovars )
10020 assert( conshdlrdata->fixnonzerovars != NULL );
10022 conshdlrdata->fixnonzerovars[conshdlrdata->nfixnonzerovars++] =
SCIPeventGetVar(event);
10025 ++(consdata->nfixednonzeros);
10034 assert( conshdlr != NULL );
10036 assert( conshdlrdata != NULL );
10039 assert( 0 <= conshdlrdata->nfixnonzerovars && conshdlrdata->nfixnonzerovars <=
SCIPgetNTotalVars(scip) );
10040 if ( conshdlrdata->nfixnonzerovars < conshdlrdata->maxnfixnonzerovars )
10042 assert( conshdlrdata->fixnonzerovars != NULL );
10044 conshdlrdata->fixnonzerovars[conshdlrdata->nfixnonzerovars++] =
SCIPeventGetVar(event);
10047 ++(consdata->nfixednonzeros);
10054 --(consdata->nfixednonzeros);
10060 --(consdata->nfixednonzeros);
10067 assert( 0 <= consdata->nfixednonzeros && consdata->nfixednonzeros <= consdata->nvars );
10070 oldbound, newbound, consdata->nfixednonzeros);
10082 assert( scip != NULL );
10083 assert( conshdlr != NULL );
10085 assert( diveset != NULL );
10086 assert( success != NULL );
10087 assert( infeasible != NULL );
10089 *infeasible =
FALSE;
10098 assert( conshdlrdata != NULL );
10103 if ( conshdlrdata->switchsos1branch )
10128 conshdlrdata->branchsos =
TRUE;
10129 conshdlrdata->switchsos1branch =
FALSE;
10130 conshdlrdata->switchcutsfromsos1 =
FALSE;
10131 conshdlrdata->eventhdlr = NULL;
10132 conshdlrdata->fixnonzerovars = NULL;
10133 conshdlrdata->maxnfixnonzerovars = 0;
10134 conshdlrdata->nfixnonzerovars = 0;
10135 conshdlrdata->conflictgraph = NULL;
10136 conshdlrdata->localconflicts = NULL;
10137 conshdlrdata->isconflocal =
FALSE;
10138 conshdlrdata->implgraph = NULL;
10139 conshdlrdata->nimplnodes = 0;
10140 conshdlrdata->nboundcuts = 0;
10141 conshdlrdata->tcliquegraph = NULL;
10142 conshdlrdata->tcliquedata = NULL;
10143 conshdlrdata->cntextsos1 = -1;
10144 conshdlrdata->varhash = NULL;
10148 if ( conshdlrdata->eventhdlr == NULL )
10157 consEnfolpSOS1, consEnfopsSOS1, consCheckSOS1, consLockSOS1, conshdlrdata) );
10158 assert(conshdlr != NULL);
10183 "do not create an adjacency matrix if number of SOS1 variables is larger than predefined value (-1: no limit)",
10188 "maximal number of extensions that will be computed for each SOS1 constraint (-1: no limit)",
10192 "maximal number of bound tightening rounds per presolving round (-1: no limit)",
10196 "if TRUE then perform implication graph analysis (might add additional SOS1 constraints)",
10200 "number of recursive calls of implication graph analysis (-1: no limit)",
10205 "whether to use conflict graph propagation",
10209 "whether to use implication graph propagation",
10213 "whether to use SOS1 constraint propagation",
10218 "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)",
10222 "if TRUE then automatically switch to SOS1 branching if the SOS1 constraints do not overlap",
10226 "if neighborhood branching is used, then fix the branching variable (if positive in sign) to the value of the feasibility tolerance",
10230 "if TRUE then add complementarity constraints to the branching nodes (can be used in combination with neighborhood or bipartite branching)",
10234 "maximal number of complementarity constraints added per branching node (-1: no limit)",
10238 "minimal feasibility value for complementarity constraints in order to be added to the branching node",
10242 "minimal feasibility value for bound inequalities in order to be added to the branching node",
10246 "should added complementarity constraints be extended to SOS1 constraints to get tighter bound inequalities",
10250 "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",
10251 &conshdlrdata->branchsos,
FALSE,
TRUE, NULL, NULL) );
10254 "Branch on SOS constraint with most number of nonzeros?",
10255 &conshdlrdata->branchnonzeros,
FALSE,
FALSE, NULL, NULL) );
10258 "Branch on SOS cons. with highest nonzero-variable weight for branching (needs branchnonzeros = false)?",
10259 &conshdlrdata->branchweight,
FALSE,
FALSE, NULL, NULL) );
10262 "only add complementarity constraints to branching nodes for predefined depth (-1: no limit)",
10267 "maximal number of strong branching rounds to perform for each node (-1: auto); only available for neighborhood and bipartite branching",
10271 "maximal number LP iterations to perform for each strong branching round (-2: auto, -1: no limit)",
10276 "if TRUE separate bound inequalities from initial SOS1 constraints",
10280 "if TRUE separate bound inequalities from the conflict graph",
10284 "if TRUE then automatically switch to separating initial SOS1 constraints if the SOS1 constraints do not overlap",
10288 "frequency for separating bound cuts; zero means to separate only in the root node",
10292 "node depth of separating bound cuts (-1: no limit)",
10296 "maximal number of bound cuts separated per branching node",
10300 "maximal number of bound cuts separated per iteration in the root node",
10304 "if TRUE then bound cuts are strengthened in case bound variables are available",
10308 "frequency for separating implied bound cuts; zero means to separate only in the root node",
10312 "node depth of separating implied bound cuts (-1: no limit)",
10316 "maximal number of implied bound cuts separated per branching node",
10320 "maximal number of implied bound cuts separated per iteration in the root node",
10369 modifiable =
FALSE;
10373 if ( conshdlr == NULL )
10384 consdata->vars = NULL;
10385 consdata->nvars = nvars;
10386 consdata->maxvars = nvars;
10387 consdata->rowub = NULL;
10388 consdata->rowlb = NULL;
10389 consdata->nfixednonzeros = transformed ? 0 : -1;
10390 consdata->weights = NULL;
10391 consdata->local = local;
10398 if ( weights != NULL )
10409 assert( weights == NULL );
10413 for (v = 0; v < nvars; ++v)
10419 SCIP_CALL(
SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
10420 local, modifiable, dynamic, removable, stickingatnode) );
10424 for (v = nvars - 1; v >= 0; --v)
10433 assert( consdata->vars[v] != NULL );
10438 assert( conshdlrdata != NULL );
10464 SCIP_CALL(
SCIPcreateConsSOS1( scip, cons, name, nvars, vars, weights,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
FALSE,
FALSE,
FALSE,
FALSE) );
10481 assert( scip != NULL );
10482 assert( var != NULL );
10483 assert( cons != NULL );
10488 assert( conshdlr != NULL );
10496 assert( conshdlrdata != NULL );
10514 assert( scip != NULL );
10515 assert( var != NULL );
10516 assert( cons != NULL );
10521 assert( conshdlr != NULL );
10529 assert( conshdlrdata != NULL );
10545 assert( scip != NULL );
10546 assert( cons != NULL );
10556 assert( consdata != NULL );
10558 return consdata->nvars;
10570 assert( scip != NULL );
10571 assert( cons != NULL );
10581 assert( consdata != NULL );
10583 return consdata->vars;
10595 assert( scip != NULL );
10596 assert( cons != NULL );
10606 assert( consdata != NULL );
10608 return consdata->weights;
10622 assert( conshdlr != NULL );
10631 assert( conshdlrdata != NULL );
10633 return conshdlrdata->conflictgraph;
10644 assert( conshdlr != NULL );
10653 assert( conshdlrdata != NULL );
10655 return conshdlrdata->nsos1vars;
10667 assert( var != NULL );
10668 assert( conshdlr != NULL );
10677 assert( conshdlrdata != NULL );
10691 assert( conshdlr != NULL );
10692 assert( var != NULL );
10701 assert( conshdlrdata != NULL );
10703 if ( conshdlrdata->varhash == NULL )
10722 assert( conflictgraph != NULL );
10728 if ( nodedata == NULL )
10735 return nodedata->var;
10753 assert( scip != NULL );
10754 assert( conshdlr != NULL );
10755 assert( sol != NULL );
10756 assert( changed != NULL );
10757 assert( success != NULL );
10765 assert( conshdlrdata != NULL );
10769 allroundable =
FALSE;
10780 if ( conshdlrdata->switchsos1branch )
10789 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 SCIPcreateDigraph(SCIP *scip, SCIP_DIGRAPH **digraph, int nnodes)
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_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 SCIPdigraphCreate(SCIP_DIGRAPH **digraph, BMS_BLKMEM *blkmem, int nnodes)
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 SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
SCIP_DIGRAPH * SCIPgetConflictgraphSOS1(SCIP_CONSHDLR *conshdlr)
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)
void SCIPupdateSolConsViolation(SCIP *scip, SCIP_SOL *sol, SCIP_Real absviol, SCIP_Real relviol)
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)