39 #define PRESOL_NAME "dualinfer" 40 #define PRESOL_DESC "exploit dual informations for fixings and side changes" 41 #define PRESOL_PRIORITY -2000 42 #define PRESOL_MAXROUNDS 0 43 #define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE 93 assert(matrix != NULL);
101 for(; (rowpnt < rowend); rowpnt++, valpnt++)
113 maxactivity += val * ub;
119 maxactivity += val * lb;
144 assert(scip != NULL);
145 assert(matrix != NULL);
153 for(; (rowpnt < rowend); rowpnt++, valpnt++)
165 minactivity += val * lb;
171 minactivity += val * ub;
201 assert(scip != NULL);
202 assert(matrix != NULL);
203 assert(minresactivity != NULL);
204 assert(maxresactivity != NULL);
205 assert(isminsettoinfinity != NULL);
206 assert(ismaxsettoinfinity != NULL);
211 *isminsettoinfinity =
FALSE;
212 *ismaxsettoinfinity =
FALSE;
226 assert(nmaxactposinf >= 1);
227 if( nmaxactposinf == 1 && nmaxactneginf == 0 )
232 *ismaxsettoinfinity =
TRUE;
237 if( (nmaxactneginf + nmaxactposinf) > 0 )
240 *ismaxsettoinfinity =
TRUE;
243 *maxresactivity = maxactivity - val * ub;
248 assert(nminactneginf >= 1);
249 if( nminactneginf == 1 && nminactposinf == 0 )
254 *isminsettoinfinity =
TRUE;
259 if( (nminactneginf + nminactposinf) > 0 )
262 *isminsettoinfinity =
TRUE;
265 *minresactivity = minactivity - val * lb;
272 assert(nmaxactneginf >= 1);
273 if( nmaxactneginf == 1 && nmaxactposinf == 0 )
278 *ismaxsettoinfinity =
TRUE;
283 if( (nmaxactneginf + nmaxactposinf) > 0 )
286 *ismaxsettoinfinity =
TRUE;
289 *maxresactivity = maxactivity - val * lb;
294 assert(nminactposinf >= 1);
295 if( nminactposinf == 1 && nminactneginf == 0 )
300 *isminsettoinfinity =
TRUE;
305 if( (nminactneginf + nminactposinf) > 0 )
308 *isminsettoinfinity =
TRUE;
311 *minresactivity = minactivity - val * ub;
335 assert(rowub != NULL);
336 assert(ubfound != NULL);
342 &isminsettoinfinity, &ismaxsettoinfinity);
351 *rowub = (rhs - minresactivity)/val;
359 *rowub = (lhs - maxresactivity)/val;
381 assert(scip != NULL);
382 assert(matrix != NULL);
391 for( ; (colpnt < colend); colpnt++, valpnt++ )
398 if( ubfound && (rowub < impliedub) )
431 assert(scip != NULL);
432 assert(matrix != NULL);
433 assert(lbdual[0] != NULL);
434 assert(ubdual[0] != NULL);
435 assert(lbdual[1] != NULL);
436 assert(ubdual[1] != NULL);
443 for( ; colpnt < colend; colpnt++, valpnt++ )
448 if( row == withoutrow )
469 mincolactivity += val * lbdual[p][row];
474 mincolactivity += val * ubdual[p][row];
486 mincolactivity += val * lbdual[p][row];
491 mincolactivity += val * ubdual[p][row];
501 return mincolactivity;
521 assert(scip != NULL);
522 assert(matrix != NULL);
523 assert(lbdual[0] != NULL);
524 assert(ubdual[0] != NULL);
525 assert(lbdual[1] != NULL);
526 assert(ubdual[1] != NULL);
527 assert(mincolact != NULL);
528 assert(mincolactinf != NULL);
529 assert(mincolresact != NULL);
538 assert(mincolactinf[col] >= 1);
539 if( mincolactinf[col] == 1 )
546 if( mincolactinf[col] > 0 )
549 *mincolresact = mincolact[col] - val * lbdual[part][row];
556 assert(mincolactinf[col] >= 1);
557 if( mincolactinf[col] == 1 )
564 if( mincolactinf[col] > 0 )
567 *mincolresact = mincolact[col] - val * ubdual[part][row];
598 assert(scip != NULL);
599 assert(matrix != NULL);
600 assert(lbdual[0] != NULL);
601 assert(ubdual[0] != NULL);
602 assert(lbdual[1] != NULL);
603 assert(ubdual[1] != NULL);
604 assert(mincolact != NULL);
605 assert(maxcolact != NULL);
606 assert(maxcolactinf != NULL);
607 assert(mincolactinf != NULL);
609 for( c = startcol; c < stopcol; c++ )
648 for( ; colpnt < colend; colpnt++, valpnt++ )
659 maxcolact[c] += val * ubdual[0][row];
664 mincolact[c] += val * lbdual[0][row];
671 maxcolact[c] += val * lbdual[0][row];
676 mincolact[c] += val * ubdual[0][row];
688 maxcolact[c] += val * ubdual[1][row];
693 mincolact[c] += val * lbdual[1][row];
700 maxcolact[c] += val * lbdual[1][row];
705 mincolact[c] += val * ubdual[1][row];
711 if( mincolactinf[c] > 0 )
713 if( maxcolactinf[c] > 0 )
738 assert(scip != NULL);
739 assert(matrix != NULL);
740 assert(lbdual[0] != NULL);
741 assert(ubdual[0] != NULL);
742 assert(lbdual[1] != NULL);
743 assert(ubdual[1] != NULL);
744 assert(boundchanges != NULL);
745 assert(updateinfcnt != NULL);
747 *updateinfcnt =
FALSE;
758 newubdual = (objval - mincolresact) / val;
759 assert(
SCIPisGE(scip, newubdual, 0.0));
761 if( newubdual < ubdual[part][row] )
764 *updateinfcnt =
TRUE;
766 ubdual[part][row] = newubdual;
772 newlbdual = (objval - mincolresact) / val;
773 assert(
SCIPisGE(scip, ubdual[part][row], newlbdual));
775 if( newlbdual > lbdual[part][row] )
778 *updateinfcnt =
TRUE;
780 lbdual[part][row] = newlbdual;
811 assert(scip != NULL);
812 assert(matrix != NULL);
813 assert(lbdual[0] != NULL);
814 assert(ubdual[0] != NULL);
815 assert(lbdual[1] != NULL);
816 assert(ubdual[1] != NULL);
817 assert(mincolact != NULL);
818 assert(maxcolact != NULL);
819 assert(maxcolactinf != NULL);
820 assert(mincolactinf != NULL);
836 for(; (rowpnt < rowend); rowpnt++, valpnt++ )
849 assert(mincolactinf[c] > 0);
852 if( mincolactinf[c] == 0 )
854 mincolact, maxcolact,
855 maxcolactinf, mincolactinf, isimplfree);
862 for(; (rowpnt < rowend); rowpnt++, valpnt++ )
875 assert(mincolactinf[c] > 0);
878 if( mincolactinf[c] == 0 )
880 mincolact, maxcolact,
881 maxcolactinf, mincolactinf, isimplfree);
894 int* npossiblefixings,
896 int* npossiblesidechanges
916 assert(scip != NULL);
917 assert(matrix != NULL);
918 assert(varstofix != NULL);
919 assert(npossiblefixings != NULL);
920 assert(sidestochange != NULL);
921 assert(npossiblesidechanges != NULL);
936 for( c = 0; c < ncols; c++ )
939 isubimplied[c] =
TRUE;
941 isubimplied[c] =
FALSE;
945 for( r = 0; r < nrows; r++ )
959 while( boundchanges && loops <
MAX_LOOPS )
965 mincolact, maxcolact, maxcolactinf, mincolactinf, isubimplied);
967 for( c = 0 ; c < ncols; c++ )
988 for( ; colpnt < colend; colpnt++, valpnt++ )
1004 part, mincolact, mincolactinf, &mincolresact);
1008 lbdual, ubdual, part, &boundchanges, &updateinfcnt);
1012 infCntUpdate(scip, matrix, val, row, lbdual, ubdual, part,
1013 mincolact, maxcolact, maxcolactinf, mincolactinf, isubimplied);
1024 mincolact, maxcolact, maxcolactinf, mincolactinf, isubimplied);
1026 for( c = 0; c < ncols; c++ )
1035 if(
SCIPisLT(scip, maxcolact[c], objval) && varstofix[c] ==
NOFIX )
1038 (*npossiblefixings)++;
1042 for( r = 0; r < nrows; r++ )
1047 if(
SCIPisGT(scip, lbdual[0][r], 0.0) )
1051 (*npossiblesidechanges)++;
1063 (*npossiblesidechanges)++;
1069 (*npossiblesidechanges)++;
1096 assert(
scip != NULL);
1097 assert(presol != NULL);
1114 assert(result != NULL);
1131 if( initialized && complete )
1134 int npossiblefixings;
1139 int npossiblesidechanges;
1147 npossiblefixings = 0;
1151 npossiblesidechanges = 0;
1153 locksconsistent =
TRUE;
1159 for(i = 0; i < ncols; i++)
1167 locksconsistent =
FALSE;
1173 if( locksconsistent )
1183 if( npossiblefixings > 0 )
1185 for( i = ncols - 1; i >= 0; --i )
1227 if( npossiblesidechanges > 0 )
1229 for( i = 0; i < nrows; i++ )
1233 const char* conshdlrname;
1243 if( strcmp(conshdlrname,
"linear") == 0 )
1286 if( (nconvarsfixed + nintvarsfixed + nbinvarsfixed) > 0 || npossiblesidechanges > 0)
1288 SCIPdebugMsg(
scip,
"### fixed vars [cont: %d, int: %d, bin: %d], changed sides [%d]\n",
1289 nconvarsfixed, nintvarsfixed, nbinvarsfixed, nsideschanged);
static void calcColActivity(SCIP *scip, SCIP_MATRIX *matrix, SCIP_Bool onlyconvars, int startcol, int stopcol, SCIP_Real *lbdual[2], SCIP_Real *ubdual[2], SCIP_Real *mincolact, SCIP_Real *maxcolact, int *maxcolactinf, int *mincolactinf, SCIP_Bool *isimplfree)
SCIP_RETCODE SCIPincludePresolBasic(SCIP *scip, SCIP_PRESOL **presolptr, const char *name, const char *desc, int priority, int maxrounds, SCIP_PRESOLTIMING timing, SCIP_DECL_PRESOLEXEC((*presolexec)), SCIP_PRESOLDATA *presoldata)
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
SCIP_STAGE SCIPgetStage(SCIP *scip)
static SCIP_Bool isUpperBoundImplied(SCIP *scip, SCIP_MATRIX *matrix, int col)
static SCIP_RETCODE dualBoundStrengthening(SCIP *scip, SCIP_MATRIX *matrix, FIXINGDIRECTION *varstofix, int *npossiblefixings, SIDECHANGE *sidestochange, int *npossiblesidechanges)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
static SCIP_Real getMaxActivitySingleRowWithoutCol(SCIP *scip, SCIP_MATRIX *matrix, int row, int col)
SCIP_CONS * SCIPmatrixGetCons(SCIP_MATRIX *matrix, int row)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
SCIP_Real SCIPinfinity(SCIP *scip)
enum SCIP_Retcode SCIP_RETCODE
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
SCIP_Real SCIPmatrixGetRowMaxActivity(SCIP_MATRIX *matrix, int row)
SCIP_RETCODE SCIPmatrixCreate(SCIP *scip, SCIP_MATRIX **matrixptr, SCIP_Bool *initialized, SCIP_Bool *complete)
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNContVars(SCIP *scip)
static void infCntUpdate(SCIP *scip, SCIP_MATRIX *matrix, SCIP_Real val, int row, SCIP_Real *lbdual[2], SCIP_Real *ubdual[2], int part, SCIP_Real *mincolact, SCIP_Real *maxcolact, int *maxcolactinf, int *mincolactinf, SCIP_Bool *isimplfree)
enum Fixingdirection FIXINGDIRECTION
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
enum Fixingdirection FIXINGDIRECTION
SCIP_Real * SCIPmatrixGetColValPtr(SCIP_MATRIX *matrix, int col)
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPmatrixGetRowNMaxActPosInf(SCIP_MATRIX *matrix, int row)
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
static SCIP_DECL_PRESOLCOPY(presolCopyDualinfer)
int SCIPmatrixGetRowNMaxActNegInf(SCIP_MATRIX *matrix, int row)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPmatrixGetColLb(SCIP_MATRIX *matrix, int col)
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
SCIP_Real SCIPmatrixGetColUb(SCIP_MATRIX *matrix, int col)
SCIP_RETCODE SCIPincludePresolDualinfer(SCIP *scip)
#define SCIPallocBufferArray(scip, ptr, num)
int SCIPvarGetNLocksUp(SCIP_VAR *var)
int * SCIPmatrixGetColIdxPtr(SCIP_MATRIX *matrix, int col)
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Constraint handler for linear constraints in their most general form, .
static void calcColActResidual(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *lbdual[2], SCIP_Real *ubdual[2], int part, SCIP_Real *mincolact, int *mincolactinf, SCIP_Real *mincolresact)
int SCIPmatrixGetRowNMinActNegInf(SCIP_MATRIX *matrix, int row)
SCIP_RETCODE SCIPchgRhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
public methods for matrix
SCIP_Bool SCIPinProbing(SCIP *scip)
static SCIP_Real getMinActivitySingleRowWithoutCol(SCIP *scip, SCIP_MATRIX *matrix, int row, int col)
int SCIPvarGetNLocksDown(SCIP_VAR *var)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPmatrixGetRowRhs(SCIP_MATRIX *matrix, int row)
enum SideChange SIDECHANGE
SCIP_Bool SCIPmatrixIsRowRhsInfinity(SCIP_MATRIX *matrix, int row)
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
SCIP_Bool SCIPallowDualReds(SCIP *scip)
SCIP_Real SCIPmatrixGetRowMinActivity(SCIP_MATRIX *matrix, int row)
int SCIPmatrixGetColNDownlocks(SCIP_MATRIX *matrix, int col)
static SCIP_DECL_PRESOLEXEC(presolExecDualinfer)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
int SCIPmatrixGetRowNMinActPosInf(SCIP_MATRIX *matrix, int row)
static SCIP_Real getMinColActWithoutRow(SCIP *scip, SCIP_MATRIX *matrix, int col, int withoutrow, SCIP_Real *lbdual[2], SCIP_Real *ubdual[2], int part)
SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
int SCIPmatrixGetColNUplocks(SCIP_MATRIX *matrix, int col)
#define BMSclearMemoryArray(ptr, num)
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
static void getVarUpperBoundOfRow(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *rowub, SCIP_Bool *ubfound)
static void getMinMaxActivityResiduals(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *minresactivity, SCIP_Real *maxresactivity, SCIP_Bool *isminsettoinfinity, SCIP_Bool *ismaxsettoinfinity)
static void updateDualBounds(SCIP *scip, SCIP_MATRIX *matrix, SCIP_Real objval, SCIP_Real val, int row, SCIP_Real mincolresact, SCIP_Real *lbdual[2], SCIP_Real *ubdual[2], int part, int *boundchanges, SCIP_Bool *updateinfcnt)
int SCIPmatrixGetColNNonzs(SCIP_MATRIX *matrix, int col)