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