SCIP
Solving Constraint Integer Programs
presol_implint.h File Reference
Detailed Description
Presolver that detects implicit integer variables.
This presolver looks for implicit integer variables, which are variables whose integrality is implied. The linear constraint handler handles the simple (primal) case such as 2x + 2y + z = 3, where z is implied integral by x and y. It also handles a more complicated dual case, where we have 'dual' implied integrality if z occurs only in inequalities of the primal form (where the equality becomes an inequality), and has integral bounds.
In this plugin we explicitly look for the following structure in the constraint matrix:
\[ \begin{array}{llll} A x & + B y & & \leq c\\ D x & & + E z & \leq f\\ & & x & \in Z^{p_1} \\ & & y & \in Z^{p_2} \times R^{n_2-p_2}\\ & & z & \in Z^{p_3} \times R^{n_3-p_3} \end{array} \]
where A and c are integral and B is totally unimodular. It is not difficult to see that after fixing the x variables, that the remaining problem on the y variables is an integral polyhedron (and independent of the z variables). Hence, y is implied integral by x.
Note that this presolver only treats integral rows, where SCIPisIntegral() is used to check integrality.
Definition in file presol_implint.h.
Go to the source code of this file.
Functions | |
| SCIP_RETCODE | SCIPincludePresolImplint (SCIP *scip) |