Solving Constraint Integer Programs

presol_dualinfer.h File Reference

Detailed Description

dual inference presolver

Dieter Weninger
Patrick Gemander

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.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 SCIPincludePresolDualinfer (SCIP *scip)