SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
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 <stdio.h>#include <assert.h>#include <string.h>#include "scip/pub_matrix.h"#include "presol_redvub.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) |
| #define PRESOL_NAME "redvub" |
Definition at line 40 of file presol_redvub.c.
Referenced by SCIPincludePresolRedvub().
| #define PRESOL_DESC "detect redundant variable bound constraints" |
Definition at line 41 of file presol_redvub.c.
Referenced by SCIPincludePresolRedvub().
| #define PRESOL_PRIORITY -9000000 |
priority of the presolver (>= 0: before, < 0: after constraint handlers)
Definition at line 42 of file presol_redvub.c.
Referenced by SCIPincludePresolRedvub().
| #define PRESOL_MAXROUNDS 0 |
maximal number of presolving rounds the presolver participates in (-1: no limit)
Definition at line 43 of file presol_redvub.c.
Referenced by SCIPincludePresolRedvub().
| #define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */ |
Definition at line 44 of file presol_redvub.c.
Referenced by SCIPincludePresolRedvub().
| #define MAXPAIRCOMP 1000 |
maximal number of pairwise comparisons
Definition at line 46 of file presol_redvub.c.
Referenced by detectDominatingVlbs(), and detectDominatingVubs().
|
static |
verify if the constraint is a variable upper bound constraint
| 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 54 of file presol_redvub.c.
References FALSE, 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().
|
static |
verify if the constraint is a variable lower bound constraint
| 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 135 of file presol_redvub.c.
References FALSE, 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().
|
static |
searches for variable upper bound constraints on the same continuous variable with a dominance relation
| 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 217 of file presol_redvub.c.
References FALSE, MAXPAIRCOMP, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPinfoMessage(), SCIPisEQ(), SCIPisGT(), SCIPisLE(), SCIPmatrixGetColNDownlocks(), SCIPmatrixGetColNUplocks(), SCIPmatrixGetCons(), SCIPmatrixGetVar(), SCIPprintCons(), SCIPvarGetName(), SCIPvarsHaveCommonClique(), and TRUE.
Referenced by findVarAggrRedVbcons().
|
static |
searches for variable lower bound constraints on the same continuous variable with a dominance relation
| 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 324 of file presol_redvub.c.
References FALSE, MAXPAIRCOMP, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPinfoMessage(), SCIPisEQ(), SCIPisGE(), SCIPisLT(), SCIPmatrixGetColNDownlocks(), SCIPmatrixGetColNUplocks(), SCIPmatrixGetCons(), SCIPmatrixGetVar(), SCIPprintCons(), SCIPvarGetName(), SCIPvarsHaveCommonClique(), and TRUE.
Referenced by findVarAggrRedVbcons().
|
static |
find variable aggregations and redundant variable bound constraints
| 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 432 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().
|
static |
execution method of presolver
Definition at line 546 of file presol_redvub.c.
References BMSclearMemoryArray, findVarAggrRedVbcons(), 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().