33 #define CONSHDLR_NAME "components" 34 #define CONSHDLR_DESC "independent components constraint handler" 35 #define CONSHDLR_ENFOPRIORITY 0 36 #define CONSHDLR_CHECKPRIORITY -9999999 37 #define CONSHDLR_EAGERFREQ -1 39 #define CONSHDLR_NEEDSCONS FALSE 41 #define CONSHDLR_PROPFREQ 1 42 #define CONSHDLR_MAXPREROUNDS -1 43 #define CONSHDLR_DELAYPROP TRUE 45 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_FINAL 46 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP 48 #define DEFAULT_MAXDEPTH -1 49 #define DEFAULT_MAXINTVARS 500 50 #define DEFAULT_MINSIZE 50 51 #define DEFAULT_MINRELSIZE 0.1 52 #define DEFAULT_NODELIMIT 10000LL 53 #define DEFAULT_INTFACTOR 1.0 54 #define DEFAULT_FEASTOLFACTOR 1.0 110 struct SCIP_ConshdlrData
138 assert(elem1 !=
NULL);
139 assert(elem2 !=
NULL);
149 else if( comp2->
ncalls == 0 )
164 assert(scip !=
NULL);
183 assert(conshdlrdata !=
NULL);
185 minsize = (int)(conshdlrdata->minrelsize *
SCIPgetNVars(scip));
186 minsize =
MAX(minsize, conshdlrdata->minsize);
204 assert(scip !=
NULL);
223 component->
nvars = 0;
242 assert(component !=
NULL);
248 assert(scip !=
NULL);
290 assert(component !=
NULL);
293 assert(subscip !=
NULL);
314 assert(problem !=
NULL);
316 scip = problem->scip;
317 assert(scip !=
NULL);
322 nvars = component->
nvars;
328 for( v = 0; v < nsourcevars; ++v )
345 component->
fixedvars[idx] = sourcevars[v];
365 SCIPdebugMsg(scip,
"%d locally fixed variables have been copied, objective contribution: %g\n",
370 #ifdef SCIP_DEBUG_SOLUTION 377 assert(problem !=
NULL);
379 scip = problem->scip;
380 assert(scip !=
NULL);
391 for( i = 0; i < component->
nvars; ++i )
418 assert(conshdlrdata !=
NULL);
432 #ifdef SCIP_DEBUG_SOLUTION 454 #ifdef SCIP_DEBUG_SOLUTION 472 assert(newconshdlr !=
NULL);
475 assert(newconshdlrdata !=
NULL);
476 newconshdlrdata->subscipdepth = conshdlrdata->subscipdepth +
SCIPgetDepth(scip);
479 #ifndef SCIP_MORE_DEBUG 511 assert(scip !=
NULL);
512 assert(subscip !=
NULL);
513 assert(vars !=
NULL);
514 assert(subvars !=
NULL);
515 assert(conss !=
NULL);
516 assert(varmap !=
NULL);
517 assert(consmap !=
NULL);
518 assert(success !=
NULL);
526 for( i = 0; i <
nvars; ++i )
537 for( i = 0; i < nconss; ++i )
575 assert(component !=
NULL);
576 assert(consmap !=
NULL);
577 assert(conss !=
NULL);
578 assert(success !=
NULL);
579 assert(component->
nvars > 0);
585 assert(scip !=
NULL);
602 conss, varmap, consmap, component->
nvars, nconss, success) );
629 assert(scip !=
NULL);
630 assert(subscip !=
NULL);
642 if( softtimelimit > -0.5 )
646 softtimelimit =
MAX(softtimelimit, 0.0);
659 if( timelimit <= 0.0 || memorylimit <= 0.0)
683 #ifdef SCIP_MORE_DEBUG 704 int* ntightenedbounds,
711 assert(scip !=
NULL);
712 assert(conshdlrdata !=
NULL);
713 assert(subscip !=
NULL);
714 assert(vars !=
NULL);
715 assert(conss !=
NULL);
716 assert(ndeletedconss !=
NULL);
718 assert(ntightenedbounds !=
NULL);
719 assert(result !=
NULL);
753 for( i = 0; i <
nvars; ++i )
775 if(
SCIPisGT(scip, fixvals[i], gub) )
777 SCIPdebugMessage(
"variable <%s> fixval: %f violates global upperbound: %f\n",
782 else if(
SCIPisLT(scip, fixvals[i], glb) )
784 SCIPdebugMessage(
"variable <%s> fixval: %f violates global lowerbound: %f\n",
804 fixvals[i] =
MIN(fixvals[i], gub);
805 fixvals[i] =
MAX(fixvals[i], glb);
818 SCIPdebugMessage(
"solution violates bounds by more than epsilon, check the corrected solution...\n");
827 for( i = 0; i <
nvars; ++i )
844 SCIPdebugMessage(
"--> corrected solution is%s feasible\n", feasible ?
"" :
" not");
848 SCIPdebugMessage(
"--> corrected solution has a different objective value (old=%16.9g, corrected=%16.9g)\n",
861 for( i = 0; i <
nvars; ++i )
875 for( i = 0; i < nconss; ++i )
915 for( i = 0; i <
nvars; ++i )
917 assert(subvars[i] !=
NULL);
920 &infeasible, &tightened) );
926 &infeasible, &tightened) );
934 *ntightenedbounds += ntightened;
936 SCIPdebugMessage(
"--> tightened %d bounds of variables due to global bounds in the sub-SCIP\n", ntightened);
960 assert(component !=
NULL);
966 assert(scip !=
NULL);
969 assert(subscip !=
NULL);
990 for( v = 0; v <
nvars; ++v )
1007 SCIPdebugMessage(
"checking new solution in component <%s> inherited from problem <%s>: primal bound %.9g --> %.9g\n",
1025 if(
problem->nlowerboundinf == 0 || (
problem->nlowerboundinf == 1
1034 if(
problem->nlowerboundinf == 0 )
1049 SCIPdebugMsg(scip,
"solve sub-SCIP for component <%s> (ncalls=%d, absgap=%16.9g)\n",
1052 if( component->
ncalls == 0 )
1067 nodelimit = 2 * lastnnodes;
1068 nodelimit =
MAX(nodelimit, 10LL);
1070 if( mainnodelimit != -1 )
1072 assert(mainnodelimit >= lastnnodes);
1073 nodelimit =
MIN(nodelimit, mainnodelimit - lastnnodes);
1097 SCIPdebugMsg(scip,
"--> (status=%d, nodes=%lld, time=%.2f): gap: %12.5g%% absgap: %16.9g\n",
1168 problem->lowerbound += newdualbound;
1177 if(
problem->nlowerboundinf == 0 )
1179 SCIPdebugMessage(
"component <%s>: dual bound increased from %16.9g to %16.9g, new dual bound of problem <%s>: %16.9g (gap: %16.9g, absgap: %16.9g)\n",
1210 for( v = 0; v < component->
nvars; ++v )
1212 var = component->
vars[v];
1213 subvar = component->
subvars[v];
1214 assert(var !=
NULL);
1215 assert(subvar !=
NULL);
1225 #ifdef SCIP_MORE_DEBUG 1231 SCIPdebugMessage(
"component <%s>: primal bound decreased from %16.9g to %16.9g, new primal bound of problem <%s>: %16.9g (gap: %16.9g, absgap: %16.9g)\n",
1278 assert(scip !=
NULL);
1294 (*problem)->scip = scip;
1297 (*problem)->ncomponents = 0;
1298 (*problem)->componentssize = ncomponents;
1299 (*problem)->nlowerboundinf = ncomponents;
1300 (*problem)->nfeascomps = 0;
1301 (*problem)->nsolvedcomps = 0;
1312 for( v = 0; v <
nvars; v++ )
1338 scip = (*problem)->scip;
1339 assert(scip !=
NULL);
1342 if( (*problem)->bestsol !=
NULL )
1348 for( c = (*problem)->ncomponents - 1; c >= 0; --c )
1352 if( (*problem)->components !=
NULL )
1383 if( conshdlr ==
NULL )
1410 int* firstvaridxpercons,
1426 assert(scip !=
NULL);
1427 assert(conshdlrdata !=
NULL);
1428 assert(digraph !=
NULL);
1429 assert(conss !=
NULL);
1430 assert(vars !=
NULL);
1431 assert(firstvaridxpercons !=
NULL);
1450 for( c = 0; c < ncomponents; ++c )
1460 for( v = 0; v < ncvars; ++v )
1468 ncontvars = ncvars - nintvars - nbinvars;
1469 ndiscvars = (int)(nbinvars + conshdlrdata->intfactor * nintvars);
1470 compsize[c] = ((1000.0 * ndiscvars + (950.0 * ncontvars)/
nvars));
1473 if( ndiscvars <= conshdlrdata->maxintvars )
1477 if( ncvars >= minsize )
1487 for( c = 0; c < ncomponents; ++c )
1488 conscomponent[permu[c]] = c;
1491 for( c = 0; c <
nvars; ++c )
1492 varcomponent[c] = conscomponent[varcomponent[c]];
1501 for( c = 0; c < nconss; c++ )
1502 conscomponent[c] = (firstvaridxpercons[c] == -1 ? -1 : varcomponent[firstvaridxpercons[c]]);
1520 int* compstartsvars,
1521 int* compstartsconss,
1538 assert((*problem)->components !=
NULL);
1544 for( comp = 0; comp < ncomponents; comp++ )
1547 assert((*problem)->ncomponents == comp+1);
1549 component = &(*problem)->components[comp];
1552 compvars = &(sortedvars[compstartsvars[comp]]);
1553 component->
nvars = compstartsvars[comp + 1 ] - compstartsvars[comp];
1559 compconss = &(sortedconss[compstartsconss[comp]]);
1560 ncompconss = compstartsconss[comp + 1] - compstartsconss[comp];
1562 #ifdef DETAILED_OUTPUT 1564 if( component->
nvars > 1 && ncompconss > 1 )
1571 for( i = 0; i < component->
nvars; ++i )
1580 SCIPdebugMsg(scip,
"component %d at node %lld, depth %d (%d): %d vars (%d bin, %d int, %d cont), %d conss\n",
1582 component->
nvars, nbinvars, nintvars, ncontvars, ncompconss);
1585 assert(ncompconss > 0 || component->
nvars == 1);
1587 SCIPdebugMsg(scip,
"build sub-SCIP for component %d of problem <%s>: %d vars, %d conss\n",
1588 component->
number, (*problem)->name, component->
nvars, ncompconss);
1593 for( i = 0; i < component->
nvars; ++i )
1648 *result = subscipresult;
1651 else if( !component->
solved )
1679 int* firstvaridxpercons,
1693 assert(scip !=
NULL);
1694 assert(digraph !=
NULL);
1695 assert(conss !=
NULL);
1696 assert(firstvaridxpercons !=
NULL);
1697 assert(success !=
NULL);
1708 for( c = 0; c < nconss; ++c )
1724 if( nconsvars >
nvars )
1732 if( nconsvars ==
nvars )
1738 assert(nconsvars <
nvars);
1757 for( v = nconsvars - 1; v >= 0; --v )
1758 assert(consvars[v] !=
NULL);
1759 if( nconsvars <
nvars )
1760 assert(consvars[nconsvars] ==
NULL);
1765 assert(requiredsize <=
nvars);
1767 firstvaridxpercons[c] = -1;
1776 while( idx1 == -1 && v < nconsvars )
1780 idx1 = unfixedvarpos[idx1];
1781 assert(idx1 < nunfixedvars);
1788 firstvaridxpercons[c] = idx1;
1793 for(; v < nconsvars; ++v )
1797 idx2 = unfixedvarpos[idx2];
1798 assert(idx2 < nunfixedvars);
1827 int* compstartsvars,
1828 int* compstartsconss,
1844 assert(scip !=
NULL);
1845 assert(conshdlrdata !=
NULL);
1846 assert(sortedvars !=
NULL);
1847 assert(sortedconss !=
NULL);
1848 assert(compstartsvars !=
NULL);
1849 assert(compstartsconss !=
NULL);
1850 assert(nsortedvars !=
NULL);
1851 assert(nsortedconss !=
NULL);
1852 assert(ncomponents !=
NULL);
1853 assert(ncompsminsize !=
NULL);
1854 assert(ncompsmaxsize !=
NULL);
1869 (*nsortedconss) = 0;
1870 for( c = 0; c < ntmpconss; c++ )
1872 sortedconss[(*nsortedconss)] = tmpconss[c];
1876 if(
nvars > 1 && *nsortedconss > 1 )
1879 int* firstvaridxpercons;
1881 int nunfixedvars = 0;
1895 for( v = 0; v <
nvars; ++v )
1900 assert(nunfixedvars <= v);
1901 sortedvars[nunfixedvars] = vars[v];
1903 unfixedvarpos[v] = nunfixedvars;
1909 unfixedvarpos[v] = -1;
1913 *nsortedvars = nunfixedvars;
1915 if( nunfixedvars > 0 )
1922 SCIP_CALL(
fillDigraph(scip, digraph, sortedconss, *nsortedconss, unfixedvarpos, nunfixedvars, firstvaridxpercons, &success) );
1935 if( *ncomponents > 1 )
1937 int nconss = *nsortedconss;
1940 nvars = *nsortedvars;
1943 "cons components found %d undirected components at node %lld, depth %d (%d)\n",
1947 SCIP_CALL(
sortComponents(scip, conshdlrdata, digraph, sortedconss, sortedvars, varcomponent, conscomponent, nconss, *nsortedvars,
1948 firstvaridxpercons, ncompsminsize, ncompsmaxsize) );
1953 while( i < nconss && conscomponent[i] == -1 )
1956 for( c = 0; c < *ncomponents + 1; ++c )
1958 assert(i == nconss || conscomponent[i] >= c);
1960 compstartsconss[c] = i;
1962 while( i < nconss && conscomponent[i] == c )
1966 for( c = 0, i = 0; c < *ncomponents + 1; ++c )
1968 assert(i == nvars || varcomponent[i] >= c);
1970 compstartsvars[c] = i;
1972 while( i < nvars && varcomponent[i] == c )
1977 for( c = 0; c < *ncomponents; ++c )
1979 for( i = compstartsconss[c]; i < compstartsconss[c+1]; ++i )
1980 assert(conscomponent[i] == c);
1981 for( i = compstartsvars[c]; i < compstartsvars[c+1]; ++i )
1982 assert(varcomponent[i] == c);
2011 assert(scip !=
NULL);
2012 assert(conshdlr !=
NULL);
2031 assert(conshdlrdata !=
NULL);
2047 assert(conshdlr !=
NULL);
2049 assert(result !=
NULL);
2054 assert(conshdlrdata !=
NULL);
2059 if(
SCIPgetDepth(scip) + conshdlrdata->subscipdepth > conshdlrdata->maxdepth
2099 int* compstartsvars;
2100 int* compstartsconss;
2117 compstartsconss, &nsortedvars, &nsortedconss, &ncomponents, &ncompsminsize, &ncompsmaxsize) );
2119 if( ncompsminsize > 1 )
2123 SCIPdebugMsg(scip,
"found %d components (%d fulfulling the minsize requirement) at node %lld at depth %d (%d)\n",
2128 if( ncomponents > ncompsminsize )
2138 for( c = 0; c < ncomponents; ++c )
2140 size = compstartsvars[c+1] - compstartsvars[c];
2142 if( size >= minsize )
2145 compstartsvars[m] = compstartsvars[c+1];
2146 compstartsconss[m] = compstartsconss[c+1];
2149 else if( c == ncomponents - 1 )
2151 assert(m == ncompsminsize);
2152 compstartsvars[m] = compstartsvars[c+1];
2153 compstartsconss[m] = compstartsconss[c+1];
2156 assert(m == ncompsminsize);
2157 assert(compstartsvars[m] == nsortedvars);
2158 assert(compstartsconss[m] == nsortedconss);
2164 compstartsconss, ncomponents, &problem) );
2167 if( problem !=
NULL )
2191 if( nodelimit == -1 )
2196 if( problem !=
NULL )
2212 int* compstartsvars;
2213 int* compstartsconss;
2221 assert(conshdlr !=
NULL);
2223 assert(result !=
NULL);
2228 assert(conshdlrdata !=
NULL);
2269 compstartsconss, &nsortedvars, &nsortedconss, &ncomponents, &ncompsminsize, &ncompsmaxsize) );
2271 if( ncompsmaxsize > 0 )
2287 SCIPdebugMsg(scip,
"found %d components (%d with small size) during presolving; overall problem size: %d vars (%d int, %d bin, %d cont), %d conss\n",
2293 if( subscip ==
NULL )
2305 for( comp = 0; comp < ncompsmaxsize && !
SCIPisStopped(scip); comp++ )
2308 compvars = &(sortedvars[compstartsvars[comp]]);
2309 ncompvars = compstartsvars[comp + 1 ] - compstartsvars[comp];
2312 compconss = &(sortedconss[compstartsconss[comp]]);
2313 ncompconss = compstartsconss[comp + 1] - compstartsconss[comp];
2316 if( ncompconss == 0 )
2318 assert(ncompvars == 1);
2323 #ifdef DETAILED_OUTPUT 2330 for( i = 0; i < ncompvars; ++i )
2339 SCIPdebugMsg(scip,
"solve component %d: %d vars (%d bin, %d int, %d cont), %d conss\n",
2340 comp, ncompvars, nbinvars, nintvars, ncontvars, ncompconss);
2346 for( i = 0; i < ncompvars; ++i )
2355 compconss, varmap, consmap, ncompvars, ncompconss, &success) );
2365 ncompvars, ncompconss, ndelconss,
nfixedvars, nchgbds, result, &solved) );
2377 else if( nsolved == ncomponents - 1 )
2402 assert(conshdlr !=
NULL);
2404 assert(consdata !=
NULL);
2405 assert(*consdata !=
NULL);
2407 problem = (
PROBLEM*)(*consdata);
2420 assert(result !=
NULL );
2440 assert(nconss == 0);
2446 #define consEnfolpComponents NULL 2447 #define consEnfopsComponents NULL 2448 #define consCheckComponents NULL 2467 conshdlrdata->subscipdepth = 0;
2474 assert(conshdlr !=
NULL);
2491 "maximum depth of a node to run components detection (-1: disable component detection during solving)",
2495 "maximum number of integer (or binary) variables to solve a subproblem during presolving (-1: unlimited)",
2499 "minimum absolute size (in terms of variables) to solve a component individually during branch-and-bound",
2503 "minimum relative size (in terms of variables) to solve a component individually during branch-and-bound",
2507 "maximum number of nodes to be solved in subproblems during presolving",
2511 "the weight of an integer variable compared to binary variables",
2515 "factor to increase the feasibility tolerance of the main SCIP in all sub-SCIPs, default value 1.0",
enum SCIP_Result SCIP_RESULT
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIP_RETCODE SCIPprintBestSol(SCIP *scip, FILE *file, SCIP_Bool printzeros)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
int SCIPgetNIntVars(SCIP *scip)
void SCIPconshdlrSetData(SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata)
#define CONSHDLR_ENFOPRIORITY
int SCIPpqueueNElems(SCIP_PQUEUE *pqueue)
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
SCIP_Bool SCIPinRepropagation(SCIP *scip)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
#define DEFAULT_MAXINTVARS
#define SCIPallocBlockMemoryArray(scip, ptr, num)
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE freeProblem(PROBLEM **problem)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
static SCIP_DECL_CONSENFORELAX(consEnforelaxComponents)
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
SCIP_RETCODE SCIPupdateCutoffbound(SCIP *scip, SCIP_Real cutoffbound)
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
SCIP_RETCODE SCIPdigraphComputeUndirectedComponents(SCIP_DIGRAPH *digraph, int minsize, int *components, int *ncomponents)
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
int SCIPgetNOrigVars(SCIP *scip)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
static SCIP_DECL_CONSDELETE(consDeleteComponents)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define DEFAULT_INTFACTOR
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPprintDisplayLine(SCIP *scip, FILE *file, SCIP_VERBLEVEL verblevel, SCIP_Bool endline)
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
static SCIP_RETCODE solveSubscip(SCIP *scip, SCIP *subscip, SCIP_Longint nodelimit, SCIP_Real gaplimit)
#define CONSHDLR_EAGERFREQ
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
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)
int SCIPgetNActivePricers(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
static int getMinsize(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
enum SCIP_Retcode SCIP_RETCODE
SCIP_RETCODE SCIPdigraphSetSizes(SCIP_DIGRAPH *digraph, int *sizes)
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
int SCIPvarGetProbindex(SCIP_VAR *var)
SCIP_RETCODE SCIPincludeConshdlrComponents(SCIP *scip)
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
int SCIPdigraphGetNComponents(SCIP_DIGRAPH *digraph)
#define SCIPfreeBlockMemory(scip, ptr)
void SCIPpqueueFree(SCIP_PQUEUE **pqueue)
void SCIPdigraphGetComponent(SCIP_DIGRAPH *digraph, int compidx, int **nodes, int *nnodes)
SCIP_Real lastprimalbound
SCIP_CONS ** SCIPgetConss(SCIP *scip)
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
SCIP_RETCODE SCIPcreate(SCIP **scip)
constraint handler for handling independent components
#define SCIPallocBlockMemory(scip, ptr)
static SCIP_RETCODE freeComponent(COMPONENT *component)
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPcopyParamSettings(SCIP *sourcescip, SCIP *targetscip)
static SCIP_RETCODE solveAndEvalSubscip(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP *subscip, SCIP_VAR **vars, SCIP_VAR **subvars, SCIP_CONS **conss, int nvars, int nconss, int *ndeletedconss, int *nfixedvars, int *ntightenedbounds, SCIP_RESULT *result, SCIP_Bool *solved)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
int SCIPgetNContVars(SCIP *scip)
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 SCIPcreateOrigSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
SCIP_Real SCIPsolGetOrigObj(SCIP_SOL *sol)
#define consEnfopsComponents
const char * SCIPgetProbName(SCIP *scip)
void SCIPsortIntPtr(int *intarray, void **ptrarray, int len)
static SCIP_DECL_CONSLOCK(consLockComponents)
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
SCIP_RETCODE SCIPdigraphCreate(SCIP_DIGRAPH **digraph, int nnodes)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
#define CONSHDLR_CHECKPRIORITY
static SCIP_RETCODE copyToSubscip(SCIP *scip, SCIP *subscip, const char *name, SCIP_VAR **vars, SCIP_VAR **subvars, SCIP_CONS **conss, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, int nvars, int nconss, SCIP_Bool *success)
SCIP_Bool SCIPisPresolveFinished(SCIP *scip)
SCIP_RETCODE SCIPsolve(SCIP *scip)
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
const char * SCIPheurGetName(SCIP_HEUR *heur)
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
#define CONSHDLR_PRESOLTIMING
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyComponents)
SCIP_Real SCIPgetDualbound(SCIP *scip)
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
SCIP_STATUS SCIPgetStatus(SCIP *scip)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
const char * SCIPconsGetName(SCIP_CONS *cons)
SCIP_RETCODE SCIPcheckSolOrig(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *feasible, SCIP_Bool printreason, SCIP_Bool completely)
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
#define CONSHDLR_MAXPREROUNDS
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
SCIP_HEUR * SCIPsolGetHeur(SCIP_SOL *sol)
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
#define CONSHDLR_DELAYPROP
static SCIP_RETCODE componentSetupWorkingSol(COMPONENT *component, SCIP_HASHMAP *varmap)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
struct Component COMPONENT
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_SORTPTRCOMP(componentSort)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
SCIP_RETCODE SCIPdigraphAddArc(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
#define SCIPdebugGetSolVal(scip, var, val)
SCIP_RETCODE SCIPgetLongintParam(SCIP *scip, const char *name, SCIP_Longint *value)
struct SCIP_ConsData SCIP_CONSDATA
void * SCIPpqueueRemove(SCIP_PQUEUE *pqueue)
SCIP_RETCODE SCIPgetConsVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int varssize, SCIP_Bool *success)
SCIP_RETCODE SCIPgetConsCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_CONS *sourcecons, SCIP_CONS **targetcons, SCIP_CONSHDLR *sourceconshdlr, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *name, 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_Bool global, SCIP_Bool *valid)
SCIP_RETCODE SCIPaddConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode)
static SCIP_DECL_CONSPRESOL(consPresolComponents)
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
static SCIP_RETCODE solveComponent(COMPONENT *component, SCIP_Bool lastcomponent, SCIP_RESULT *result)
SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
SCIP_RETCODE SCIPcheckSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *feasible)
static SCIP_RETCODE findComponents(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_Real *fixedvarsobjsum, SCIP_VAR **sortedvars, SCIP_CONS **sortedconss, int *compstartsvars, int *compstartsconss, int *nsortedvars, int *nsortedconss, int *ncomponents, int *ncompsminsize, int *ncompsmaxsize)
static SCIP_RETCODE createConsComponents(SCIP *scip, SCIP_CONS **cons, const char *name, PROBLEM *problem)
int SCIPgetNImplVars(SCIP *scip)
#define SCIPduplicateMemoryArray(scip, ptr, source, num)
static SCIP_RETCODE fillDigraph(SCIP *scip, SCIP_DIGRAPH *digraph, SCIP_CONS **conss, int nconss, int *unfixedvarpos, int nunfixedvars, int *firstvaridxpercons, SCIP_Bool *success)
enum SCIP_Status SCIP_STATUS
#define DEFAULT_FEASTOLFACTOR
#define consCheckComponents
int SCIPgetDepth(SCIP *scip)
SCIP_Real SCIPgetGap(SCIP *scip)
static SCIP_RETCODE initComponent(PROBLEM *problem)
void SCIPsolSetHeur(SCIP_SOL *sol, SCIP_HEUR *heur)
#define SCIPdebugSolIsValidInSubtree(scip, isvalidinsubtree)
int SCIPvarGetNLocksUp(SCIP_VAR *var)
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
#define CONSHDLR_PROPFREQ
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
static SCIP_DECL_CONSPROP(consPropComponents)
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
int SCIPgetNSols(SCIP *scip)
#define SCIPfreeMemoryArray(scip, ptr)
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
SCIP_RETCODE SCIPfixParam(SCIP *scip, const char *name)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
int SCIPgetNBinVars(SCIP *scip)
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
SCIP_Bool SCIPinProbing(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
SCIP_RETCODE SCIPupdateLocalLowerbound(SCIP *scip, SCIP_Real newbound)
SCIP_RETCODE SCIPaddSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *stored)
SCIP_RETCODE SCIPcopyProb(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, const char *name)
int SCIPvarGetNLocksDown(SCIP_VAR *var)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
SCIP_RETCODE SCIPpqueueInsert(SCIP_PQUEUE *pqueue, void *elem)
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_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
SCIP_RETCODE SCIPpqueueCreate(SCIP_PQUEUE **pqueue, int initsize, SCIP_Real sizefac, SCIP_DECL_SORTPTRCOMP((*ptrcomp)))
int SCIPgetNConss(SCIP *scip)
static SCIP_RETCODE componentCreateSubscip(COMPONENT *component, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_CONS **conss, int nconss, SCIP_Bool *success)
static SCIP_RETCODE sortComponents(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_DIGRAPH *digraph, SCIP_CONS **conss, SCIP_VAR **vars, int *varcomponent, int *conscomponent, int nconss, int nvars, int *firstvaridxpercons, int *ncompsminsize, int *ncompsmaxsize)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
SCIP_Real fixedvarsobjsum
SCIP_Bool SCIPallowDualReds(SCIP *scip)
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
static SCIP_DECL_CONSINITSOL(consInitsolComponents)
#define DEFAULT_MINRELSIZE
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
static SCIP_RETCODE createAndSplitProblem(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_Real fixedvarsobjsum, SCIP_VAR **sortedvars, SCIP_CONS **sortedconss, int *compstartsvars, int *compstartsconss, int ncomponents, PROBLEM **problem)
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
SCIP_Bool SCIPisStopped(SCIP *scip)
static SCIP_RETCODE solveProblem(PROBLEM *problem, SCIP_RESULT *result)
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
#define DEFAULT_NODELIMIT
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
int SCIPvarGetIndex(SCIP_VAR *var)
#define SCIPdebugAddSolVal(scip, var, val)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE initProblem(SCIP *scip, PROBLEM **problem, SCIP_Real fixedvarsobjsum, int ncomponents)
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
static SCIP_DECL_CONSFREE(conshdlrFreeComponents)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
#define CONSHDLR_NEEDSCONS
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
#define BMSclearMemoryArray(ptr, num)
SCIP_Bool SCIPisSumLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define CONSHDLR_PROP_TIMING
void SCIPaddNNodes(SCIP *scip, SCIP_Longint nnodes)
void SCIPdigraphFree(SCIP_DIGRAPH **digraph)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
#define SCIPdebugSolEnable(scip)
SCIP_RETCODE SCIPgetActiveVars(SCIP *scip, SCIP_VAR **vars, int *nvars, int varssize, int *requiredsize)
#define consEnfolpComponents
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
static SCIP_RETCODE createSubscip(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP **subscip)
int SCIPsolGetIndex(SCIP_SOL *sol)
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_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
SCIP_RETCODE SCIPcopyPlugins(SCIP *sourcescip, SCIP *targetscip, SCIP_Bool copyreaders, SCIP_Bool copypricers, SCIP_Bool copyconshdlrs, SCIP_Bool copyconflicthdlrs, SCIP_Bool copypresolvers, SCIP_Bool copyrelaxators, SCIP_Bool copyseparators, SCIP_Bool copypropagators, SCIP_Bool copyheuristics, SCIP_Bool copyeventhdlrs, SCIP_Bool copynodeselectors, SCIP_Bool copybranchrules, SCIP_Bool copydisplays, SCIP_Bool copydialogs, SCIP_Bool copynlpis, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
SCIP_Bool SCIPallowObjProp(SCIP *scip)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
#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)