SCIP
Solving Constraint Integer Programs
presol_domcol.c File Reference
Detailed Description
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 "blockmemshell/memory.h"#include "scip/presol_domcol.h"#include "scip/pub_matrix.h"#include "scip/pub_message.h"#include "scip/pub_misc_sort.h"#include "scip/pub_presol.h"#include "scip/pub_var.h"#include "scip/scip_general.h"#include "scip/scip_mem.h"#include "scip/scip_message.h"#include "scip/scip_nlp.h"#include "scip/scip_numerics.h"#include "scip/scip_param.h"#include "scip/scip_presol.h"#include "scip/scip_pricer.h"#include "scip/scip_prob.h"#include "scip/scip_probing.h"#include "scip/scip_var.h"#include <string.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, FIXATUB = 1, 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) |
Macro Definition Documentation
◆ PRESOL_NAME
| #define PRESOL_NAME "domcol" |
Definition at line 61 of file presol_domcol.c.
Referenced by SCIP_DECL_PRESOLCOPY(), and SCIPincludePresolDomcol().
◆ PRESOL_DESC
| #define PRESOL_DESC "dominated column presolver" |
Definition at line 62 of file presol_domcol.c.
Referenced by SCIPincludePresolDomcol().
◆ PRESOL_PRIORITY
| #define PRESOL_PRIORITY -1000 |
priority of the presolver (>= 0: before, < 0: after constraint handlers)
Definition at line 63 of file presol_domcol.c.
Referenced by SCIPincludePresolDomcol().
◆ PRESOL_MAXROUNDS
| #define PRESOL_MAXROUNDS -1 |
maximal number of presolving rounds the presolver participates in (-1: no limit)
Definition at line 64 of file presol_domcol.c.
Referenced by SCIPincludePresolDomcol().
◆ PRESOL_TIMING
| #define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */ |
Definition at line 65 of file presol_domcol.c.
Referenced by SCIPincludePresolDomcol().
◆ DEFAULT_NUMMINPAIRS
| #define DEFAULT_NUMMINPAIRS 1024 |
minimal number of pair comparisons
Definition at line 67 of file presol_domcol.c.
Referenced by SCIPincludePresolDomcol().
◆ DEFAULT_NUMMAXPAIRS
| #define DEFAULT_NUMMAXPAIRS 1048576 |
maximal number of pair comparisons
Definition at line 68 of file presol_domcol.c.
Referenced by SCIPincludePresolDomcol().
◆ DEFAULT_PREDBNDSTR
| #define DEFAULT_PREDBNDSTR FALSE |
should predictive bound strengthening be applied?
Definition at line 70 of file presol_domcol.c.
Referenced by SCIPincludePresolDomcol().
◆ DEFAULT_CONTINUOUS_RED
| #define DEFAULT_CONTINUOUS_RED TRUE |
should reductions for continuous variables be carried out?
Definition at line 71 of file presol_domcol.c.
Referenced by SCIPincludePresolDomcol().
Typedef Documentation
◆ FIXINGDIRECTION
| typedef enum Fixingdirection FIXINGDIRECTION |
Definition at line 96 of file presol_domcol.c.
Enumeration Type Documentation
◆ Fixingdirection
| enum Fixingdirection |
type of fixing direction
Definition at line 90 of file presol_domcol.c.
Function Documentation
◆ getActivityResidualsUpperBound()
|
static |
get minimum/maximum residual activity for the specified variable and with another variable set to its upper bound
Definition at line 244 of file presol_domcol.c.
References FALSE, NULL, SCIP_Real, SCIPinfinity(), SCIPisInfinity(), SCIPmatrixGetNRows(), SCIPmatrixGetRowMaxActivity(), SCIPmatrixGetRowMinActivity(), SCIPmatrixGetRowNMaxActNegInf(), SCIPmatrixGetRowNMaxActPosInf(), SCIPmatrixGetRowNMinActNegInf(), SCIPmatrixGetRowNMinActPosInf(), SCIPmatrixGetVar(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.
Referenced by calcVarBoundsDominated().
◆ getActivityResidualsLowerBound()
|
static |
get minimum/maximum residual activity for the specified variable and with another variable set to its lower bound
- Parameters
-
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 421 of file presol_domcol.c.
References FALSE, NULL, SCIP_Real, SCIPinfinity(), SCIPisInfinity(), SCIPmatrixGetNRows(), SCIPmatrixGetRowMaxActivity(), SCIPmatrixGetRowMinActivity(), SCIPmatrixGetRowNMaxActNegInf(), SCIPmatrixGetRowNMaxActPosInf(), SCIPmatrixGetRowNMinActNegInf(), SCIPmatrixGetRowNMinActPosInf(), SCIPmatrixGetVar(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.
Referenced by calcVarBoundsDominating().
◆ calcVarBoundsDominated()
|
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.
- Parameters
-
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 600 of file presol_domcol.c.
References FALSE, getActivityResidualsUpperBound(), NULL, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPinfinity(), SCIPisInfinity(), SCIPisZero(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowRhs(), SCIPmatrixGetVar(), SCIPmatrixIsRowRhsInfinity(), SCIPvarGetStatus(), and TRUE.
Referenced by updateBounds().
◆ calcVarBoundsDominating()
|
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.
- Parameters
-
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 775 of file presol_domcol.c.
References FALSE, getActivityResidualsLowerBound(), NULL, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPinfinity(), SCIPisInfinity(), SCIPisZero(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowRhs(), SCIPmatrixGetVar(), SCIPmatrixIsRowRhsInfinity(), SCIPvarGetStatus(), and TRUE.
Referenced by updateBounds().
◆ updateBounds()
|
static |
try to find new variable bounds and update them when they are better then the old bounds
- Parameters
-
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 948 of file presol_domcol.c.
References calcVarBoundsDominated(), calcVarBoundsDominating(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, and SCIPinfinity().
Referenced by findDominancePairs().
◆ detectParallelCols()
|
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
- Parameters
-
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 1028 of file presol_domcol.c.
References BMSclearMemoryArray, NULL, r, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisEQ(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowValPtr(), SCIPmatrixIsRowRhsInfinity(), SCIPsortIntIntReal(), SCIPsortRealInt(), and TRUE.
Referenced by SCIP_DECL_PRESOLEXEC().
◆ predBndStr()
|
static |
try to improve variable bounds by predictive bound strengthening
- Parameters
-
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 1199 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().
◆ findFixings()
|
static |
try to find variable fixings
- Parameters
-
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 1397 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().
◆ findDominancePairs()
|
static |
find dominance relation between variable pairs
- Parameters
-
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 1535 of file presol_domcol.c.
References FALSE, findFixings(), FIXATLB, MAX, NOFIX, NULL, 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().
◆ SCIP_DECL_PRESOLCOPY()
|
static |
copy method for constraint handler plugins (called when SCIP copies plugins)
Definition at line 1969 of file presol_domcol.c.
References NULL, PRESOL_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePresolDomcol(), and SCIPpresolGetName().
◆ SCIP_DECL_PRESOLFREE()
|
static |
destructor of presolver to free user data (called when SCIP is exiting)
Definition at line 1983 of file presol_domcol.c.
References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPpresolGetData(), and SCIPpresolSetData().
◆ SCIP_DECL_PRESOLEXEC()
|
static |
execution method of presolver
Definition at line 1999 of file presol_domcol.c.
References BMSclearMemoryArray, detectParallelCols(), FALSE, findDominancePairs(), FIXATLB, FIXATUB, NOFIX, NULL, r, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_OKAY, SCIP_PRESOLTIMING_EXHAUSTIVE, SCIP_Real, SCIP_SUCCESS, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPallocBufferArray, SCIPallowStrongDualReds(), SCIPdebugMsg, SCIPfixVar(), SCIPfreeBufferArray, SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPgetNVars(), SCIPisFeasIntegral(), SCIPisStopped(), SCIPmatrixCreate(), SCIPmatrixDownlockConflict(), SCIPmatrixFree(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetVar(), SCIPmatrixUplockConflict(), SCIPpresolGetData(), SCIPsortIntInt(), SCIPvarGetLbGlobal(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), and TRUE.