61#define HEUR_NAME "shiftandpropagate"
62#define HEUR_DESC "Pre-root heuristic to expand an auxiliary branch-and-bound tree and apply propagation techniques"
63#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_PROP
64#define HEUR_PRIORITY 1000
67#define HEUR_MAXDEPTH -1
68#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
69#define HEUR_USESSUBSCIP FALSE
71#define DEFAULT_WEIGHT_INEQUALITY 1
72#define DEFAULT_WEIGHT_EQUALITY 3
73#define DEFAULT_RELAX TRUE
74#define DEFAULT_PROBING TRUE
75#define DEFAULT_ONLYWITHOUTSOL TRUE
76#define DEFAULT_NPROPROUNDS 10
77#define DEFAULT_PROPBREAKER 65000
78#define DEFAULT_CUTOFFBREAKER 15
79#define DEFAULT_RANDSEED 29
80#define DEFAULT_SORTKEY 'v'
81#define DEFAULT_SORTVARS TRUE
82#define DEFAULT_COLLECTSTATS TRUE
83#define DEFAULT_STOPAFTERFEASIBLE TRUE
84#define DEFAULT_PREFERBINARIES TRUE
85#define DEFAULT_SELECTBEST FALSE
86#define DEFAULT_MAXCUTOFFQUOT 0.0
87#define SORTKEYS "nrtuv"
89#define DEFAULT_NOZEROFIXING FALSE
90#define DEFAULT_FIXBINLOCKS TRUE
91#define DEFAULT_BINLOCKSFIRST FALSE
92#define DEFAULT_NORMALIZE TRUE
93#define DEFAULT_UPDATEWEIGHTS FALSE
94#define DEFAULT_IMPLISCONTINUOUS TRUE
95#define DEFAULT_MINFIXINGRATELP 0.0
97#define EVENTHDLR_NAME "eventhdlrshiftandpropagate"
98#define EVENTHDLR_DESC "event handler to catch bound changes"
99#define EVENTTYPE_SHIFTANDPROPAGATE (SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_GBDCHANGED)
114 SCIP_Bool onlywithoutsol;
121 SCIP_Real maxcutoffquot;
122 SCIP_Real minfixingratelp;
125 SCIP_Bool collectstats;
126 SCIP_Bool stopafterfeasible;
128 SCIP_Bool preferbinaries;
129 SCIP_Bool nozerofixing;
130 SCIP_Bool fixbinlocks;
131 SCIP_Bool binlocksfirst;
133 SCIP_Bool updateweights;
134 SCIP_Bool impliscontinuous;
135 SCIP_Bool selectbest;
138 SCIP_Longint ntotaldomredsfound;
139 SCIP_Longint nlpiters;
157struct ConstraintMatrix
159 SCIP_Real* rowmatvals;
162 SCIP_Real* colmatvals;
170 SCIP_Real* upperbounds;
171 SCIP_Real* transformshiftvals;
176 SCIP_Bool normalized;
180struct SCIP_EventhdlrData
201 SCIP_Bool impliscontinuous
211 SCIP_Bool impliscontinuous
222 SCIP_Real** valpointer,
232 assert(0 <= rowindex && rowindex < matrix->nrows);
234 arrayposition = matrix->rowmatbegin[rowindex];
236 if ( nrowvals !=
NULL )
238 if( rowindex == matrix->nrows - 1 )
239 *nrowvals = matrix->nnonzs - arrayposition;
241 *nrowvals = matrix->rowmatbegin[rowindex + 1] - arrayposition;
244 if( valpointer !=
NULL )
245 *valpointer = &(matrix->rowmatvals[arrayposition]);
246 if( indexpointer !=
NULL )
247 *indexpointer = &(matrix->rowmatind[arrayposition]);
250 *lhs = matrix->lhs[rowindex];
253 *rhs = matrix->rhs[rowindex];
261 SCIP_Real** valpointer,
269 assert(0 <= colindex && colindex < matrix->ncols);
271 arrayposition = matrix->colmatbegin[colindex];
273 if( ncolvals !=
NULL )
275 if( colindex == matrix->ncols - 1 )
276 *ncolvals = matrix->nnonzs - arrayposition;
278 *ncolvals = matrix->colmatbegin[colindex + 1] - arrayposition;
280 if( valpointer !=
NULL )
281 *valpointer = &(matrix->colmatvals[arrayposition]);
283 if( indexpointer !=
NULL )
284 *indexpointer = &(matrix->colmatind[arrayposition]);
325 assert(matrix->normalized);
327 for(
r = 0;
r < ncolvals; ++
r )
332 SCIP_Real lhsvarbound;
333 SCIP_Real rhsvarbound;
350 assert(0 <= rowindex && rowindex < matrix->nrows);
370 matrix->lhs[rowindex] -= colval * lhsvarbound;
375 matrix->rhs[rowindex] -= colval * rhsvarbound;
379 SCIPdebugMsg(
scip,
"Row <%s> changed:Coefficient <%g>, LHS <%g> --> <%g>, RHS <%g> --> <%g>\n",
380 SCIProwGetName(colrow), colval, lhs, matrix->lhs[rowindex], rhs, matrix->rhs[rowindex]);
406 SCIP_Bool negatecoeffs;
407 SCIP_Real deltashift;
410 assert(0 <= colpos && colpos < heurdata->nlpcols);
421 negatecoeffs =
FALSE;
431 deltashift = matrix->transformshiftvals[colpos];
432 matrix->transformshiftvals[colpos] = 0.0;
441 matrix->transformshiftvals[colpos] = lb;
450 matrix->transformshiftvals[colpos] = ub;
476 for(
i = 0;
i < nrows; ++
i )
478 int rowpos = rows[
i];
480 assert(rowpos < matrix->nrows);
483 matrix->lhs[rowpos] -= (vals[
i]) * deltashift;
486 matrix->rhs[rowpos] -= (vals[
i]) * deltashift;
489 (vals[
i]) = -(vals[
i]);
494 SCIPdebugMsg(
scip,
"Variable <%s> at colpos %d transformed. Status %d LB <%g> --> <%g>, UB <%g> --> <%g>\n",
495 SCIPvarGetName(
var), colpos, matrix->transformstatus[colpos], lb, 0.0, ub, matrix->upperbounds[colpos]);
510 SCIP_Bool* initialized,
511 SCIP_Bool* infeasible
516 SCIP_Bool impliscontinuous;
530 SCIPdebugMsg(
scip,
"entering Matrix Initialization method of SHIFTANDPROPAGATE heuristic!\n");
537 matrix->nrows = nrows;
539 matrix->normalized =
FALSE;
540 matrix->ndiscvars = 0;
542 impliscontinuous =
heurdata->impliscontinuous;
545 for( j = 0; j < ncols; ++j )
557 matrix->ncols = matrix->ndiscvars;
559 if( matrix->nnonzs == 0 )
561 SCIPdebugMsg(
scip,
"No matrix entries - Terminating initialization of matrix.\n");
563 *initialized =
FALSE;
584 for( j = 0; j < matrix->ndiscvars; ++j )
593 for(
i = 0;
i < nrows; ++
i )
614 matrix->rowmatbegin[
i] = currentpointer;
635 matrix->lhs[
i] /= maxval;
637 matrix->rhs[
i] /= maxval;
644 SCIPdebugMsg(
scip,
" Matrix initialization stopped because of row infeasibility! \n");
649 for( j = 0; j < nrowlpnonz; ++j )
654 assert(currentpointer < matrix->nnonzs);
656 matrix->rowmatvals[currentpointer] = rowvals[j];
658 matrix->rowmatvals[currentpointer] /= maxval;
666 matrix->normalized =
TRUE;
671 assert(currentpointer == matrix->nnonzs);
676 for( j = 0; j < matrix->ncols; ++j )
685 currentcol = lpcols[j];
691 matrix->colnorms[j] = ncolnonz;
693 *nmaxrows =
MAX(*nmaxrows, ncolnonz);
696 matrix->colmatbegin[j] = currentpointer;
698 for(
i = 0;
i < ncolnonz; ++
i )
705 assert(currentpointer < matrix->nnonzs);
712 matrix->colmatvals[currentpointer] = colvals[
i];
714 matrix->colmatvals[currentpointer] /= maxval;
719 matrix->colnorms[j] +=
ABS(matrix->colmatvals[currentpointer]);
723 assert(currentpointer == matrix->nnonzs);
726 for( j = 0; j < (relax ? ncols : matrix->ndiscvars); ++j )
733 matrix->transformshiftvals[j] = 0.0;
746 SCIPdebugMsg(
scip,
"Matrix initialized for %d discrete variables with %d cols, %d rows and %d nonzero entries\n",
747 matrix->ndiscvars, matrix->ncols, matrix->nrows, matrix->nnonzs);
762 if( (*matrix)->nnonzs > 0 )
774 assert((*matrix)->transformshiftvals !=
NULL);
791 (*matrix)->nrows = 0;
792 (*matrix)->ncols = 0;
809 SCIP_Bool updateweights
827 assert(*nviolatedrows < matrix->nrows);
829 violatedrows[*nviolatedrows] = rowindex;
830 violatedrowpos[rowindex] = *nviolatedrows;
833 ++rowweights[rowindex];
841 if( violatedrowpos[rowindex] != *nviolatedrows - 1 )
843 assert(*nviolatedrows - 1 >= 0);
844 violatedrows[violatedrowpos[rowindex]] = violatedrows[*nviolatedrows - 1];
845 violatedrowpos[violatedrows[*nviolatedrows - 1]] = violatedrowpos[rowindex];
849 violatedrowpos[rowindex] = -1;
855 for(
c = 0;
c < ncols; ++
c )
857 matrix->violrows[cols[
c]] += violadd;
858 assert(matrix->violrows[cols[
c]] >= 0);
874 SCIP_Bool updateweights
885 assert(-1 <= colidx && colidx < matrix->ncols);
892 nrows = matrix->nrows;
897 for(
i = 0;
i < nrows; ++
i )
898 violatedrowpos[
i] = -1;
904 assert(colidx < 0 || *nviolatedrows >= 0);
907 for(
i = 0;
i < nrows; ++
i )
913 rowpos = rowindices[
i];
918 checkRowViolation(
scip, matrix, rowpos, violatedrows, violatedrowpos, nviolatedrows, rowweights, updateweights);
940 status = matrix->transformstatus[varindex];
948 return solvalue + matrix->transformshiftvals[varindex];
953 return matrix->transformshiftvals[varindex] - solvalue;
968 int* violationchange,
976 SCIP_Real slacksurplus;
977 SCIP_Real upperbound;
990 assert(direction == 1 || direction == -1);
992 upperbound = matrix->upperbounds[varindex];
1002 for(
i = 0;
i < nrows; ++
i )
1008 SCIP_Bool rowisviolated;
1014 lhs = matrix->lhs[rowpos];
1015 rhs = matrix->rhs[rowpos];
1016 rowweight = rowweights[rowpos];
1017 val = direction * vals[
i];
1025 if( !rowisviolated )
1027 SCIP_Real maxfeasshift;
1043 slacksurplus += val;
1045 slacksurplus -= val;
1050 steps[
i] = maxfeasshift + 1.0;
1051 violationchange[
i] = rowweight;
1056 steps[
i] = upperbound;
1057 violationchange[
i] = 0;
1065 SCIP_Real minfeasshift;
1082 steps[
i] = minfeasshift;
1083 violationchange[
i] = -rowweight;
1088 steps[
i] = upperbound;
1089 violationchange[
i] = 0;
1100 *beststep = direction * upperbound;
1122 sum += violationchange[
i];
1127 if( (
i == nrows-1 || steps[
i+1] > steps[
i]) && sum < *rowviolations )
1129 *rowviolations = sum;
1130 *beststep = direction * steps[
i];
1133 assert(*rowviolations <= 0);
1152 int* violatedrowpos,
1157 SCIP_Real deltashift;
1158 SCIP_Bool checkviolations;
1162 assert(0 <= varindex && varindex < matrix->ndiscvars);
1166 status = matrix->transformstatus[varindex];
1168 SCIPdebugMsg(
scip,
" Variable <%d> [%g,%g], status %d(%g), ub %g \n", varindex, lb, ub, status,
1169 matrix->transformshiftvals[varindex], matrix->upperbounds[varindex]);
1171 checkviolations =
FALSE;
1179 checkviolations =
TRUE;
1183 deltashift = lb - (matrix->transformshiftvals[varindex]);
1184 matrix->transformshiftvals[varindex] = lb;
1186 matrix->upperbounds[varindex] = ub - lb;
1195 checkviolations =
TRUE;
1199 deltashift = (matrix->transformshiftvals[varindex]) - ub;
1200 matrix->transformshiftvals[varindex] = ub;
1216 checkviolations =
TRUE;
1225 SCIPerrorMessage(
"Error: Invalid variable status <%d> in shift and propagagate heuristic, aborting!\n", status);
1243 for(
i = 0;
i < nrows; ++
i )
1245 SCIPdebugMsg(
scip,
" update slacks of row<%d>: coefficient <%g>, %g <= 0 <= %g \n",
1246 rows[
i], vals[
i], matrix->lhs[rows[
i]], matrix->rhs[rows[
i]]);
1249 matrix->lhs[rows[
i]] -= (vals[
i]) * deltashift;
1252 matrix->rhs[rows[
i]] -= (vals[
i]) * deltashift;
1254 checkviolations =
TRUE;
1258 if( checkviolations )
1261 SCIPdebugMsg(
scip,
" Variable <%d> [%g,%g], status %d(%g), ub %g \n", varindex, lb, ub, status,
1262 matrix->transformshiftvals[varindex], matrix->upperbounds[varindex]);
1351 " DETAILS : %d violations left, %d probing status\n",
1444 SCIP_Real* colnorms;
1447 int* violationchange;
1450 int* violatedrowpos;
1452 int* violatedvarrows;
1457 int lastindexofsusp;
1471 SCIP_Bool initialized;
1474 SCIP_Bool infeasible;
1475 SCIP_Bool impliscontinuous;
1487 SCIPdebugMsg(
scip,
"entering execution method of shift and propagate heuristic\n");
1524 if(
nlprows == 0 || nlpcols == 0 )
1528 initialized =
FALSE;
1534 impliscontinuous =
heurdata->impliscontinuous;
1552 for(
c = 0;
c < nlpcols; ++
c )
1601 if( !initialized || infeasible )
1603 SCIPdebugMsg(
scip,
" MATRIX not initialized -> Execution of heuristic stopped! \n");
1610 if( matrix->ndiscvars < ndiscvars )
1612 SCIPdebugMsg(
scip,
"Not all discrete variables are in the current LP. Shiftandpropagate execution terminated.\n");
1618 eventhdlrdata->matrix = matrix;
1619 eventhdlrdata->heurdata =
heurdata;
1636 eventhdlrdata->violatedrows = violatedrows;
1637 eventhdlrdata->violatedrowpos = violatedrowpos;
1638 eventhdlrdata->nviolatedrows = &nviolatedrows;
1641 for(
i = 0;
i < ndiscvars; ++
i )
1645 for(
r = 0;
r < matrix->nrows; ++
r )
1652 colnorms = matrix->colnorms;
1667 violatedvarrows =
NULL;
1689 SCIPdebugMsg(
scip,
"Variables sorted down w.r.t their normalized columns!\n");
1721 SCIPdebugMsg(
scip,
"Variables sorted down w.r.t their number of currently infeasible rows!\n");
1738 SCIPdebugMsg(
scip,
"Variables sorted (upwards) w.r.t their number of currently infeasible rows!\n");
1766 int nbinwithoutlocks = 0;
1781 for(
c = 0;
c < ndiscvars; ++
c )
1793 if( nbinwithoutlocks > 0 )
1801 while(
c < nbinwithoutlocks &&
b < ndiscvars )
1814 if(
c >= nbinwithoutlocks )
1818 if(
c >= nbinwithoutlocks )
1836 tmp = permutation[
b];
1837 permutation[
b] = permutation[
c];
1838 permutation[
c] = tmp;
1847 for(
c = 0;
c < ndiscvars; ++
c )
1860 for(
c = 0;
c < matrix->ndiscvars; ++
c )
1871 eventdatas[
c]->colpos =
c;
1878 lastindexofsusp = -1;
1882 SCIPdebugMsg(
scip,
"SHIFT_AND_PROPAGATE heuristic starts main loop with %d violations and %d remaining variables!\n",
1883 nviolatedrows, ndiscvars);
1885 assert(matrix->ndiscvars == ndiscvars);
1888 for(
c = 0;
c < ndiscvars; ++
c )
1891 SCIP_Longint ndomredsfound;
1892 SCIP_Real optimalshiftvalue;
1893 SCIP_Real origsolval;
1897 int permutedvarindex;
1899 SCIP_Bool marksuspicious;
1904 while( j < ndiscvars )
1907 if( matrix->violrows[permutation[
c]] < matrix->violrows[permutation[j]] )
1910 tmp = permutation[
c];
1911 permutation[
c] = permutation[j];
1912 permutation[j] = tmp;
1917 permutedvarindex = permutation[
c];
1918 optimalshiftvalue = 0.0;
1942 SCIPdebugMsg(
scip,
"Variable %s with local bounds [%g,%g], status <%d>, matrix bound <%g>\n",
1943 SCIPvarGetName(
var), lb, ub, matrix->transformstatus[permutedvarindex], matrix->upperbounds[permutedvarindex]);
1956 marksuspicious =
FALSE;
1976 if( !
heurdata->stopafterfeasible || nviolatedrows > 0 )
1980 &optimalshiftvalue, &nviolations) );
1986 SCIP_Real downshiftvalue;
1987 int ndownviolations;
1989 downshiftvalue = 0.0;
1990 ndownviolations = 0;
1992 &downshiftvalue, &ndownviolations) );
1997 if( ndownviolations < nviolations )
1999 optimalshiftvalue = downshiftvalue;
2004 optimalshiftvalue = 0.0;
2008 marksuspicious =
TRUE;
2025 if( !marksuspicious && probing )
2036 SCIPdebugMsg(
scip,
" Shift %g(%g originally) is optimal, propagate solution\n", optimalshiftvalue, origsolval);
2116 marksuspicious =
TRUE;
2120 if( marksuspicious )
2123 assert(permutedvarindex == permutation[
c]);
2126 assert(lastindexofsusp >= 0 && lastindexofsusp <=
c);
2128 permutation[
c] = permutation[lastindexofsusp];
2129 permutation[lastindexofsusp] = permutedvarindex;
2131 SCIPdebugMsg(
scip,
" Suspicious variable! Postponed from pos <%d> to position <%d>\n",
c, lastindexofsusp);
2135 SCIPdebugMsg(
scip,
"Variable <%d><%s> successfully shifted by value <%g>!\n", permutedvarindex,
2148 SCIPdebugMsg(
scip,
"Heuristic finished with %d remaining violations and %d remaining variables!\n",
2149 nviolatedrows, lastindexofsusp + 1);
2154 if( nviolatedrows == 0 && !
cutoff )
2160 for( v = 0; v <= lastindexofsusp; ++v )
2163 SCIP_Real origsolval;
2164 int permutedvarindex;
2167 permutedvarindex = permutation[v];
2189 if( nviolatedrows > 0 )
2195 if( nlpcols != matrix->ndiscvars )
2200 int nfixedvars = ndiscvars;
2205 for( v = ndiscvars; v <
nvars && nfixedvars < nminfixings; ++v )
2211 solvelp = (nfixedvars >= nminfixings);
2213 SCIPdebugMsg(
scip,
"Fixed %d of %d (%.1f %%) variables after probing -> %s\n",
2214 nfixedvars,
nvars, (100.0 * nfixedvars / (SCIP_Real)
nvars),
2215 solvelp ?
"continue and solve LP for remaining variables" :
"terminate without LP");
2237 for( v = 0; v < ndiscvars; ++v )
2254 if( nunfixedcols > 0.5 * ncols )
2257 "Heuristic " HEUR_NAME " solving LP from scratch with %.1f %% unfixed columns (%d of %d) ...\n",
2258 100.0 * (nunfixedcols / (SCIP_Real)ncols), nunfixedcols, ncols);
2278 SCIPwarningMessage(
scip,
"Error while solving LP in SHIFTANDPROPAGATE heuristic; LP solve terminated with code <%d>\n",
2307 SCIP_Bool printreason;
2308 SCIP_Bool completely;
2312 printreason =
FALSE;
2335 SCIPdebugMsg(
scip,
"Solution constructed by heuristic is already known to be infeasible\n");
2342 for(
c = matrix->ndiscvars - 1;
c >= 0; --
c )
2355 if( violatedvarrows !=
NULL )
2369 eventhdlrdata->nviolatedrows =
NULL;
2370 eventhdlrdata->violatedrowpos =
NULL;
2371 eventhdlrdata->violatedrows =
NULL;
2385 eventhdlrdata->matrix =
NULL;
2411 matrix = eventhdlrdata->matrix;
2413 heurdata = eventhdlrdata->heurdata;
2416 colpos = eventdata->colpos;
2418 assert(0 <= colpos && colpos < matrix->ndiscvars);
2427 eventhdlrdata->violatedrowpos, eventhdlrdata->nviolatedrows) );
2447 eventhandlerdata->matrix =
NULL;
2451 eventExecShiftandpropagate, eventhandlerdata) );
2475 "The number of propagation rounds used for each propagation",
2482 "Should heuristic only be executed if no primal solution was found, yet?",
2487 "the key for variable sorting: (n)orms down, norms (u)p, (v)iolations down, viola(t)ions up, or (r)andom",
2494 "Should the heuristic stop calculating optimal shift values when no more rows are violated?",
2497 "Should binary variables be shifted first?",
2500 "should variables with a zero shifting value be delayed instead of being fixed?",
2503 "should binary variables with no locks in one direction be fixed to that direction?",
2506 "should binary variables with no locks be preferred in the ordering?",
2509 "should coefficients and left/right hand sides be normalized by max row coeff?",
2512 "should row weight be increased every time the row is violated?",
2515 "should implicit integer variables be treated as continuous variables?",
2518 "should the heuristic choose the best candidate in every round? (set to FALSE for static order)?",
2521 "maximum percentage of allowed cutoffs before stopping the heuristic",
2524 "minimum fixing rate over all variables (including continuous) to solve LP",
#define SCIP_MAXTREEDEPTH
#define SCIP_LONGINT_FORMAT
SCIP_Bool SCIPisStopped(SCIP *scip)
int SCIPgetNContVars(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
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)
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 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 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)
void SCIPrandomPermuteIntArray(SCIP_RANDNUMGEN *randnumgen, int *array, int begin, int end)
SCIP_RETCODE SCIPincludeHeurShiftandpropagate(SCIP *scip)
int SCIPcolGetLPPos(SCIP_COL *col)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
int SCIPcolGetNLPNonz(SCIP_COL *col)
SCIP_Bool SCIPcolIsInLP(SCIP_COL *col)
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
SCIP_EVENTHDLRDATA * SCIPeventhdlrGetData(SCIP_EVENTHDLR *eventhdlr)
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur,)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur,)
const char * SCIPheurGetName(SCIP_HEUR *heur)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
SCIP_RETCODE SCIPflushLP(SCIP *scip)
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
SCIP_RETCODE SCIPconstructLP(SCIP *scip, SCIP_Bool *cutoff)
SCIP_Bool SCIPisLPConstructed(SCIP *scip)
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
int SCIPgetNLPRows(SCIP *scip)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
int SCIPgetNUnfixedLPCols(SCIP *scip)
int SCIPgetNLPCols(SCIP *scip)
SCIP_RETCODE SCIPwriteLP(SCIP *scip, const char *filename)
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
#define SCIPfreeBuffer(scip, ptr)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBuffer(scip, ptr)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPfreeBlockMemoryNull(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
int SCIPgetProbingDepth(SCIP *scip)
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
char * SCIPsnprintfProbingStats(SCIP *scip, char *strbuf, int len)
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
int SCIProwGetNLPNonz(SCIP_ROW *row)
int SCIProwGetLPPos(SCIP_ROW *row)
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
const char * SCIProwGetName(SCIP_ROW *row)
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
void SCIPsolSetHeur(SCIP_SOL *sol, SCIP_HEUR *heur)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
int SCIPgetDepth(SCIP *scip)
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
void SCIPdisableVarHistory(SCIP *scip)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
void SCIPenableVarHistory(SCIP *scip)
SCIP_Bool SCIPvarIsInLP(SCIP_VAR *var)
void SCIPsortDownIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIPfreeSol(scip, &heurdata->sol))
SCIPcreateSol(scip, &heurdata->sol, heur))
SCIPfreeRandom(scip, &heurdata->randnumgen)
static SCIP_LPSOLSTAT lpsolstat
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
assert(minobj< SCIPgetCutoffbound(scip))
SCIPlinkLPSol(scip, sol))
#define DEFAULT_ONLYWITHOUTSOL
#define DEFAULT_NORMALIZE
static void transformVariable(SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_HEURDATA *heurdata, int colpos)
static SCIP_RETCODE getOptimalShiftingValue(SCIP *scip, CONSTRAINTMATRIX *matrix, int varindex, int direction, int *rowweights, SCIP_Real *steps, int *violationchange, SCIP_Real *beststep, int *rowviolations)
static void getRowData(CONSTRAINTMATRIX *matrix, int rowindex, SCIP_Real **valpointer, SCIP_Real *lhs, SCIP_Real *rhs, int **indexpointer, int *nrowvals)
static void checkRowViolation(SCIP *scip, CONSTRAINTMATRIX *matrix, int rowindex, int *violatedrows, int *violatedrowpos, int *nviolatedrows, int *rowweights, SCIP_Bool updateweights)
#define DEFAULT_MINFIXINGRATELP
static SCIP_Bool colIsDiscrete(SCIP_COL *col, SCIP_Bool impliscontinuous)
#define DEFAULT_PROPBREAKER
#define DEFAULT_IMPLISCONTINUOUS
#define DEFAULT_PREFERBINARIES
#define DEFAULT_NPROPROUNDS
#define DEFAULT_FIXBINLOCKS
static void freeMatrix(SCIP *scip, CONSTRAINTMATRIX **matrix)
#define DEFAULT_SELECTBEST
static void relaxVar(SCIP *scip, SCIP_VAR *var, CONSTRAINTMATRIX *matrix, SCIP_Bool normalize)
#define DEFAULT_BINLOCKSFIRST
static SCIP_RETCODE updateTransformation(SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_HEURDATA *heurdata, int varindex, SCIP_Real lb, SCIP_Real ub, int *violatedrows, int *violatedrowpos, int *nviolatedrows)
#define DEFAULT_MAXCUTOFFQUOT
#define DEFAULT_CUTOFFBREAKER
static SCIP_RETCODE initMatrix(SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_HEURDATA *heurdata, int *colposs, SCIP_Bool normalize, int *nmaxrows, SCIP_Bool relax, SCIP_Bool *initialized, SCIP_Bool *infeasible)
enum TransformStatus TRANSFORMSTATUS
#define DEFAULT_WEIGHT_INEQUALITY
#define DEFAULT_NOZEROFIXING
static void checkViolations(SCIP *scip, CONSTRAINTMATRIX *matrix, int colidx, int *violatedrows, int *violatedrowpos, int *nviolatedrows, int *rowweights, SCIP_Bool updateweights)
#define DEFAULT_UPDATEWEIGHTS
#define DEFAULT_COLLECTSTATS
static SCIP_Real retransformVariable(SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_VAR *var, int varindex, SCIP_Real solvalue)
static SCIP_Bool varIsDiscrete(SCIP_VAR *var, SCIP_Bool impliscontinuous)
struct ConstraintMatrix CONSTRAINTMATRIX
#define DEFAULT_WEIGHT_EQUALITY
static void getColumnData(CONSTRAINTMATRIX *matrix, int colindex, SCIP_Real **valpointer, int **indexpointer, int *ncolvals)
#define DEFAULT_STOPAFTERFEASIBLE
#define EVENTTYPE_SHIFTANDPROPAGATE
preroot heuristic that alternatingly fixes variables and propagates domains
memory allocation routines
#define BMScopyMemoryArray(ptr, source, num)
#define BMSclearMemoryArray(ptr, num)
public methods for managing events
public methods for primal heuristics
public methods for LP management
public methods for message output
#define SCIPstatisticMessage
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for primal CIP solutions
public methods for problem variables
public methods for event handler plugins and event handlers
public methods for primal heuristic plugins and divesets
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for the probing mode
public methods for random numbers
public methods for solutions
public methods for querying solving statistics
public methods for the branch-and-bound tree
public methods for SCIP variables
struct SCIP_EventData SCIP_EVENTDATA
struct SCIP_EventhdlrData SCIP_EVENTHDLRDATA
#define SCIP_DECL_EVENTEXEC(x)
#define SCIP_DECL_HEURCOPY(x)
struct SCIP_HeurData SCIP_HEURDATA
#define SCIP_DECL_HEURINIT(x)
#define SCIP_DECL_HEUREXIT(x)
#define SCIP_DECL_HEURFREE(x)
#define SCIP_DECL_HEUREXEC(x)
enum SCIP_LPSolStat SCIP_LPSOLSTAT
@ SCIP_LPSOLSTAT_NOTSOLVED
#define SCIP_DECL_SORTPTRCOMP(x)
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_CONTINUOUS
enum SCIP_Vartype SCIP_VARTYPE