Scippy

SCIP

Solving Constraint Integer Programs

presol_qpkktref.h File Reference

Detailed Description

qpkktref presolver

Author
Tobias Fischer

This presolver tries to add the KKT conditions as additional (redundant) constraints to the (mixed-binary) quadratic program

\[ \begin{array}{ll} \min & x^T Q x + c^T x + d \\ & A x \leq b, \\ & x \in \{0, 1\}^{p} \times R^{n-p}. \end{array} \]

We first check if the structure of the program is like (QP), see the documentation of the function checkConsQuadraticProblem().

If the problem is known to be bounded (all variables have finite lower and upper bounds), then we add the KKT conditions. For a continuous QPs the KKT conditions have the form

\[ \begin{array}{ll} Q x + c + A^T \mu = 0,\\ Ax \leq b,\\ \mu_i \cdot (Ax - b)_i = 0, & i \in \{1, \dots, m\},\\ \mu \geq 0. \end{array} \]

where \(\mu\) are the Lagrangian variables. Each of the complementarity constraints \(\mu_i \cdot (Ax - b)_i = 0\) is enforced via an SOS1 constraint for \(\mu_i\) and an additional slack variable \(s_i = (Ax - b)_i\).

For mixed-binary QPs, the KKT-like conditions are

\[ \begin{array}{ll} Q x + c + A^T \mu + I_J \lambda = 0,\\ Ax \leq b,\\ x_j \in \{0,1\} & j \in J,\\ (1 - x_j) \cdot z_j = 0 & j \in J,\\ x_j \cdot (z_j - \lambda_j) = 0 & j \in J,\\ \mu_i \cdot (Ax - b)_i = 0 & i \in \{1, \dots, m\},\\ \mu \geq 0, \end{array} \]

where \(J = \{1,\dots, p\}\), \(\mu\) and \(\lambda\) are the Lagrangian variables, and \(I_J\) is the submatrix of the \(n\times n\) identity matrix with columns indexed by \(J\). For the derivation of the KKT-like conditions, see

Branch-And-Cut for Complementarity and Cardinality Constrained Linear Programs,
Tobias Fischer, PhD Thesis (2016)

Algorithmically:

we have a hashmap from each variable to the index of the dual constraint in the KKT conditions.

Definition in file presol_qpkktref.h.

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

Go to the source code of this file.

Functions

SCIP_RETCODE SCIPincludePresolQPKKTref (SCIP *scip)