Solving Constraint Integer Programs

presol_dualsparsify.h File Reference

Detailed Description

cancel nonzeros of the constraint matrix based on the columns

Dieter Weninger
Leona Gottwald
Ambros Gleixner
Weikun Chen

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 no implied 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.h.

#include "scip/def.h"
#include "scip/type_retcode.h"
#include "scip/type_scip.h"

Go to the source code of this file.


SCIP_EXPORT SCIP_RETCODE SCIPincludePresolDualsparsify (SCIP *scip)

Function Documentation

◆ SCIPincludePresolDualsparsify()