Scippy

SCIP

Solving Constraint Integer Programs

presol_tworowbnd.c File Reference

Detailed Description

do bound tightening by using two rows

Author
Dieter Weninger

Perform bound tightening on two inequalities with some common variables.

Let two constraints be given:

\begin{eqnarray*} A_{iR} x_R + A_{iS} x_S \geq b_i\\ A_{kR} x_R + A_{kT} x_T \geq b_k \end{eqnarray*}

with $N$ the set of variable indexes, $R \subseteq N$, $S \subseteq N$, $T \subseteq N$, $R \cap S = \emptyset$, $R \cap T = \emptyset$, $S \cap T = \emptyset$ and $i \not= k$.

Solve the following two LPs

\begin{eqnarray*} L = \min \{ A_{kR} x_R : A_{iR} x_R + A_{iS} x_S \geq b_i \}\\ U = \max \{ A_{kR} x_R : A_{iR} x_R + A_{iS} x_S \geq b_i \} \end{eqnarray*}

and use $L$ and $U$ for getting bounds on $x_T$.

If $L + \mbox{infimum}(A_{kT}x_T) \geq b_k$, then the second constraint above is redundant.

Definition in file presol_tworowbnd.c.

#include <stdio.h>
#include <assert.h>
#include <string.h>
#include "scip/pub_matrix.h"
#include "presol_tworowbnd.h"

Go to the source code of this file.

Macros

#define PRESOL_NAME   "tworowbnd"
 
#define PRESOL_DESC   "do bound tigthening by using two rows"
 
#define PRESOL_PRIORITY   -500000
 
#define PRESOL_MAXROUNDS   0
 
#define PRESOL_TIMING   SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
 
#define SUPPORT_THRESHOLD   0.5
 
#define FASTMODE_THRESHOLD   1000
 

Typedefs

typedef enum Bndchgtype BNDCHGTYPE
 

Enumerations

enum  Bndchgtype {
  LOWERBOUND = 1,
  UPPERBOUND = 2,
  BOTHBOUNDS = 3
}
 

Functions

static void getActivities (SCIP *scip, SCIP_MATRIX *matrix, int baserow, int otherrow, int numoverlap, int *overlapidx, int *othernonoverlapidx, SCIP_Real *coefbaseoverlap, SCIP_Real *coefotheroverlap, SCIP_Real *coefothernonoverlap, SCIP_Real *lowerbds, SCIP_Real *upperbds, SCIP_Real *tmplowerbds, SCIP_Real *tmpupperbds, SCIP_Real *minratios, SCIP_Real *maxratios, int *minsortedidx, int *maxsortedidx, SCIP_Real *minact, SCIP_Real *maxact)
 
static SCIP_Real getMinActivity (SCIP *scip, int len, int *varidxs, SCIP_Real *coefs, SCIP_Real *lowerbds, SCIP_Real *upperbds)
 
static SCIP_Real getMaxActivity (SCIP *scip, int len, int *varidxs, SCIP_Real *coefs, SCIP_Real *lowerbds, SCIP_Real *upperbds, int *infcnt)
 
static SCIP_Real getMaxResActivity (SCIP *scip, int len, int *varidxs, SCIP_Real *coefs, SCIP_Real *lowerbds, SCIP_Real *upperbds, int idx)
 
static void applyTightening (SCIP *scip, SCIP_MATRIX *matrix, int baserow, int otherrow, int numoverlap, int *overlapidx, int *othernonoverlapidx, int *basenonoverlapidx, SCIP_Real *coefbaseoverlap, SCIP_Real *coefotheroverlap, SCIP_Real *coefbasenonoverlap, SCIP_Real *coefothernonoverlap, SCIP_Real *lowerbds, SCIP_Real *upperbds, SCIP_Real *tmplowerbds, SCIP_Real *tmpupperbds, SCIP_Real *minratios, SCIP_Real *maxratios, int *minsortedidx, int *maxsortedidx, int *ntightenbnds, BNDCHGTYPE *tighten, int *ndeletecons, SCIP_Bool *deletecons)
 
