Scippy

SCIP

Solving Constraint Integer Programs

cons_pseudoboolean.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_pseudoboolean.h
17  * @ingroup CONSHDLRS
18  * @brief constraint handler for pseudoboolean constraints
19  * @author Stefan Heinz
20  * @author Michael Winkler
21  *
22  * The constraint handler deals with pseudo boolean constraints. These are constraints of the form
23  * \f[
24  * \mbox{lhs} \leq \sum_{k=0}^m c_k \cdot x_k + \sum_{i=0}^n c_i \cdot \prod_{j \in I_i} x_j \leq \mbox{rhs}
25  * \f]
26  * where all \f$x\f$ are binary and all \f$c\f$ are integer.
27  *
28  */
29 
30 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
31 
32 #ifndef __SCIP_CONS_PSEUDOBOOLEAN_H__
33 #define __SCIP_CONS_PSEUDOBOOLEAN_H__
34 
35 
36 #include "scip/scip.h"
37 
38 #ifdef __cplusplus
39 extern "C" {
40 #endif
41 
42 #define ARTIFICIALVARNAMEPREFIX "andresultant_"
43 
44 /** solution status after solving LP */
45 enum SCIP_LinearConsType
46 {
47  SCIP_LINEARCONSTYPE_INVALIDCONS = -1, /**< this is no valid linear constraint type */
48  SCIP_LINEARCONSTYPE_LINEAR = 0, /**< this is the common linear constraint */
49  SCIP_LINEARCONSTYPE_LOGICOR = 1, /**< this is a logicor constraint */
50  SCIP_LINEARCONSTYPE_KNAPSACK = 2, /**< this is a knapsack constraint */
51 #ifndef WITHEQKNAPSACK
52  SCIP_LINEARCONSTYPE_SETPPC = 3 /**< this is a setppc constraint */
53 #else
54  SCIP_LINEARCONSTYPE_SETPPC = 3, /**< this is a setppc constraint */
55  SCIP_LINEARCONSTYPE_EQKNAPSACK = 4 /**< this is a equality knapsack constraint */
56 #endif
57 };
58 typedef enum SCIP_LinearConsType SCIP_LINEARCONSTYPE;
59 
60 
61 /** creates the handler for pseudoboolean constraints and includes it in SCIP */
62 extern
63 SCIP_RETCODE SCIPincludeConshdlrPseudoboolean(
64  SCIP* scip /**< SCIP data structure */
65  );
66 
67 /** creates and captures a pseudoboolean constraint, with given linear and and-constraints */
68 extern
69 SCIP_RETCODE SCIPcreateConsPseudobooleanWithConss(
70  SCIP* scip, /**< SCIP data structure */
71  SCIP_CONS** cons, /**< pointer to hold the created constraint */
72  const char* name, /**< name of constraint */
73  SCIP_CONS* lincons, /**< associated linear constraint */
74  SCIP_LINEARCONSTYPE linconstype, /**< linear constraint type of associated linear constraint */
75  SCIP_CONS** andconss, /**< associated and-constraints */
76  SCIP_Real* andcoefs, /**< associated coefficients of and-constraints */
77  int nandconss, /**< number of associated and-constraints */
78  SCIP_VAR* indvar, /**< indicator variable if it's a soft constraint, or NULL */
79  SCIP_Real weight, /**< weight of the soft constraint, if it is one */
80  SCIP_Bool issoftcons, /**< is this a soft constraint */
81  SCIP_VAR* intvar, /**< a artificial variable which was added only for the objective function,
82  * if this variable is not NULL this constraint (without this integer
83  * variable) describes the objective funktion */
84  SCIP_Real lhs, /**< left hand side of constraint */
85  SCIP_Real rhs, /**< right hand side of constraint */
86  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
87  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
88  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
89  * Usually set to TRUE. */
90  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
91  * TRUE for model constraints, FALSE for additional, redundant
92  * constraints. */
93  SCIP_Bool check, /**< should the constraint be checked for feasibility?
94  * TRUE for model constraints, FALSE for additional, redundant
95  * constraints. */
96  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
97  * Usually set to TRUE. */
98  SCIP_Bool local, /**< is constraint only valid locally?
99  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching
100  * constraints. */
101  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
102  * Usually set to FALSE. In column generation applications, set to TRUE if
103  * pricing adds coefficients to this constraint. */
104  SCIP_Bool dynamic, /**< is constraint subject to aging?
105  * Usually set to FALSE. Set to TRUE for own cuts which are seperated as
106  * constraints. */
107  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
108  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user
109  * 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
113  * node data. */
114  );
115 
116 /** creates and captures a pseudoboolean constraint
117  *
118  * @note linear and nonlinear terms can be added using SCIPaddCoefPseudoboolean() and SCIPaddTermPseudoboolean(),
119  * respectively
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 SCIPcreateConsPseudoboolean(
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** linvars, /**< variables of the linear part, or NULL */
129  int nlinvars, /**< number of variables of the linear part */
130  SCIP_Real* linvals, /**< coefficients of linear part, or NULL */
131  SCIP_VAR*** terms, /**< nonlinear terms of variables, or NULL */
132  int nterms, /**< number of terms of variables of nonlinear term */
133  int* ntermvars, /**< number of variables in nonlinear terms, or NULL */
134  SCIP_Real* termvals, /**< coefficients of nonlinear parts, or NULL */
135  SCIP_VAR* indvar, /**< indicator variable if it's a soft constraint, or NULL */
136  SCIP_Real weight, /**< weight of the soft constraint, if it is one */
137  SCIP_Bool issoftcons, /**< is this a soft constraint */
138  SCIP_VAR* intvar, /**< a artificial variable which was added only for the objective function,
139  * if this variable is not NULL this constraint (without this integer
140  * variable) describes the objective function */
141  SCIP_Real lhs, /**< left hand side of constraint */
142  SCIP_Real rhs, /**< right hand side of constraint */
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 pseudoboolean 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 SCIPcreateConsPseudoboolean() 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 SCIPcreateConsBasicPseudoboolean(
178  SCIP* scip, /**< SCIP data structure */
179  SCIP_CONS** cons, /**< pointer to hold the created constraint */
180  const char* name, /**< name of constraint */
181  SCIP_VAR** linvars, /**< variables of the linear part, or NULL */
182  int nlinvars, /**< number of variables of the linear part */
183  SCIP_Real* linvals, /**< coefficients of linear part, or NULL */
184  SCIP_VAR*** terms, /**< nonlinear terms of variables, or NULL */
185  int nterms, /**< number of terms of variables of nonlinear term */
186  int* ntermvars, /**< number of variables in nonlinear terms, or NULL */
187  SCIP_Real* termvals, /**< coefficients of nonlinear parts, or NULL */
188  SCIP_VAR* indvar, /**< indicator variable if it's a soft constraint, or NULL */
189  SCIP_Real weight, /**< weight of the soft constraint, if it is one */
190  SCIP_Bool issoftcons, /**< is this a soft constraint */
191  SCIP_VAR* intvar, /**< a artificial variable which was added only for the objective function,
192  * if this variable is not NULL this constraint (without this integer
193  * variable) describes the objective function */
194  SCIP_Real lhs, /**< left hand side of constraint */
195  SCIP_Real rhs /**< right hand side of constraint */
196  );
197 
198 /** adds linear term pseudo boolean constraint (if it is not zero)
199  *
200  * @note you can only add a coefficient if the special type of linear constraint won't changed
201  *
202  * @todo if adding a coefficient would change the type of the special linear constraint, we need to erase it and
203  * create a new linear constraint
204  */
205 extern
206 SCIP_RETCODE SCIPaddCoefPseudoboolean(
207  SCIP*const scip, /**< SCIP data structure */
208  SCIP_CONS*const cons, /**< pseudoboolean constraint */
209  SCIP_VAR* const var, /**< variable of constraint entry */
210  SCIP_Real const val /**< coefficient of constraint entry */
211  );
212 
213 /** adds nonlinear term to pseudo boolean constraint (if it is not zero)
214  *
215  * @note you can only add a coefficient if the special type of linear constraint won't changed
216  *
217  * @todo if adding a coefficient would change the type of the special linear constraint, we need to erase it and
218  * create a new linear constraint
219  */
220 extern
221 SCIP_RETCODE SCIPaddTermPseudoboolean(
222  SCIP*const scip, /**< SCIP data structure */
223  SCIP_CONS*const cons, /**< pseudoboolean constraint */
224  SCIP_VAR**const vars, /**< variables of the nonlinear term */
225  int const nvars, /**< number of variables of the nonlinear term */
226  SCIP_Real const val /**< coefficient of constraint entry */
227  );
228 
229 /** gets indicator variable of pseudoboolean constraint, or NULL if there is no */
230 extern
231 SCIP_VAR* SCIPgetIndVarPseudoboolean(
232  SCIP*const scip, /**< SCIP data structure */
233  SCIP_CONS*const cons /**< pseudoboolean constraint */
234  );
235 
236 /** gets linear constraint of pseudoboolean constraint */
237 extern
238 SCIP_CONS* SCIPgetLinearConsPseudoboolean(
239  SCIP*const scip, /**< SCIP data structure */
240  SCIP_CONS*const cons /**< pseudoboolean constraint */
241  );
242 
243 /** gets type of linear constraint of pseudoboolean constraint */
244 extern
245 SCIP_LINEARCONSTYPE SCIPgetLinearConsTypePseudoboolean(
246  SCIP*const scip, /**< SCIP data structure */
247  SCIP_CONS*const cons /**< pseudoboolean constraint */
248  );
249 
250 /** gets number of linear variables without artificial terms variables of pseudoboolean constraint */
251 extern
252 int SCIPgetNLinVarsWithoutAndPseudoboolean(
253  SCIP*const scip, /**< SCIP data structure */
254  SCIP_CONS*const cons /**< pseudoboolean constraint */
255  );
256 
257 /** gets linear constraint of pseudoboolean constraint */
258 extern
259 SCIP_RETCODE SCIPgetLinDatasWithoutAndPseudoboolean(
260  SCIP*const scip, /**< SCIP data structure */
261  SCIP_CONS*const cons, /**< pseudoboolean constraint */
262  SCIP_VAR**const linvars, /**< array to store and-constraints */
263  SCIP_Real*const lincoefs, /**< array to store and-coefficients */
264  int*const nlinvars /**< pointer to store the required array size for and-constraints, have to
265  * be initialized with size of given array */
266  );
267 
268 /** gets and-constraints of pseudoboolean constraint */
269 extern
270 SCIP_RETCODE SCIPgetAndDatasPseudoboolean(
271  SCIP*const scip, /**< SCIP data structure */
272  SCIP_CONS*const cons, /**< pseudoboolean constraint */
273  SCIP_CONS**const andconss, /**< array to store and-constraints */
274  SCIP_Real*const andcoefs, /**< array to store and-coefficients */
275  int*const nandconss /**< pointer to store the required array size for and-constraints, have to
276  * be initialized with size of given array */
277  );
278 
279 /** gets number of and constraints of pseudoboolean constraint */
280 extern
281 int SCIPgetNAndsPseudoboolean(
282  SCIP*const scip, /**< SCIP data structure */
283  SCIP_CONS*const cons /**< pseudoboolean constraint */
284  );
285 
286 /** changes left hand side of pseudoboolean constraint
287  *
288  * @note you can only change the left hand side if the special type of linear constraint won't changed
289  *
290  * @todo if changing the left hand side would change the type of the special linear constraint, we need to erase it
291  * and create a new linear constraint
292  */
293 extern
294 SCIP_RETCODE SCIPchgLhsPseudoboolean(
295  SCIP*const scip, /**< SCIP data structure */
296  SCIP_CONS*const cons, /**< pseudoboolean constraint */
297  SCIP_Real const lhs /**< new left hand side */
298  );
299 
300 /** changes right hand side of pseudoboolean constraint
301  *
302  * @note you can only change the right hand side if the special type of linear constraint won't changed
303  *
304  * @todo if changing the right hand side would change the type of the special linear constraint, we need to erase it
305  * and create a new linear constraint
306  */
307 extern
308 SCIP_RETCODE SCIPchgRhsPseudoboolean(
309  SCIP*const scip, /**< SCIP data structure */
310  SCIP_CONS*const cons, /**< pseudoboolean constraint */
311  SCIP_Real const rhs /**< new right hand side */
312  );
313 
314 /** get left hand side of pseudoboolean constraint */
315 extern
316 SCIP_Real SCIPgetLhsPseudoboolean(
317  SCIP*const scip, /**< SCIP data structure */
318  SCIP_CONS*const cons /**< pseudoboolean constraint */
319  );
320 
321 /** get right hand side of pseudoboolean constraint */
322 extern
323 SCIP_Real SCIPgetRhsPseudoboolean(
324  SCIP*const scip, /**< SCIP data structure */
325  SCIP_CONS*const cons /**< pseudoboolean constraint */
326  );
327 
328 #ifdef __cplusplus
329 }
330 #endif
331 
332 #endif
333