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);
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);
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;
1015 if(
SCIPisFeasLE(scip, maxfeasshift + 1.0, upperbound) )
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;
1066 *beststep =
SCIPisFeasGT(scip, slacksurplus, 0.0) ? direction * upperbound : 0.0;
1085 sum += violationchange[i];
1090 if( (i == nrows-1 || steps[i+1] > steps[i]) && sum < *rowviolations )
1092 *rowviolations = sum;
1093 *beststep = direction * steps[i];
1096 assert(*rowviolations <= 0);
1109 CONSTRAINTMATRIX* matrix,
1115 int* violatedrowpos,
1123 assert(scip !=
NULL);
1124 assert(matrix !=
NULL);
1125 assert(0 <= varindex && varindex < matrix->ndiscvars);
1129 status = matrix->transformstatus[varindex];
1131 SCIPdebugMsg(scip,
" Variable <%d> [%g,%g], status %d(%g), ub %g \n", varindex, lb, ub, status,
1132 matrix->transformshiftvals[varindex], matrix->upperbounds[varindex]);
1134 checkviolations =
FALSE;
1142 checkviolations =
TRUE;
1146 deltashift = lb - (matrix->transformshiftvals[varindex]);
1147 matrix->transformshiftvals[varindex] = lb;
1149 matrix->upperbounds[varindex] = ub - lb;
1158 checkviolations =
TRUE;
1162 deltashift = (matrix->transformshiftvals[varindex]) - ub;
1163 matrix->transformshiftvals[varindex] = ub;
1166 matrix->upperbounds[varindex] = ub - lb;
1177 checkviolations =
TRUE;
1186 SCIPerrorMessage(
"Error: Invalid variable status <%d> in shift and propagagate heuristic, aborting!\n");
1204 for( i = 0; i < nrows; ++i )
1206 SCIPdebugMsg(scip,
" update slacks of row<%d>: coefficient <%g>, %g <= 0 <= %g \n",
1207 rows[i], vals[i], matrix->lhs[rows[i]], matrix->rhs[rows[i]]);
1210 matrix->lhs[rows[i]] -= (vals[i]) * deltashift;
1213 matrix->rhs[rows[i]] -= (vals[i]) * deltashift;
1215 checkviolations =
TRUE;
1219 if( checkviolations )
1220 checkViolations(scip, matrix, varindex, violatedrows, violatedrowpos, nviolatedrows, heurdata->rowweights, heurdata->updateweights);
1222 SCIPdebugMsg(scip,
" Variable <%d> [%g,%g], status %d(%g), ub %g \n", varindex, lb, ub, status,
1223 matrix->transformshiftvals[varindex], matrix->upperbounds[varindex]);
1245 assert(var1 !=
NULL && var2 !=
NULL);
1304 assert(heurdata !=
NULL);
1312 " DETAILS : %d violations left, %d probing status, %d redundant rows\n",
1313 heurdata->nremainingviols,
1317 " SHIFTANDPROPAGATE PROBING : %d probings, %" SCIP_LONGINT_FORMAT
" domain reductions, ncutoffs: %d , LP iterations: %" SCIP_LONGINT_FORMAT
" \n ",
1318 heurdata->nprobings,
1319 heurdata->ntotaldomredsfound,
1321 heurdata->nlpiters);
1338 assert(heurdata !=
NULL);
1346 heurdata->nremainingviols = 0;
1347 heurdata->nprobings = 0;
1348 heurdata->ntotaldomredsfound = 0;
1349 heurdata->ncutoffs = 0;
1350 heurdata->nlpiters = 0;
1364 assert(heurdata !=
NULL);
1365 eventhdlr = heurdata->eventhdlr;
1366 assert(eventhdlr !=
NULL);
1384 assert(scip !=
NULL);
1385 assert(heur !=
NULL);
1403 CONSTRAINTMATRIX* matrix;
1409 int* violationchange;
1412 int* violatedrowpos;
1414 int* violatedvarrows;
1419 int lastindexofsusp;
1438 assert(heurdata !=
NULL);
1440 eventhdlr = heurdata->eventhdlr;
1441 assert(eventhdlr !=
NULL);
1444 assert(eventhdlrdata !=
NULL);
1447 SCIPdebugMsg(scip,
"entering execution method of shift and propagate heuristic\n");
1481 assert(nlpcols == 0 || lpcols !=
NULL);
1484 if( nlprows == 0 || nlpcols == 0 )
1489 initialized =
FALSE;
1493 heurdata->nlpcols = nlpcols;
1495 impliscontinuous = heurdata->impliscontinuous;
1504 SCIPsortPtr((
void**)heurdata->lpcols, heurSortColsShiftandpropagate, nlpcols);
1514 for( c = 0; c < nlpcols; ++c )
1519 col = heurdata->lpcols[c];
1520 assert(col !=
NULL);
1522 assert(colvar !=
NULL);
1535 assert(nbinvars + nintvars <= ndiscvars);
1541 if( heurdata->collectstats )
1558 SCIP_CALL(
initMatrix(scip, matrix, heurdata, colposs, heurdata->normalize, &nmaxrows, heurdata->relax, &initialized, &infeasible) );
1564 if( !initialized || infeasible )
1566 SCIPdebugMsg(scip,
" MATRIX not initialized -> Execution of heuristic stopped! \n");
1573 if( matrix->ndiscvars < ndiscvars )
1575 SCIPdebugMsg(scip,
"Not all discrete variables are in the current LP. Shiftandpropagate execution terminated.\n");
1579 assert(nmaxrows > 0);
1581 eventhdlrdata->matrix = matrix;
1582 eventhdlrdata->heurdata = heurdata;
1599 eventhdlrdata->violatedrows = violatedrows;
1600 eventhdlrdata->violatedrowpos = violatedrowpos;
1601 eventhdlrdata->nviolatedrows = &nviolatedrows;
1606 for( i = 0; i < ndiscvars; ++i )
1610 for( r = 0; r < matrix->nrows; ++r )
1618 colnorms = matrix->colnorms;
1620 assert(nbinvars >= 0);
1621 assert(nintvars >= 0);
1624 checkViolations(scip, matrix, -1, violatedrows, violatedrowpos, &nviolatedrows, heurdata->rowweights, heurdata->updateweights);
1627 if( heurdata->sortvars && (heurdata->sortkey ==
't' || heurdata->sortkey ==
'v') )
1633 violatedvarrows =
NULL;
1638 if( heurdata->sortvars )
1640 switch (heurdata->sortkey)
1644 if( heurdata->preferbinaries )
1648 if( nbinvars < ndiscvars )
1655 SCIPdebugMsg(scip,
"Variables sorted down w.r.t their normalized columns!\n");
1659 if( heurdata->preferbinaries )
1663 if( nbinvars < ndiscvars )
1664 SCIPsortRealInt(&colnorms[nbinvars], &permutation[nbinvars], ndiscvars - nbinvars);
1670 SCIPdebugMsg(scip,
"Variables sorted w.r.t their normalized columns!\n");
1674 assert(violatedvarrows !=
NULL);
1675 if( heurdata->preferbinaries )
1679 if( nbinvars < ndiscvars )
1680 SCIPsortDownIntInt(&violatedvarrows[nbinvars], &permutation[nbinvars], ndiscvars - nbinvars);
1687 SCIPdebugMsg(scip,
"Variables sorted down w.r.t their number of currently infeasible rows!\n");
1691 assert(violatedvarrows !=
NULL);
1692 if( heurdata->preferbinaries )
1696 if( nbinvars < ndiscvars )
1697 SCIPsortIntInt(&violatedvarrows[nbinvars], &permutation[nbinvars], ndiscvars - nbinvars);
1704 SCIPdebugMsg(scip,
"Variables sorted (upwards) w.r.t their number of currently infeasible rows!\n");
1708 if( heurdata->preferbinaries )
1712 if( nbinvars < ndiscvars )
1714 ndiscvars - nbinvars - 1);
1723 SCIPdebugMsg(scip,
"No variable permutation applied\n");
1729 if( heurdata->binlocksfirst )
1732 int nbinwithoutlocks = 0;
1735 if( heurdata->preferbinaries )
1737 for( c = 0; c < nbinvars; ++c )
1746 for( c = 0; c < ndiscvars; ++c )
1757 if( nbinwithoutlocks > 0 )
1765 while( c < nbinwithoutlocks && b < ndiscvars )
1768 assert(c < ndiscvars);
1769 assert(b < ndiscvars);
1777 if( c >= nbinwithoutlocks )
1781 if( c >= nbinwithoutlocks )
1793 assert(b < ndiscvars);
1798 tmp = permutation[b];
1799 permutation[b] = permutation[c];
1800 permutation[c] = tmp;
1809 for( c = 0; c < ndiscvars; ++c )
1822 for( c = 0; c < matrix->ndiscvars; ++c )
1827 assert(var !=
NULL);
1829 assert(eventdatas[c] ==
NULL);
1833 eventdatas[c]->colpos = c;
1840 lastindexofsusp = -1;
1841 probing = heurdata->probing;
1844 SCIPdebugMsg(scip,
"SHIFT_AND_PROPAGATE heuristic starts main loop with %d violations and %d remaining variables!\n",
1845 nviolatedrows, ndiscvars);
1847 assert(matrix->ndiscvars == ndiscvars);
1850 for( c = 0; c < ndiscvars; ++c )
1859 int permutedvarindex;
1863 if( heurdata->selectbest )
1866 while( j < ndiscvars )
1869 if( matrix->violrows[permutation[c]] < matrix->violrows[permutation[j]] )
1872 tmp = permutation[c];
1873 permutation[c] = permutation[j];
1874 permutation[j] = tmp;
1879 permutedvarindex = permutation[c];
1880 optimalshiftvalue = 0.0;
1898 if( heurdata->probing )
1902 SCIPdebugMsg(scip,
"Variable %s with local bounds [%g,%g], status <%d>, matrix bound <%g>\n",
1903 SCIPvarGetName(var), lb, ub, matrix->transformstatus[permutedvarindex], matrix->upperbounds[permutedvarindex]);
1906 if(
SCIPisFeasZero(scip, matrix->upperbounds[permutedvarindex]) )
1916 marksuspicious =
FALSE;
1934 if( !heurdata->stopafterfeasible || nviolatedrows > 0 )
1938 &optimalshiftvalue, &nviolations) );
1945 int ndownviolations;
1947 downshiftvalue = 0.0;
1948 ndownviolations = 0;
1950 &downshiftvalue, &ndownviolations) );
1952 assert(
SCIPisLE(scip, downshiftvalue, 0.0));
1955 if( ndownviolations < nviolations )
1957 optimalshiftvalue = downshiftvalue;
1962 optimalshiftvalue = 0.0;
1965 if( heurdata->nozerofixing && nviolations > 0 &&
SCIPisFeasZero(scip, optimalshiftvalue) )
1966 marksuspicious =
TRUE;
1983 if( !marksuspicious && probing )
1994 SCIPdebugMsg(scip,
" Shift %g(%g originally) is optimal, propagate solution\n", optimalshiftvalue, origsolval);
1998 SCIPstatistic( heurdata->ntotaldomredsfound += ndomredsfound );
1999 SCIPdebugMsg(scip,
"Propagation finished! <%" SCIP_LONGINT_FORMAT
"> domain reductions %s, <%d> probing depth\n", ndomredsfound, cutoff ?
"CUTOFF" :
"",
2002 assert(!cutoff || probing);
2012 if( heurdata->cutoffbreaker >= 0 && ncutoffs >= ((heurdata->maxcutoffquot *
SCIPgetProbingDepth(scip)) + heurdata->cutoffbreaker) )
2049 SCIPstatistic( heurdata->ntotaldomredsfound += ndomredsfound );
2063 SCIPstatistic( heurdata->ntotaldomredsfound += ndomredsfound );
2075 marksuspicious =
TRUE;
2079 if( marksuspicious )
2082 assert(permutedvarindex == permutation[c]);
2085 assert(lastindexofsusp >= 0 && lastindexofsusp <= c);
2087 permutation[c] = permutation[lastindexofsusp];
2088 permutation[lastindexofsusp] = permutedvarindex;
2090 SCIPdebugMsg(scip,
" Suspicious variable! Postponed from pos <%d> to position <%d>\n", c, lastindexofsusp);
2094 SCIPdebugMsg(scip,
"Variable <%d><%s> successfully shifted by value <%g>!\n", permutedvarindex,
2107 SCIPdebugMsg(scip,
"Heuristic finished with %d remaining violations and %d remaining variables!\n",
2108 nviolatedrows, lastindexofsusp + 1);
2113 if( nviolatedrows == 0 && !cutoff )
2118 for( v = 0; v <= lastindexofsusp; ++v )
2122 int permutedvarindex;
2125 permutedvarindex = permutation[v];
2130 if( heurdata->probing )
2147 if( nviolatedrows > 0 )
2155 if( nlpcols != matrix->ndiscvars )
2165 assert(vars !=
NULL);
2167 for( v = 0; v < ndiscvars; ++v )
2191 SCIPwarningMessage(scip,
"Error while solving LP in SHIFTANDPROPAGATE heuristic; LP solve terminated with code <%d>\n",
2225 printreason =
FALSE;
2238 SCIPdebugMsg(scip,
"found feasible shifted solution:\n");
2248 SCIPdebugMsg(scip,
"Solution constructed by heuristic is already known to be infeasible\n");
2251 SCIPstatistic( heurdata->nremainingviols = nviolatedrows; );
2255 for( c = matrix->ndiscvars - 1; c >= 0; --c )
2260 assert(var !=
NULL);
2261 assert(eventdatas[c] !=
NULL);
2268 if( violatedvarrows !=
NULL )
2270 assert(heurdata->sortkey ==
'v' || heurdata->sortkey ==
't');
2282 eventhdlrdata->nviolatedrows =
NULL;
2283 eventhdlrdata->violatedrowpos =
NULL;
2284 eventhdlrdata->violatedrows =
NULL;
2289 heurdata->ncutoffs += ncutoffs;
2290 heurdata->nprobings += nprobings;
2297 eventhdlrdata->matrix =
NULL;
2313 CONSTRAINTMATRIX* matrix;
2316 assert(scip !=
NULL);
2317 assert(eventhdlr !=
NULL);
2321 assert(eventhdlrdata !=
NULL);
2323 matrix = eventhdlrdata->matrix;
2325 heurdata = eventhdlrdata->heurdata;
2326 assert(heurdata !=
NULL && heurdata->lpcols !=
NULL);
2328 colpos = eventdata->colpos;
2330 assert(0 <= colpos && colpos < matrix->ndiscvars);
2332 col = heurdata->lpcols[colpos];
2339 eventhdlrdata->violatedrowpos, eventhdlrdata->nviolatedrows) );
2359 eventhandlerdata->matrix =
NULL;
2363 eventExecShiftandpropagate, eventhandlerdata) );
2364 assert(eventhdlr !=
NULL);
2368 heurdata->rowweights =
NULL;
2369 heurdata->nlpcols = 0;
2370 heurdata->eventhdlr = eventhdlr;
2377 assert(heur !=
NULL);
2388 "The number of propagation rounds used for each propagation",
2395 "Should heuristic only be executed if no primal solution was found, yet?",
2400 "the key for variable sorting: (n)orms down, norms (u)p, (v)iolations down, viola(t)ions up, or (r)andom",
2402 SCIP_CALL(
SCIPaddBoolParam(scip,
"heuristics/shiftandpropagate/sortvars",
"Should variables be sorted for the heuristic?",
2407 "Should the heuristic stop calculating optimal shift values when no more rows are violated?",
2410 "Should binary variables be shifted first?",
2413 "should variables with a zero shifting value be delayed instead of being fixed?",
2416 "should binary variables with no locks in one direction be fixed to that direction?",
2419 "should binary variables with no locks be preferred in the ordering?",
2422 "should coefficients and left/right hand sides be normalized by max row coeff?",
2425 "should row weight be increased every time the row is violated?",
2428 "should implicit integer variables be treated as continuous variables?",
2431 "should the heuristic choose the best candidate in every round? (set to FALSE for static order)?",
2434 "maximum percentage of allowed cutoffs before stopping the heuristic",
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
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_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)
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen)
#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
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
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
unsigned int SCIPinitializeRandomSeed(SCIP *scip, int initialseedvalue)
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)
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)