SCIP
Solving Constraint Integer Programs
presol_qpkktref.h File Reference
Detailed Description
qpkktref presolver
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 handle the quadratic term variables of the quadratic constraint like in the method presolveAddKKTQuadQuadraticTerms()
- we handle the bilinear term variables of the quadratic constraint like in the method presolveAddKKTQuadBilinearTerms()
- we handle the linear term variables of the quadratic constraint like in the method presolveAddKKTQuadLinearTerms()
- we handle linear constraints in the method presolveAddKKTLinearConss()
- we handle aggregated variables in the method presolveAddKKTAggregatedVars()
we have a hashmap from each variable to the index of the dual constraint in the KKT conditions.
Definition in file presol_qpkktref.h.
Go to the source code of this file.
Functions | |
| SCIP_EXPORT SCIP_RETCODE | SCIPincludePresolQPKKTref (SCIP *scip) |