static void getCoefficients (SCIP *scip, SCIP_MATRIX *matrix, int baserow, int otherrow, int numoverlap, int *olapidxbaseorder, int *olapidxotherorder, int *othernonoverlapidx, int *basenonoverlapidx, SCIP_Real *coefbaseoverlap, SCIP_Real *coefotheroverlap, SCIP_Real *coefbasenonoverlap, SCIP_Real *coefothernonoverlap)
 
static void getNumOverlap (SCIP *scip, SCIP_MATRIX *matrix, int baserow, int otherrow, int *countings, int *clearinfo, int *numoverlap, int *olapidxotherorder)
 
static void getOverlapBaseOrdered (SCIP *scip, SCIP_MATRIX *matrix, int baserow, int otherrow, int *countings, int *clearinfo, int numoverlap, int *olapidxbaseorder)
 
static SCIP_RETCODE calcTwoRowBnds (SCIP *scip, SCIP_MATRIX *matrix, int nbaserows, int *baserows, SCIP_Real *lowerbds, SCIP_Real *upperbds, int *ntightenbnds, BNDCHGTYPE *tighten, int *ndeletecons, SCIP_Bool *deletecons)
 
static SCIP_RETCODE getBaseRows (SCIP *scip, SCIP_MATRIX *matrix, int *nbaserows, int *baserows)
 
static void getBounds (SCIP *scip, SCIP_MATRIX *matrix, SCIP_Real *lowerbds, SCIP_Real *upperbds)
 
static SCIP_DECL_PRESOLCOPY (presolCopyTworowbnd)
 
static SCIP_DECL_PRESOLEXEC (presolExecTworowbnd)
 
SCIP_RETCODE SCIPincludePresolTworowbnd (SCIP *scip)
 

Macro Definition Documentation

#define PRESOL_NAME   "tworowbnd"

Definition at line 49 of file presol_tworowbnd.c.

Referenced by SCIP_DECL_PRESOLCOPY(), and SCIPincludePresolTworowbnd().

#define PRESOL_DESC   "do bound tigthening by using two rows"

Definition at line 50 of file presol_tworowbnd.c.

Referenced by SCIPincludePresolTworowbnd().

#define PRESOL_PRIORITY   -500000

priority of the presolver (>= 0: before, < 0: after constraint handlers)

Definition at line 51 of file presol_tworowbnd.c.

Referenced by SCIPincludePresolTworowbnd().

#define PRESOL_MAXROUNDS   0

maximal number of presolving rounds the presolver participates in (-1: no limit)

Definition at line 52 of file presol_tworowbnd.c.

Referenced by SCIPincludePresolTworowbnd().

#define PRESOL_TIMING   SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */

Definition at line 53 of file presol_tworowbnd.c.

Referenced by SCIPincludePresolTworowbnd().

#define SUPPORT_THRESHOLD   0.5

threshold for two constraints overlap

Definition at line 55 of file presol_tworowbnd.c.

Referenced by calcTwoRowBnds().

#define FASTMODE_THRESHOLD   1000

max number of baserows for switching to fast mode

Definition at line 56 of file presol_tworowbnd.c.

Referenced by calcTwoRowBnds().

Typedef Documentation

typedef enum Bndchgtype BNDCHGTYPE

Definition at line 68 of file presol_tworowbnd.c.

Enumeration Type Documentation

enum Bndchgtype

type of bound change

Enumerator
LOWERBOUND 
UPPERBOUND 
BOTHBOUNDS 

Definition at line 62 of file presol_tworowbnd.c.

Function Documentation

