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