Scippy

SCIP

Solving Constraint Integer Programs

cons_indicator.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_indicator.h
17  * @ingroup CONSHDLRS
18  * @brief constraint handler for indicator constraints
19  * @author Marc Pfetsch
20  *
21  * An indicator constraint is given by a binary variable \f$z\f$ and an inequality \f$ax \leq
22  * b\f$. It states that if \f$z = 1\f$ then \f$ax \leq b\f$ holds.
23  *
24  * This constraint is handled by adding a slack variable \f$s:\; ax - s \leq b\f$ with \f$s \geq
25  * 0\f$. The constraint is enforced by fixing \f$s\f$ to 0 if \f$z = 1\f$.
26  *
27  * @note The constraint only implements an implication not an equivalence, i.e., it does not ensure
28  * that \f$z = 1\f$ if \f$ax \leq b\f$ or equivalently if \f$s = 0\f$ holds.
29  *
30  * This constraint is equivalent to a linear constraint \f$ax - s \leq b\f$ and an SOS1 constraint on
31  * \f$z\f$ and \f$s\f$ (at most one should be nonzero). In the indicator context we can, however,
32  * separate more inequalities.
33  *
34  * The name indicator apparently comes from CPLEX.
35  */
36 
37 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
38 
39 #ifndef __SCIP_CONS_INDICATOR_H__
40 #define __SCIP_CONS_INDICATOR_H__
41 
42 
43 #include "scip/scip.h"
44 
45 #ifdef __cplusplus
46 extern "C" {
47 #endif
48 
49 /** creates the handler for indicator constraints and includes it in SCIP */
50 extern
51 SCIP_RETCODE SCIPincludeConshdlrIndicator(
52  SCIP* scip /**< SCIP data structure */
53  );
54 
55 /** creates and captures an indicator constraint
56  *
57  * @note @a binvar is checked to be binary only later. This enables a change of the type in
58  * procedures reading an instance.
59  *
60  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
61  */
62 extern
63 SCIP_RETCODE SCIPcreateConsIndicator(
64  SCIP* scip, /**< SCIP data structure */
65  SCIP_CONS** cons, /**< pointer to hold the created constraint (indicator or quadratic) */
66  const char* name, /**< name of constraint */
67  SCIP_VAR* binvar, /**< binary indicator variable (or NULL) */
68  int nvars, /**< number of variables in the inequality */
69  SCIP_VAR** vars, /**< array with variables of inequality (or NULL) */
70  SCIP_Real* vals, /**< values of variables in inequality (or NULL) */
71  SCIP_Real rhs, /**< rhs of the inequality */
72  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? Usually set to TRUE. */
73  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
74  * Usually set to TRUE. */
75  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
76  * TRUE for model constraints, FALSE for additional, redundant constraints. */
77  SCIP_Bool check, /**< should the constraint be checked for feasibility?
78  * TRUE for model constraints, FALSE for additional, redundant constraints. */
79  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
80  * Usually set to TRUE. */
81  SCIP_Bool local, /**< is constraint only valid locally?
82  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
83  SCIP_Bool dynamic, /**< is constraint subject to aging?
84  * Usually set to FALSE. Set to TRUE for own cuts which
85  * are separated as constraints. */
86  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
87  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
88  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
89  * if it may be moved to a more global node?
90  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
91  );
92 
93 /** creates and captures an indicator constraint
94  * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
95  * method SCIPcreateConsIndicator(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
96  *
97  * @see SCIPcreateConsIndicator() for information about the basic constraint flag configuration
98  *
99  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
100  */
101 extern
102 SCIP_RETCODE SCIPcreateConsBasicIndicator(
103  SCIP* scip, /**< SCIP data structure */
104  SCIP_CONS** cons, /**< pointer to hold the created constraint (indicator or quadratic) */
105  const char* name, /**< name of constraint */
106  SCIP_VAR* binvar, /**< binary indicator variable (or NULL) */
107  int nvars, /**< number of variables in the inequality */
108  SCIP_VAR** vars, /**< array with variables of inequality (or NULL) */
109  SCIP_Real* vals, /**< values of variables in inequality (or NULL) */
110  SCIP_Real rhs /**< rhs of the inequality */
111  );
112 
113 /** creates and captures an indicator constraint with given linear constraint and slack variable
114  *
115  * @note @a binvar is checked to be binary only later. This enables a change of the type in
116  * procedures reading an instance.
117  *
118  * @note we assume that @a slackvar actually appears in @a lincons and we also assume that it takes
119  * the role of a slack variable!
120  *
121  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
122  */
123 extern
124 SCIP_RETCODE SCIPcreateConsIndicatorLinCons(
125  SCIP* scip, /**< SCIP data structure */
126  SCIP_CONS** cons, /**< pointer to hold the created constraint */
127  const char* name, /**< name of constraint */
128  SCIP_VAR* binvar, /**< binary indicator variable (or NULL) */
129  SCIP_CONS* lincons, /**< linear constraint */
130  SCIP_VAR* slackvar, /**< slack variable */
131  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? Usually set to TRUE. */
132  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
133  * Usually set to TRUE. */
134  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
135  * TRUE for model constraints, FALSE for additional, redundant constraints. */
136  SCIP_Bool check, /**< should the constraint be checked for feasibility?
137  * TRUE for model constraints, FALSE for additional, redundant constraints. */
138  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
139  * Usually set to TRUE. */
140  SCIP_Bool local, /**< is constraint only valid locally?
141  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
142  SCIP_Bool dynamic, /**< is constraint subject to aging?
143  * Usually set to FALSE. Set to TRUE for own cuts which
144  * are separated as constraints. */
145  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
146  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
147  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
148  * if it may be moved to a more global node?
149  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
150  );
151 
152 /** creates and captures an indicator constraint with given linear constraint and slack variable
153  * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
154  * method SCIPcreateConsIndicator(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
155 
156  * @note @a binvar is checked to be binary only later. This enables a change of the type in
157  * procedures reading an instance.
158  *
159  * @note we assume that @a slackvar actually appears in @a lincons and we also assume that it takes
160  * the role of a slack variable!
161  *
162  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
163  *
164  * @see SCIPcreateConsIndicatorLinCons() for information about the basic constraint flag configuration
165  *
166  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
167  */
168 extern
169 SCIP_RETCODE SCIPcreateConsBasicIndicatorLinCons(
170  SCIP* scip, /**< SCIP data structure */
171  SCIP_CONS** cons, /**< pointer to hold the created constraint */
172  const char* name, /**< name of constraint */
173  SCIP_VAR* binvar, /**< binary indicator variable (or NULL) */
174  SCIP_CONS* lincons, /**< linear constraint */
175  SCIP_VAR* slackvar /**< slack variable */
176  );
177 
178 /** adds variable to the inequality of the indicator constraint */
179 extern
180 SCIP_RETCODE SCIPaddVarIndicator(
181  SCIP* scip, /**< SCIP data structure */
182  SCIP_CONS* cons, /**< indicator constraint */
183  SCIP_VAR* var, /**< variable to add to the inequality */
184  SCIP_Real val /**< value of variable */
185  );
186 
187 /** gets the linear constraint corresponding to the indicator constraint (may be NULL) */
188 extern
189 SCIP_CONS* SCIPgetLinearConsIndicator(
190  SCIP_CONS* cons /**< indicator constraint */
191  );
192 
193 /** sets the linear constraint corresponding to the indicator constraint (may be NULL) */
194 extern
195 SCIP_RETCODE SCIPsetLinearConsIndicator(
196  SCIP* scip, /**< SCIP data structure */
197  SCIP_CONS* cons, /**< indicator constraint */
198  SCIP_CONS* lincons /**< linear constraint */
199  );
200 
201 /** sets binary indicator variable for indicator constraint */
202 extern
203 SCIP_RETCODE SCIPsetBinaryVarIndicator(
204  SCIP* scip, /**< SCIP data structure */
205  SCIP_CONS* cons, /**< indicator constraint */
206  SCIP_VAR* binvar /**< binary variable to add to the inequality */
207  );
208 
209 /** gets binary variable corresponding to indicator constraint */
210 extern
211 SCIP_VAR* SCIPgetBinaryVarIndicator(
212  SCIP_CONS* cons /**< indicator constraint */
213  );
214 
215 /** gets slack variable corresponding to indicator constraint */
216 extern
217 SCIP_VAR* SCIPgetSlackVarIndicator(
218  SCIP_CONS* cons /**< indicator constraint */
219  );
220 
221 /** checks whether indicator constraint is violated w.r.t. sol */
222 extern
223 SCIP_Bool SCIPisViolatedIndicator(
224  SCIP* scip, /**< SCIP data structure */
225  SCIP_CONS* cons, /**< indicator constraint */
226  SCIP_SOL* sol /**< solution, or NULL to use current node's solution */
227  );
228 
229 /** Based on values of other variables, computes slack and binary variable to turn constraint feasible */
230 extern
231 SCIP_RETCODE SCIPmakeIndicatorFeasible(
232  SCIP* scip, /**< SCIP data structure */
233  SCIP_CONS* cons, /**< indicator constraint */
234  SCIP_SOL* sol, /**< solution */
235  SCIP_Bool* changed /**< pointer to store whether the solution has been changed */
236  );
237 
238 /** Based on values of other variables, computes slack and binary variable to turn all constraints feasible */
239 extern
240 SCIP_RETCODE SCIPmakeIndicatorsFeasible(
241  SCIP* scip, /**< SCIP data structure */
242  SCIP_CONSHDLR* conshdlr, /**< indicator constraint handler */
243  SCIP_SOL* sol, /**< solution */
244  SCIP_Bool* changed /**< pointer to store whether the solution has been changed */
245  );
246 
247 /** adds additional linear constraint that is not connected by an indicator constraint, but can be used for separation */
248 extern
249 SCIP_RETCODE SCIPaddLinearConsIndicator(
250  SCIP* scip, /**< SCIP data structure */
251  SCIP_CONSHDLR* conshdlr, /**< indicator constraint handler */
252  SCIP_CONS* lincons /**< linear constraint */
253  );
254 
255 /** adds additional globally valid row that is not connected by an indicator constraint, but can be used for separation */
256 extern
257 SCIP_RETCODE SCIPaddRowIndicator(
258  SCIP* scip, /**< SCIP data structure */
259  SCIP_CONSHDLR* conshdlr, /**< indicator constraint handler */
260  SCIP_ROW* row /**< row to add */
261  );
262 
263 #ifdef __cplusplus
264 }
265 #endif
266 
267 #endif
268