static void getActivities ( SCIP scip,
SCIP_MATRIX matrix,
int  baserow,
int  otherrow,
int  numoverlap,
int *  overlapidx,
int *  othernonoverlapidx,
SCIP_Real coefbaseoverlap,
SCIP_Real coefotheroverlap,
SCIP_Real coefothernonoverlap,
SCIP_Real lowerbds,
SCIP_Real upperbds,
SCIP_Real tmplowerbds,
SCIP_Real tmpupperbds,
SCIP_Real minratios,
SCIP_Real maxratios,
int *  minsortedidx,
int *  maxsortedidx,
SCIP_Real minact,
SCIP_Real maxact 
)
static

solve two LPs with one row (single constraint) each

a1x + a3y >= b1 (other row) a2x + a4z >= b2 (base row)

minact = min{a2x : a1x + a3y >= b1} maxact = max{a2x : a1x + a3y >= b1}

Parameters
scipSCIP data structure
matrixconstraint matrix object
baserowbase row index
otherrowother row index
numoverlapoverlap-size
overlapidxoverlap column indexes
othernonoverlapidxother row non overlap indexes
coefbaseoverlapbase row overlap coefficients
coefotheroverlapother row overlap coefficients
coefothernonoverlapother row non overlap coefficients
lowerbdslower bounds
upperbdsupper bounds
tmplowerbdstmp lower bounds
tmpupperbdstmp upper bounds
minratiosmin LP ratios
maxratiosmax LP ratios
minsortedidxmin LP sorted indexes
maxsortedidxmax LP sorted indexes
minactcalculated overlap minimal activity w.r.t. to the other row
maxactcalculated overlap maximal activity w.r.t. to the other row

Definition at line 224 of file presol_tworowbnd.c.

