29 #define HEUR_NAME "shiftandpropagate" 30 #define HEUR_DESC "Pre-root heuristic to expand an auxiliary branch-and-bound tree and apply propagation techniques" 31 #define HEUR_DISPCHAR 'T' 32 #define HEUR_PRIORITY 1000 34 #define HEUR_FREQOFS 0 35 #define HEUR_MAXDEPTH -1 36 #define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE 37 #define HEUR_USESSUBSCIP FALSE 39 #define DEFAULT_WEIGHT_INEQUALITY 1 40 #define DEFAULT_WEIGHT_EQUALITY 3 41 #define DEFAULT_RELAX TRUE 42 #define DEFAULT_PROBING TRUE 43 #define DEFAULT_ONLYWITHOUTSOL TRUE 44 #define DEFAULT_NPROPROUNDS 10 45 #define DEFAULT_PROPBREAKER 65000 46 #define DEFAULT_CUTOFFBREAKER 15 47 #define DEFAULT_RANDSEED 29 48 #define DEFAULT_SORTKEY 'v' 49 #define DEFAULT_SORTVARS TRUE 50 #define DEFAULT_COLLECTSTATS TRUE 51 #define DEFAULT_STOPAFTERFEASIBLE TRUE 52 #define DEFAULT_PREFERBINARIES TRUE 53 #define DEFAULT_SELECTBEST FALSE 54 #define DEFAULT_MAXCUTOFFQUOT 0.0 55 #define SORTKEYS "nrtuv" 57 #define DEFAULT_NOZEROFIXING FALSE 58 #define DEFAULT_FIXBINLOCKS TRUE 59 #define DEFAULT_BINLOCKSFIRST FALSE 60 #define DEFAULT_NORMALIZE TRUE 61 #define DEFAULT_UPDATEWEIGHTS FALSE 62 #define DEFAULT_IMPLISCONTINUOUS TRUE 64 #define EVENTHDLR_NAME "eventhdlrshiftandpropagate" 65 #define EVENTHDLR_DESC "event handler to catch bound changes" 66 #define EVENTTYPE_SHIFTANDPROPAGATE (SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_GBDCHANGED) 123 struct ConstraintMatrix
144 typedef struct ConstraintMatrix CONSTRAINTMATRIX;
146 struct SCIP_EventhdlrData
148 CONSTRAINTMATRIX* matrix;
155 struct SCIP_EventData
186 CONSTRAINTMATRIX* matrix,
197 assert(matrix != NULL);
198 assert(0 <= rowindex && rowindex < matrix->nrows);
200 arrayposition = matrix->rowmatbegin[rowindex];
202 if ( nrowvals != NULL )
204 if( rowindex == matrix->nrows - 1 )
205 *nrowvals = matrix->nnonzs - arrayposition;
207 *nrowvals = matrix->rowmatbegin[rowindex + 1] - arrayposition;
210 if( valpointer != NULL )
211 *valpointer = &(matrix->rowmatvals[arrayposition]);
212 if( indexpointer != NULL )
213 *indexpointer = &(matrix->rowmatind[arrayposition]);
216 *lhs = matrix->lhs[rowindex];
219 *rhs = matrix->rhs[rowindex];
225 CONSTRAINTMATRIX* matrix,
234 assert(matrix != NULL);
235 assert(0 <= colindex && colindex < matrix->ncols);
237 arrayposition = matrix->colmatbegin[colindex];
239 if( ncolvals != NULL )
241 if( colindex == matrix->ncols - 1 )
242 *ncolvals = matrix->nnonzs - arrayposition;
244 *ncolvals = matrix->colmatbegin[colindex + 1] - arrayposition;
246 if( valpointer != NULL )
247 *valpointer = &(matrix->colmatvals[arrayposition]);
249 if( indexpointer != NULL )
250 *indexpointer = &(matrix->colmatind[arrayposition]);
260 CONSTRAINTMATRIX* matrix,
276 assert(varcol != NULL);
286 assert(colvals != NULL || ncolvals == 0);
288 SCIPdebugMsg(scip,
"Relaxing variable <%s> with lb <%g> and ub <%g>\n",
291 assert(matrix->normalized);
293 for( r = 0; r < ncolvals; ++r )
311 assert(colvals != NULL);
316 assert(0 <= rowindex && rowindex < matrix->nrows);
317 getRowData(matrix, rowindex, NULL, &lhs, &rhs, NULL, NULL);
336 matrix->lhs[rowindex] -= colval * lhsvarbound;
341 matrix->rhs[rowindex] -= colval * rhsvarbound;
345 SCIPdebugMsg(scip,
"Row <%s> changed:Coefficient <%g>, LHS <%g> --> <%g>, RHS <%g> --> <%g>\n",
346 SCIProwGetName(colrow), colval, lhs, matrix->lhs[rowindex], rhs, matrix->rhs[rowindex]);
362 CONSTRAINTMATRIX* matrix,
375 assert(matrix != NULL);
376 assert(0 <= colpos && colpos < heurdata->nlpcols);
377 col = heurdata->lpcols[colpos];
387 negatecoeffs =
FALSE;
397 deltashift = matrix->transformshiftvals[colpos];
398 matrix->transformshiftvals[colpos] = 0.0;
406 matrix->transformshiftvals[colpos] = lb;
415 matrix->transformshiftvals[colpos] = ub;
420 matrix->upperbounds[colpos] = ub - lb;
438 assert(nrows == 0 ||(vals != NULL && rows != NULL));
441 for( i = 0; i < nrows; ++i )
443 int rowpos = rows[i];
445 assert(rowpos < matrix->nrows);
448 matrix->lhs[rowpos] -= (vals[i]) * deltashift;
451 matrix->rhs[rowpos] -= (vals[i]) * deltashift;
454 (vals[i]) = -(vals[i]);
456 assert(
SCIPisFeasLE(scip, matrix->lhs[rowpos], matrix->rhs[rowpos]));
459 SCIPdebugMsg(scip,
"Variable <%s> at colpos %d transformed. LB <%g> --> <%g>, UB <%g> --> <%g>\n",
460 SCIPvarGetName(var), colpos, lb, 0.0, ub, matrix->upperbounds[colpos]);
469 CONSTRAINTMATRIX* matrix,
489 assert(scip != NULL);
490 assert(matrix != NULL);
491 assert(initialized!= NULL);
492 assert(infeasible != NULL);
493 assert(nmaxrows != NULL);
495 SCIPdebugMsg(scip,
"entering Matrix Initialization method of SHIFTANDPROPAGATE heuristic!\n");
499 lpcols = heurdata->lpcols;
500 ncols = heurdata->nlpcols;
502 matrix->nrows = nrows;
504 matrix->normalized =
FALSE;
505 matrix->ndiscvars = 0;
507 impliscontinuous = heurdata->impliscontinuous;
510 for( j = 0; j < ncols; ++j )
512 assert(lpcols[j] != NULL);
522 matrix->ncols = matrix->ndiscvars;
524 if( matrix->nnonzs == 0 )
526 SCIPdebugMsg(scip,
"No matrix entries - Terminating initialization of matrix.\n");
528 *initialized =
FALSE;
549 for( j = 0; j < matrix->ndiscvars; ++j )
558 for( i = 0; i < nrows; ++i )
579 matrix->rowmatbegin[i] = currentpointer;
600 matrix->lhs[i] /= maxval;
602 matrix->rhs[i] /= maxval;
610 SCIPdebugMsg(scip,
" Matrix initialization stopped because of row infeasibility! \n");
615 for( j = 0; j < nrowlpnonz; ++j )
620 assert(currentpointer < matrix->nnonzs);
622 matrix->rowmatvals[currentpointer] = rowvals[j];
624 matrix->rowmatvals[currentpointer] /= maxval;
632 matrix->normalized =
TRUE;
637 assert(currentpointer == matrix->nnonzs);
642 for( j = 0; j < matrix->ncols; ++j )
652 currentcol = lpcols[j];
658 matrix->colnorms[j] = ncolnonz;
660 *nmaxrows =
MAX(*nmaxrows, ncolnonz);
663 matrix->colmatbegin[j] = currentpointer;
665 for( i = 0; i < ncolnonz; ++i )
669 assert(rows[i] != NULL);
672 assert(currentpointer < matrix->nnonzs);
679 matrix->colmatvals[currentpointer] = colvals[i];
681 matrix->colmatvals[currentpointer] /= maxval;
686 matrix->colnorms[j] += ABS(matrix->colmatvals[currentpointer]);
690 assert(currentpointer == matrix->nnonzs);
693 for( j = 0; j < (relax ? ncols : matrix->ndiscvars); ++j )
700 matrix->transformshiftvals[j] = 0.0;
708 relaxVar(scip, var, matrix, normalize);
713 SCIPdebugMsg(scip,
"Matrix initialized for %d discrete variables with %d cols, %d rows and %d nonzero entries\n",
714 matrix->ndiscvars, matrix->ncols, matrix->nrows, matrix->nnonzs);
722 CONSTRAINTMATRIX** matrix
725 assert(scip != NULL);
726 assert(matrix != NULL);
729 if( (*matrix)->nnonzs > 0 )
731 assert((*matrix) != NULL);
732 assert((*matrix)->rowmatbegin != NULL);
733 assert((*matrix)->rowmatvals != NULL);
734 assert((*matrix)->rowmatind != NULL);
735 assert((*matrix)->colmatbegin != NULL);
736 assert((*matrix)->colmatvals!= NULL);
737 assert((*matrix)->colmatind != NULL);
738 assert((*matrix)->lhs != NULL);
739 assert((*matrix)->rhs != NULL);
740 assert((*matrix)->transformstatus != NULL);
741 assert((*matrix)->transformshiftvals != NULL);
758 (*matrix)->nrows = 0;
759 (*matrix)->ncols = 0;
770 CONSTRAINTMATRIX* matrix,
783 assert(matrix != NULL);
784 assert(violatedrows != NULL);
785 assert(violatedrowpos != NULL);
786 assert(nviolatedrows != NULL);
788 getRowData(matrix, rowindex, NULL, NULL, NULL, &cols, &ncols);
792 if( violatedrowpos[rowindex] == -1 && (
SCIPisFeasGT(scip, matrix->lhs[rowindex], 0.0) ||
SCIPisFeasLT(scip, matrix->rhs[rowindex], 0.0)) )
794 assert(*nviolatedrows < matrix->nrows);
796 violatedrows[*nviolatedrows] = rowindex;
797 violatedrowpos[rowindex] = *nviolatedrows;
800 ++rowweights[rowindex];
805 else if( violatedrowpos[rowindex] >= 0 &&
SCIPisFeasLE(scip, matrix->lhs[rowindex], 0.0) &&
SCIPisFeasGE(scip, matrix->rhs[rowindex], 0.0) )
808 if( violatedrowpos[rowindex] != *nviolatedrows - 1 )
810 assert(*nviolatedrows - 1 >= 0);
811 violatedrows[violatedrowpos[rowindex]] = violatedrows[*nviolatedrows - 1];
812 violatedrowpos[violatedrows[*nviolatedrows - 1]] = violatedrowpos[rowindex];
816 violatedrowpos[rowindex] = -1;
822 for( c = 0; c < ncols; ++c )
824 matrix->violrows[cols[c]] += violadd;
825 assert(matrix->violrows[cols[c]] >= 0);
835 CONSTRAINTMATRIX* matrix,
848 assert(matrix != NULL);
849 assert(violatedrows != NULL);
850 assert(violatedrowpos != NULL);
851 assert(nviolatedrows != NULL);
852 assert(-1 <= colidx && colidx < matrix->ncols);
859 nrows = matrix->nrows;
864 for( i = 0; i < nrows; ++i )
865 violatedrowpos[i] = -1;
871 assert(colidx < 0 || *nviolatedrows >= 0);
872 SCIPdebugMsg(scip,
"Entering violation check for %d rows! \n", nrows);
874 for( i = 0; i < nrows; ++i )
879 assert(rowindices != NULL);
880 rowpos = rowindices[i];
885 checkRowViolation(scip, matrix, rowpos, violatedrows, violatedrowpos, nviolatedrows, rowweights, updateweights);
887 assert((violatedrowpos[rowpos] == -1 &&
SCIPisFeasGE(scip, matrix->rhs[rowpos], 0.0) &&
SCIPisFeasLE(scip, matrix->lhs[rowpos], 0.0))
888 || (violatedrowpos[rowpos] >= 0 &&(
SCIPisFeasLT(scip, matrix->rhs[rowpos], 0.0) ||
SCIPisFeasGT(scip, matrix->lhs[rowpos], 0.0))));
896 CONSTRAINTMATRIX* matrix,
904 assert(matrix != NULL);
907 status = matrix->transformstatus[varindex];
915 return solvalue + matrix->transformshiftvals[varindex];
920 return matrix->transformshiftvals[varindex] - solvalue;
930 CONSTRAINTMATRIX* matrix,
935 int* violationchange,
952 assert(beststep != NULL);
953 assert(rowviolations != NULL);
954 assert(rowweights != NULL);
955 assert(steps != NULL);
956 assert(violationchange != NULL);
957 assert(direction == 1 || direction == -1);
959 upperbound = matrix->upperbounds[varindex];
969 for( i = 0; i < nrows; ++i )
981 lhs = matrix->lhs[rowpos];
982 rhs = matrix->rhs[rowpos];
983 rowweight = rowweights[rowpos];
984 val = direction * vals[i];
1010 slacksurplus += val;
1012 slacksurplus -= val;
1017 steps[i] = maxfeasshift + 1.0;
1018 violationchange[i] = rowweight;
1023 steps[i] = upperbound;
1024 violationchange[i] = 0;
1049 steps[i] = minfeasshift;
1050 violationchange[i] = -rowweight;
1055 steps[i] = upperbound;
1056 violationchange[i] = 0;
1067 *beststep = direction * upperbound;
1089 sum += violationchange[i];
1094 if( (i == nrows-1 || steps[i+1] > steps[i]) && sum < *rowviolations )
1096 *rowviolations = sum;
1097 *beststep = direction * steps[i];
1100 assert(*rowviolations <= 0);
1113 CONSTRAINTMATRIX* matrix,
1119 int* violatedrowpos,
1127 assert(scip != NULL);
1128 assert(matrix != NULL);
1129 assert(0 <= varindex && varindex < matrix->ndiscvars);
1133 status = matrix->transformstatus[varindex];
1135 SCIPdebugMsg(scip,
" Variable <%d> [%g,%g], status %d(%g), ub %g \n", varindex, lb, ub, status,
1136 matrix->transformshiftvals[varindex], matrix->upperbounds[varindex]);
1138 checkviolations =
FALSE;
1146 checkviolations =
TRUE;
1150 deltashift = lb - (matrix->transformshiftvals[varindex]);
1151 matrix->transformshiftvals[varindex] = lb;
1153 matrix->upperbounds[varindex] = ub - lb;
1162 checkviolations =
TRUE;
1166 deltashift = (matrix->transformshiftvals[varindex]) - ub;
1167 matrix->transformshiftvals[varindex] = ub;
1170 matrix->upperbounds[varindex] = ub - lb;
1183 checkviolations =
TRUE;
1192 SCIPerrorMessage(
"Error: Invalid variable status <%d> in shift and propagagate heuristic, aborting!\n");
1210 for( i = 0; i < nrows; ++i )
1212 SCIPdebugMsg(scip,
" update slacks of row<%d>: coefficient <%g>, %g <= 0 <= %g \n",
1213 rows[i], vals[i], matrix->lhs[rows[i]], matrix->rhs[rows[i]]);
1216 matrix->lhs[rows[i]] -= (vals[i]) * deltashift;
1219 matrix->rhs[rows[i]] -= (vals[i]) * deltashift;
1221 checkviolations =
TRUE;
1225 if( checkviolations )
1226 checkViolations(scip, matrix, varindex, violatedrows, violatedrowpos, nviolatedrows, heurdata->rowweights, heurdata->updateweights);
1228 SCIPdebugMsg(scip,
" Variable <%d> [%g,%g], status %d(%g), ub %g \n", varindex, lb, ub, status,
1229 matrix->transformshiftvals[varindex], matrix->upperbounds[varindex]);
1251 assert(var1 != NULL && var2 != NULL);
1310 assert(heurdata != NULL);
1318 " DETAILS : %d violations left, %d probing status\n",
1319 heurdata->nremainingviols,
1323 " SHIFTANDPROPAGATE PROBING : %d probings, %" SCIP_LONGINT_FORMAT
" domain reductions, ncutoffs: %d , LP iterations: %" SCIP_LONGINT_FORMAT
" \n ",
1324 heurdata->nprobings,
1325 heurdata->ntotaldomredsfound,
1327 heurdata->nlpiters);
1344 assert(heurdata != NULL);
1352 heurdata->nremainingviols = 0;
1353 heurdata->nprobings = 0;
1354 heurdata->ntotaldomredsfound = 0;
1355 heurdata->ncutoffs = 0;
1356 heurdata->nlpiters = 0;
1370 assert(heurdata != NULL);
1371 eventhdlr = heurdata->eventhdlr;
1372 assert(eventhdlr != NULL);
1390 assert(scip != NULL);
1391 assert(heur != NULL);
1409 CONSTRAINTMATRIX* matrix;
1415 int* violationchange;
1418 int* violatedrowpos;
1420 int* violatedvarrows;
1425 int lastindexofsusp;
1444 assert(heurdata != NULL);
1446 eventhdlr = heurdata->eventhdlr;
1447 assert(eventhdlr != NULL);
1450 assert(eventhdlrdata != NULL);
1453 SCIPdebugMsg(scip,
"entering execution method of shift and propagate heuristic\n");
1487 assert(nlpcols == 0 || lpcols != NULL);
1490 if( nlprows == 0 || nlpcols == 0 )
1495 initialized =
FALSE;
1499 heurdata->nlpcols = nlpcols;
1501 impliscontinuous = heurdata->impliscontinuous;
1510 SCIPsortPtr((
void**)heurdata->lpcols, heurSortColsShiftandpropagate, nlpcols);
1520 for( c = 0; c < nlpcols; ++c )
1525 col = heurdata->lpcols[c];
1526 assert(col != NULL);
1528 assert(colvar != NULL);
1541 assert(nbinvars + nintvars <= ndiscvars);
1547 if( heurdata->collectstats )
1564 SCIP_CALL(
initMatrix(scip, matrix, heurdata, colposs, heurdata->normalize, &nmaxrows, heurdata->relax, &initialized, &infeasible) );
1570 if( !initialized || infeasible )
1572 SCIPdebugMsg(scip,
" MATRIX not initialized -> Execution of heuristic stopped! \n");
1579 if( matrix->ndiscvars < ndiscvars )
1581 SCIPdebugMsg(scip,
"Not all discrete variables are in the current LP. Shiftandpropagate execution terminated.\n");
1585 assert(nmaxrows > 0);
1587 eventhdlrdata->matrix = matrix;
1588 eventhdlrdata->heurdata = heurdata;
1605 eventhdlrdata->violatedrows = violatedrows;
1606 eventhdlrdata->violatedrowpos = violatedrowpos;
1607 eventhdlrdata->nviolatedrows = &nviolatedrows;
1612 for( i = 0; i < ndiscvars; ++i )
1616 for( r = 0; r < matrix->nrows; ++r )
1624 colnorms = matrix->colnorms;
1626 assert(nbinvars >= 0);
1627 assert(nintvars >= 0);
1630 checkViolations(scip, matrix, -1, violatedrows, violatedrowpos, &nviolatedrows, heurdata->rowweights, heurdata->updateweights);
1633 if( heurdata->sortvars && (heurdata->sortkey ==
't' || heurdata->sortkey ==
'v') )
1639 violatedvarrows = NULL;
1644 if( heurdata->sortvars )
1646 switch (heurdata->sortkey)
1650 if( heurdata->preferbinaries )
1654 if( nbinvars < ndiscvars )
1661 SCIPdebugMsg(scip,
"Variables sorted down w.r.t their normalized columns!\n");
1665 if( heurdata->preferbinaries )
1669 if( nbinvars < ndiscvars )
1670 SCIPsortRealInt(&colnorms[nbinvars], &permutation[nbinvars], ndiscvars - nbinvars);
1676 SCIPdebugMsg(scip,
"Variables sorted w.r.t their normalized columns!\n");
1680 assert(violatedvarrows != NULL);
1681 if( heurdata->preferbinaries )
1685 if( nbinvars < ndiscvars )
1686 SCIPsortDownIntInt(&violatedvarrows[nbinvars], &permutation[nbinvars], ndiscvars - nbinvars);
1693 SCIPdebugMsg(scip,
"Variables sorted down w.r.t their number of currently infeasible rows!\n");
1697 assert(violatedvarrows != NULL);
1698 if( heurdata->preferbinaries )
1702 if( nbinvars < ndiscvars )
1703 SCIPsortIntInt(&violatedvarrows[nbinvars], &permutation[nbinvars], ndiscvars - nbinvars);
1710 SCIPdebugMsg(scip,
"Variables sorted (upwards) w.r.t their number of currently infeasible rows!\n");
1714 if( heurdata->preferbinaries )
1718 if( nbinvars < ndiscvars )
1720 ndiscvars - nbinvars - 1);
1729 SCIPdebugMsg(scip,
"No variable permutation applied\n");
1735 if( heurdata->binlocksfirst )
1738 int nbinwithoutlocks = 0;
1741 if( heurdata->preferbinaries )
1743 for( c = 0; c < nbinvars; ++c )
1752 for( c = 0; c < ndiscvars; ++c )
1763 if( nbinwithoutlocks > 0 )
1771 while( c < nbinwithoutlocks && b < ndiscvars )
1774 assert(c < ndiscvars);
1775 assert(b < ndiscvars);
1783 if( c >= nbinwithoutlocks )
1787 if( c >= nbinwithoutlocks )
1799 assert(b < ndiscvars);
1804 tmp = permutation[b];
1805 permutation[b] = permutation[c];
1806 permutation[c] = tmp;
1815 for( c = 0; c < ndiscvars; ++c )
1828 for( c = 0; c < matrix->ndiscvars; ++c )
1833 assert(var != NULL);
1835 assert(eventdatas[c] == NULL);
1839 eventdatas[c]->colpos = c;
1846 lastindexofsusp = -1;
1847 probing = heurdata->probing;
1850 SCIPdebugMsg(scip,
"SHIFT_AND_PROPAGATE heuristic starts main loop with %d violations and %d remaining variables!\n",
1851 nviolatedrows, ndiscvars);
1853 assert(matrix->ndiscvars == ndiscvars);
1856 for( c = 0; c < ndiscvars; ++c )
1865 int permutedvarindex;
1869 if( heurdata->selectbest )
1872 while( j < ndiscvars )
1875 if( matrix->violrows[permutation[c]] < matrix->violrows[permutation[j]] )
1878 tmp = permutation[c];
1879 permutation[c] = permutation[j];
1880 permutation[j] = tmp;
1885 permutedvarindex = permutation[c];
1886 optimalshiftvalue = 0.0;
1904 if( heurdata->probing )
1908 SCIPdebugMsg(scip,
"Variable %s with local bounds [%g,%g], status <%d>, matrix bound <%g>\n",
1909 SCIPvarGetName(var), lb, ub, matrix->transformstatus[permutedvarindex], matrix->upperbounds[permutedvarindex]);
1912 if(
SCIPisFeasZero(scip, matrix->upperbounds[permutedvarindex]) )
1922 marksuspicious =
FALSE;
1940 if( !heurdata->stopafterfeasible || nviolatedrows > 0 )
1944 &optimalshiftvalue, &nviolations) );
1951 int ndownviolations;
1953 downshiftvalue = 0.0;
1954 ndownviolations = 0;
1956 &downshiftvalue, &ndownviolations) );
1958 assert(
SCIPisLE(scip, downshiftvalue, 0.0));
1961 if( ndownviolations < nviolations )
1963 optimalshiftvalue = downshiftvalue;
1968 optimalshiftvalue = 0.0;
1971 if( heurdata->nozerofixing && nviolations > 0 &&
SCIPisFeasZero(scip, optimalshiftvalue) )
1972 marksuspicious =
TRUE;
1989 if( !marksuspicious && probing )
2000 SCIPdebugMsg(scip,
" Shift %g(%g originally) is optimal, propagate solution\n", optimalshiftvalue, origsolval);
2004 SCIPstatistic( heurdata->ntotaldomredsfound += ndomredsfound );
2005 SCIPdebugMsg(scip,
"Propagation finished! <%" SCIP_LONGINT_FORMAT
"> domain reductions %s, <%d> probing depth\n", ndomredsfound, cutoff ?
"CUTOFF" :
"",
2008 assert(!cutoff || probing);
2018 if( heurdata->cutoffbreaker >= 0 && ncutoffs >= ((heurdata->maxcutoffquot *
SCIPgetProbingDepth(scip)) + heurdata->cutoffbreaker) )
2055 SCIPstatistic( heurdata->ntotaldomredsfound += ndomredsfound );
2069 SCIPstatistic( heurdata->ntotaldomredsfound += ndomredsfound );
2081 marksuspicious =
TRUE;
2085 if( marksuspicious )
2088 assert(permutedvarindex == permutation[c]);
2091 assert(lastindexofsusp >= 0 && lastindexofsusp <= c);
2093 permutation[c] = permutation[lastindexofsusp];
2094 permutation[lastindexofsusp] = permutedvarindex;
2096 SCIPdebugMsg(scip,
" Suspicious variable! Postponed from pos <%d> to position <%d>\n", c, lastindexofsusp);
2100 SCIPdebugMsg(scip,
"Variable <%d><%s> successfully shifted by value <%g>!\n", permutedvarindex,
2113 SCIPdebugMsg(scip,
"Heuristic finished with %d remaining violations and %d remaining variables!\n",
2114 nviolatedrows, lastindexofsusp + 1);
2119 if( nviolatedrows == 0 && !cutoff )
2124 for( v = 0; v <= lastindexofsusp; ++v )
2128 int permutedvarindex;
2131 permutedvarindex = permutation[v];
2136 if( heurdata->probing )
2153 if( nviolatedrows > 0 )
2161 if( nlpcols != matrix->ndiscvars )
2171 assert(vars != NULL);
2173 for( v = 0; v < ndiscvars; ++v )
2197 SCIPwarningMessage(scip,
"Error while solving LP in SHIFTANDPROPAGATE heuristic; LP solve terminated with code <%d>\n",
2231 printreason =
FALSE;
2244 SCIPdebugMsg(scip,
"found feasible shifted solution:\n");
2254 SCIPdebugMsg(scip,
"Solution constructed by heuristic is already known to be infeasible\n");
2257 SCIPstatistic( heurdata->nremainingviols = nviolatedrows; );
2261 for( c = matrix->ndiscvars - 1; c >= 0; --c )
2266 assert(var != NULL);
2267 assert(eventdatas[c] != NULL);
2274 if( violatedvarrows != NULL )
2276 assert(heurdata->sortkey ==
'v' || heurdata->sortkey ==
't');
2288 eventhdlrdata->nviolatedrows = NULL;
2289 eventhdlrdata->violatedrowpos = NULL;
2290 eventhdlrdata->violatedrows = NULL;
2295 heurdata->ncutoffs += ncutoffs;
2296 heurdata->nprobings += nprobings;
2303 eventhdlrdata->matrix = NULL;
2319 CONSTRAINTMATRIX* matrix;
2322 assert(scip != NULL);
2323 assert(eventhdlr != NULL);
2327 assert(eventhdlrdata != NULL);
2329 matrix = eventhdlrdata->matrix;
2331 heurdata = eventhdlrdata->heurdata;
2332 assert(heurdata != NULL && heurdata->lpcols != NULL);
2334 colpos = eventdata->colpos;
2336 assert(0 <= colpos && colpos < matrix->ndiscvars);
2338 col = heurdata->lpcols[colpos];
2345 eventhdlrdata->violatedrowpos, eventhdlrdata->nviolatedrows) );
2365 eventhandlerdata->matrix = NULL;
2369 eventExecShiftandpropagate, eventhandlerdata) );
2370 assert(eventhdlr != NULL);
2374 heurdata->rowweights = NULL;
2375 heurdata->nlpcols = 0;
2376 heurdata->eventhdlr = eventhdlr;
2383 assert(heur != NULL);
2394 "The number of propagation rounds used for each propagation",
2401 "Should heuristic only be executed if no primal solution was found, yet?",
2406 "the key for variable sorting: (n)orms down, norms (u)p, (v)iolations down, viola(t)ions up, or (r)andom",
2408 SCIP_CALL(
SCIPaddBoolParam(scip,
"heuristics/shiftandpropagate/sortvars",
"Should variables be sorted for the heuristic?",
2413 "Should the heuristic stop calculating optimal shift values when no more rows are violated?",
2416 "Should binary variables be shifted first?",
2419 "should variables with a zero shifting value be delayed instead of being fixed?",
2422 "should binary variables with no locks in one direction be fixed to that direction?",
2425 "should binary variables with no locks be preferred in the ordering?",
2428 "should coefficients and left/right hand sides be normalized by max row coeff?",
2431 "should row weight be increased every time the row is violated?",
2434 "should implicit integer variables be treated as continuous variables?",
2437 "should the heuristic choose the best candidate in every round? (set to FALSE for static order)?",
2440 "maximum percentage of allowed cutoffs before stopping the heuristic",
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
#define DEFAULT_FIXBINLOCKS
preroot heuristic that alternatingly fixes variables and propagates domains
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static void relaxVar(SCIP *scip, SCIP_VAR *var, CONSTRAINTMATRIX *matrix, SCIP_Bool normalize)
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
int SCIPgetProbingDepth(SCIP *scip)
SCIP_RETCODE SCIPwriteLP(SCIP *scip, const char *filename)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
static SCIP_DECL_HEUREXEC(heurExecShiftandpropagate)
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed)
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
const char * SCIProwGetName(SCIP_ROW *row)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
struct SCIP_EventhdlrData SCIP_EVENTHDLRDATA
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
int SCIProwGetNLPNonz(SCIP_ROW *row)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
#define DEFAULT_CUTOFFBREAKER
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
static SCIP_DECL_EVENTEXEC(eventExecShiftandpropagate)
SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
static void freeMatrix(SCIP *scip, CONSTRAINTMATRIX **matrix)
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
SCIP_Real SCIPinfinity(SCIP *scip)
enum SCIP_Retcode SCIP_RETCODE
#define SCIPstatisticMessage
#define DEFAULT_UPDATEWEIGHTS
#define DEFAULT_BINLOCKSFIRST
struct SCIP_HeurData SCIP_HEURDATA
void SCIPsortDownIntInt(int *intarray1, int *intarray2, int len)
#define SCIPfreeBlockMemory(scip, ptr)
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 SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
#define DEFAULT_WEIGHT_INEQUALITY
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIP_RETCODE SCIPconstructLP(SCIP *scip, SCIP_Bool *cutoff)
#define SCIPfreeBufferArray(scip, ptr)
enum SCIP_LPSolStat SCIP_LPSOLSTAT
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
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)
int SCIPgetNContVars(SCIP *scip)
#define DEFAULT_ONLYWITHOUTSOL
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLPConstructed(SCIP *scip)
static SCIP_DECL_HEUREXIT(heurExitShiftandpropagate)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
#define DEFAULT_NORMALIZE
const char * SCIPheurGetName(SCIP_HEUR *heur)
static SCIP_Bool varIsDiscrete(SCIP_VAR *var, SCIP_Bool impliscontinuous)
#define DEFAULT_STOPAFTERFEASIBLE
#define DEFAULT_SELECTBEST
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
static void transformVariable(SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_HEURDATA *heurdata, int colpos)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
static SCIP_Bool colIsDiscrete(SCIP_COL *col, SCIP_Bool impliscontinuous)
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
#define SCIPallocBuffer(scip, ptr)
#define EVENTTYPE_SHIFTANDPROPAGATE
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)
SCIP_RETCODE SCIPendProbing(SCIP *scip)
struct SCIP_EventData SCIP_EVENTDATA
const char * SCIPvarGetName(SCIP_VAR *var)
#define DEFAULT_PREFERBINARIES
int SCIPgetNLPRows(SCIP *scip)
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
#define DEFAULT_NOZEROFIXING
#define SCIPfreeBlockMemoryNull(scip, ptr)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_HEURINIT(heurInitShiftandpropagate)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
public data structures and miscellaneous methods
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
SCIP_Bool SCIPvarIsInLP(SCIP_VAR *var)
#define DEFAULT_NPROPROUNDS
int SCIPgetDepth(SCIP *scip)
void SCIPsolSetHeur(SCIP_SOL *sol, SCIP_HEUR *heur)
void SCIPrandomPermuteIntArray(SCIP_RANDNUMGEN *randnumgen, int *array, int begin, int end)
int SCIPvarGetNLocksUp(SCIP_VAR *var)
enum TransformStatus TRANSFORMSTATUS
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
void SCIPenableVarHistory(SCIP *scip)
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
#define DEFAULT_MAXCUTOFFQUOT
#define DEFAULT_IMPLISCONTINUOUS
#define BMScopyMemoryArray(ptr, source, num)
#define DEFAULT_WEIGHT_EQUALITY
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
SCIP_RETCODE SCIPflushLP(SCIP *scip)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
static void getColumnData(CONSTRAINTMATRIX *matrix, int colindex, SCIP_Real **valpointer, int **indexpointer, int *ncolvals)
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)
#define SCIP_MAXTREEDEPTH
static void checkRowViolation(SCIP *scip, CONSTRAINTMATRIX *matrix, int rowindex, int *violatedrows, int *violatedrowpos, int *nviolatedrows, int *rowweights, SCIP_Bool updateweights)
int SCIPgetNVars(SCIP *scip)
static void checkViolations(SCIP *scip, CONSTRAINTMATRIX *matrix, int colidx, int *violatedrows, int *violatedrowpos, int *nviolatedrows, int *rowweights, SCIP_Bool updateweights)
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
#define SCIPfreeBuffer(scip, ptr)
int SCIPvarGetNLocksDown(SCIP_VAR *var)
static SCIP_DECL_HEURCOPY(heurCopyShiftandpropagate)
static SCIP_Real retransformVariable(SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_VAR *var, int varindex, SCIP_Real solvalue)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
SCIP_RETCODE SCIPincludeHeurShiftandpropagate(SCIP *scip)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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)
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_VAR * SCIPcolGetVar(SCIP_COL *col)
static void getRowData(CONSTRAINTMATRIX *matrix, int rowindex, SCIP_Real **valpointer, SCIP_Real *lhs, SCIP_Real *rhs, int **indexpointer, int *nrowvals)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
int SCIProwGetLPPos(SCIP_ROW *row)
SCIP_Bool SCIPisStopped(SCIP *scip)
static SCIP_DECL_SORTPTRCOMP(heurSortColsShiftandpropagate)
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define DEFAULT_PROPBREAKER
enum SCIP_Vartype SCIP_VARTYPE
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
#define DEFAULT_COLLECTSTATS
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
#define BMSclearMemoryArray(ptr, num)
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
SCIP_EVENTHDLRDATA * SCIPeventhdlrGetData(SCIP_EVENTHDLR *eventhdlr)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
int SCIPcolGetNLPNonz(SCIP_COL *col)
int SCIPcolGetLPPos(SCIP_COL *col)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
static SCIP_DECL_HEURFREE(heurFreeShiftandpropagate)
void SCIPdisableVarHistory(SCIP *scip)
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_Bool SCIPcolIsInLP(SCIP_COL *col)
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)
static SCIP_RETCODE getOptimalShiftingValue(SCIP *scip, CONSTRAINTMATRIX *matrix, int varindex, int direction, int *rowweights, SCIP_Real *steps, int *violationchange, SCIP_Real *beststep, int *rowviolations)
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)