Toggle navigation
SCIP Optimization Suite
SCIP
SoPlex
ZIMPL
UG
GCG
Documentation
SCIP 9.2.0
SCIP 8.1.0
SCIP 7.0.3
SCIP 6.0.2
SCIP 5.0.1
SCIP 4.0.1
SCIP 3.2.1
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
94
SCIP_RETCODE
SCIPincludePresolQPKKTref
(
95
SCIP
*
scip
/**< SCIP data structure */
96
);
97
98
#ifdef __cplusplus
99
}
100
#endif
101
102
#endif
Scip
Definition:
struct_scip.h:58
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition:
type_retcode.h:53
SCIPincludePresolQPKKTref
SCIP_RETCODE SCIPincludePresolQPKKTref(SCIP *scip)
Definition:
presol_qpkktref.c:1977
scip
Definition:
objbranchrule.h:33
scip.h
SCIP callable library.