1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/* */
/* This file is part of the program and library */
/* SCIP --- Solving Constraint Integer Programs */
/* */
/* Copyright 2002-2022 Zuse Institute Berlin */
/* */
/* Licensed under the Apache License, Version 2.0 (the "License"); */
/* you may not use this file except in compliance with the License. */
/* You may obtain a copy of the License at */
/* */
/* http://www.apache.org/licenses/LICENSE-2.0 */
/* */
/* Unless required by applicable law or agreed to in writing, software */
/* distributed under the License is distributed on an "AS IS" BASIS, */
/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
/* See the License for the specific language governing permissions and */
/* limitations under the License. */
/* */
/* You should have received a copy of the Apache-2.0 license */
/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
/* */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/**@file cons_setppc.h
* @ingroup CONSHDLRS
* @brief Constraint handler for the set partitioning / packing / covering constraints \f$1^T x\ \{=, \le, \ge\}\ 1\f$.
* @author Tobias Achterberg
* @author Michael Winkler
*
*/
/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
#ifndef __SCIP_CONS_SETPPC_H__
#define __SCIP_CONS_SETPPC_H__
#include "scip/def.h"
#include "scip/type_cons.h"
#include "scip/type_lp.h"
#include "scip/type_retcode.h"
#include "scip/type_scip.h"
#include "scip/type_var.h"
#ifdef __cplusplus
extern "C" {
#endif
/** creates the handler for set partitioning / packing / covering constraints and includes it in SCIP
*
* @ingroup ConshdlrIncludes
* */
SCIP_EXPORT
SCIP_RETCODE SCIPincludeConshdlrSetppc(
SCIP* scip /**< SCIP data structure */
);
/**@addtogroup CONSHDLRS
*
* @{
*
* @name Set Packing/Partitioning/Covering Constraints
*
* @{
*
* This constraint handler handles three special classes of linear constraints, namely
* set partitioning, set packing, and set covering constraints.
* For a set of binary variables \f$x_i, i=1,\dots,n\f$, a set partitioning constraint has the form
* \f[
* \sum_{i=1}^n x_i = 1,
* \f]
* a set packing constraint has the form
* \f[
* \sum_{i=1}^n x_i \le 1,
* \f]
* and a set covering constraint has the form
* \f[
* \sum_{i=1}^n x_i \ge 1.
* \f]
*/
/** type of setppc constraint: set partitioning, set packing, or set covering */
enum SCIP_SetppcType
{
SCIP_SETPPCTYPE_PARTITIONING = 0, /**< constraint is a set partitioning constraint: sum(x) == 1 */
SCIP_SETPPCTYPE_PACKING = 1, /**< constraint is a set packing constraint: sum(x) <= 1 */
SCIP_SETPPCTYPE_COVERING = 2 /**< constraint is a set covering constraint: sum(x) >= 1 */
};
typedef enum SCIP_SetppcType SCIP_SETPPCTYPE;
/** creates and captures a set partitioning constraint
*
* @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
*/
SCIP_EXPORT
SCIP_RETCODE SCIPcreateConsSetpart(
SCIP* scip, /**< SCIP data structure */
SCIP_CONS** cons, /**< pointer to hold the created constraint */
const char* name, /**< name of constraint */
int nvars, /**< number of variables in the constraint */
SCIP_VAR** vars, /**< array with variables of constraint entries */
SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
* Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
SCIP_Bool separate, /**< should the constraint be separated during LP processing?
* Usually set to TRUE. */
SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
* TRUE for model constraints, FALSE for additional, redundant constraints. */
SCIP_Bool check, /**< should the constraint be checked for feasibility?
* TRUE for model constraints, FALSE for additional, redundant constraints. */
SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
* Usually set to TRUE. */
SCIP_Bool local, /**< is constraint only valid locally?
* Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
* Usually set to FALSE. In column generation applications, set to TRUE if pricing
* adds coefficients to this constraint. */
SCIP_Bool dynamic, /**< is constraint subject to aging?
* Usually set to FALSE. Set to TRUE for own cuts which
* are separated as constraints. */
SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
* Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
* if it may be moved to a more global node?
* Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
);
/** creates and captures a set partitioning constraint
* in its most basic variant, i. e., with all constraint flags set to their default values, which can be set
* afterwards using SCIPsetConsFLAGNAME() in scip.h
*
* @see SCIPcreateConsSetpart() for the default constraint flag configuration
*
* @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
*/
SCIP_EXPORT
SCIP_RETCODE SCIPcreateConsBasicSetpart(
SCIP* scip, /**< SCIP data structure */
SCIP_CONS** cons, /**< pointer to hold the created constraint */
const char* name, /**< name of constraint */
int nvars, /**< number of variables in the constraint */
SCIP_VAR** vars /**< array with variables of constraint entries */
);
/** creates and captures a set packing constraint
*
* @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
*/
SCIP_EXPORT
SCIP_RETCODE SCIPcreateConsSetpack(
SCIP* scip, /**< SCIP data structure */
SCIP_CONS** cons, /**< pointer to hold the created constraint */
const char* name, /**< name of constraint */
int nvars, /**< number of variables in the constraint */
SCIP_VAR** vars, /**< array with variables of constraint entries */
SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
* Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
SCIP_Bool separate, /**< should the constraint be separated during LP processing?
* Usually set to TRUE. */
SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
* TRUE for model constraints, FALSE for additional, redundant constraints. */
SCIP_Bool check, /**< should the constraint be checked for feasibility?
* TRUE for model constraints, FALSE for additional, redundant constraints. */
SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
* Usually set to TRUE. */
SCIP_Bool local, /**< is constraint only valid locally?
* Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
* Usually set to FALSE. In column generation applications, set to TRUE if pricing
* adds coefficients to this constraint. */
SCIP_Bool dynamic, /**< is constraint subject to aging?
* Usually set to FALSE. Set to TRUE for own cuts which
* are separated as constraints. */
SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
* Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
* if it may be moved to a more global node?
* Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
);
/** creates and captures a set packing constraint
* in its most basic variant, i. e., with all constraint flags set to their default values, which can be set
* afterwards using SCIPsetConsFLAGNAME() in scip.h
*
* @see SCIPcreateConsSetpack() for the default constraint flag configuration
*
* @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
*/
SCIP_EXPORT
SCIP_RETCODE SCIPcreateConsBasicSetpack(
SCIP* scip, /**< SCIP data structure */
SCIP_CONS** cons, /**< pointer to hold the created constraint */
const char* name, /**< name of constraint */
int nvars, /**< number of variables in the constraint */
SCIP_VAR** vars /**< array with variables of constraint entries */
);
/** creates and captures a set covering constraint
*
* @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
*/
SCIP_EXPORT
SCIP_RETCODE SCIPcreateConsSetcover(
SCIP* scip, /**< SCIP data structure */
SCIP_CONS** cons, /**< pointer to hold the created constraint */
const char* name, /**< name of constraint */
int nvars, /**< number of variables in the constraint */
SCIP_VAR** vars, /**< array with variables of constraint entries */
SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
* Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
SCIP_Bool separate, /**< should the constraint be separated during LP processing?
* Usually set to TRUE. */
SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
* TRUE for model constraints, FALSE for additional, redundant constraints. */
SCIP_Bool check, /**< should the constraint be checked for feasibility?
* TRUE for model constraints, FALSE for additional, redundant constraints. */
SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
* Usually set to TRUE. */
SCIP_Bool local, /**< is constraint only valid locally?
* Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
* Usually set to FALSE. In column generation applications, set to TRUE if pricing
* adds coefficients to this constraint. */
SCIP_Bool dynamic, /**< is constraint subject to aging?
* Usually set to FALSE. Set to TRUE for own cuts which
* are separated as constraints. */
SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
* Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
* if it may be moved to a more global node?
* Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
);
/** creates and captures a set packing constraint
* in its most basic variant, i. e., with all constraint flags set to their default values, which can be set
* afterwards using SCIPsetConsFLAGNAME() in scip.h
*
* @see SCIPcreateConsSetpack() for the default constraint flag configuration
*
* @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
*/
SCIP_EXPORT
SCIP_RETCODE SCIPcreateConsBasicSetcover(
SCIP* scip, /**< SCIP data structure */
SCIP_CONS** cons, /**< pointer to hold the created constraint */
const char* name, /**< name of constraint */
int nvars, /**< number of variables in the constraint */
SCIP_VAR** vars /**< array with variables of constraint entries */
);
/** adds coefficient in set partitioning / packing / covering constraint */
SCIP_EXPORT
SCIP_RETCODE SCIPaddCoefSetppc(
SCIP* scip, /**< SCIP data structure */
SCIP_CONS* cons, /**< constraint data */
SCIP_VAR* var /**< variable to add to the constraint */
);
/** gets number of variables in set partitioning / packing / covering constraint */
SCIP_EXPORT
int SCIPgetNVarsSetppc(
SCIP* scip, /**< SCIP data structure */
SCIP_CONS* cons /**< constraint data */
);
/** gets array of variables in set partitioning / packing / covering constraint */
SCIP_EXPORT
SCIP_VAR** SCIPgetVarsSetppc(
SCIP* scip, /**< SCIP data structure */
SCIP_CONS* cons /**< constraint data */
);
/** gets type of set partitioning / packing / covering constraint */
SCIP_EXPORT
SCIP_SETPPCTYPE SCIPgetTypeSetppc(
SCIP* scip, /**< SCIP data structure */
SCIP_CONS* cons /**< constraint data */
);
/** gets the dual solution of the set partitioning / packing / covering constraint in the current LP */
SCIP_EXPORT
SCIP_Real SCIPgetDualsolSetppc(
SCIP* scip, /**< SCIP data structure */
SCIP_CONS* cons /**< constraint data */
);
/** gets the dual Farkas value of the set partitioning / packing / covering constraint in the current infeasible LP */
SCIP_EXPORT
SCIP_Real SCIPgetDualfarkasSetppc(
SCIP* scip, /**< SCIP data structure */
SCIP_CONS* cons /**< constraint data */
);
/** returns the linear relaxation of the given set partitioning / packing / covering constraint; may return NULL if no
* LP row was yet created; the user must not modify the row!
*/
SCIP_EXPORT
SCIP_ROW* SCIPgetRowSetppc(
SCIP* scip, /**< SCIP data structure */
SCIP_CONS* cons /**< constraint data */
);
/** returns current number of variables fixed to one in the constraint */
SCIP_EXPORT
int SCIPgetNFixedonesSetppc(
SCIP* scip, /**< SCIP data structure */
SCIP_CONS* cons /**< constraint data */
);
/** returns current number of variables fixed to zero in the constraint */
SCIP_EXPORT
int SCIPgetNFixedzerosSetppc(
SCIP* scip, /**< SCIP data structure */
SCIP_CONS* cons /**< constraint data */
);
/** cleans up (multi-)aggregations and fixings from setppc constraints */
SCIP_EXPORT
SCIP_RETCODE SCIPcleanupConssSetppc(
SCIP* scip, /**< SCIP data structure */
SCIP_Bool onlychecked, /**< should only checked constraints be cleaned up? */
SCIP_Bool* infeasible, /**< pointer to return whether problem was detected to be infeasible */
int* naddconss, /**< pointer to count number of added (linear) constraints */
int* ndelconss, /**< pointer to count number of deleted (setppc) constraints */
int* nchgcoefs, /**< pointer to count number of changed coefficients */
int* nfixedvars /**< pointer to count number of fixed variables */
);
/** @} */
/** @} */
#ifdef __cplusplus
}
#endif
#endif