SCIP
Solving Constraint Integer Programs
Detailed Description
remove redundant variable upper bound constraints
This presolver looks for dominating variable bound constraints on the same continuous variable and discards them. For example let x be a continuous variable and y, y' are binary variables. In addition, let two variable upper bound constraints ax - by <= e and cx - dy' <= f are given. If ax - by <= e implies cx - dy' <= f, then we can remove the second constraint and substitute/aggregate y' := y. The same can be done with variable lower bound constraints.
Definition in file presol_redvub.c.
#include "blockmemshell/memory.h"#include "scip/presol_redvub.h"#include "scip/pub_matrix.h"#include "scip/pub_message.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_presol.h"#include "scip/scip_pricer.h"#include "scip/scip_prob.h"#include "scip/scip_probing.h"#include "scip/scip_var.h"Go to the source code of this file.
Macros | |
| #define | PRESOL_NAME "redvub" |
| #define | PRESOL_DESC "detect redundant variable bound constraints" |
| #define | PRESOL_PRIORITY -9000000 |
| #define | PRESOL_MAXROUNDS 0 |
| #define | PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */ |
| #define | MAXPAIRCOMP 1000 |
Functions | |
| static SCIP_Bool | isVub (SCIP *scip, SCIP_MATRIX *matrix, int row, SCIP_Real *lowthreshold, SCIP_Real *highthreshold, int *conidx, int *binidx) |
| static SCIP_Bool | isVlb (SCIP *scip, SCIP_MATRIX *matrix, int row, SCIP_Real *lowthreshold, SCIP_Real *highthreshold, int *conidx, int *binidx) |
| static SCIP_RETCODE | detectDominatingVubs (SCIP *scip, SCIP_MATRIX *matrix, int nvubs, int *vubs, SCIP_Real *lowthresholds, SCIP_Real *highthresholds, int *conidxs, int *binidxs, int *nvaragg, SCIP_Bool *isvartoagg, SCIP_VAR **aggvars, int *ndeletecons, SCIP_Bool *deletecons) |
| static SCIP_RETCODE | detectDominatingVlbs (SCIP *scip, SCIP_MATRIX *matrix, int nvlbs, int *vlbs, SCIP_Real *lowthresholds, SCIP_Real *highthresholds, int *conidxs, int *binidxs, int *nvaragg, SCIP_Bool *isvartoagg, SCIP_VAR **aggvars, int *ndeletecons, SCIP_Bool *deletecons) |
| static SCIP_RETCODE | findVarAggrRedVbcons (SCIP *scip, SCIP_MATRIX *matrix, int *nvaragg, SCIP_Bool *isvartoagg, SCIP_VAR **aggvars, int *ndeletecons, SCIP_Bool *deletecons) |
| static | SCIP_DECL_PRESOLEXEC (presolExecRedvub) |
| SCIP_RETCODE | SCIPincludePresolRedvub (SCIP *scip) |
Macro Definition Documentation
◆ PRESOL_NAME
| #define PRESOL_NAME "redvub" |
Definition at line 48 of file presol_redvub.c.
Referenced by SCIPincludePresolRedvub().
◆ PRESOL_DESC
| #define PRESOL_DESC "detect redundant variable bound constraints" |
Definition at line 49 of file presol_redvub.c.
Referenced by SCIPincludePresolRedvub().
◆ PRESOL_PRIORITY
| #define PRESOL_PRIORITY -9000000 |
priority of the presolver (>= 0: before, < 0: after constraint handlers)
Definition at line 50 of file presol_redvub.c.
Referenced by SCIPincludePresolRedvub().
◆ PRESOL_MAXROUNDS
| #define PRESOL_MAXROUNDS 0 |
maximal number of presolving rounds the presolver participates in (-1: no limit)
Definition at line 51 of file presol_redvub.c.
Referenced by SCIPincludePresolRedvub().
◆ PRESOL_TIMING
| #define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */ |
Definition at line 52 of file presol_redvub.c.
Referenced by SCIPincludePresolRedvub().
◆ MAXPAIRCOMP
| #define MAXPAIRCOMP 1000 |
maximal number of pairwise comparisons
Definition at line 54 of file presol_redvub.c.
Referenced by detectDominatingVlbs(), and detectDominatingVubs().
Function Documentation
◆ isVub()
|
static |
verify if the constraint is a variable upper bound constraint
- Parameters
-
scip SCIP main data structure matrix matrix instance row row index lowthreshold low switching threshold highthreshold high switching threshold conidx variable index of continuous variable binidx variable index of binary variable
Definition at line 62 of file presol_redvub.c.
References FALSE, NULL, SCIP_Bool, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIPisGE(), SCIPmatrixGetNRows(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowValPtr(), SCIPmatrixGetVar(), SCIPmatrixIsRowRhsInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetType(), and TRUE.
Referenced by findVarAggrRedVbcons().
◆ isVlb()
|
static |
verify if the constraint is a variable lower bound constraint
- Parameters
-
scip SCIP main data structure matrix matrix instance row row index lowthreshold low switching threshold highthreshold high switching threshold conidx variable index of continuous variable binidx variable index of binary variable
Definition at line 143 of file presol_redvub.c.
References FALSE, NULL, SCIP_Bool, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIPisGE(), SCIPmatrixGetNRows(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowValPtr(), SCIPmatrixGetVar(), SCIPmatrixIsRowRhsInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetType(), and TRUE.
Referenced by findVarAggrRedVbcons().
◆ detectDominatingVubs()
|
static |
searches for variable upper bound constraints on the same continuous variable with a dominance relation
- Parameters
-
scip SCIP main data structure matrix matrix containing the constraints nvubs number of vubs vubs row indices of the vubs lowthresholds low switching thresholds highthresholds high switching thresholds conidxs variable indexes of continuous variable binidxs variable indexes of binary variable nvaragg number of variables for aggregation isvartoagg flags indicating if variable could be aggregated aggvars pointers to the variables by which the aggregation should be done ndeletecons number of deleteable constraints deletecons flags which constraints could be deleted
Definition at line 225 of file presol_redvub.c.
References FALSE, MAXPAIRCOMP, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPinfoMessage(), SCIPisEQ(), SCIPisGT(), SCIPisLE(), SCIPmatrixGetColNDownlocks(), SCIPmatrixGetColNUplocks(), SCIPmatrixGetCons(), SCIPmatrixGetVar(), SCIPprintCons(), SCIPvarGetName(), SCIPvarsHaveCommonClique(), and TRUE.
Referenced by findVarAggrRedVbcons().
◆ detectDominatingVlbs()
|
static |
searches for variable lower bound constraints on the same continuous variable with a dominance relation
- Parameters
-
scip SCIP main data structure matrix matrix containing the constraints nvlbs number of vlbs vlbs row indices of the vlbs lowthresholds low switching thresholds highthresholds high switching thresholds conidxs variable indexes of continuous variable binidxs variable indexes of binary variable nvaragg number of variables for aggregation isvartoagg flags indicating if variable could be aggregated aggvars pointers to the variables by which the aggregation should be done ndeletecons number of deleteable constraints deletecons flags which constraints could be deleted
Definition at line 331 of file presol_redvub.c.
References FALSE, MAXPAIRCOMP, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPinfoMessage(), SCIPisEQ(), SCIPisGE(), SCIPisLT(), SCIPmatrixGetColNDownlocks(), SCIPmatrixGetColNUplocks(), SCIPmatrixGetCons(), SCIPmatrixGetVar(), SCIPprintCons(), SCIPvarGetName(), SCIPvarsHaveCommonClique(), and TRUE.
Referenced by findVarAggrRedVbcons().
◆ findVarAggrRedVbcons()
|
static |
find variable aggregations and redundant variable bound constraints
- Parameters
-
scip SCIP main data structure matrix constraint matrix nvaragg number of redundant variables isvartoagg flags indicating which variables could be substituted/aggregated aggvars pointers to the variables by which the aggregation should be done ndeletecons number of redundant constraints deletecons flags indicating which constraints could be deleted
Definition at line 438 of file presol_redvub.c.
References detectDominatingVlbs(), detectDominatingVubs(), isVlb(), isVub(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetVar(), and SCIPvarGetType().
Referenced by SCIP_DECL_PRESOLEXEC().
◆ SCIP_DECL_PRESOLEXEC()
|
static |
execution method of presolver
Definition at line 552 of file presol_redvub.c.
References BMSclearMemoryArray, findVarAggrRedVbcons(), NULL, r, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_STAGE_PRESOLVING, SCIP_SUCCESS, SCIPaggregateVars(), SCIPallocBufferArray, SCIPdebugMsg, SCIPdelCons(), SCIPfreeBufferArray, SCIPgetNActivePricers(), SCIPgetNContVars(), SCIPgetStage(), SCIPinProbing(), SCIPisNLPEnabled(), SCIPisStopped(), SCIPmatrixCreate(), SCIPmatrixFree(), SCIPmatrixGetCons(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), and SCIPmatrixGetVar().