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 2002-2022 Zuse Institute Berlin */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file presol_qpkktref.h
26  * @ingroup PRESOLVERS
27  * @brief qpkktref presolver
28  * @author Tobias Fischer
29  *
30  * This presolver tries to add the KKT conditions as additional (redundant) constraints to the (mixed-binary) quadratic
31  * program
32  * \f[
33  * \begin{array}{ll}
34  * \min & x^T Q x + c^T x + d \\
35  * & A x \leq b, \\
36  * & x \in \{0, 1\}^{p} \times R^{n-p}.
37  * \end{array}
38  * \f]
39  *
40  * We first check if the structure of the program is like (QP), see the documentation of the function
41  * checkConsQuadraticProblem().
42  *
43  * If the problem is known to be bounded (all variables have finite lower and upper bounds), then we add the KKT
44  * conditions. For a continuous QPs the KKT conditions have the form
45  * \f[
46  * \begin{array}{ll}
47  * Q x + c + A^T \mu = 0,\\
48  * Ax \leq b,\\
49  * \mu_i \cdot (Ax - b)_i = 0, & i \in \{1, \dots, m\},\\
50  * \mu \geq 0.
51  * \end{array}
52  * \f]
53  * where \f$\mu\f$ are the Lagrangian variables. Each of the complementarity constraints \f$\mu_i \cdot (Ax - b)_i = 0\f$
54  * is enforced via an SOS1 constraint for \f$\mu_i\f$ and an additional slack variable \f$s_i = (Ax - b)_i\f$.
55  *
56  * For mixed-binary QPs, the KKT-like conditions are
57  * \f[
58  * \begin{array}{ll}
59  * Q x + c + A^T \mu + I_J \lambda = 0,\\
60  * Ax \leq b,\\
61  * x_j \in \{0,1\} & j \in J,\\
62  * (1 - x_j) \cdot z_j = 0 & j \in J,\\
63  * x_j \cdot (z_j - \lambda_j) = 0 & j \in J,\\
64  * \mu_i \cdot (Ax - b)_i = 0 & i \in \{1, \dots, m\},\\
65  * \mu \geq 0,
66  * \end{array}
67  * \f]
68  * 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
69  * submatrix of the \f$n\times n\f$ identity matrix with columns indexed by \f$J\f$. For the derivation of the KKT-like
70  * conditions, see
71  *
72  * Branch-And-Cut for Complementarity and Cardinality Constrained Linear Programs,@n
73  * Tobias Fischer, PhD Thesis (2016)
74  *
75  * Algorithmically:
76  *
77  * - we handle the quadratic term variables of the quadratic constraint like in the method
78  * presolveAddKKTQuadQuadraticTerms()
79  * - we handle the bilinear term variables of the quadratic constraint like in the method presolveAddKKTQuadBilinearTerms()
80  * - we handle the linear term variables of the quadratic constraint like in the method presolveAddKKTQuadLinearTerms()
81  * - we handle linear constraints in the method presolveAddKKTLinearConss()
82  * - we handle aggregated variables in the method presolveAddKKTAggregatedVars()
83  *
84  * we have a hashmap from each variable to the index of the dual constraint in the KKT conditions.
85  */
86 
87 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
88 
89 #ifndef __SCIP_PRESOL_QPKKTREF_H__
90 #define __SCIP_PRESOL_QPKKTREF_H__
91 
92 #include "scip/def.h"
93 #include "scip/type_retcode.h"
94 #include "scip/type_scip.h"
95 
96 #ifdef __cplusplus
97 extern "C" {
98 #endif
99 
100 /** creates the QP KKT reformulation presolver and includes it in SCIP
101  *
102  * @ingroup PresolverIncludes
103  */
104 SCIP_EXPORT
106  SCIP* scip /**< SCIP data structure */
107  );
108 
109 #ifdef __cplusplus
110 }
111 #endif
112 
113 #endif
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
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