do bound tightening by using two rows
Perform bound tightening on two inequalities with some common variables. Two possible methods are being used.
\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 row indices \(i \not= k\).Let \(\ell\) and \(u\) be bound vectors for x and solve the following two LPs
\begin{eqnarray*} L = \min \{ A_{kR} x_R : A_{iR} x_R + A_{iS} x_S \geq b_i, \ell \leq x \leq u \}\\ U = \max \{ A_{kR} x_R : A_{iR} x_R + A_{iS} x_S \geq b_i, \ell \leq x \leq u \} \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.
More details can be found in
Definition in file presol_tworowbnd.c.
#include <assert.h>
#include "scip/cons_linear.h"
#include "scip/scipdefplugins.h"
#include "scip/pub_matrix.h"
#include "scip/presol_tworowbnd.h"
#include <string.h>
Go to the source code of this file.
Data Structures | |
struct | RowPair |
Macros | |
#define | PRESOL_NAME "tworowbnd" |
#define | PRESOL_DESC "do bound tigthening by using two rows" |
#define | PRESOL_PRIORITY -2000 |
#define | PRESOL_MAXROUNDS 0 |
#define | PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */ |
#define | DEFAULT_ENABLECOPY TRUE |
#define | DEFAULT_MAXCONSIDEREDNONZEROS 100 |
#define | DEFAULT_MAXRETRIEVEFAILS 1000 |
#define | DEFAULT_MAXCOMBINEFAILS 1000 |
#define | DEFAULT_MAXHASHFAC 10 |
#define | DEFAULT_MAXPAIRFAC 1 |
Functions | |
static void * | encodeRowPair (ROWPAIR *rowpair) |
static int | hashIndexPair (int idx1, int idx2) |
static SCIP_RETCODE | addEntry (SCIP *scip, int *pos, int *listsize, int **hashlist, int **rowidxlist, int hash, int rowidx) |
static void | findNextBlock (int *list, int len, int *start, int *end) |
static SCIP_RETCODE | solveSingleRowLP (SCIP *scip, SCIP_Real *a, SCIP_Real b, SCIP_Real *c, SCIP_Real *lbs, SCIP_Real *ubs, int len, SCIP_Real *obj, SCIP_Bool *solvable) |
static SCIP_RETCODE | transformAndSolve (SCIP *scip, SCIP_MATRIX *matrix, int row1idx, int row2idx, SCIP_Bool swaprow1, SCIP_Bool swaprow2, SCIP_Real *aoriginal, SCIP_Real *acopy, SCIP_Real *coriginal, SCIP_Real *ccopy, SCIP_Bool *cangetbnd, SCIP_Real *lbs, SCIP_Real *ubs, SCIP_Real *newlbsoriginal, SCIP_Real *newlbscopy, SCIP_Real *newubsoriginal, SCIP_Real *newubscopy, SCIP_Bool *success, SCIP_Bool *infeasible) |
static SCIP_RETCODE | applyLPboundTightening (SCIP *scip, SCIP_MATRIX *matrix, int row1, int row2, SCIP_Bool swaprow1, SCIP_Bool swaprow2, SCIP_Real *lbs, SCIP_Real *ubs, SCIP_Bool *success) |
static SCIP_RETCODE | processHashlists (SCIP *scip, SCIP_PRESOLDATA *presoldata, SCIP_MATRIX *matrix, int *hashlist1, int *hashlist2, int lenhashlist1, int lenhashlist2, int *rowidxlist1, int *rowidxlist2, SCIP_Real *newlbs, SCIP_Real *newubs) |
static | SCIP_DECL_PRESOLCOPY (presolCopyTworowbnd) |
static | SCIP_DECL_PRESOLFREE (presolFreeTworowbnd) |
static | SCIP_DECL_PRESOLINIT (presolInitTworowbnd) |
static | SCIP_DECL_PRESOLEXEC (presolExecTworowbnd) |
SCIP_RETCODE | SCIPincludePresolTworowbnd (SCIP *scip) |
#define PRESOL_NAME "tworowbnd" |
Definition at line 73 of file presol_tworowbnd.c.
#define PRESOL_DESC "do bound tigthening by using two rows" |
Definition at line 74 of file presol_tworowbnd.c.
#define PRESOL_PRIORITY -2000 |
priority of the presolver (>= 0: before, < 0: after constraint handlers); combined with propagators
Definition at line 75 of file presol_tworowbnd.c.
#define PRESOL_MAXROUNDS 0 |
maximal number of presolving rounds the presolver participates in (-1: no limit)
Definition at line 76 of file presol_tworowbnd.c.
#define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */ |
Definition at line 77 of file presol_tworowbnd.c.
#define DEFAULT_ENABLECOPY TRUE |
should tworowbnd presolver be copied to sub-SCIPs?
Definition at line 79 of file presol_tworowbnd.c.
#define DEFAULT_MAXCONSIDEREDNONZEROS 100 |
maximal number of considered non-zeros within one row (-1: no limit)
Definition at line 80 of file presol_tworowbnd.c.
#define DEFAULT_MAXRETRIEVEFAILS 1000 |
maximal number of consecutive useless hashtable retrieves
Definition at line 81 of file presol_tworowbnd.c.
#define DEFAULT_MAXCOMBINEFAILS 1000 |
maximal number of consecutive useless row combines
Definition at line 82 of file presol_tworowbnd.c.
#define DEFAULT_MAXHASHFAC 10 |
maximal number of hashlist entries as multiple of number of rows in the problem (-1: no limit)
Definition at line 83 of file presol_tworowbnd.c.
#define DEFAULT_MAXPAIRFAC 1 |
maximal number of processed row pairs as multiple of the number of rows in the problem (-1: no limit)
Definition at line 84 of file presol_tworowbnd.c.
Definition at line 110 of file presol_tworowbnd.c.
|
static |
encode contents of a rowpair as void* pointer
rowpair | pointer to rowpair |
Definition at line 119 of file presol_tworowbnd.c.
References a, b, RowPair::row1idx, and RowPair::row2idx.
Referenced by processHashlists().
|
static |
compute single positive int hashvalue for two ints
idx1 | first integer index |
idx2 | second integer index |
Definition at line 130 of file presol_tworowbnd.c.
References SCIPhashTwo.
Referenced by SCIP_DECL_PRESOLEXEC().
|
static |
add hash/rowidx pair to hashlist/rowidxlist
scip | SCIP datastructure |
pos | position of last entry added |
listsize | size of hashlist and rowidxlist |
hashlist | block memory array containing hashes |
rowidxlist | block memory array containing row indices |
hash | hash to be inserted |
rowidx | row index to be inserted |
Definition at line 141 of file presol_tworowbnd.c.
References SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBlockMemoryArray.
Referenced by SCIP_DECL_PRESOLEXEC().
|
static |
list | list of integers |
len | length of list |
start | variable to contain start index of found block |
end | variable to contain end index of found block |
Definition at line 173 of file presol_tworowbnd.c.
References i.
Referenced by processHashlists().
|
static |
scip | SCIP data structure |
a | constraint coefficients |
b | right hand side |
c | objective coefficients |
lbs | lower variable bounds |
ubs | upper variable bounds |
len | length of arrays |
obj | objective value of solution |
solvable | status whether LP was solvable |
Definition at line 200 of file presol_tworowbnd.c.
References a, assert(), b, c, FALSE, i, MAX, MIN, nvars, obj, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPinfinity(), SCIPisEQ(), SCIPisInfinity(), SCIPisLE(), SCIPisLT(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIPselectWeightedReal(), and TRUE.
Referenced by transformAndSolve().
|
static |
Transform rows into single row LPs, solve them and and tighten bounds
During transformation, create coefficient arrays where variables with a zero coefficient in both rows are ignored and bring the LP in the form min c^T x, s.t. a^T x >= b, lbs <= x <= ubs. These LPs are then solved and bounds tightened as described in LP-bound (see above).
scip | SCIP data structure |
matrix | constraint matrix object, rows specified by row1idx/row2idx must be sorted |
row1idx | index of first row |
row2idx | index of second row |
swaprow1 | should row1 <= rhs be used in addition to lhs <= row1 |
swaprow2 | should row2 <= rhs be used in addition to lhs <= row2 |
aoriginal | buffer array for original constraint coefficients |
acopy | buffer array for coefficients adjusted to single-row LP to be solved |
coriginal | buffer array for original objective coefficients |
ccopy | buffer array for coefficients adjusted to single-row LP to be solved |
cangetbnd | buffer array for flags of which variables a bound can be generated |
lbs | buffer array for lower bounds for single-row LP |
ubs | buffer array for upper bounds for single-row LP |
newlbsoriginal | buffer array for new lower bounds not adjusted to individual single-row LPs |
newlbscopy | buffer array for adjusted lower bounds |
newubsoriginal | buffer array for new upper bounds not adjusted to individual single-row LPs |
newubscopy | buffer array for adjusted upper bounds |
success | return (success || "found better bounds") |
infeasible | we return (infeasible || "detected infeasibility") |
Definition at line 546 of file presol_tworowbnd.c.
References assert(), FALSE, i, MAX, minobj, nvars, RowPair::row1idx, RowPair::row2idx, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPceil(), SCIPdebugMsg, SCIPfloor(), SCIPisGT(), SCIPisInfinity(), SCIPisLT(), SCIPisNegative(), SCIPisPositive(), SCIPmatrixGetColName(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowRhs(), SCIPmatrixGetRowValPtr(), SCIPmatrixGetVar(), SCIPvarGetName(), SCIPvarGetType(), solveSingleRowLP(), and TRUE.
Referenced by applyLPboundTightening().
|
static |
create required buffer arrays and apply LP-based bound tightening in both directions
scip | SCIP data structure |
matrix | constraint matrix object |
row1 | index of first row |
row2 | index of seond row |
swaprow1 | should row1 <= rhs be used in addition to lhs <= row1 |
swaprow2 | should row2 <= rhs be used in addition to lhs <= row2 |
lbs | lower variable bounds |
ubs | upper variable bounds |
success | return (success || "found better bounds") |
Definition at line 1087 of file presol_tworowbnd.c.
References FALSE, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPmatrixGetNColumns(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowName(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowValPtr(), SCIPsortIntReal(), and transformAndSolve().
Referenced by processHashlists().
|
static |
scip | SCIP data structure |
presoldata | presolver data structure |
matrix | constraint matrix object |
hashlist1 | first list of hashes |
hashlist2 | second list of hashes |
lenhashlist1 | length of first hashlist |
lenhashlist2 | length of second hashlist |
rowidxlist1 | list of row indices corresponding to hashes in hashlist1 |
rowidxlist2 | list of row indices corresponding to hashes in hashlist2 |
newlbs | lower variable bounds, new bounds will be written here |
newubs | upper variable bounds, new bound will be written here |
Definition at line 1159 of file presol_tworowbnd.c.
References applyLPboundTightening(), assert(), encodeRowPair(), FALSE, findNextBlock(), i, MAX, MIN, RowPair::row1idx, RowPair::row2idx, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_MAX, SCIP_OKAY, SCIP_Real, SCIPblkmem(), SCIPhashsetCreate(), SCIPhashsetExists(), SCIPhashsetFree(), SCIPhashsetInsert(), SCIPisInfinity(), SCIPisStopped(), SCIPmatrixGetNRows(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowRhs(), and TRUE.
Referenced by SCIP_DECL_PRESOLEXEC().
|
static |
copy method for constraint handler plugins (called when SCIP copies plugins)
Definition at line 1289 of file presol_tworowbnd.c.
References assert(), NULL, PRESOL_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePresolTworowbnd(), SCIPpresolGetData(), and SCIPpresolGetName().
|
static |
destructor of presolver to free user data (called when SCIP is exiting)
Definition at line 1310 of file presol_tworowbnd.c.
References assert(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPpresolGetData(), and SCIPpresolSetData().
|
static |
initialization method of presolver (called after problem was transformed)
Definition at line 1326 of file presol_tworowbnd.c.
References SCIP_OKAY, and SCIPpresolGetData().
|
static |
execution method of presolver
Definition at line 1339 of file presol_tworowbnd.c.
References addEntry(), assert(), FALSE, hashIndexPair(), i, MIN, NULL, processHashlists(), result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_LONGINT_MAX, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPceil(), SCIPdebugMessage, SCIPdebugMsg, SCIPfixVar(), SCIPfloor(), SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPisEQ(), SCIPisGT(), SCIPisInfinity(), SCIPisLT(), SCIPisPositive(), SCIPisStopped(), SCIPmatrixCreate(), SCIPmatrixFree(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowRhs(), SCIPmatrixGetRowValPtr(), SCIPmatrixGetVar(), SCIPpresolGetData(), SCIPsortIntInt(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetType(), SCIPvarGetUbLocal(), TRUE, and var.