Scippy

SCIP

Solving Constraint Integer Programs

presol_redvub.c File Reference

Detailed Description

remove redundant variable upper bound constraints

Author
Dieter Weninger

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)
 

Macro Definition Documentation

#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().

Function Documentation

static SCIP_Bool isVub ( SCIP scip,
SCIP_MATRIX matrix,
int  row,
SCIP_Real lowthreshold,
SCIP_Real highthreshold,
int *  conidx,
int *  binidx 
)
static

verify if the constraint is a variable upper bound constraint

Parameters
scipSCIP main data structure
matrixmatrix instance
rowrow index
lowthresholdlow switching threshold
highthresholdhigh switching threshold
conidxvariable index of continuous variable
binidxvariable index of binary variable

Definition at line 54 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().

static SCIP_Bool isVlb ( SCIP scip,
SCIP_MATRIX matrix,
int  row,
SCIP_Real lowthreshold,
SCIP_Real highthreshold,
int *  conidx,
int *  binidx 
)
static

verify if the constraint is a variable lower bound constraint

Parameters
scipSCIP main data structure
matrixmatrix instance
rowrow index
lowthresholdlow switching threshold
highthresholdhigh switching threshold
conidxvariable index of continuous variable
binidxvariable index of binary variable

Definition at line 135 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().

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

searches for variable upper bound constraints on the same continuous variable with a dominance relation

Parameters
scipSCIP main data structure
matrixmatrix containing the constraints
nvubsnumber of vubs
vubsrow indices of the vubs
lowthresholdslow switching thresholds
highthresholdshigh switching thresholds
conidxsvariable indexes of continuous variable
binidxsvariable indexes of binary variable
nvaraggnumber of variables for aggregation
isvartoaggflags indicating if variable could be aggregated
aggvarspointers to the variables by which the aggregation should be done
ndeleteconsnumber of deleteable constraints
deleteconsflags which constraints could be deleted

Definition at line 217 of file presol_redvub.c.

References FALSE, MAXPAIRCOMP, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPinfoMessage(), SCIPisEQ(), SCIPisGT(), SCIPisLE(), SCIPmatrixGetColNDownlocks(), SCIPmatrixGetCons(), SCIPmatrixGetVar(), SCIPprintCons(), SCIPvarGetName(), and TRUE.

Referenced by findVarAggrRedVbcons().

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

searches for variable lower bound constraints on the same continuous variable with a dominance relation

Parameters
scipSCIP main data structure
matrixmatrix containing the constraints
nvlbsnumber of vlbs
vlbsrow indices of the vlbs
lowthresholdslow switching thresholds
highthresholdshigh switching thresholds
conidxsvariable indexes of continuous variable
binidxsvariable indexes of binary variable
nvaraggnumber of variables for aggregation
isvartoaggflags indicating if variable could be aggregated
aggvarspointers to the variables by which the aggregation should be done
ndeleteconsnumber of deleteable constraints
deleteconsflags which constraints could be deleted

Definition at line 316 of file presol_redvub.c.

References FALSE, MAXPAIRCOMP, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPinfoMessage(), SCIPisEQ(), SCIPisGE(), SCIPisLT(), SCIPmatrixGetColNUplocks(), SCIPmatrixGetCons(), SCIPmatrixGetVar(), SCIPprintCons(), SCIPvarGetName(), and TRUE.

Referenced by findVarAggrRedVbcons().

static SCIP_RETCODE findVarAggrRedVbcons ( SCIP scip,
SCIP_MATRIX matrix,
int *  nvaragg,
SCIP_Bool isvartoagg,
SCIP_VAR **  aggvars,
int *  ndeletecons,
SCIP_Bool deletecons 
)
static

find variable aggregations and redundant variable bound constraints

Parameters
scipSCIP main data structure
matrixconstraint matrix
nvaraggnumber of redundant variables
isvartoaggflags indicating which variables could be substituted/aggregated
aggvarspointers to the variables by which the aggregation should be done
ndeleteconsnumber of redundant constraints
deleteconsflags indicating which constraints could be deleted

Definition at line 415 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_RETCODE SCIPincludePresolRedvub ( SCIP scip)

creates the redvub presolver and includes it in SCIP

Parameters
scipSCIP data structure

Definition at line 648 of file presol_redvub.c.

References NULL, PRESOL_DESC, PRESOL_MAXROUNDS, PRESOL_NAME, PRESOL_PRIORITY, PRESOL_TIMING, SCIP_CALL, SCIP_OKAY, and SCIPincludePresolBasic().

Referenced by SCIPincludeDefaultPlugins().