Scippy

SCIP

Solving Constraint Integer Programs

cons_setppc.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_setppc.h
17  * @ingroup CONSHDLRS
18  * @brief Constraint handler for the set partitioning / packing / covering constraints \f$1^T x\ \{=, \le, \ge\}\ 1\f$.
19  * @author Tobias Achterberg
20  * @author Michael Winkler
21  *
22  * This constraint handler handles three special classes of linear constraints, namely
23  * set partitioning, set packing, and set covering constraints.
24  * For a set of binary variables \f$x_i, i=1,\dots,n\f$, a set partitioning constraint has the form
25  * \f[
26  * \sum_{i=1}^n x_i = 1,
27  * \f]
28  * a set packing constraint has the form
29  * \f[
30  * \sum_{i=1}^n x_i \le 1,
31  * \f]
32  * and a set covering constraint has the form
33  * \f[
34  * \sum_{i=1}^n x_i \ge 1.
35  * \f]
36  */
37 
38 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
39 
40 #ifndef __SCIP_CONS_SETPPC_H__
41 #define __SCIP_CONS_SETPPC_H__
42 
43 
44 #include "scip/scip.h"
45 
46 #ifdef __cplusplus
47 extern "C" {
48 #endif
49 
50 /** type of setppc constraint: set partitioning, set packing, or set covering */
51 enum SCIP_SetppcType
52 {
53  SCIP_SETPPCTYPE_PARTITIONING = 0, /**< constraint is a set partitioning constraint: sum(x) == 1 */
54  SCIP_SETPPCTYPE_PACKING = 1, /**< constraint is a set packing constraint: sum(x) <= 1 */
55  SCIP_SETPPCTYPE_COVERING = 2 /**< constraint is a set covering constraint: sum(x) >= 1 */
56 };
57 typedef enum SCIP_SetppcType SCIP_SETPPCTYPE;
58 
59 /** creates the handler for set partitioning / packing / covering constraints and includes it in SCIP */
60 extern
61 SCIP_RETCODE SCIPincludeConshdlrSetppc(
62  SCIP* scip /**< SCIP data structure */
63  );
64 
65 /** creates and captures a set partitioning constraint
66  *
67  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
68  */
69 extern
70 SCIP_RETCODE SCIPcreateConsSetpart(
71  SCIP* scip, /**< SCIP data structure */
72  SCIP_CONS** cons, /**< pointer to hold the created constraint */
73  const char* name, /**< name of constraint */
74  int nvars, /**< number of variables in the constraint */
75  SCIP_VAR** vars, /**< array with variables of constraint entries */
76  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
77  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
78  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
79  * Usually set to TRUE. */
80  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
81  * TRUE for model constraints, FALSE for additional, redundant constraints. */
82  SCIP_Bool check, /**< should the constraint be checked for feasibility?
83  * TRUE for model constraints, FALSE for additional, redundant constraints. */
84  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
85  * Usually set to TRUE. */
86  SCIP_Bool local, /**< is constraint only valid locally?
87  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
88  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
89  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
90  * adds coefficients to this constraint. */
91  SCIP_Bool dynamic, /**< is constraint subject to aging?
92  * Usually set to FALSE. Set to TRUE for own cuts which
93  * are separated as constraints. */
94  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
95  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
96  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
97  * if it may be moved to a more global node?
98  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
99  );
100 
101 /** creates and captures a set partitioning constraint
102  * in its most basic variant, i. e., with all constraint flags set to their default values, which can be set
103  * afterwards using SCIPsetConsFLAGNAME() in scip.h
104  *
105  * @see SCIPcreateConsSetpart() for the default constraint flag configuration
106  *
107  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
108  */
109 extern
110 SCIP_RETCODE SCIPcreateConsBasicSetpart(
111  SCIP* scip, /**< SCIP data structure */
112  SCIP_CONS** cons, /**< pointer to hold the created constraint */
113  const char* name, /**< name of constraint */
114  int nvars, /**< number of variables in the constraint */
115  SCIP_VAR** vars /**< array with variables of constraint entries */
116  );
117 
118 /** creates and captures a set packing constraint
119  *
120  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
121  */
122 extern
123 SCIP_RETCODE SCIPcreateConsSetpack(
124  SCIP* scip, /**< SCIP data structure */
125  SCIP_CONS** cons, /**< pointer to hold the created constraint */
126  const char* name, /**< name of constraint */
127  int nvars, /**< number of variables in the constraint */
128  SCIP_VAR** vars, /**< array with variables of constraint entries */
129  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
130  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
131  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
132  * Usually set to TRUE. */
133  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
134  * TRUE for model constraints, FALSE for additional, redundant constraints. */
135  SCIP_Bool check, /**< should the constraint be checked for feasibility?
136  * TRUE for model constraints, FALSE for additional, redundant constraints. */
137  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
138  * Usually set to TRUE. */
139  SCIP_Bool local, /**< is constraint only valid locally?
140  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
141  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
142  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
143  * adds coefficients to this constraint. */
144  SCIP_Bool dynamic, /**< is constraint subject to aging?
145  * Usually set to FALSE. Set to TRUE for own cuts which
146  * are separated as constraints. */
147  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
148  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
149  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
150  * if it may be moved to a more global node?
151  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
152  );
153 
154 /** creates and captures a set packing constraint
155  * in its most basic variant, i. e., with all constraint flags set to their default values, which can be set
156  * afterwards using SCIPsetConsFLAGNAME() in scip.h
157  *
158  * @see SCIPcreateConsSetpack() for the default constraint flag configuration
159  *
160  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
161  */
162 extern
163 SCIP_RETCODE SCIPcreateConsBasicSetpack(
164  SCIP* scip, /**< SCIP data structure */
165  SCIP_CONS** cons, /**< pointer to hold the created constraint */
166  const char* name, /**< name of constraint */
167  int nvars, /**< number of variables in the constraint */
168  SCIP_VAR** vars /**< array with variables of constraint entries */
169  );
170 
171 /** creates and captures a set covering constraint
172  *
173  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
174  */
175 extern
176 SCIP_RETCODE SCIPcreateConsSetcover(
177  SCIP* scip, /**< SCIP data structure */
178  SCIP_CONS** cons, /**< pointer to hold the created constraint */
179  const char* name, /**< name of constraint */
180  int nvars, /**< number of variables in the constraint */
181  SCIP_VAR** vars, /**< array with variables of constraint entries */
182  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
183  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
184  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
185  * Usually set to TRUE. */
186  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
187  * TRUE for model constraints, FALSE for additional, redundant constraints. */
188  SCIP_Bool check, /**< should the constraint be checked for feasibility?
189  * TRUE for model constraints, FALSE for additional, redundant constraints. */
190  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
191  * Usually set to TRUE. */
192  SCIP_Bool local, /**< is constraint only valid locally?
193  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
194  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
195  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
196  * adds coefficients to this constraint. */
197  SCIP_Bool dynamic, /**< is constraint subject to aging?
198  * Usually set to FALSE. Set to TRUE for own cuts which
199  * are separated as constraints. */
200  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
201  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
202  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
203  * if it may be moved to a more global node?
204  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
205  );
206 
207 /** creates and captures a set packing constraint
208  * in its most basic variant, i. e., with all constraint flags set to their default values, which can be set
209  * afterwards using SCIPsetConsFLAGNAME() in scip.h
210  *
211  * @see SCIPcreateConsSetpack() for the default constraint flag configuration
212  *
213  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
214  */
215 extern
216 SCIP_RETCODE SCIPcreateConsBasicSetcover(
217  SCIP* scip, /**< SCIP data structure */
218  SCIP_CONS** cons, /**< pointer to hold the created constraint */
219  const char* name, /**< name of constraint */
220  int nvars, /**< number of variables in the constraint */
221  SCIP_VAR** vars /**< array with variables of constraint entries */
222  );
223 
224 /** adds coefficient in set partitioning / packing / covering constraint */
225 extern
226 SCIP_RETCODE SCIPaddCoefSetppc(
227  SCIP* scip, /**< SCIP data structure */
228  SCIP_CONS* cons, /**< constraint data */
229  SCIP_VAR* var /**< variable to add to the constraint */
230  );
231 
232 /** gets number of variables in set partitioning / packing / covering constraint */
233 extern
234 int SCIPgetNVarsSetppc(
235  SCIP* scip, /**< SCIP data structure */
236  SCIP_CONS* cons /**< constraint data */
237  );
238 
239 /** gets array of variables in set partitioning / packing / covering constraint */
240 extern
241 SCIP_VAR** SCIPgetVarsSetppc(
242  SCIP* scip, /**< SCIP data structure */
243  SCIP_CONS* cons /**< constraint data */
244  );
245 
246 /** gets type of set partitioning / packing / covering constraint */
247 extern
248 SCIP_SETPPCTYPE SCIPgetTypeSetppc(
249  SCIP* scip, /**< SCIP data structure */
250  SCIP_CONS* cons /**< constraint data */
251  );
252 
253 /** gets the dual solution of the set partitioning / packing / covering constraint in the current LP */
254 extern
255 SCIP_Real SCIPgetDualsolSetppc(
256  SCIP* scip, /**< SCIP data structure */
257  SCIP_CONS* cons /**< constraint data */
258  );
259 
260 /** gets the dual Farkas value of the set partitioning / packing / covering constraint in the current infeasible LP */
261 extern
262 SCIP_Real SCIPgetDualfarkasSetppc(
263  SCIP* scip, /**< SCIP data structure */
264  SCIP_CONS* cons /**< constraint data */
265  );
266 
267 /** returns the linear relaxation of the given set partitioning / packing / covering constraint; may return NULL if no
268  * LP row was yet created; the user must not modify the row!
269  */
270 extern
271 SCIP_ROW* SCIPgetRowSetppc(
272  SCIP* scip, /**< SCIP data structure */
273  SCIP_CONS* cons /**< constraint data */
274  );
275 
276 /** returns current number of variables fixed to one in the constraint */
277 extern
278 int SCIPgetNFixedonesSetppc(
279  SCIP* scip, /**< SCIP data structure */
280  SCIP_CONS* cons /**< constraint data */
281  );
282 
283 /** returns current number of variables fixed to zero in the constraint */
284 extern
285 int SCIPgetNFixedzerosSetppc(
286  SCIP* scip, /**< SCIP data structure */
287  SCIP_CONS* cons /**< constraint data */
288  );
289 
290 #ifdef __cplusplus
291 }
292 #endif
293 
294 #endif
295