do bound tightening by using two rows
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) |
#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 enum Bndchgtype BNDCHGTYPE |
Definition at line 68 of file presol_tworowbnd.c.
enum Bndchgtype |
type of bound change
Enumerator | |
---|---|
LOWERBOUND | |
UPPERBOUND | |
BOTHBOUNDS |
Definition at line 62 of file presol_tworowbnd.c.
|
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}
scip | SCIP data structure |
matrix | constraint matrix object |
baserow | base row index |
otherrow | other row index |
numoverlap | overlap-size |
overlapidx | overlap column indexes |
othernonoverlapidx | other row non overlap indexes |
coefbaseoverlap | base row overlap coefficients |
coefotheroverlap | other row overlap coefficients |
coefothernonoverlap | other row non overlap coefficients |
lowerbds | lower bounds |
upperbds | upper bounds |
tmplowerbds | tmp lower bounds |
tmpupperbds | tmp upper bounds |
minratios | min LP ratios |
maxratios | max LP ratios |
minsortedidx | min LP sorted indexes |
maxsortedidx | max LP sorted indexes |
minact | calculated overlap minimal activity w.r.t. to the other row |
maxact | calculated overlap maximal activity w.r.t. to the other row |
Definition at line 224 of file presol_tworowbnd.c.
References FALSE, SCIP_Bool, SCIP_CALL_ABORT, 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 |
calculate min activity
scip | SCIP data structure |
len | length |
varidxs | variables indexes |
coefs | coefficients |
lowerbds | lower bounds |
upperbds | upper bounds |
Definition at line 656 of file presol_tworowbnd.c.
References SCIP_Real, SCIPinfinity(), and SCIPisInfinity().
Referenced by applyTightening().
|
static |
calculate max activity
scip | SCIP data structure |
len | length |
varidxs | variable indexes |
coefs | coefficients |
lowerbds | lower bounds |
upperbds | upper bounds |
infcnt | infinity counter |
Definition at line 703 of file presol_tworowbnd.c.
References SCIP_Real, SCIPinfinity(), and SCIPisInfinity().
Referenced by applyTightening().
|
static |
get max activity without one column
scip | SCIP data structure |
len | length |
varidxs | variable indexes |
coefs | coefficients |
lowerbds | upper bounds |
upperbds | lower bounds |
idx | omitting index |
Definition at line 745 of file presol_tworowbnd.c.
References SCIP_Real, and SCIPisInfinity().
Referenced by applyTightening().
|
static |
apply bound tightening on two overlapping constraints
scip | SCIP data structure |
matrix | constraint matrix object |
baserow | base row index |
otherrow | other row index |
numoverlap | overlap-size |
overlapidx | overlap column indexes |
othernonoverlapidx | other row non overlap indexes |
basenonoverlapidx | base row non overlap indexes |
coefbaseoverlap | base row overlap coefficients |
coefotheroverlap | other row overlap coefficients |
coefbasenonoverlap | base row non overlap coefficients |
coefothernonoverlap | other row non overlap coefficients |
lowerbds | lower bounds |
upperbds | upper bounds |
tmplowerbds | tmp lower bounds |
tmpupperbds | tmp upper bounds |
minratios | min LP ratios |
maxratios | max LP ratios |
minsortedidx | min LP sorted indexes |
maxsortedidx | max LP sorted indexes |
ntightenbnds | number of tightened bounds |
tighten | tightened bounds |
ndeletecons | number of redundant constraints |
deletecons | redundant constraints |
Definition at line 782 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 |
extract coefficients from matrix
scip | SCIP data structure |
matrix | constraint matrix object |
baserow | base row index |
otherrow | other row index |
numoverlap | overlap-size |
olapidxbaseorder | overlap column indexes in baserow order |
olapidxotherorder | overlap column indexes in otherrow order |
othernonoverlapidx | other row non overlap indexes |
basenonoverlapidx | base row non overlap indexes |
coefbaseoverlap | base row overlap coefficients |
coefotheroverlap | other row overlap coefficients |
coefbasenonoverlap | base row non overlap coefficients |
coefothernonoverlap | other row non overlap coefficients |
Definition at line 952 of file presol_tworowbnd.c.
References SCIP_Real, SCIPmatrixGetNColumns(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowNNonzs(), and SCIPmatrixGetRowValPtr().
Referenced by calcTwoRowBnds().
|
static |
calculate overlap-size
scip | SCIP data structure |
matrix | constraint matrix object |
baserow | base row index |
otherrow | other row index |
countings | overlap counting helper array |
clearinfo | reset helper array |
numoverlap | overlap-size |
olapidxotherorder | overlap column indexes in otherrow order |
Definition at line 1050 of file presol_tworowbnd.c.
References SCIPmatrixGetRowIdxPtr(), and SCIPmatrixGetRowNNonzs().
Referenced by calcTwoRowBnds().
|
static |
scip | SCIP data structure |
matrix | constraint matrix object |
baserow | base row index |
otherrow | other row index |
countings | overlap counting helper array |
clearinfo | reset helper array |
numoverlap | just calculated overlap-size |
olapidxbaseorder | overlap column indexes in baserow order |
Definition at line 1109 of file presol_tworowbnd.c.
References SCIPmatrixGetRowIdxPtr(), and SCIPmatrixGetRowNNonzs().
Referenced by calcTwoRowBnds().
|
static |
perform bound tightening on two rows with a specific support intersection
scip | SCIP data structure |
matrix | constraint matrix object |
nbaserows | number of base rows |
baserows | base rows indexes |
lowerbds | lower bounds |
upperbds | upper bounds |
ntightenbnds | number of tightened bounds |
tighten | bound tighten information |
ndeletecons | number of redundant constraints |
deletecons | redundant constraints |
Definition at line 1165 of file presol_tworowbnd.c.
References applyTightening(), BMSclearMemoryArray, FALSE, FASTMODE_THRESHOLD, getCoefficients(), getNumOverlap(), getOverlapBaseOrdered(), 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 |
determine base rows
scip | SCIP main data structure |
matrix | constraint matrix |
nbaserows | number of present base rows |
baserows | indexes of base rows |
Definition at line 1336 of file presol_tworowbnd.c.
References SCIP_OKAY, SCIPmatrixGetNRows(), and SCIPmatrixIsRowRhsInfinity().
Referenced by SCIP_DECL_PRESOLEXEC().
|
static |
get bounds of variables
scip | SCIP main data structure |
matrix | constraint matrix |
lowerbds | lower bounds |
upperbds | upper bounds |
Definition at line 1371 of file presol_tworowbnd.c.
References SCIPmatrixGetNColumns(), SCIPmatrixGetVar(), SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().
Referenced by SCIP_DECL_PRESOLEXEC().
|
static |
copy method for constraint handler plugins (called when SCIP copies plugins)
Definition at line 1403 of file presol_tworowbnd.c.
References PRESOL_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePresolTworowbnd(), and SCIPpresolGetName().
|
static |
execution method of presolver
Definition at line 1417 of file presol_tworowbnd.c.
References BMSclearMemoryArray, BOTHBOUNDS, calcTwoRowBnds(), FALSE, getBaseRows(), getBounds(), LOWERBOUND, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_STAGE_PRESOLVING, SCIPallocBufferArray, SCIPdelCons(), SCIPfreeBufferArray, SCIPgetNActivePricers(), SCIPgetNVars(), SCIPgetStage(), SCIPinProbing(), SCIPisNLPEnabled(), SCIPisStopped(), SCIPmatrixCreate(), SCIPmatrixFree(), SCIPmatrixGetCons(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetVar(), SCIPtightenVarLb(), SCIPtightenVarUb(), and UPPERBOUND.