SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
dominated column presolver
This presolver looks for dominance relations between variable pairs. From a dominance relation and certain bound/clique-constellations variable fixings mostly at the lower bound of the dominated variable can be derived. Additionally it is possible to improve bounds by predictive bound strengthening.
Definition in file presol_domcol.c.
#include <stdio.h>#include <assert.h>#include <string.h>#include "scip/pub_matrix.h"#include "presol_domcol.h"Go to the source code of this file.
Macros | |
| #define | PRESOL_NAME "domcol" |
| #define | PRESOL_DESC "dominated column presolver" |
| #define | PRESOL_PRIORITY -1000 |
| #define | PRESOL_MAXROUNDS -1 |
| #define | PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */ |
| #define | DEFAULT_NUMMINPAIRS 1024 |
| #define | DEFAULT_NUMMAXPAIRS 1048576 |
| #define | DEFAULT_PREDBNDSTR FALSE |
| #define | DEFAULT_CONTINUOUS_RED TRUE |
Typedefs | |
| typedef enum Fixingdirection | FIXINGDIRECTION |
Enumerations | |
| enum | Fixingdirection { FIXATLB = -1, NOFIX = 0, FIXATUB = 1, FIXATLB = -1, NOFIX = 0, FIXATUB = 1, FIXATLB = -1, NOFIX = 0, FIXATLB = -1, NOFIX = 0, FIXATUB = 1 } |
Functions | |
| static void | getActivityResidualsUpperBound (SCIP *scip, SCIP_MATRIX *matrix, int row, int col, SCIP_Real coef, int upperboundcol, SCIP_Real upperboundcoef, SCIP_Real *minresactivity, SCIP_Real *maxresactivity, SCIP_Bool *success) |
| static void | getActivityResidualsLowerBound (SCIP *scip, SCIP_MATRIX *matrix, int row, int col, SCIP_Real coef, int lowerboundcol, SCIP_Real lowerboundcoef, SCIP_Real *minresactivity, SCIP_Real *maxresactivity, SCIP_Bool *success) |
| static SCIP_RETCODE | calcVarBoundsDominated (SCIP *scip, SCIP_MATRIX *matrix, int row, int coldominating, SCIP_Real valdominating, int coldominated, SCIP_Real valdominated, SCIP_Bool *ubcalculated, SCIP_Real *calculatedub, SCIP_Bool *wclbcalculated, SCIP_Real *calculatedwclb, SCIP_Bool *lbcalculated, SCIP_Real *calculatedlb, SCIP_Bool *wcubcalculated, SCIP_Real *calculatedwcub) |
| static SCIP_RETCODE | calcVarBoundsDominating (SCIP *scip, SCIP_MATRIX *matrix, int row, int coldominating, SCIP_Real valdominating, int coldominated, SCIP_Real valdominated, SCIP_Bool *ubcalculated, SCIP_Real *calculatedub, SCIP_Bool *wclbcalculated, SCIP_Real *calculatedwclb, SCIP_Bool *lbcalculated, SCIP_Real *calculatedlb, SCIP_Bool *wcubcalculated, SCIP_Real *calculatedwcub) |
| static SCIP_RETCODE | updateBounds (SCIP *scip, SCIP_MATRIX *matrix, int row, int col1, SCIP_Real val1, int col2, SCIP_Real val2, SCIP_Bool predictdominating, SCIP_Real *upperbound, SCIP_Real *wclowerbound, SCIP_Real *lowerbound, SCIP_Real *wcupperbound) |
| static SCIP_RETCODE | detectParallelCols (SCIP *scip, SCIP_MATRIX *matrix, int *pclass, SCIP_Bool *varineq) |
| static SCIP_RETCODE | predBndStr (SCIP *scip, SCIP_VAR *dominatingvar, int dominatingidx, SCIP_Real dominatingub, SCIP_Real dominatinglb, SCIP_Real dominatingwcub, SCIP_VAR *dominatedvar, int dominatedidx, SCIP_Real dominatedub, SCIP_Real dominatedwclb, SCIP_Real dominatedlb, FIXINGDIRECTION *varstofix, int *nchgbds) |
| static SCIP_RETCODE | findFixings (SCIP *scip, SCIP_MATRIX *matrix, SCIP_VAR *dominatingvar, int dominatingidx, SCIP_Real dominatingub, SCIP_Real dominatingwclb, SCIP_Real dominatinglb, SCIP_Real dominatingwcub, SCIP_VAR *dominatedvar, int dominatedidx, FIXINGDIRECTION *varstofix, SCIP_Bool onlybinvars, SCIP_Bool onlyoneone, int *nfixings) |
| static SCIP_RETCODE | findDominancePairs (SCIP *scip, SCIP_MATRIX *matrix, SCIP_PRESOLDATA *presoldata, int *searchcols, int searchsize, SCIP_Bool onlybinvars, FIXINGDIRECTION *varstofix, int *nfixings, SCIP_Longint *ndomrelations, int *nchgbds) |
| static | SCIP_DECL_PRESOLCOPY (presolCopyDomcol) |
| static | SCIP_DECL_PRESOLFREE (presolFreeDomcol) |
| static | SCIP_DECL_PRESOLEXEC (presolExecDomcol) |
| SCIP_RETCODE | SCIPincludePresolDomcol (SCIP *scip) |
| #define PRESOL_NAME "domcol" |
Definition at line 46 of file presol_domcol.c.
Referenced by SCIP_DECL_PRESOLCOPY(), and SCIPincludePresolDomcol().
| #define PRESOL_DESC "dominated column presolver" |
Definition at line 47 of file presol_domcol.c.
Referenced by SCIPincludePresolDomcol().
| #define PRESOL_PRIORITY -1000 |
priority of the presolver (>= 0: before, < 0: after constraint handlers)
Definition at line 48 of file presol_domcol.c.
Referenced by SCIPincludePresolDomcol().
| #define PRESOL_MAXROUNDS -1 |
maximal number of presolving rounds the presolver participates in (-1: no limit)
Definition at line 49 of file presol_domcol.c.
Referenced by SCIPincludePresolDomcol().
| #define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */ |
Definition at line 50 of file presol_domcol.c.
Referenced by SCIPincludePresolDomcol().
| #define DEFAULT_NUMMINPAIRS 1024 |
minimal number of pair comparisons
Definition at line 52 of file presol_domcol.c.
Referenced by SCIPincludePresolDomcol().
| #define DEFAULT_NUMMAXPAIRS 1048576 |
maximal number of pair comparisons
Definition at line 53 of file presol_domcol.c.
Referenced by SCIPincludePresolDomcol().
| #define DEFAULT_PREDBNDSTR FALSE |
should predictive bound strengthening be applied?
Definition at line 55 of file presol_domcol.c.
Referenced by SCIPincludePresolDomcol().
| #define DEFAULT_CONTINUOUS_RED TRUE |
should reductions for continuous variables be carried out?
Definition at line 56 of file presol_domcol.c.
Referenced by SCIPincludePresolDomcol().
| typedef enum Fixingdirection FIXINGDIRECTION |
Definition at line 81 of file presol_domcol.c.
| enum Fixingdirection |
type of fixing direction
Definition at line 75 of file presol_domcol.c.
|
static |
get minimum/maximum residual activity for the specified variable and with another variable set to its upper bound
Definition at line 229 of file presol_domcol.c.
References FALSE, SCIP_Real, SCIPinfinity(), SCIPisInfinity(), SCIPmatrixGetNRows(), SCIPmatrixGetRowMaxActivity(), SCIPmatrixGetRowMinActivity(), SCIPmatrixGetRowNMaxActNegInf(), SCIPmatrixGetRowNMaxActPosInf(), SCIPmatrixGetRowNMinActNegInf(), SCIPmatrixGetRowNMinActPosInf(), SCIPmatrixGetVar(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.
Referenced by calcVarBoundsDominated().
|
static |
get minimum/maximum residual activity for the specified variable and with another variable set to its lower bound
| scip | SCIP main data structure |
| matrix | matrix containing the constraints |
| row | row index |
| col | column index |
| coef | coefficient of the column in this row |
| lowerboundcol | column index of variable to set to its lower bound |
| lowerboundcoef | coefficient in this row of the column to be set to its lower bound |
| minresactivity | minimum residual activity of this row |
| maxresactivity | maximum residual activity of this row |
| success | pointer to store whether the computation was successful |
Definition at line 406 of file presol_domcol.c.
References FALSE, SCIP_Real, SCIPinfinity(), SCIPisInfinity(), SCIPmatrixGetNRows(), SCIPmatrixGetRowMaxActivity(), SCIPmatrixGetRowMinActivity(), SCIPmatrixGetRowNMaxActNegInf(), SCIPmatrixGetRowNMaxActPosInf(), SCIPmatrixGetRowNMinActNegInf(), SCIPmatrixGetRowNMinActPosInf(), SCIPmatrixGetVar(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.
Referenced by calcVarBoundsDominating().
|
static |
Calculate bounds of the dominated variable by rowbound analysis. We use a special kind of predictive rowbound analysis by first setting the dominating variable to its upper bound.
| scip | SCIP main data structure |
| matrix | matrix containing the constraints |
| row | current row index |
| coldominating | column index of dominating variable |
| valdominating | row coefficient of dominating variable |
| coldominated | column index of dominated variable |
| valdominated | row coefficient of dominated variable |
| ubcalculated | was a upper bound calculated? |
| calculatedub | predicted upper bound |
| wclbcalculated | was a lower worst case bound calculated? |
| calculatedwclb | predicted worst case lower bound |
| lbcalculated | was a lower bound calculated? |
| calculatedlb | predicted lower bound |
| wcubcalculated | was a worst case upper bound calculated? |
| calculatedwcub | calculated worst case upper bound |
Definition at line 585 of file presol_domcol.c.
References FALSE, getActivityResidualsUpperBound(), SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPinfinity(), SCIPisInfinity(), SCIPisZero(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowRhs(), SCIPmatrixGetVar(), SCIPmatrixIsRowRhsInfinity(), SCIPvarGetStatus(), and TRUE.
Referenced by updateBounds().
|
static |
Calculate bounds of the dominating variable by rowbound analysis. We use a special kind of predictive rowbound analysis by first setting the dominated variable to its lower bound.
| scip | SCIP main data structure |
| matrix | matrix containing the constraints |
| row | current row index |
| coldominating | column index of dominating variable |
| valdominating | row coefficient of dominating variable |
| coldominated | column index of dominated variable |
| valdominated | row coefficient of dominated variable |
| ubcalculated | was a upper bound calculated? |
| calculatedub | predicted upper bound |
| wclbcalculated | was a lower worst case bound calculated? |
| calculatedwclb | predicted worst case lower bound |
| lbcalculated | was a lower bound calculated? |
| calculatedlb | predicted lower bound |
| wcubcalculated | was a worst case upper bound calculated? |
| calculatedwcub | calculated worst case upper bound |
Definition at line 760 of file presol_domcol.c.
References FALSE, getActivityResidualsLowerBound(), SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPinfinity(), SCIPisInfinity(), SCIPisZero(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowRhs(), SCIPmatrixGetVar(), SCIPmatrixIsRowRhsInfinity(), SCIPvarGetStatus(), and TRUE.
Referenced by updateBounds().
|
static |
try to find new variable bounds and update them when they are better then the old bounds
| scip | SCIP main data structure |
| matrix | matrix containing the constraints |
| row | row index |
| col1 | dominating variable index |
| val1 | dominating variable coefficient |
| col2 | dominated variable index |
| val2 | dominated variable coefficient |
| predictdominating | flag indicating if bounds of dominating or dominated variable are predicted |
| upperbound | predicted upper bound |
| wclowerbound | predicted worst case lower bound |
| lowerbound | predicted lower bound |
| wcupperbound | predicted worst case upper bound |
Definition at line 933 of file presol_domcol.c.
References calcVarBoundsDominated(), calcVarBoundsDominating(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, and SCIPinfinity().
Referenced by findDominancePairs().
|
static |
detect parallel columns by using the algorithm of Bixby and Wagner see paper: "A note on Detecting Simple Redundancies in Linear Systems", June 1986
| scip | SCIP main data structure |
| matrix | matrix containing the constraints |
| pclass | parallel column classes |
| varineq | indicating if variable is within an equation |
Definition at line 1013 of file presol_domcol.c.
References BMSclearMemoryArray, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisEQ(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowValPtr(), SCIPmatrixIsRowRhsInfinity(), SCIPsortIntIntReal(), SCIPsortRealInt(), and TRUE.
Referenced by SCIP_DECL_PRESOLEXEC().
|
static |
try to improve variable bounds by predictive bound strengthening
| scip | SCIP main data structure |
| dominatingvar | dominating variable |
| dominatingidx | column index of the dominating variable |
| dominatingub | predicted upper bound of the dominating variable |
| dominatinglb | predicted lower bound of the dominating variable |
| dominatingwcub | predicted worst case upper bound of the dominating variable |
| dominatedvar | dominated variable |
| dominatedidx | column index of the dominated variable |
| dominatedub | predicted upper bound of the dominated variable |
| dominatedwclb | predicted worst case lower bound of the dominated variable |
| dominatedlb | predicted lower bound of the dominated variable |
| varstofix | array holding fixing information |
| nchgbds | count number of bound changes |
Definition at line 1184 of file presol_domcol.c.
References NOFIX, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPceil(), SCIPchgVarLb(), SCIPchgVarUb(), SCIPdebugMsg, SCIPfloor(), SCIPisInfinity(), SCIPisLE(), SCIPisLT(), SCIPisNegative(), SCIPisPositive(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetType(), SCIPvarGetUbGlobal(), and SCIPvarIsBinary().
Referenced by findDominancePairs().
|
static |
try to find variable fixings
| scip | SCIP main data structure |
| matrix | constraint matrix structure |
| dominatingvar | dominating variable |
| dominatingidx | column index of the dominating variable |
| dominatingub | predicted upper bound of the dominating variable |
| dominatingwclb | predicted worst case lower bound of the dominating variable |
| dominatinglb | predicted lower bound of the dominating variable |
| dominatingwcub | predicted worst case upper bound of the dominating variable |
| dominatedvar | dominated variable |
| dominatedidx | column index of the dominated variable |
| varstofix | array holding fixing information |
| onlybinvars | flag indicating only binary variables are present |
| onlyoneone | when onlybinvars is TRUE, flag indicates if both binary variables are in clique |
| nfixings | counter for possible fixings |
Definition at line 1382 of file presol_domcol.c.
References FALSE, FIXATLB, FIXATUB, NOFIX, SCIP_OKAY, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPisEQ(), SCIPisGE(), SCIPisInfinity(), SCIPisLE(), SCIPisNegative(), SCIPisPositive(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowRhs(), SCIPvarGetObj(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), SCIPvarsHaveCommonClique(), and TRUE.
Referenced by findDominancePairs().
|
static |
find dominance relation between variable pairs
| scip | SCIP main data structure |
| matrix | matrix containing the constraints |
| presoldata | presolver data |
| searchcols | indexes of variables for pair comparisons |
| searchsize | number of variables for pair comparisons |
| onlybinvars | flag indicating searchcols contains only binary variable indexes |
| varstofix | array holding information for later upper/lower bound fixing |
| nfixings | found number of possible fixings |
| ndomrelations | found number of dominance relations |
| nchgbds | number of changed bounds |
Definition at line 1520 of file presol_domcol.c.
References FALSE, findFixings(), FIXATLB, MAX, NOFIX, predBndStr(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPinfinity(), SCIPisEQ(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisGE(), SCIPisLT(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetColValPtr(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowMaxActivity(), SCIPmatrixGetRowMinActivity(), SCIPmatrixGetRowNMaxActNegInf(), SCIPmatrixGetRowNMaxActPosInf(), SCIPmatrixGetRowNMinActNegInf(), SCIPmatrixGetRowNMinActPosInf(), SCIPmatrixGetRowRhs(), SCIPmatrixGetVar(), SCIPmatrixIsRowRhsInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), TRUE, and updateBounds().
Referenced by SCIP_DECL_PRESOLEXEC().
|
static |
copy method for constraint handler plugins (called when SCIP copies plugins)
Definition at line 1954 of file presol_domcol.c.
References PRESOL_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePresolDomcol(), and SCIPpresolGetName().
|
static |
destructor of presolver to free user data (called when SCIP is exiting)
Definition at line 1968 of file presol_domcol.c.
References SCIP_OKAY, SCIPfreeBlockMemory, SCIPpresolGetData(), and SCIPpresolSetData().
|
static |
execution method of presolver
Definition at line 1984 of file presol_domcol.c.
References BMSclearMemoryArray, detectParallelCols(), FALSE, findDominancePairs(), FIXATLB, FIXATUB, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_OKAY, SCIP_PRESOLTIMING_EXHAUSTIVE, SCIP_Real, SCIP_STAGE_PRESOLVING, SCIP_SUCCESS, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPallocBufferArray, SCIPallowDualReds(), SCIPdebugMsg, SCIPfixVar(), SCIPfreeBufferArray, SCIPgetNActivePricers(), SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPgetNVars(), SCIPgetStage(), SCIPinProbing(), SCIPisFeasIntegral(), SCIPisNLPEnabled(), SCIPisStopped(), SCIPmatrixCreate(), SCIPmatrixFree(), SCIPmatrixGetColNDownlocks(), SCIPmatrixGetColNUplocks(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetVar(), SCIPpresolGetData(), SCIPsortIntInt(), SCIPvarGetLbGlobal(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), and TRUE.