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-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 visit 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 
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24 
25 #ifndef __SCIP_CONS_PSEUDOBOOLEAN_H__
26 #define __SCIP_CONS_PSEUDOBOOLEAN_H__
27 
28 
29 #include "scip/def.h"
30 #include "scip/type_cons.h"
31 #include "scip/type_retcode.h"
32 #include "scip/type_scip.h"
33 #include "scip/type_var.h"
34 
35 #ifdef __cplusplus
36 extern "C" {
37 #endif
38 
39 #define ARTIFICIALVARNAMEPREFIX "andresultant_"
40 
41 
42 
43 /** creates the handler for pseudoboolean constraints and includes it in SCIP
44  *
45  * @ingroup ConshdlrIncludes
46  * */
47 extern
49  SCIP* scip /**< SCIP data structure */
50  );
51 
52 /**@addtogroup CONSHDLRS
53  *
54  * @{
55  *
56  * @name Pseudoboolean Constraints
57  *
58  * @{
59  *
60  * The constraint handler deals with pseudo boolean constraints. These are constraints of the form
61  * \f[
62  * \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}
63  * \f]
64  * where all \f$x\f$ are binary and all \f$c\f$ are integer.
65  */
66 
67 /** solution status after solving LP */
69 {
70  SCIP_LINEARCONSTYPE_INVALIDCONS = -1, /**< this is no valid linear constraint type */
71  SCIP_LINEARCONSTYPE_LINEAR = 0, /**< this is the common linear constraint */
72  SCIP_LINEARCONSTYPE_LOGICOR = 1, /**< this is a logicor constraint */
73  SCIP_LINEARCONSTYPE_KNAPSACK = 2, /**< this is a knapsack constraint */
74 #ifndef WITHEQKNAPSACK
75  SCIP_LINEARCONSTYPE_SETPPC = 3 /**< this is a setppc constraint */
76 #else
77  SCIP_LINEARCONSTYPE_SETPPC = 3, /**< this is a setppc constraint */
78  SCIP_LINEARCONSTYPE_EQKNAPSACK = 4 /**< this is a equality knapsack constraint */
79 #endif
80 };
82 
83 /** creates and captures a pseudoboolean constraint, with given linear and and-constraints */
84 extern
86  SCIP* scip, /**< SCIP data structure */
87  SCIP_CONS** cons, /**< pointer to hold the created constraint */
88  const char* name, /**< name of constraint */
89  SCIP_CONS* lincons, /**< associated linear constraint */
90  SCIP_LINEARCONSTYPE linconstype, /**< linear constraint type of associated linear constraint */
91  SCIP_CONS** andconss, /**< associated and-constraints */
92  SCIP_Real* andcoefs, /**< associated coefficients of and-constraints */
93  int nandconss, /**< number of associated and-constraints */
94  SCIP_VAR* indvar, /**< indicator variable if it's a soft constraint, or NULL */
95  SCIP_Real weight, /**< weight of the soft constraint, if it is one */
96  SCIP_Bool issoftcons, /**< is this a soft constraint */
97  SCIP_VAR* intvar, /**< an artificial variable which was added only for the objective function,
98  * if this variable is not NULL this constraint (without this integer
99  * variable) describes the objective function */
100  SCIP_Real lhs, /**< left hand side of constraint */
101  SCIP_Real rhs, /**< right hand side of constraint */
102  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
103  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
104  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
105  * Usually set to TRUE. */
106  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
107  * TRUE for model constraints, FALSE for additional, redundant
108  * constraints. */
109  SCIP_Bool check, /**< should the constraint be checked for feasibility?
110  * TRUE for model constraints, FALSE for additional, redundant
111  * constraints. */
112  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
113  * Usually set to TRUE. */
114  SCIP_Bool local, /**< is constraint only valid locally?
115  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching
116  * constraints. */
117  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
118  * Usually set to FALSE. In column generation applications, set to TRUE if
119  * pricing adds coefficients to this constraint. */
120  SCIP_Bool dynamic, /**< is constraint subject to aging?
121  * Usually set to FALSE. Set to TRUE for own cuts which are seperated as
122  * constraints. */
123  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
124  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user
125  * cuts'. */
126  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
127  * if it may be moved to a more global node?
128  * Usually set to FALSE. Set to TRUE to for constraints that represent
129  * node data. */
130  );
131 
132 /** creates and captures a pseudoboolean constraint
133  *
134  * @note linear and nonlinear terms can be added using SCIPaddCoefPseudoboolean() and SCIPaddTermPseudoboolean(),
135  * respectively
136  *
137  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
138  */
139 extern
141  SCIP* scip, /**< SCIP data structure */
142  SCIP_CONS** cons, /**< pointer to hold the created constraint */
143  const char* name, /**< name of constraint */
144  SCIP_VAR** linvars, /**< variables of the linear part, or NULL */
145  int nlinvars, /**< number of variables of the linear part */
146  SCIP_Real* linvals, /**< coefficients of linear part, or NULL */
147  SCIP_VAR*** terms, /**< nonlinear terms of variables, or NULL */
148  int nterms, /**< number of terms of variables of nonlinear term */
149  int* ntermvars, /**< number of variables in nonlinear terms, or NULL */
150  SCIP_Real* termvals, /**< coefficients of nonlinear parts, or NULL */
151  SCIP_VAR* indvar, /**< indicator variable if it's a soft constraint, or NULL */
152  SCIP_Real weight, /**< weight of the soft constraint, if it is one */
153  SCIP_Bool issoftcons, /**< is this a soft constraint */
154  SCIP_VAR* intvar, /**< an artificial variable which was added only for the objective function,
155  * if this variable is not NULL this constraint (without this integer
156  * variable) describes the objective function */
157  SCIP_Real lhs, /**< left hand side of constraint */
158  SCIP_Real rhs, /**< right hand side of constraint */
159  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
160  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
161  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
162  * Usually set to TRUE. */
163  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
164  * TRUE for model constraints, FALSE for additional, redundant constraints. */
165  SCIP_Bool check, /**< should the constraint be checked for feasibility?
166  * TRUE for model constraints, FALSE for additional, redundant constraints. */
167  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
168  * Usually set to TRUE. */
169  SCIP_Bool local, /**< is constraint only valid locally?
170  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
171  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
172  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
173  * adds coefficients to this constraint. */
174  SCIP_Bool dynamic, /**< is constraint subject to aging?
175  * Usually set to FALSE. Set to TRUE for own cuts which
176  * are separated as constraints. */
177  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
178  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
179  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
180  * if it may be moved to a more global node?
181  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
182  );
183 
184 /** creates and captures a pseudoboolean constraint
185  * in its most basic variant, i. e., with all constraint flags set to their default values, which can be set
186  * afterwards using SCIPsetConsFLAGNAME() in scip.h
187  *
188  * @see SCIPcreateConsPseudoboolean() for the default constraint flag configuration
189  *
190  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
191  */
192 extern
194  SCIP* scip, /**< SCIP data structure */
195  SCIP_CONS** cons, /**< pointer to hold the created constraint */
196  const char* name, /**< name of constraint */
197  SCIP_VAR** linvars, /**< variables of the linear part, or NULL */
198  int nlinvars, /**< number of variables of the linear part */
199  SCIP_Real* linvals, /**< coefficients of linear part, or NULL */
200  SCIP_VAR*** terms, /**< nonlinear terms of variables, or NULL */
201  int nterms, /**< number of terms of variables of nonlinear term */
202  int* ntermvars, /**< number of variables in nonlinear terms, or NULL */
203  SCIP_Real* termvals, /**< coefficients of nonlinear parts, or NULL */
204  SCIP_VAR* indvar, /**< indicator variable if it's a soft constraint, or NULL */
205  SCIP_Real weight, /**< weight of the soft constraint, if it is one */
206  SCIP_Bool issoftcons, /**< is this a soft constraint */
207  SCIP_VAR* intvar, /**< a artificial variable which was added only for the objective function,
208  * if this variable is not NULL this constraint (without this integer
209  * variable) describes the objective function */
210  SCIP_Real lhs, /**< left hand side of constraint */
211  SCIP_Real rhs /**< right hand side of constraint */
212  );
213 
214 /** adds linear term pseudo boolean constraint (if it is not zero)
215  *
216  * @note you can only add a coefficient if the special type of linear constraint won't changed
217  *
218  * @todo if adding a coefficient would change the type of the special linear constraint, we need to erase it and
219  * create a new linear constraint
220  */
221 extern
223  SCIP*const scip, /**< SCIP data structure */
224  SCIP_CONS*const cons, /**< pseudoboolean constraint */
225  SCIP_VAR* const var, /**< variable of constraint entry */
226  SCIP_Real const val /**< coefficient of constraint entry */
227  );
228 
229 /** adds nonlinear term to pseudo boolean constraint (if it is not zero)
230  *
231  * @note you can only add a coefficient if the special type of linear constraint won't changed
232  *
233  * @todo if adding a coefficient would change the type of the special linear constraint, we need to erase it and
234  * create a new linear constraint
235  */
236 extern
238  SCIP*const scip, /**< SCIP data structure */
239  SCIP_CONS*const cons, /**< pseudoboolean constraint */
240  SCIP_VAR**const vars, /**< variables of the nonlinear term */
241  int const nvars, /**< number of variables of the nonlinear term */
242  SCIP_Real const val /**< coefficient of constraint entry */
243  );
244 
245 /** gets indicator variable of pseudoboolean constraint, or NULL if there is no */
246 extern
248  SCIP*const scip, /**< SCIP data structure */
249  SCIP_CONS*const cons /**< pseudoboolean constraint */
250  );
251 
252 /** gets linear constraint of pseudoboolean constraint */
253 extern
255  SCIP*const scip, /**< SCIP data structure */
256  SCIP_CONS*const cons /**< pseudoboolean constraint */
257  );
258 
259 /** gets type of linear constraint of pseudoboolean constraint */
260 extern
261 SCIP_LINEARCONSTYPE SCIPgetLinearConsTypePseudoboolean(
262  SCIP*const scip, /**< SCIP data structure */
263  SCIP_CONS*const cons /**< pseudoboolean constraint */
264  );
265 
266 /** gets number of linear variables without artificial terms variables of pseudoboolean constraint */
267 extern
269  SCIP*const scip, /**< SCIP data structure */
270  SCIP_CONS*const cons /**< pseudoboolean constraint */
271  );
272 
273 /** gets linear constraint of pseudoboolean constraint */
274 extern
276  SCIP*const scip, /**< SCIP data structure */
277  SCIP_CONS*const cons, /**< pseudoboolean constraint */
278  SCIP_VAR**const linvars, /**< array to store and-constraints */
279  SCIP_Real*const lincoefs, /**< array to store and-coefficients */
280  int*const nlinvars /**< pointer to store the required array size for and-constraints, have to
281  * be initialized with size of given array */
282  );
283 
284 /** gets and-constraints of pseudoboolean constraint */
285 extern
287  SCIP*const scip, /**< SCIP data structure */
288  SCIP_CONS*const cons, /**< pseudoboolean constraint */
289  SCIP_CONS**const andconss, /**< array to store and-constraints */
290  SCIP_Real*const andcoefs, /**< array to store and-coefficients */
291  int*const nandconss /**< pointer to store the required array size for and-constraints, have to
292  * be initialized with size of given array */
293  );
294 
295 /** gets number of and constraints of pseudoboolean constraint */
296 extern
298  SCIP*const scip, /**< SCIP data structure */
299  SCIP_CONS*const cons /**< pseudoboolean constraint */
300  );
301 
302 /** changes left hand side of pseudoboolean constraint
303  *
304  * @note you can only change the left hand side if the special type of linear constraint won't changed
305  *
306  * @todo if changing the left hand side would change the type of the special linear constraint, we need to erase it
307  * and create a new linear constraint
308  */
309 extern
311  SCIP*const scip, /**< SCIP data structure */
312  SCIP_CONS*const cons, /**< pseudoboolean constraint */
313  SCIP_Real const lhs /**< new left hand side */
314  );
315 
316 /** changes right hand side of pseudoboolean constraint
317  *
318  * @note you can only change the right hand side if the special type of linear constraint won't changed
319  *
320  * @todo if changing the right hand side would change the type of the special linear constraint, we need to erase it
321  * and create a new linear constraint
322  */
323 extern
325  SCIP*const scip, /**< SCIP data structure */
326  SCIP_CONS*const cons, /**< pseudoboolean constraint */
327  SCIP_Real const rhs /**< new right hand side */
328  );
329 
330 /** get left hand side of pseudoboolean constraint */
331 extern
333  SCIP*const scip, /**< SCIP data structure */
334  SCIP_CONS*const cons /**< pseudoboolean constraint */
335  );
336 
337 /** get right hand side of pseudoboolean constraint */
338 extern
340  SCIP*const scip, /**< SCIP data structure */
341  SCIP_CONS*const cons /**< pseudoboolean constraint */
342  );
343 
344 /* @} */
345 
346 /* @} */
347 
348 #ifdef __cplusplus
349 }
350 #endif
351 
352 #endif
static volatile int nterms
Definition: interrupt.c:37
SCIP_RETCODE SCIPgetAndDatasPseudoboolean(SCIP *const scip, SCIP_CONS *const cons, SCIP_CONS **const andconss, SCIP_Real *const andcoefs, int *const nandconss)
SCIP_RETCODE SCIPincludeConshdlrPseudoboolean(SCIP *scip)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPchgLhsPseudoboolean(SCIP *const scip, SCIP_CONS *const cons, SCIP_Real const lhs)
SCIP_RETCODE SCIPcreateConsPseudoboolean(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR **linvars, int nlinvars, SCIP_Real *linvals, SCIP_VAR ***terms, int nterms, int *ntermvars, SCIP_Real *termvals, SCIP_VAR *indvar, SCIP_Real weight, SCIP_Bool issoftcons, SCIP_VAR *intvar, SCIP_Real lhs, SCIP_Real rhs, 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)
type definitions for return codes for SCIP methods
SCIP_VAR * SCIPgetIndVarPseudoboolean(SCIP *const scip, SCIP_CONS *const cons)
SCIP_RETCODE SCIPaddTermPseudoboolean(SCIP *const scip, SCIP_CONS *const cons, SCIP_VAR **const vars, int const nvars, SCIP_Real const val)
type definitions for SCIP&#39;s main datastructure
SCIP_RETCODE SCIPcreateConsPseudobooleanWithConss(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONS *lincons, SCIP_LINEARCONSTYPE linconstype, SCIP_CONS **andconss, SCIP_Real *andcoefs, int nandconss, SCIP_VAR *indvar, SCIP_Real weight, SCIP_Bool issoftcons, SCIP_VAR *intvar, SCIP_Real lhs, SCIP_Real rhs, 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)
SCIP_RETCODE SCIPgetLinDatasWithoutAndPseudoboolean(SCIP *const scip, SCIP_CONS *const cons, SCIP_VAR **const linvars, SCIP_Real *const lincoefs, int *const nlinvars)
int SCIPgetNLinVarsWithoutAndPseudoboolean(SCIP *const scip, SCIP_CONS *const cons)
enum SCIP_LinearConsType SCIP_LINEARCONSTYPE
type definitions for problem variables
SCIP_Real SCIPgetLhsPseudoboolean(SCIP *const scip, SCIP_CONS *const cons)
SCIP_RETCODE SCIPaddCoefPseudoboolean(SCIP *const scip, SCIP_CONS *const cons, SCIP_VAR *const var, SCIP_Real const val)
#define SCIP_Bool
Definition: def.h:62
int SCIPgetNAndsPseudoboolean(SCIP *const scip, SCIP_CONS *const cons)
SCIP_RETCODE SCIPchgRhsPseudoboolean(SCIP *const scip, SCIP_CONS *const cons, SCIP_Real const rhs)
SCIP_LinearConsType
SCIP_CONS * SCIPgetLinearConsPseudoboolean(SCIP *const scip, SCIP_CONS *const cons)
SCIP_LINEARCONSTYPE SCIPgetLinearConsTypePseudoboolean(SCIP *const scip, SCIP_CONS *const cons)
#define SCIP_Real
Definition: def.h:150
SCIP_RETCODE SCIPcreateConsBasicPseudoboolean(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR **linvars, int nlinvars, SCIP_Real *linvals, SCIP_VAR ***terms, int nterms, int *ntermvars, SCIP_Real *termvals, SCIP_VAR *indvar, SCIP_Real weight, SCIP_Bool issoftcons, SCIP_VAR *intvar, SCIP_Real lhs, SCIP_Real rhs)
common defines and data types used in all packages of SCIP
type definitions for constraints and constraint handlers
SCIP_Real SCIPgetRhsPseudoboolean(SCIP *const scip, SCIP_CONS *const cons)