Scippy

SCIP

Solving Constraint Integer Programs

presol_qpkktref.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file presol_qpkktref.h
17  * @brief qpkktref presolver
18  * @author Tobias Fischer
19  *
20  * This presolver tries to add the KKT conditions as additional (redundant) constraints to the (mixed-binary) quadratic
21  * program
22  * \f[
23  * \begin{array}{ll}
24  * \min & x^T Q x + c^T x + d \\
25  * & A x \leq b, \\
26  * & x \in \{0, 1\}^{p} \times R^{n-p}.
27  * \end{array}
28  * \f]
29  *
30  * We first check if the structure of the program is like (QP), see the documentation of the function
31  * checkConsQuadraticProblem().
32  *
33  * If the problem is known to be bounded (all variables have finite lower and upper bounds), then we add the KKT
34  * conditions. For a continuous QPs the KKT conditions have the form
35  * \f[
36  * \begin{array}{ll}
37  * Q x + c + A^T \mu = 0,\\
38  * Ax \leq b,\\
39  * \mu_i \cdot (Ax - b)_i = 0, & i \in \{1, \dots, m\},\\
40  * \mu \geq 0.
41  * \end{array}
42  * \f]
43  * where \f$\mu\f$ are the Lagrangian variables. Each of the complementarity constraints \f$\mu_i \cdot (Ax - b)_i = 0\f$
44  * is enforced via an SOS1 constraint for \f$\mu_i\f$ and an additional slack variable \f$s_i = (Ax - b)_i\f$.
45  *
46  * For mixed-binary QPs, the KKT-like conditions are
47  * \f[
48  * \begin{array}{ll}
49  * Q x + c + A^T \mu + I_J \lambda = 0,\\
50  * Ax \leq b,\\
51  * x_j \in \{0,1\} & j \in J,\\
52  * (1 - x_j) \cdot z_j = 0 & j \in J,\\
53  * x_j \cdot (z_j - \lambda_j) = 0 & j \in J,\\
54  * \mu_i \cdot (Ax - b)_i = 0 & i \in \{1, \dots, m\},\\
55  * \mu \geq 0,
56  * \end{array}
57  * \f]
58  * where \f$J = \{1,\dots, p\}\f$, \f$\mu\f$ and \f$\lambda\f$ are the Lagrangian variables, and \f$I_J\f$ is the
59  * submatrix of the \f$n\times n\f$ identity matrix with columns indexed by \f$J\f$. For the derivation of the KKT-like
60  * conditions, see
61  *
62  * Branch-And-Cut for Complementarity and Cardinality Constrained Linear Programs,@n
63  * Tobias Fischer, PhD Thesis (2016)
64  *
65  * Algorithmically:
66  *
67  * - we handle the quadratic term variables of the quadratic constraint like in the method
68  * presolveAddKKTQuadQuadraticTerms()
69  * - we handle the bilinear term variables of the quadratic constraint like in the method presolveAddKKTQuadBilinearTerms()
70  * - we handle the linear term variables of the quadratic constraint like in the method presolveAddKKTQuadLinearTerms()
71  * - we handle linear constraints in the method presolveAddKKTLinearConss()
72  * - we handle aggregated variables in the method presolveAddKKTAggregatedVars()
73  *
74  * we have a hashmap from each variable to the index of the dual constraint in the KKT conditions.
75  */
76 
77 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
78 
79 #ifndef __SCIP_PRESOL_QPKKTREF_H__
80 #define __SCIP_PRESOL_QPKKTREF_H__
81 
82 
83 #include "scip/scip.h"
84 
85 #ifdef __cplusplus
86 extern "C" {
87 #endif
88 
89 /** creates the QP KKT reformulation presolver and includes it in SCIP
90  *
91  * @ingroup PresolverIncludes
92  */
93 extern
95  SCIP* scip /**< SCIP data structure */
96  );
97 
98 #ifdef __cplusplus
99 }
100 #endif
101 
102 #endif
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPincludePresolQPKKTref(SCIP *scip)
SCIP callable library.