dual inference presolver
This presolver does bound strengthening on continuous variables (columns) for getting bounds on dual variables y. The bounds of the dual variables are then used to fix primal variables or change the side of constraints. For ranged rows one needs to decide which side (rhs or lhs) determines the equality.
We distinguish two cases concerning complementary slackness: i) reduced cost fixing: c_j - sup_y(y^T A_{.j}) > 0 => x_j = l_j c_j - inf_y(y^T A_{.j}) < 0 => x_j = u_j ii) positive dual lower bound: y_i > 0 => A_{i.}x = b_i
Further information on this presolving approach are given in Achterberg et al. "Presolve reductions in mixed integer programming" and for a two-column extension in Chen et al. "Two-row and two-column mixed-integer presolve using hasing-based pairing methods".
Definition in file presol_dualinfer.c.
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include "scip/scipdefplugins.h"
#include "scip/pub_matrix.h"
#include "blockmemshell/memory.h"
#include "scip/cons_linear.h"
#include "scip/presol_dualinfer.h"
#include "scip/pub_cons.h"
#include "scip/pub_message.h"
#include "scip/pub_presol.h"
#include "scip/pub_var.h"
#include "scip/scip_general.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_presol.h"
#include "scip/scip_prob.h"
#include "scip/scip_probing.h"
#include "scip/scip_var.h"
Go to the source code of this file.
Data Structures | |
struct | ColPair |
Macros | |
#define | PRESOL_NAME "dualinfer" |
#define | PRESOL_DESC "exploit dual information for fixings and side changes" |
#define | PRESOL_PRIORITY (-3000) |
#define | PRESOL_MAXROUNDS 0 |
#define | PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */ |
#define | DEFAULT_TWOCOLUMN_COMBINE TRUE |
#define | DEFAULT_MAXLOOPS_DUALBNDSTR 12 |
#define | DEFAULT_MAXCONSIDEREDNONZEROS 100 |
#define | DEFAULT_MAXRETRIEVEFAILS 1000 |
#define | DEFAULT_MAXCOMBINEFAILS 1000 |
#define | DEFAULT_MAXHASHFAC 10 |
#define | DEFAULT_MAXPAIRFAC 1 |
#define | DEFAULT_MAXROWSUPPORT 3 |
Functions | |
static void * | encodeColPair (COLPAIR *colpair) |
static int | hashIndexPair (int idx1, int idx2) |
static SCIP_RETCODE | addEntry (SCIP *scip, int *pos, int *listsize, int **hashlist, int **colidxlist, int hash, int colidx) |
static void | findNextBlock (const int *list, int len, int *start, int *end) |
static SCIP_RETCODE | combineCols (SCIP *scip, int *row1idxptr, int *row2idxptr, SCIP_Real *row1valptr, SCIP_Real *row2valptr, SCIP_Real b1, SCIP_Real b2, int row1len, int row2len, int ncols, SCIP_Bool swaprow1, SCIP_Bool swaprow2, SCIP_Real *lbs, SCIP_Real *ubs, SCIP_Bool *success) |
static void | getMinMaxActivityResiduals (SCIP *scip, SCIP_MATRIX *matrix, int withoutcol, int row, SCIP_Real *lbs, SCIP_Real *ubs, SCIP_Real *minresactivity, SCIP_Real *maxresactivity, SCIP_Bool *isminsettoinfinity, SCIP_Bool *ismaxsettoinfinity) |
static void | getVarBoundsOfRow (SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *lbs, SCIP_Real *ubs, SCIP_Real *rowub, SCIP_Bool *ubfound, SCIP_Real *rowlb, SCIP_Bool *lbfound) |
static void | getImpliedBounds (SCIP *scip, SCIP_MATRIX *matrix, int col, SCIP_Real *lbs, SCIP_Real *ubs, SCIP_Bool *ubimplied, SCIP_Bool *lbimplied) |
static SCIP_Real | getMinColActWithoutRow (SCIP *scip, SCIP_MATRIX *matrix, int col, int withoutrow, SCIP_Real *lbdual, SCIP_Real *ubdual) |
static void | calcMinColActResidual (SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *lbdual, SCIP_Real *ubdual, const SCIP_Real *mincolact, const int *mincolactinf, SCIP_Real *mincolresact) |
static void | calcMinColActivity (SCIP *scip, SCIP_MATRIX *matrix, int col, SCIP_Real *lbdual, SCIP_Real *ubdual, SCIP_Real *mincolact, int *mincolactinf) |
static void | calcMaxColActivity (SCIP *scip, SCIP_MATRIX *matrix, int col, SCIP_Real *lbdual, SCIP_Real *ubdual, SCIP_Real *maxcolact, int *maxcolactinf) |
static void | infinityCountUpdate (SCIP *scip, SCIP_MATRIX *matrix, int row, SCIP_Real *lbdual, SCIP_Real *ubdual, const SCIP_Bool *isubimplied, SCIP_Real *mincolact, int *mincolactinf, SCIP_Bool ubinfchange, SCIP_Bool lbinfchange) |
static void | updateDualBounds (SCIP *scip, SCIP_MATRIX *matrix, SCIP_Real objval, SCIP_Real val, int row, SCIP_Real mincolresact, SCIP_Real *lbdual, SCIP_Real *ubdual, int *boundchanges, SCIP_Bool *ubinfchange, SCIP_Bool *lbinfchange) |
static SCIP_RETCODE | dualBoundStrengthening (SCIP *scip, SCIP_MATRIX *matrix, SCIP_PRESOLDATA *presoldata, FIXINGDIRECTION *varstofix, int *npossiblefixings, SIDECHANGE *sidestochange, int *npossiblesidechanges) |
static | SCIP_DECL_PRESOLCOPY (presolCopyDualinfer) |
static | SCIP_DECL_PRESOLFREE (presolFreeDualinfer) |
static | SCIP_DECL_PRESOLEXEC (presolExecDualinfer) |
SCIP_RETCODE | SCIPincludePresolDualinfer (SCIP *scip) |
#define PRESOL_NAME "dualinfer" |
Definition at line 70 of file presol_dualinfer.c.
#define PRESOL_DESC "exploit dual information for fixings and side changes" |
Definition at line 71 of file presol_dualinfer.c.
#define PRESOL_PRIORITY (-3000) |
priority of the presolver (>= 0: before, < 0: after constraint handlers)
Definition at line 72 of file presol_dualinfer.c.
#define PRESOL_MAXROUNDS 0 |
maximal number of presolving rounds the presolver participates in (-1: no limit)
Definition at line 73 of file presol_dualinfer.c.
#define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */ |
Definition at line 74 of file presol_dualinfer.c.
#define DEFAULT_TWOCOLUMN_COMBINE TRUE |
should two column convex combination be used per default
Definition at line 76 of file presol_dualinfer.c.
Referenced by SCIPincludePresolDualinfer().
#define DEFAULT_MAXLOOPS_DUALBNDSTR 12 |
default maximal number of loops for dual bound strengthening
Definition at line 77 of file presol_dualinfer.c.
Referenced by SCIPincludePresolDualinfer().
#define DEFAULT_MAXCONSIDEREDNONZEROS 100 |
default maximal number of considered non-zeros within one row
Definition at line 78 of file presol_dualinfer.c.
Referenced by SCIPincludePresolDualinfer(), SCIPincludePresolDualsparsify(), SCIPincludePresolSparsify(), and SCIPincludePresolTworowbnd().
#define DEFAULT_MAXRETRIEVEFAILS 1000 |
default maximal number of consecutive useless hashtable retrieves
Definition at line 79 of file presol_dualinfer.c.
Referenced by SCIPincludePresolDualinfer(), and SCIPincludePresolTworowbnd().
#define DEFAULT_MAXCOMBINEFAILS 1000 |
default maximal number of consecutive useless row combines
Definition at line 80 of file presol_dualinfer.c.
Referenced by SCIPincludePresolDualinfer(), and SCIPincludePresolTworowbnd().
#define DEFAULT_MAXHASHFAC 10 |
default maximal number of hashlist entries as multiple of number of rows in the problem
Definition at line 81 of file presol_dualinfer.c.
Referenced by SCIPincludePresolDualinfer(), and SCIPincludePresolTworowbnd().
#define DEFAULT_MAXPAIRFAC 1 |
default maximal number of processed row pairs as multiple of the number of rows in the problem
Definition at line 82 of file presol_dualinfer.c.
Referenced by SCIPincludePresolDualinfer(), and SCIPincludePresolTworowbnd().
#define DEFAULT_MAXROWSUPPORT 3 |
default maximal number of non-zeros in one row for turning an inequality into an equality
Definition at line 83 of file presol_dualinfer.c.
Referenced by SCIPincludePresolDualinfer().
typedef enum SideChange SIDECHANGE |
Definition at line 119 of file presol_dualinfer.c.
Definition at line 135 of file presol_dualinfer.c.
enum Fixingdirection |
type of variable fixing direction
Enumerator | |
---|---|
FIXATLB | |
NOFIX | fix variable at its lower bound |
FIXATUB | no fixing |
Definition at line 104 of file presol_dualinfer.c.
enum SideChange |
type of constraint side change
Enumerator | |
---|---|
RHSTOLHS | |
NOCHANGE | set rhs to value of lhs |
LHSTORHS | no side change |
Definition at line 113 of file presol_dualinfer.c.
enum signum |
Signum for convex-combined variable coefficients \((\lambda * A_{ri} + (1 - \lambda) * A_{si})\) UP - Coefficient changes from negative to positive for increasing lambda DN - Coefficient changes from positive to negative for increasing lambda POS - Coefficient is positive for all lambda in (0,1) NEG - Coefficient is negative for all lambda in (0,1)
Enumerator | |
---|---|
UP | |
DN | |
POS | |
NEG |
Definition at line 127 of file presol_dualinfer.c.
|
static |
encode contents of a colpair as void* pointer
colpair | pointer to colpair |
Definition at line 144 of file presol_dualinfer.c.
References a, assert(), b, ColPair::col1idx, and ColPair::col2idx.
Referenced by dualBoundStrengthening().
|
static |
compute single positive int hashvalue for two ints
idx1 | first integer index |
idx2 | second integer index |
Definition at line 162 of file presol_dualinfer.c.
References SCIPhashTwo.
Referenced by dualBoundStrengthening().
|
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 |
colidxlist | block memory array containing column indices |
hash | hash to be inserted |
colidx | column index to be inserted |
Definition at line 173 of file presol_dualinfer.c.
References SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBlockMemoryArray.
Referenced by dualBoundStrengthening().
|
static |
Within a sorted list, get next block with same value E.g. for [h1, h1, h1, h2, h2, h2, h2, h3,...] and end = 0 returns start = 0, end = 3 and on a second call with end = 3 on the same list returns start = 3, end = 7.
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 205 of file presol_dualinfer.c.
References i.
Referenced by dualBoundStrengthening().
|
static |
The algorithm described in Belotti P. "Bound reduction using pairs of linear inequalities" tries to derive upper and lower bounds for all variables via convex combinations of linear inequalities We apply Belotti's algorithm to pairs of columns of continuous variables.
scip | SCIP datastructure |
row1idxptr | indices specifying bound positions in lbs and ubs for first row |
row2idxptr | indices specifying bound positions in lbs und ubs for second row |
row1valptr | first row coefficients |
row2valptr | second row coefficients |
b1 | rhs of first row |
b2 | rhs of second row |
row1len | length of first row (e.g. row1idxptr and row1valptr) |
row2len | length of second row (e.g. row2idxptr and row2valptr) |
ncols | length of bound arrays lbs and ubs |
swaprow1 | should the sense of the first row be swapped to <= ? |
swaprow2 | should the sense of the second row be swapped to <= ? |
lbs | lower bound array |
ubs | upper bound array |
success | we return (success || found better bounds") |
Definition at line 227 of file presol_dualinfer.c.
References assert(), DN, FALSE, i, MAX, MIN, NEG, nvars, POS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPisEQ(), SCIPisGE(), SCIPisGT(), SCIPisInfinity(), SCIPisLE(), SCIPisLT(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIPsortIntReal(), SCIPsortRealInt(), TRUE, and UP.
Referenced by dualBoundStrengthening().
|
static |
get minimal and maximal residual activities without one specific column
scip | SCIP main data structure |
matrix | matrix containing the constraints |
withoutcol | exclude this column index |
row | row index |
lbs | lower bounds |
ubs | upper bounds |
minresactivity | minimum residual activity of this row |
maxresactivity | maximum residual activity of this row |
isminsettoinfinity | flag indicating if minresactiviy is set to infinity |
ismaxsettoinfinity | flag indicating if maxresactiviy is set to infinity |
Definition at line 719 of file presol_dualinfer.c.
References assert(), FALSE, NULL, SCIP_Bool, SCIP_Real, SCIPisInfinity(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowValPtr(), and TRUE.
Referenced by getVarBoundsOfRow().
|
static |
calculate the upper and lower bound of one variable from one row
scip | SCIP main data structure |
matrix | matrix containing the constraints |
col | column index of variable |
row | row index |
val | coefficient of this column in this row |
lbs | lower bounds |
ubs | upper bounds |
rowub | upper bound of row |
ubfound | flag indicating that an upper bound was calculated |
rowlb | lower bound of row |
lbfound | flag indicating that a lower bound was caluclated |
Definition at line 814 of file presol_dualinfer.c.
References assert(), FALSE, getMinMaxActivityResiduals(), NULL, SCIP_Bool, SCIP_Real, SCIPinfinity(), SCIPisInfinity(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowRhs(), and TRUE.
Referenced by getImpliedBounds().
|
static |
detect implied variable bounds
scip | SCIP main data structure |
matrix | matrix containing the constraints |
col | column index for implied free test |
lbs | lower bounds |
ubs | upper bounds |
ubimplied | flag indicating an implied upper bound |
lbimplied | flag indicating an implied lower bound |
Definition at line 885 of file presol_dualinfer.c.
References assert(), FALSE, getVarBoundsOfRow(), NULL, SCIP_Bool, SCIP_Real, SCIPinfinity(), SCIPisGE(), SCIPisInfinity(), SCIPisLE(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetColValPtr(), and TRUE.
Referenced by dualBoundStrengthening().
|
static |
calculate minimal column activity from one variable without one row
scip | SCIP main data structure |
matrix | matrix containing the constraints |
col | column index |
withoutrow | exclude this row index |
lbdual | lower bounds of dual variables |
ubdual | upper bounds of dual variables |
Definition at line 947 of file presol_dualinfer.c.
References assert(), NULL, SCIP_Real, SCIPisInfinity(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNNonzs(), and SCIPmatrixGetColValPtr().
Referenced by calcMinColActResidual().
|
static |
In the primal the residual activity of a constraint w.r.t. a variable is the activity of the constraint without the variable. This function does the same but in the dual. It computes the residual activity of column 'col' w.r.t. variable 'row'
scip | SCIP main data structure |
matrix | matrix containing the constraints |
col | column index |
row | row index |
val | matrix coefficient |
lbdual | lower bounds of the dual variables |
ubdual | upper bounds of the dual variables |
mincolact | minimal column activities |
mincolactinf | number of infinite contributions to minimal column activity |
mincolresact | minimal residual column activity |
Definition at line 1003 of file presol_dualinfer.c.
References assert(), getMinColActWithoutRow(), NULL, SCIP_Real, SCIPinfinity(), and SCIPisInfinity().
Referenced by dualBoundStrengthening().
|
static |
calculate minimal column activity of one column
scip | SCIP main data structure |
matrix | matrix containing the constraints |
col | column for activity calculations |
lbdual | lower bounds of dual variables |
ubdual | upper bounds of dual variables |
mincolact | minimal column activities |
mincolactinf | number of -inf contributions to minimal column activity |
Definition at line 1066 of file presol_dualinfer.c.
References assert(), NULL, SCIP_Real, SCIPinfinity(), SCIPisInfinity(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNNonzs(), and SCIPmatrixGetColValPtr().
Referenced by dualBoundStrengthening(), and infinityCountUpdate().
|
static |
calculate maximal column activity of one column
scip | SCIP main data structure |
matrix | matrix containing the constraints |
col | column for activity calculations |
lbdual | lower bounds of dual variables |
ubdual | upper bounds of dual variables |
maxcolact | minimal column activities |
maxcolactinf | number of -inf contributions to minimal column activity |
Definition at line 1126 of file presol_dualinfer.c.
References assert(), NULL, SCIP_Real, SCIPinfinity(), SCIPisInfinity(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNNonzs(), and SCIPmatrixGetColValPtr().
Referenced by dualBoundStrengthening().
|
static |
update minimal/maximal column activity infinity counters
scip | SCIP main data structure |
matrix | matrix containing the constraints |
row | row index |
lbdual | lower bounds of dual variables |
ubdual | upper bounds of dual variables |
isubimplied | flags indicating of the upper bound is implied |
mincolact | minimal column activities |
mincolactinf | number of infinity contributions to minimal column activity |
ubinfchange | flag indicating if the upper bound has changed from infinity to a finite value |
lbinfchange | flag indicating if the lower bound has changed from -infinity to a finite value |
Definition at line 1187 of file presol_dualinfer.c.
References assert(), calcMinColActivity(), SCIP_Bool, SCIP_Real, SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowNNonzs(), and SCIPmatrixGetRowValPtr().
Referenced by dualBoundStrengthening().
|
static |
update bounds of the dual variables
scip | SCIP main data structure |
matrix | matrix containing the constraints |
objval | objective function value |
val | matrix coefficient |
row | row index |
mincolresact | minimal column residual activity |
lbdual | dual lower bounds |
ubdual | dual upper bounds |
boundchanges | counter for the number of bound changes |
ubinfchange | flag indicating an upper bound change from infinite to finite |
lbinfchange | flag indicating a lower bound change from infinite to finite |
Definition at line 1483 of file presol_dualinfer.c.
References assert(), FALSE, NULL, objval, SCIP_Bool, SCIP_Real, SCIPisInfinity(), SCIPisLE(), and TRUE.
Referenced by dualBoundStrengthening().
|
static |
dual bound strengthening
scip | SCIP main data structure |
matrix | matrix containing the constraints |
presoldata | presolver data structure |
varstofix | array holding information for later upper/lower bound fixing |
npossiblefixings | number of possible fixings |
sidestochange | array holding if this is an implied equality |
npossiblesidechanges | number of possible equality changes |
Definition at line 1552 of file presol_dualinfer.c.
References addEntry(), assert(), calcMaxColActivity(), calcMinColActivity(), calcMinColActResidual(), ColPair::col1idx, ColPair::col2idx, combineCols(), encodeColPair(), FALSE, findNextBlock(), FIXATLB, FIXATUB, getImpliedBounds(), hashIndexPair(), i, infinityCountUpdate(), LHSTORHS, MAX, MIN, NOCHANGE, NOFIX, NULL, objval, RHSTOLHS, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_MAX, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPblkmem(), SCIPdebugMsg, SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPhashsetCreate(), SCIPhashsetExists(), SCIPhashsetFree(), SCIPhashsetInsert(), SCIPinfinity(), SCIPisEQ(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPisPositive(), SCIPmatrixDownlockConflict(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetColValPtr(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowRhs(), SCIPmatrixGetVar(), SCIPmatrixIsRowRhsInfinity(), SCIPmatrixUplockConflict(), SCIPsortIntInt(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetObj(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TRUE, updateDualBounds(), and var.
Referenced by SCIP_DECL_PRESOLEXEC().
|
static |
copy method for constraint handler plugins (called when SCIP copies plugins)
Definition at line 2153 of file presol_dualinfer.c.
References assert(), NULL, PRESOL_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePresolDualinfer(), and SCIPpresolGetName().
|
static |
destructor of presolver to free user data (called when SCIP is exiting)
Definition at line 2167 of file presol_dualinfer.c.
References assert(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPpresolGetData(), and SCIPpresolSetData().
|
static |
execution method of presolver
Definition at line 2183 of file presol_dualinfer.c.
References assert(), BMSclearMemoryArray, dualBoundStrengthening(), FALSE, FIXATLB, FIXATUB, i, LHSTORHS, NOCHANGE, NOFIX, NULL, result, RHSTOLHS, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIPallocBufferArray, SCIPallowWeakDualReds(), SCIPchgLhsLinear(), SCIPchgRhsLinear(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPfixVar(), SCIPfreeBufferArray, SCIPgetLhsLinear(), SCIPgetNContVars(), SCIPgetNImplVars(), SCIPgetPseudoObjval(), SCIPgetRhsLinear(), SCIPisEQ(), SCIPisInfinity(), SCIPmatrixCreate(), SCIPmatrixDownlockConflict(), SCIPmatrixFree(), SCIPmatrixGetCons(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowRhs(), SCIPmatrixGetVar(), SCIPmatrixUplockConflict(), SCIPpresolGetData(), SCIPvarGetLbLocal(), SCIPvarGetType(), SCIPvarGetUbLocal(), TRUE, and var.