References FALSE, NULL, SCIP_Bool, SCIP_LONGINT_MAX, SCIP_Real, SCIP_STATUS_OPTIMAL, SCIPcreate(), SCIPfree(), SCIPgetBestSol(), SCIPgetNVars(), SCIPgetSolOrigObj(), SCIPgetStatus(), SCIPgetVars(), SCIPincludeDefaultPlugins(), SCIPinfinity(), SCIPisEQ(), SCIPisInfinity(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowNNonzs(), SCIPmatrixPrintRow(), SCIPreadProb(), SCIPsetIntParam(), SCIPsolve(), SCIPsortRealInt(), SCIPvarGetObj(), and TRUE.

Referenced by applyTightening().

static SCIP_Real getMinActivity ( SCIP scip,
int  len,
int *  varidxs,
SCIP_Real coefs,
SCIP_Real lowerbds,
SCIP_Real upperbds 
)
static

calculate min activity

Parameters
scipSCIP data structure
lenlength
varidxsvariables indexes
coefscoefficients
lowerbdslower bounds
upperbdsupper bounds

Definition at line 660 of file presol_tworowbnd.c.

References SCIP_Real, SCIPinfinity(), and SCIPisInfinity().

Referenced by applyTightening().

static SCIP_Real getMaxActivity ( SCIP scip,
int  len,
int *  varidxs,
SCIP_Real coefs,
SCIP_Real lowerbds,
SCIP_Real upperbds,
int *  infcnt 
)
static

calculate max activity

Parameters
scipSCIP data structure
lenlength
varidxsvariable indexes
coefscoefficients
lowerbdslower bounds
upperbdsupper bounds
infcntinfinity counter

Definition at line 707 of file presol_tworowbnd.c.

References SCIP_Real, SCIPinfinity(), and SCIPisInfinity().

Referenced by applyTightening().

static SCIP_Real getMaxResActivity ( SCIP scip,
int  len,
int *  varidxs,
SCIP_Real coefs,
SCIP_Real lowerbds,
SCIP_Real upperbds,
int  idx 
)
static

get max activity without one column

Parameters
scipSCIP data structure
lenlength
varidxsvariable indexes
coefscoefficients
lowerbdsupper bounds
upperbdslower bounds
idxomitting index

Definition at line 749 of file presol_tworowbnd.c.

References SCIP_Real, and SCIPisInfinity().

Referenced by applyTightening().

static void applyTightening ( SCIP scip,
SCIP_MATRIX matrix,
int  baserow,
int  otherrow,
int  numoverlap,
int *  overlapidx,
int *  othernonoverlapidx,
int *  basenonoverlapidx,
SCIP_Real coefbaseoverlap,
SCIP_Real coefotheroverlap,
SCIP_Real coefbasenonoverlap,
SCIP_Real coefothernonoverlap,
SCIP_Real lowerbds,
SCIP_Real upperbds,
SCIP_Real tmplowerbds,
SCIP_Real tmpupperbds,
SCIP_Real minratios,
SCIP_Real maxratios,
int *  minsortedidx,
int *  maxsortedidx,
int *  ntightenbnds,
BNDCHGTYPE tighten,
int *  ndeletecons,
SCIP_Bool deletecons 
)
static

apply bound tightening on two overlapping constraints

Parameters
scipSCIP data structure
matrixconstraint matrix object
baserowbase row index
otherrowother row index
numoverlapoverlap-size
overlapidxoverlap column indexes
othernonoverlapidxother row non overlap indexes
basenonoverlapidxbase row non overlap indexes
coefbaseoverlapbase row overlap coefficients
coefotheroverlapother row overlap coefficients
coefbasenonoverlapbase row non overlap coefficients
coefothernonoverlapother row non overlap coefficients
lowerbdslower bounds
upperbdsupper bounds
tmplowerbdstmp lower bounds
tmpupperbdstmp upper bounds
minratiosmin LP ratios
maxratiosmax LP ratios
minsortedidxmin LP sorted indexes
maxsortedidxmax LP sorted indexes
ntightenbndsnumber of tightened bounds
tightentightened bounds
ndeleteconsnumber of redundant constraints
deleteconsredundant constraints

Definition at line 786 of file presol_tworowbnd.c.

References BOTHBOUNDS, getActivities(), getMaxActivity(), getMaxResActivity(), getMinActivity(), LOWERBOUND, SCIP_Real, SCIPisGE(), SCIPisInfinity(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowNNonzs(), TRUE, and UPPERBOUND.

Referenced by calcTwoRowBnds().

static void getCoefficients ( SCIP scip,
SCIP_MATRIX matrix,
int  baserow,
int  otherrow,
int  numoverlap,
int *  olapidxbaseorder,
int *  olapidxotherorder,
int *  othernonoverlapidx,
int *  basenonoverlapidx,
SCIP_Real coefbaseoverlap,
SCIP_Real coefotheroverlap,
SCIP_Real coefbasenonoverlap,
SCIP_Real coefothernonoverlap 
)
static

extract coefficients from matrix

Parameters
scipSCIP data structure
matrixconstraint matrix object
baserowbase row index
otherrowother row index
numoverlapoverlap-size
olapidxbaseorderoverlap column indexes in baserow order
olapidxotherorderoverlap column indexes in otherrow order
othernonoverlapidxother row non overlap indexes
basenonoverlapidxbase row non overlap indexes
coefbaseoverlapbase row overlap coefficients
coefotheroverlapother row overlap coefficients
coefbasenonoverlapbase row non overlap coefficients
coefothernonoverlapother row non overlap coefficients

Definition at line 956 of file presol_tworowbnd.c.

References SCIP_Real, SCIPmatrixGetNColumns(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowNNonzs(), and SCIPmatrixGetRowValPtr().

Referenced by calcTwoRowBnds().

static void getNumOverlap ( SCIP scip,
SCIP_MATRIX matrix,
int  baserow,
int  otherrow,
int *  countings,
int *  clearinfo,
int *  numoverlap,
int *  olapidxotherorder 
)
static

calculate overlap-size

Parameters
scipSCIP data structure
matrixconstraint matrix object
baserowbase row index
otherrowother row index
countingsoverlap counting helper array
clearinforeset helper array
numoverlapoverlap-size
olapidxotherorderoverlap column indexes in otherrow order

Definition at line 1054 of file presol_tworowbnd.c.

References SCIPmatrixGetRowIdxPtr(), and SCIPmatrixGetRowNNonzs().

Referenced by calcTwoRowBnds().

static void getOverlapBaseOrdered ( SCIP scip,
SCIP_MATRIX matrix,
int  baserow,
int  otherrow,
int *  countings,
int *  clearinfo,
int  numoverlap,
int *  olapidxbaseorder 
)
static
Parameters
scipSCIP data structure
matrixconstraint matrix object
baserowbase row index
otherrowother row index
countingsoverlap counting helper array
clearinforeset helper array
numoverlapjust calculated overlap-size
olapidxbaseorderoverlap column indexes in baserow order

Definition at line 1113 of file presol_tworowbnd.c.

References SCIPmatrixGetRowIdxPtr(), and SCIPmatrixGetRowNNonzs().

Referenced by calcTwoRowBnds().

static SCIP_RETCODE calcTwoRowBnds ( SCIP scip,
SCIP_MATRIX matrix,
int  nbaserows,
int *  baserows,
SCIP_Real lowerbds,
SCIP_Real upperbds,
int *  ntightenbnds,
BNDCHGTYPE tighten,
int *  ndeletecons,
SCIP_Bool deletecons 
)
static

perform bound tightening on two rows with a specific support intersection

Parameters
scipSCIP data structure
matrixconstraint matrix object
nbaserowsnumber of base rows
baserowsbase rows indexes
lowerbdslower bounds
upperbdsupper bounds
ntightenbndsnumber of tightened bounds
tightenbound tighten information
ndeleteconsnumber of redundant constraints
deleteconsredundant constraints

Definition at line 1169 of file presol_tworowbnd.c.

References applyTightening(), BMSclearMemoryArray, FALSE, FASTMODE_THRESHOLD, getCoefficients(), getNumOverlap(), getOverlapBaseOrdered(), MIN, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowNNonzs(), SCIPmatrixIsRowRhsInfinity(), SUPPORT_THRESHOLD, and TRUE.

Referenced by SCIP_DECL_PRESOLEXEC().

static SCIP_RETCODE getBaseRows ( SCIP scip,
SCIP_MATRIX matrix,
int *  nbaserows,
int *  baserows 
)
static

determine base rows

Parameters
scipSCIP main data structure
matrixconstraint matrix
nbaserowsnumber of present base rows
baserowsindexes of base rows

Definition at line 1340 of file presol_tworowbnd.c.

References NULL, SCIP_OKAY, SCIPmatrixGetNRows(), and SCIPmatrixIsRowRhsInfinity().

Referenced by SCIP_DECL_PRESOLEXEC().

static void getBounds ( SCIP scip,
SCIP_MATRIX matrix,
SCIP_Real lowerbds,
SCIP_Real upperbds 
)
static

get bounds of variables

Parameters
scipSCIP main data structure
matrixconstraint matrix
lowerbdslower bounds
upperbdsupper bounds

Definition at line 1375 of file presol_tworowbnd.c.

References NULL, SCIPmatrixGetNColumns(), SCIPmatrixGetVar(), SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().

Referenced by SCIP_DECL_PRESOLEXEC().

static SCIP_DECL_PRESOLCOPY ( presolCopyTworowbnd  )
static

copy method for constraint handler plugins (called when SCIP copies plugins)

Definition at line 1407 of file presol_tworowbnd.c.

References NULL, PRESOL_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePresolTworowbnd(), and SCIPpresolGetName().

SCIP_RETCODE SCIPincludePresolTworowbnd ( SCIP scip)

creates the tworowbnd presolver and includes it in SCIP

Parameters
scipSCIP data structure

Definition at line 1547 of file presol_tworowbnd.c.

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

Referenced by SCIP_DECL_PRESOLCOPY(), and SCIPincludeDefaultPlugins().