Scippy

SCIP

Solving Constraint Integer Programs

cons_soc.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-2014 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 cons_soc.h
17  * @ingroup CONSHDLRS
18  * @brief constraint handler for second order cone constraints \f$\sqrt{\gamma + \sum_{i=1}^{n} (\alpha_i\, (x_i + \beta_i))^2} \leq \alpha_{n+1}\, (x_{n+1}+\beta_{n+1})\f$
19  * @author Stefan Vigerske
20  *
21  * This constraint handler implements second order cone constraints of the form
22  * \f[
23  * \sqrt{\gamma + \sum_{i=1}^{n} (\alpha_i\, (x_i + \beta_i))^2} \leq \alpha_{n+1}\, (x_{n+1}+\beta_{n+1})
24  * \f]
25  * Here, \f$\gamma \geq 0\f$ and either \f$x_{n+1} \geq -\beta_{n+1}, \alpha_{n+1} \geq 0\f$ or
26  * \f$x_{n+1} \leq -\beta_{n+1}, \alpha_{n+1} \leq 0\f$.
27  *
28  * Constraints are enforced by separation, where cuts are generated by linearizing the (convex) nonlinear function on the left-hand-side of the constraint.
29  * Further, a linear outer-approximation (which includes new variables) based on Ben-Tal & Nemirovski or Glineur can be added.
30  * See also
31  *
32  * @par
33  * Timo Berthold and Stefan Heinz and Stefan Vigerske@n
34  * <a href="http://dx.doi.org/10.1007/978-1-4614-1927-3">Extending a CIP framework to solve MIQCPs</a>@n
35  * In: Jon Lee and Sven Leyffer (eds.),
36  * Mixed-integer nonlinear optimization: Algorithmic advances and applications,
37  * IMA volumes in Mathematics and its Applications, volume 154, 427-444, 2012.
38  *
39  * @par
40  * Aharon Ben-Tal and Arkadi Nemirovski@n
41  * On Polyhedral Approximations of the Second-order Cone@n
42  * Mathematics of Operations Research 26:2, 193-205, 2001
43  *
44  * @par
45  * Fran&ccedil;ois Glineur@n
46  * Computational experiments with a linear approximation of second order cone optimization@n
47  * Technical Report 2000:1, Facult&eacute; Polytechnique de Mons, Belgium
48  */
49 
50 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
51 
52 #ifndef __SCIP_CONS_SOC_H__
53 #define __SCIP_CONS_SOC_H__
54 
55 #include "scip/scip.h"
56 #include "nlpi/type_nlpi.h"
57 
58 #ifdef __cplusplus
59 extern "C" {
60 #endif
61 
62 /** creates the handler for second order cone constraints and includes it in SCIP */
63 extern
64 SCIP_RETCODE SCIPincludeConshdlrSOC(
65  SCIP* scip /**< SCIP data structure */
66  );
67 
68 /** creates and captures a second order cone constraint
69  *
70  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
71  */
72 extern
73 SCIP_RETCODE SCIPcreateConsSOC(
74  SCIP* scip, /**< SCIP data structure */
75  SCIP_CONS** cons, /**< pointer to hold the created constraint */
76  const char* name, /**< name of constraint */
77  int nvars, /**< number of variables on left hand side of constraint (n) */
78  SCIP_VAR** vars, /**< array with variables on left hand side (x_i) */
79  SCIP_Real* coefs, /**< array with coefficients of left hand side variables (alpha_i), or NULL if all 1.0 */
80  SCIP_Real* offsets, /**< array with offsets of variables (beta_i), or NULL if all 0.0 */
81  SCIP_Real constant, /**< constant on left hand side (gamma) */
82  SCIP_VAR* rhsvar, /**< variable on right hand side of constraint (x_{n+1}) */
83  SCIP_Real rhscoeff, /**< coefficient of variable on right hand side (alpha_{n+1}) */
84  SCIP_Real rhsoffset, /**< offset of variable on right hand side (beta_{n+1}) */
85  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
86  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
87  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
88  * Usually set to TRUE. */
89  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
90  * TRUE for model constraints, FALSE for additional, redundant constraints. */
91  SCIP_Bool check, /**< should the constraint be checked for feasibility?
92  * TRUE for model constraints, FALSE for additional, redundant constraints. */
93  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
94  * Usually set to TRUE. */
95  SCIP_Bool local, /**< is constraint only valid locally?
96  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
97  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
98  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
99  * adds coefficients to this constraint. */
100  SCIP_Bool dynamic, /**< is constraint subject to aging?
101  * Usually set to FALSE. Set to TRUE for own cuts which
102  * are separated as constraints. */
103  SCIP_Bool removable /**< should the relaxation be removed from the LP due to aging or cleanup?
104  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
105  );
106 
107 /** creates and captures a second order cone constraint
108  * in its most basic variant, i. e., with all constraint flags set to their default values, which can be set
109  * afterwards using SCIPsetConsFLAGNAME() in scip.h
110  *
111  * @see SCIPcreateConsSOC() for the default constraint flag configuration
112  *
113  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
114  */
115 extern
116 SCIP_RETCODE SCIPcreateConsBasicSOC(
117  SCIP* scip, /**< SCIP data structure */
118  SCIP_CONS** cons, /**< pointer to hold the created constraint */
119  const char* name, /**< name of constraint */
120  int nvars, /**< number of variables on left hand side of constraint (n) */
121  SCIP_VAR** vars, /**< array with variables on left hand side (x_i) */
122  SCIP_Real* coefs, /**< array with coefficients of left hand side variables (alpha_i), or NULL if all 1.0 */
123  SCIP_Real* offsets, /**< array with offsets of variables (beta_i), or NULL if all 0.0 */
124  SCIP_Real constant, /**< constant on left hand side (gamma) */
125  SCIP_VAR* rhsvar, /**< variable on right hand side of constraint (x_{n+1}) */
126  SCIP_Real rhscoeff, /**< coefficient of variable on right hand side (alpha_{n+1}) */
127  SCIP_Real rhsoffset /**< offset of variable on right hand side (beta_{n+1}) */
128  );
129 
130 /** Gets the SOC constraint as a nonlinear row representation.
131  */
132 extern
133 SCIP_RETCODE SCIPgetNlRowSOC(
134  SCIP* scip, /**< SCIP data structure */
135  SCIP_CONS* cons, /**< constraint */
136  SCIP_NLROW** nlrow /**< pointer to store nonlinear row */
137  );
138 
139 /** Gets the number of variables on the left hand side of a SOC constraint.
140  */
141 extern
142 int SCIPgetNLhsVarsSOC(
143  SCIP* scip, /**< SCIP data structure */
144  SCIP_CONS* cons /**< constraint data */
145  );
146 
147 /** Gets the variables on the left hand side of a SOC constraint.
148  */
149 extern
150 SCIP_VAR** SCIPgetLhsVarsSOC(
151  SCIP* scip, /**< SCIP data structure */
152  SCIP_CONS* cons /**< constraint data */
153  );
154 
155 /** Gets the coefficients of the variables on the left hand side of a SOC constraint, or NULL if all are equal to 1.0.
156  */
157 extern
158 SCIP_Real* SCIPgetLhsCoefsSOC(
159  SCIP* scip, /**< SCIP data structure */
160  SCIP_CONS* cons /**< constraint data */
161  );
162 
163 /** Gets the offsets of the variables on the left hand side of a SOC constraint, or NULL if all are equal to 0.0.
164  */
165 extern
166 SCIP_Real* SCIPgetLhsOffsetsSOC(
167  SCIP* scip, /**< SCIP data structure */
168  SCIP_CONS* cons /**< constraint data */
169  );
170 
171 /** Gets the constant on the left hand side of a SOC constraint.
172  */
173 extern
174 SCIP_Real SCIPgetLhsConstantSOC(
175  SCIP* scip, /**< SCIP data structure */
176  SCIP_CONS* cons /**< constraint data */
177  );
178 
179 /** Gets the variable on the right hand side of a SOC constraint.
180  */
181 extern
182 SCIP_VAR* SCIPgetRhsVarSOC(
183  SCIP* scip, /**< SCIP data structure */
184  SCIP_CONS* cons /**< constraint data */
185  );
186 
187 /** Gets the coefficient of the variable on the right hand side of a SOC constraint.
188  */
189 extern
190 SCIP_Real SCIPgetRhsCoefSOC(
191  SCIP* scip, /**< SCIP data structure */
192  SCIP_CONS* cons /**< constraint data */
193  );
194 
195 /** Gets the offset of the variables on the right hand side of a SOC constraint.
196  */
197 extern
198 SCIP_Real SCIPgetRhsOffsetSOC(
199  SCIP* scip, /**< SCIP data structure */
200  SCIP_CONS* cons /**< constraint data */
201  );
202 
203 /** Adds the constraint to an NLPI problem.
204  * Uses nonconvex formulation as quadratic function.
205  */
206 extern
207 SCIP_RETCODE SCIPaddToNlpiProblemSOC(
208  SCIP* scip, /**< SCIP data structure */
209  SCIP_CONS* cons, /**< SOC constraint */
210  SCIP_NLPI* nlpi, /**< interface to NLP solver */
211  SCIP_NLPIPROBLEM* nlpiprob, /**< NLPI problem where to add constraint */
212  SCIP_HASHMAP* scipvar2nlpivar, /**< mapping from SCIP variables to variable indices in NLPI */
213  SCIP_Bool names /**< whether to pass constraint names to NLPI */
214  );
215 
216 #ifdef __cplusplus
217 }
218 #endif
219 
220 #endif
221