cancel nonzeros of the constraint matrix based on the columns
This presolver attempts to cancel non-zero entries of the constraint matrix by adding scaled columns to other columns.
In more detail, for two columns A_{j.} and A_{k.}, suppose for a given value s, we have
| A_{j.} | - | A_{j.} - s*A_{k.} | > eta,
where eta is an nonnegative integer. Then we introduce a new variable y := s*x_j + x_k and aggregate the variable x_k = y - s*x_j. After aggregation, the column of the variable x_j is A_{j.} + s*A_{j.} which is sparser than A_{j.}. In the case that x_k is nonimplied free variable, we need to add a new constraint l_k <= y - weight*x_j <= u_k into the problem to keep the bounds constraints of variable x_k.
Further information can be found in Chen et al. "Two-row and two-column mixed-integer presolve using hasing-based pairing methods".
Definition in file presol_dualsparsify.c.
#include "blockmemshell/memory.h"
#include "scip/cons_linear.h"
#include "scip/debug.h"
#include "scip/presol_dualsparsify.h"
#include "scip/pub_cons.h"
#include "scip/pub_matrix.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_presol.h"
#include "scip/pub_var.h"
#include "scip/scip_cons.h"
#include "scip/scip_general.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_nlp.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_presol.h"
#include "scip/scip_pricer.h"
#include "scip/scip_prob.h"
#include "scip/scip_probing.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_timing.h"
#include "scip/scip_var.h"
#include <string.h>
Go to the source code of this file.
Data Structures | |
struct | ColConsPair |
Macros | |
#define | PRESOL_NAME "dualsparsify" |
#define | PRESOL_DESC "eliminate non-zero coefficients" |
#define | PRESOL_PRIORITY -240000 |
#define | PRESOL_MAXROUNDS -1 |
#define | PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */ |
#define | DEFAULT_ENABLECOPY TRUE |
#define | DEFAULT_PRESERVEINTCOEFS FALSE |
#define | DEFAULT_PRESERVEGOODLOCKS FALSE |
#define | DEFAULT_MAX_CONT_FILLIN 1 |
#define | DEFAULT_MAX_BIN_FILLIN 1 |
#define | DEFAULT_MAX_INT_FILLIN 1 |
#define | DEFAULT_MAXCONSIDEREDNONZEROS 70 |
#define | DEFAULT_MINELIMINATEDNONZEROS 100 |
#define | DEFAULT_MAXRETRIEVEFAC 100.0 |
#define | DEFAULT_WAITINGFAC 2.0 |
#define | MAXSCALE 1000.0 |
Functions | |
static | SCIP_DECL_HASHKEYEQ (consPairsEqual) |
static | SCIP_DECL_HASHKEYVAL (consPairHashval) |
static SCIP_Real | getMaxActivitySingleRowWithoutCol (SCIP *scip, SCIP_MATRIX *matrix, int row, int col) |
static SCIP_Real | getMinActivitySingleRowWithoutCol (SCIP *scip, SCIP_MATRIX *matrix, int row, int col) |
static void | getMinMaxActivityResiduals (SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, 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 *rowub, SCIP_Bool *ubfound, SCIP_Real *rowlb, SCIP_Bool *lbfound) |
static void | getImpliedBounds (SCIP *scip, SCIP_MATRIX *matrix, int col, SCIP_Bool *ubimplied, SCIP_Bool *lbimplied) |
static SCIP_RETCODE | aggregation (SCIP *scip, SCIP_MATRIX *matrix, SCIP_PRESOLDATA *presoldata, SCIP_VAR **vars, int colidx1, int colidx2, SCIP_Bool isimpliedfree, SCIP_Real weight1) |
static SCIP_RETCODE | cancelCol (SCIP *scip, SCIP_MATRIX *matrix, SCIP_PRESOLDATA *presoldata, SCIP_HASHTABLE *pairtable, SCIP_Bool *ishashingcols, SCIP_VAR **vars, SCIP_Bool *isblockedvar, int colidx, int maxcontfillin, int maxintfillin, int maxbinfillin, int maxconsiderednonzeros, SCIP_Bool preserveintcoefs, SCIP_Longint *nuseless, int *nchgcoefs, int *ncanceled, int *nfillin, SCIP_Bool isaddedcons) |
static void | updateFailureStatistic (SCIP_PRESOLDATA *presoldata, SCIP_Bool success) |
static | SCIP_DECL_PRESOLCOPY (presolCopyDualsparsify) |
static | SCIP_DECL_PRESOLEXEC (presolExecDualsparsify) |
static | SCIP_DECL_PRESOLFREE (presolFreeDualsparsify) |
static | SCIP_DECL_PRESOLINIT (presolInitDualsparsify) |
SCIP_RETCODE | SCIPincludePresolDualsparsify (SCIP *scip) |
#define PRESOL_NAME "dualsparsify" |
Definition at line 80 of file presol_dualsparsify.c.
#define PRESOL_DESC "eliminate non-zero coefficients" |
Definition at line 81 of file presol_dualsparsify.c.
#define PRESOL_PRIORITY -240000 |
priority of the presolver (>= 0: before, < 0: after constraint handlers)
Definition at line 83 of file presol_dualsparsify.c.
#define PRESOL_MAXROUNDS -1 |
maximal number of presolving rounds the presolver participates in (-1: no limit)
Definition at line 84 of file presol_dualsparsify.c.
#define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */ |
Definition at line 85 of file presol_dualsparsify.c.
#define DEFAULT_ENABLECOPY TRUE |
should dualsparsify presolver be copied to sub-SCIPs?
Definition at line 87 of file presol_dualsparsify.c.
Referenced by SCIPincludePresolDualsparsify(), SCIPincludePresolSparsify(), and SCIPincludePresolTworowbnd().
#define DEFAULT_PRESERVEINTCOEFS FALSE |
should we forbid cancellations that destroy integer coefficients?
Definition at line 88 of file presol_dualsparsify.c.
Referenced by SCIPincludePresolDualsparsify(), and SCIPincludePresolSparsify().
#define DEFAULT_PRESERVEGOODLOCKS FALSE |
should we preserve good locked properties of variables (at most one lock in one direction)?
Definition at line 89 of file presol_dualsparsify.c.
Referenced by SCIPincludePresolDualsparsify().
#define DEFAULT_MAX_CONT_FILLIN 1 |
default value for the maximal fillin for continuous variables
Definition at line 90 of file presol_dualsparsify.c.
Referenced by SCIPincludePresolDualsparsify(), and SCIPincludePresolSparsify().
#define DEFAULT_MAX_BIN_FILLIN 1 |
default value for the maximal fillin for binary variables
Definition at line 91 of file presol_dualsparsify.c.
Referenced by SCIPincludePresolDualsparsify(), and SCIPincludePresolSparsify().
#define DEFAULT_MAX_INT_FILLIN 1 |
default value for the maximal fillin for integer variables (including binary)
Definition at line 92 of file presol_dualsparsify.c.
Referenced by SCIPincludePresolDualsparsify(), and SCIPincludePresolSparsify().
#define DEFAULT_MAXCONSIDEREDNONZEROS 70 |
maximal number of considered nonzeros within one column (-1: no limit)
Definition at line 93 of file presol_dualsparsify.c.
#define DEFAULT_MINELIMINATEDNONZEROS 100 |
minimal eleminated nonzeros within one column if we need to add a constraint to the problem
Definition at line 94 of file presol_dualsparsify.c.
Referenced by SCIPincludePresolDualsparsify().
#define DEFAULT_MAXRETRIEVEFAC 100.0 |
limit on the number of useless vs. useful hashtable retrieves as a multiple of the number of constraints
Definition at line 95 of file presol_dualsparsify.c.
Referenced by SCIPincludePresolDualsparsify(), and SCIPincludePresolSparsify().
#define DEFAULT_WAITINGFAC 2.0 |
number of calls to wait until next execution as a multiple of the number of useless calls
Definition at line 96 of file presol_dualsparsify.c.
Referenced by SCIPincludePresolDualsparsify(), and SCIPincludePresolSparsify().
#define MAXSCALE 1000.0 |
maximal allowed scale for cancelling nonzeros
Definition at line 98 of file presol_dualsparsify.c.
Referenced by cancelCol(), cancelRow(), and transformNonIntegralRow().
typedef struct ColConsPair COLCONSPAIR |
Definition at line 133 of file presol_dualsparsify.c.
|
static |
returns TRUE iff both keys are equal
Definition at line 141 of file presol_dualsparsify.c.
References ColConsPair::conscoef1, ColConsPair::conscoef2, ColConsPair::consindex1, ColConsPair::consindex2, FALSE, SCIP_Real, and SCIPisEQ().
|
static |
returns the hash value of the key
Definition at line 167 of file presol_dualsparsify.c.
References ColConsPair::conscoef1, ColConsPair::conscoef2, ColConsPair::consindex1, ColConsPair::consindex2, SCIPhashThree, and SCIPrealHashCode().
|
static |
calculate maximal activity of one row without one specific column
scip | SCIP main data structure |
matrix | matrix containing the constraints |
row | row index |
col | column index |
Definition at line 178 of file presol_dualsparsify.c.
References assert(), c, NULL, SCIP_Real, SCIPisInfinity(), SCIPmatrixGetColLb(), SCIPmatrixGetColUb(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowNNonzs(), and SCIPmatrixGetRowValPtr().
Referenced by getMinMaxActivityResiduals().
|
static |
calculate minimal activity of one row without one specific column
scip | SCIP main data structure |
matrix | matrix containing the constraints |
row | row index |
col | column index |
Definition at line 232 of file presol_dualsparsify.c.
References assert(), c, NULL, SCIP_Real, SCIPisInfinity(), SCIPmatrixGetColLb(), SCIPmatrixGetColUb(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowNNonzs(), and SCIPmatrixGetRowValPtr().
Referenced by getMinMaxActivityResiduals().
|
static |
get minimal and maximal residual activity without one specified column
scip | SCIP main data structure |
matrix | matrix containing the constraints |
col | column index |
row | row index |
val | coefficient of this variable in this row |
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 286 of file presol_dualsparsify.c.
References assert(), FALSE, getMaxActivitySingleRowWithoutCol(), getMinActivitySingleRowWithoutCol(), NULL, SCIP_Bool, SCIP_Real, SCIPinfinity(), SCIPisInfinity(), SCIPmatrixGetColLb(), SCIPmatrixGetColUb(), SCIPmatrixGetRowMaxActivity(), SCIPmatrixGetRowMinActivity(), SCIPmatrixGetRowNMaxActNegInf(), SCIPmatrixGetRowNMaxActPosInf(), SCIPmatrixGetRowNMinActNegInf(), SCIPmatrixGetRowNMinActPosInf(), 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 |
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 424 of file presol_dualsparsify.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 |
ubimplied | flag indicating an implied upper bound |
lbimplied | flag indicating an implied lower bound |
Definition at line 492 of file presol_dualsparsify.c.
References assert(), FALSE, getVarBoundsOfRow(), NULL, SCIP_Bool, SCIP_Real, SCIPinfinity(), SCIPisGE(), SCIPisInfinity(), SCIPisLE(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColLb(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetColUb(), SCIPmatrixGetColValPtr(), and TRUE.
Referenced by aggregation(), cancelCol(), and SCIP_DECL_PRESOLEXEC().
|
static |
y = weight1 * var[colidx1] + var[colidx2]
scip | SCIP datastructure |
matrix | matrix datastructure |
presoldata | presolver data |
vars | the current variables |
colidx1 | one of the indexes of column to try nonzero cancellation for |
colidx2 | one of the indexes of column to try nonzero cancellation for |
isimpliedfree | is the aggregated variable implied free? |
weight1 | weight variable one in the aggregated expression |
Definition at line 553 of file presol_dualsparsify.c.
References assert(), FALSE, getImpliedBounds(), NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPaddCons(), SCIPaddVar(), SCIPcreateConsLinear(), SCIPcreateVar(), SCIPdebugAddSolVal, SCIPdebugGetSolVal, SCIPdebugMsg, SCIPdebugPrintCons, SCIPdoNotMultaggrVar(), SCIPinfinity(), SCIPisInfinity(), SCIPisZero(), SCIPmatrixRemoveColumnBounds(), SCIPmultiaggregateVar(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarIsInitial(), SCIPvarIsIntegral(), SCIPvarIsRemovable(), TRUE, and vars.
Referenced by cancelCol().
|
static |
try nonzero cancellation for given column
scip | SCIP datastructure |
matrix | the constraint matrix |
presoldata | presolver data |
pairtable | the hashtable containing COLCONSPAIR's of equations |
ishashingcols | array to indicates whether it is impliedfree or not |
vars | array to store the current variables |
isblockedvar | array to indicates whether it is blocked or not |
colidx | index of column to try nonzero cancellation for |
maxcontfillin | maximal fill-in allowed for continuous variables |
maxintfillin | maximal fill-in allowed for integral variables |
maxbinfillin | maximal fill-in allowed for binary variables |
maxconsiderednonzeros | maximal number of nonzeros to consider for cancellation |
preserveintcoefs | only perform nonzero cancellation if integrality of coefficients is preserved? |
nuseless | pointer to update number of useless hashtable retrieves |
nchgcoefs | pointer to update number of changed coefficients |
ncanceled | pointer to update number of canceled nonzeros |
nfillin | pointer to update the produced fill-in |
isaddedcons | whether a linear constraint required to added to keep the validity |
Definition at line 706 of file presol_dualsparsify.c.
References a, aggregation(), assert(), b, bestcand, ColConsPair::colindex, ColConsPair::conscoef1, ColConsPair::conscoef2, ColConsPair::consindex1, ColConsPair::consindex2, COPYSIGN, FALSE, getImpliedBounds(), i, MAX, MAXSCALE, MIN, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_IMPLINT, SCIPallocBufferArray, SCIPdebugMsg, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPhashtableRetrieve(), SCIPisEQ(), SCIPisInfinity(), SCIPisIntegral(), SCIPisZero(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNDownlocks(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetColNUplocks(), SCIPmatrixGetColValPtr(), SCIPmatrixGetNColumns(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowRhs(), SCIPsortRealInt(), SCIPswapPointers(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), SCIPvarIsIntegral(), TRUE, and vars.
Referenced by SCIP_DECL_PRESOLEXEC().
|
static |
updates failure counter after one execution
presoldata | presolver data |
success | was this execution successful? |
Definition at line 1204 of file presol_dualsparsify.c.
References assert(), NULL, SCIP_Bool, and SCIP_Real.
Referenced by SCIP_DECL_PRESOLEXEC().
|
static |
copy method for constraint handler plugins (called when SCIP copies plugins)
Definition at line 1229 of file presol_dualsparsify.c.
References assert(), NULL, PRESOL_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePresolDualsparsify(), SCIPpresolGetData(), and SCIPpresolGetName().
|
static |
execution method of presolver
Definition at line 1251 of file presol_dualsparsify.c.
References assert(), c, cancelCol(), ColConsPair::colindex, ColConsPair::conscoef1, ColConsPair::conscoef2, ColConsPair::consindex1, ColConsPair::consindex2, FALSE, getImpliedBounds(), i, MIN, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIP_VERBLEVEL_HIGH, SCIPallocBufferArray, SCIPblkmem(), SCIPcalcMemGrowSize(), SCIPdebugMsg, SCIPdoNotAggr(), SCIPdoNotMultaggrVar(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetNRuns(), SCIPgetSolvingTime(), SCIPhashtableCreate(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPhashtableRemove(), SCIPhashtableRemoveAll(), SCIPhashtableRetrieve(), SCIPisStopped(), SCIPmatrixCreate(), SCIPmatrixDownlockConflict(), SCIPmatrixFree(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetColValPtr(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetVar(), SCIPmatrixUplockConflict(), SCIPpresolGetData(), SCIPreallocBufferArray, SCIPsortIntInt(), SCIPsortIntReal(), SCIPsortRealInt(), SCIPverbMessage(), TRUE, updateFailureStatistic(), and vars.
|
static |
destructor of presolver to free user data (called when SCIP is exiting)
Definition at line 1746 of file presol_dualsparsify.c.
References assert(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPpresolGetData(), and SCIPpresolSetData().
|
static |
initialization method of presolver (called after problem was transformed)
Definition at line 1762 of file presol_dualsparsify.c.
References SCIP_OKAY, and SCIPpresolGetData().
SCIP_RETCODE SCIPincludePresolDualsparsify | ( | SCIP * | scip | ) |
creates the dualsparsify presolver and includes it in SCIP
scip | SCIP data structure |
Definition at line 1776 of file presol_dualsparsify.c.
References DEFAULT_ENABLECOPY, DEFAULT_MAX_BIN_FILLIN, DEFAULT_MAX_CONT_FILLIN, DEFAULT_MAX_INT_FILLIN, DEFAULT_MAXCONSIDEREDNONZEROS, DEFAULT_MAXRETRIEVEFAC, DEFAULT_MINELIMINATEDNONZEROS, DEFAULT_PRESERVEGOODLOCKS, DEFAULT_PRESERVEINTCOEFS, DEFAULT_WAITINGFAC, FALSE, NULL, PRESOL_DESC, PRESOL_MAXROUNDS, PRESOL_NAME, PRESOL_PRIORITY, PRESOL_TIMING, SCIP_CALL, SCIP_OKAY, SCIP_REAL_MAX, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPaddRealParam(), SCIPallocBlockMemory, SCIPincludePresolBasic(), SCIPsetPresolCopy(), SCIPsetPresolFree(), SCIPsetPresolInit(), and TRUE.
Referenced by SCIP_DECL_PRESOLCOPY(), and SCIPincludeDefaultPlugins().