Scippy

SCIP

Solving Constraint Integer Programs

implics.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 implics.h
17  * @brief methods for implications, variable bounds, and cliques
18  * @author Tobias Achterberg
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #ifndef __SCIP_IMPLICS_H__
24 #define __SCIP_IMPLICS_H__
25 
26 
27 #include "scip/def.h"
28 #include "blockmemshell/memory.h"
29 #include "scip/type_retcode.h"
30 #include "scip/type_set.h"
31 #include "scip/type_stat.h"
32 #include "scip/type_event.h"
33 #include "scip/type_lp.h"
34 #include "scip/type_var.h"
35 #include "scip/type_implics.h"
36 #include "scip/type_branch.h"
37 #include "scip/pub_implics.h"
38 
39 #ifdef NDEBUG
40 #include "scip/struct_implics.h"
41 #endif
42 
43 #ifdef __cplusplus
44 extern "C" {
45 #endif
46 
47 /*
48  * Methods for Variable Bounds
49  */
50 
51 /** frees a variable bounds data structure */
52 extern
53 void SCIPvboundsFree(
54  SCIP_VBOUNDS** vbounds, /**< pointer to store variable bounds data structure */
55  BMS_BLKMEM* blkmem /**< block memory */
56  );
57 
58 /** adds a variable bound to the variable bounds data structure */
59 extern
60 SCIP_RETCODE SCIPvboundsAdd(
61  SCIP_VBOUNDS** vbounds, /**< pointer to variable bounds data structure */
62  BMS_BLKMEM* blkmem, /**< block memory */
63  SCIP_SET* set, /**< global SCIP settings */
64  SCIP_BOUNDTYPE vboundtype, /**< type of variable bound (LOWER or UPPER) */
65  SCIP_VAR* var, /**< variable z in x <= b*z + d or x >= b*z + d */
66  SCIP_Real coef, /**< coefficient b in x <= b*z + d or x >= b*z + d */
67  SCIP_Real constant, /**< constant d in x <= b*z + d or x >= b*z + d */
68  SCIP_Bool* added /**< pointer to store whether the variable bound was added */
69  );
70 
71 /** removes from variable x a variable bound x >=/<= b*z + d with binary or integer z */
72 extern
73 SCIP_RETCODE SCIPvboundsDel(
74  SCIP_VBOUNDS** vbounds, /**< pointer to variable bounds data structure */
75  BMS_BLKMEM* blkmem, /**< block memory */
76  SCIP_VAR* vbdvar, /**< variable z in x >=/<= b*z + d */
77  SCIP_Bool negativecoef /**< is coefficient b negative? */
78  );
79 
80 /** reduces the number of variable bounds stored in the given variable bounds data structure */
81 void SCIPvboundsShrink(
82  SCIP_VBOUNDS** vbounds, /**< pointer to variable bounds data structure */
83  BMS_BLKMEM* blkmem, /**< block memory */
84  int newnvbds /**< new number of variable bounds */
85  );
86 
87 
88 /** gets number of variable bounds contained in given variable bounds data structure */
89 extern
90 int SCIPvboundsGetNVbds(
91  SCIP_VBOUNDS* vbounds /**< variable bounds data structure */
92  );
93 
94 /** gets array of variables contained in given variable bounds data structure */
95 extern
96 SCIP_VAR** SCIPvboundsGetVars(
97  SCIP_VBOUNDS* vbounds /**< variable bounds data structure */
98  );
99 
100 /** gets array of coefficients contained in given variable bounds data structure */
101 extern
102 SCIP_Real* SCIPvboundsGetCoefs(
103  SCIP_VBOUNDS* vbounds /**< variable bounds data structure */
104  );
105 
106 /** gets array of constants contained in given variable bounds data structure */
107 extern
108 SCIP_Real* SCIPvboundsGetConstants(
109  SCIP_VBOUNDS* vbounds /**< variable bounds data structure */
110  );
111 
112 #ifdef NDEBUG
113 
114 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
115  * speed up the algorithms.
116  */
117 
118 #define SCIPvboundsGetNVbds(vbounds) ((vbounds) != NULL ? (vbounds)->len : 0)
119 #define SCIPvboundsGetVars(vbounds) ((vbounds) != NULL ? (vbounds)->vars : NULL)
120 #define SCIPvboundsGetCoefs(vbounds) ((vbounds) != NULL ? (vbounds)->coefs : NULL)
121 #define SCIPvboundsGetConstants(vbounds) ((vbounds) != NULL ? (vbounds)->constants : NULL)
122 
123 #endif
124 
125 
126 
127 
128 /*
129  * Methods for Implications
130  */
131 
132 /** frees an implications data structure */
133 extern
134 void SCIPimplicsFree(
135  SCIP_IMPLICS** implics, /**< pointer of implications data structure to free */
136  BMS_BLKMEM* blkmem /**< block memory */
137  );
138 
139 /** adds an implication x == 0/1 -> y <= b or y >= b to the implications data structure;
140  * the implication must be non-redundant
141  */
142 extern
143 SCIP_RETCODE SCIPimplicsAdd(
144  SCIP_IMPLICS** implics, /**< pointer to implications data structure */
145  BMS_BLKMEM* blkmem, /**< block memory */
146  SCIP_SET* set, /**< global SCIP settings */
147  SCIP_STAT* stat, /**< problem statistics */
148  SCIP_Bool varfixing, /**< FALSE if implication for x == 0 has to be added, TRUE for x == 1 */
149  SCIP_VAR* implvar, /**< variable y in implication y <= b or y >= b */
150  SCIP_BOUNDTYPE impltype, /**< type of implication y <= b (SCIP_BOUNDTYPE_UPPER) or y >= b (SCIP_BOUNDTYPE_LOWER) */
151  SCIP_Real implbound, /**< bound b in implication y <= b or y >= b */
152  SCIP_Bool isshortcut, /**< is the implication a shortcut, i.e., added as part of the transitive closure of another implication? */
153  SCIP_Bool* conflict, /**< pointer to store whether implication causes a conflict for variable x */
154  SCIP_Bool* added /**< pointer to store whether the implication was added */
155  );
156 
157 /** removes the implication x <= 0 or x >= 1 ==> y <= b or y >= b from the implications data structure */
158 extern
159 SCIP_RETCODE SCIPimplicsDel(
160  SCIP_IMPLICS** implics, /**< pointer to implications data structure */
161  BMS_BLKMEM* blkmem, /**< block memory */
162  SCIP_SET* set, /**< global SCIP settings */
163  SCIP_Bool varfixing, /**< FALSE if y should be removed from implications for x <= 0, TRUE for x >= 1 */
164  SCIP_VAR* implvar, /**< variable y in implication y <= b or y >= b */
165  SCIP_BOUNDTYPE impltype /**< type of implication y <= b (SCIP_BOUNDTYPE_UPPER) or y >= b (SCIP_BOUNDTYPE_LOWER) */
166  );
167 
168 /** returns which implications on given variable y are contained in implications for x == 0 or x == 1 */
169 extern
170 void SCIPimplicsGetVarImplics(
171  SCIP_IMPLICS* implics, /**< implications data structure */
172  SCIP_Bool varfixing, /**< FALSE if y should be searched in implications for x == 0, TRUE for x == 1 */
173  SCIP_VAR* implvar, /**< variable y to search for */
174  SCIP_Bool* haslowerimplic, /**< pointer to store whether there exists an implication y >= l */
175  SCIP_Bool* hasupperimplic /**< pointer to store whether there exists an implication y <= u */
176  );
177 
178 /** returns whether an implication y <= b or y >= b is contained in implications for x == 0 or x == 1 */
179 extern
180 SCIP_Bool SCIPimplicsContainsImpl(
181  SCIP_IMPLICS* implics, /**< implications data structure */
182  SCIP_Bool varfixing, /**< FALSE if y should be searched in implications for x == 0, TRUE for x == 1 */
183  SCIP_VAR* implvar, /**< variable y to search for */
184  SCIP_BOUNDTYPE impltype /**< type of implication y <=/>= b to search for */
185  );
186 
187 
188 /** gets number of implications for a given binary variable fixing */
189 extern
190 int SCIPimplicsGetNImpls(
191  SCIP_IMPLICS* implics, /**< implication data */
192  SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
193  );
194 
195 /** gets number of implications on binary variables for a given binary variable fixing */
196 extern
197 int SCIPimplicsGetNBinImpls(
198  SCIP_IMPLICS* implics, /**< implication data */
199  SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
200  );
201 
202 /** gets array with implied variables for a given binary variable fixing */
203 extern
204 SCIP_VAR** SCIPimplicsGetVars(
205  SCIP_IMPLICS* implics, /**< implication data */
206  SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
207  );
208 
209 /** gets array with implication types for a given binary variable fixing */
210 extern
211 SCIP_BOUNDTYPE* SCIPimplicsGetTypes(
212  SCIP_IMPLICS* implics, /**< implication data */
213  SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
214  );
215 
216 /** gets array with implication bounds for a given binary variable fixing */
217 extern
218 SCIP_Real* SCIPimplicsGetBounds(
219  SCIP_IMPLICS* implics, /**< implication data */
220  SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
221  );
222 
223 /** Gets array with unique implication identifiers for a given binary variable fixing.
224  * If an implication is a shortcut, i.e., it was added as part of the transitive closure of another implication,
225  * its id is negative, otherwise it is nonnegative.
226  */
227 extern
228 int* SCIPimplicsGetIds(
229  SCIP_IMPLICS* implics, /**< implication data */
230  SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
231  );
232 
233 #ifdef NDEBUG
234 
235 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
236  * speed up the algorithms.
237  */
238 
239 #define SCIPimplicsGetNImpls(implics, varfixing) ((implics) != NULL ? (implics)->nimpls[varfixing] : 0)
240 #define SCIPimplicsGetNBinImpls(implics, varfixing) ((implics) != NULL ? (implics)->nbinimpls[varfixing] : 0)
241 #define SCIPimplicsGetVars(implics, varfixing) ((implics) != NULL ? (implics)->vars[varfixing] : NULL)
242 #define SCIPimplicsGetTypes(implics, varfixing) ((implics) != NULL ? (implics)->types[varfixing] : NULL)
243 #define SCIPimplicsGetBounds(implics, varfixing) ((implics) != NULL ? (implics)->bounds[varfixing] : NULL)
244 #define SCIPimplicsGetIds(implics, varfixing) ((implics) != NULL ? (implics)->ids[varfixing] : NULL)
245 
246 #endif
247 
248 
249 
250 
251 /*
252  * methods for cliques
253  */
254 
255 /** adds a single variable to the given clique */
256 extern
257 SCIP_RETCODE SCIPcliqueAddVar(
258  SCIP_CLIQUE* clique, /**< clique data structure */
259  BMS_BLKMEM* blkmem, /**< block memory */
260  SCIP_SET* set, /**< global SCIP settings */
261  SCIP_VAR* var, /**< variable to add to the clique */
262  SCIP_Bool value, /**< value of the variable in the clique */
263  SCIP_Bool* doubleentry, /**< pointer to store whether the variable and value occurs twice in the clique */
264  SCIP_Bool* oppositeentry /**< pointer to store whether the variable with opposite value is in the clique */
265  );
266 
267 /** removes a single variable from the given clique */
268 extern
269 SCIP_RETCODE SCIPcliqueDelVar(
270  SCIP_CLIQUE* clique, /**< clique data structure */
271  SCIP_VAR* var, /**< variable to remove from the clique */
272  SCIP_Bool value /**< value of the variable in the clique */
273  );
274 
275 /** frees a clique list data structure */
276 extern
277 void SCIPcliquelistFree(
278  SCIP_CLIQUELIST** cliquelist, /**< pointer to the clique list data structure */
279  BMS_BLKMEM* blkmem /**< block memory */
280  );
281 
282 /** adds a clique to the clique list */
283 extern
284 SCIP_RETCODE SCIPcliquelistAdd(
285  SCIP_CLIQUELIST** cliquelist, /**< pointer to the clique list data structure */
286  BMS_BLKMEM* blkmem, /**< block memory */
287  SCIP_SET* set, /**< global SCIP settings */
288  SCIP_Bool value, /**< value of the variable for which the clique list should be extended */
289  SCIP_CLIQUE* clique /**< clique that should be added to the clique list */
290  );
291 
292 /** removes a clique from the clique list */
293 extern
294 SCIP_RETCODE SCIPcliquelistDel(
295  SCIP_CLIQUELIST** cliquelist, /**< pointer to the clique list data structure */
296  BMS_BLKMEM* blkmem, /**< block memory */
297  SCIP_Bool value, /**< value of the variable for which the clique list should be reduced */
298  SCIP_CLIQUE* clique /**< clique that should be deleted from the clique list */
299  );
300 
301 /** returns whether the given clique lists have a non-empty intersection, i.e. whether there is a clique that appears
302  * in both lists
303  */
304 extern
305 SCIP_Bool SCIPcliquelistsHaveCommonClique(
306  SCIP_CLIQUELIST* cliquelist1, /**< first clique list data structure */
307  SCIP_Bool value1, /**< value of first variable */
308  SCIP_CLIQUELIST* cliquelist2, /**< second clique list data structure */
309  SCIP_Bool value2 /**< value of second variable */
310  );
311 
312 /** removes all listed entries from the cliques */
313 extern
314 void SCIPcliquelistRemoveFromCliques(
315  SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */
316  SCIP_VAR* var /**< active problem variable the clique list belongs to */
317  );
318 
319 /** creates a clique table data structure */
320 extern
321 SCIP_RETCODE SCIPcliquetableCreate(
322  SCIP_CLIQUETABLE** cliquetable /**< pointer to store clique table data structure */
323  );
324 
325 /** frees a clique table data structure */
326 extern
327 SCIP_RETCODE SCIPcliquetableFree(
328  SCIP_CLIQUETABLE** cliquetable, /**< pointer to store clique table data structure */
329  BMS_BLKMEM* blkmem /**< block memory */
330  );
331 
332 /** adds a clique to the clique table, using the given values for the given variables;
333  * performs implications if the clique contains the same variable twice
334  */
335 extern
336 SCIP_RETCODE SCIPcliquetableAdd(
337  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
338  BMS_BLKMEM* blkmem, /**< block memory */
339  SCIP_SET* set, /**< global SCIP settings */
340  SCIP_STAT* stat, /**< problem statistics */
341  SCIP_PROB* transprob, /**< transformed problem */
342  SCIP_PROB* origprob, /**< original problem */
343  SCIP_TREE* tree, /**< branch and bound tree if in solving stage */
344  SCIP_LP* lp, /**< current LP data */
345  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
346  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
347  SCIP_VAR** vars, /**< binary variables in the clique: at most one can be set to the given value */
348  SCIP_Bool* values, /**< values of the variables in the clique; NULL to use TRUE for all vars */
349  int nvars, /**< number of variables in the clique */
350  SCIP_Bool* infeasible, /**< pointer to store whether an infeasibility was detected */
351  int* nbdchgs /**< pointer to count the number of performed bound changes, or NULL */
352  );
353 
354 /** removes all empty and single variable cliques from the clique table, and converts all two variable cliques
355  * into implications; removes double entries from the clique table
356  */
357 extern
358 SCIP_RETCODE SCIPcliquetableCleanup(
359  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
360  BMS_BLKMEM* blkmem, /**< block memory */
361  SCIP_SET* set, /**< global SCIP settings */
362  SCIP_STAT* stat, /**< problem statistics */
363  SCIP_PROB* transprob, /**< transformed problem */
364  SCIP_PROB* origprob, /**< original problem */
365  SCIP_TREE* tree, /**< branch and bound tree if in solving stage */
366  SCIP_LP* lp, /**< current LP data */
367  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
368  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
369  SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
370  );
371 
372 /** returns the number of cliques stored in the clique list */
373 extern
374 int SCIPcliquelistGetNCliques(
375  SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */
376  SCIP_Bool value /**< value of the variable for which the cliques should be returned */
377  );
378 
379 /** returns the cliques stored in the clique list, or NULL if the clique list is empty */
380 extern
381 SCIP_CLIQUE** SCIPcliquelistGetCliques(
382  SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */
383  SCIP_Bool value /**< value of the variable for which the cliques should be returned */
384  );
385 
386 /** checks whether variable is contained in all cliques of the cliquelist */
387 extern
388 void SCIPcliquelistCheck(
389  SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */
390  SCIP_VAR* var /**< variable, the clique list belongs to */
391  );
392 
393 /** gets the number of cliques stored in the clique table */
394 extern
395 int SCIPcliquetableGetNCliques(
396  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
397  );
398 
399 /** gets the array of cliques stored in the clique table */
400 extern
401 SCIP_CLIQUE** SCIPcliquetableGetCliques(
402  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
403  );
404 
405 #ifdef NDEBUG
406 
407 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
408  * speed up the algorithms.
409  */
410 
411 #define SCIPcliquelistGetNCliques(cliquelist, value) ((cliquelist) != NULL ? (cliquelist)->ncliques[value] : 0)
412 #define SCIPcliquelistGetCliques(cliquelist, value) ((cliquelist) != NULL ? (cliquelist)->cliques[value] : NULL)
413 #define SCIPcliquelistCheck(cliquelist, var) /**/
414 #define SCIPcliquetableGetNCliques(cliquetable) ((cliquetable)->ncliques)
415 #define SCIPcliquetableGetCliques(cliquetable) ((cliquetable)->cliques)
416 
417 #endif
418 
419 #ifdef __cplusplus
420 }
421 #endif
422 
423 #endif
424