Scippy

SCIP

Solving Constraint Integer Programs

scip_sepa.c
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-2022 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 scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file scip_sepa.c
17  * @ingroup OTHER_CFILES
18  * @brief public methods for separator plugins
19  * @author Tobias Achterberg
20  * @author Timo Berthold
21  * @author Gerald Gamrath
22  * @author Leona Gottwald
23  * @author Stefan Heinz
24  * @author Gregor Hendel
25  * @author Thorsten Koch
26  * @author Alexander Martin
27  * @author Marc Pfetsch
28  * @author Michael Winkler
29  * @author Kati Wolter
30  *
31  * @todo check all SCIP_STAGE_* switches, and include the new stages TRANSFORMED and INITSOLVE
32  */
33 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 #include "scip/debug.h"
37 #include "scip/pub_message.h"
38 #include "scip/scip_sepa.h"
39 #include "scip/sepa.h"
40 #include "scip/set.h"
41 #include "scip/struct_mem.h"
42 #include "scip/struct_scip.h"
43 #include "scip/struct_set.h"
44 #include "scip/tree.h"
45 
46 /** creates a separator and includes it in SCIP.
47  *
48  * @note method has all separator callbacks as arguments and is thus changed every time a new
49  * callback is added
50  * in future releases; consider using SCIPincludeSepaBasic() and setter functions
51  * if you seek for a method which is less likely to change in future releases
52  */
54  SCIP* scip, /**< SCIP data structure */
55  const char* name, /**< name of separator */
56  const char* desc, /**< description of separator */
57  int priority, /**< priority of separator (>= 0: before, < 0: after constraint handlers) */
58  int freq, /**< frequency for calling separator */
59  SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound compared
60  * to best node's dual bound for applying separation */
61  SCIP_Bool usessubscip, /**< does the separator use a secondary SCIP instance? */
62  SCIP_Bool delay, /**< should separator be delayed, if other separators found cuts? */
63  SCIP_DECL_SEPACOPY ((*sepacopy)), /**< copy method of separator or NULL if you don't want to copy your plugin into sub-SCIPs */
64  SCIP_DECL_SEPAFREE ((*sepafree)), /**< destructor of separator */
65  SCIP_DECL_SEPAINIT ((*sepainit)), /**< initialize separator */
66  SCIP_DECL_SEPAEXIT ((*sepaexit)), /**< deinitialize separator */
67  SCIP_DECL_SEPAINITSOL ((*sepainitsol)), /**< solving process initialization method of separator */
68  SCIP_DECL_SEPAEXITSOL ((*sepaexitsol)), /**< solving process deinitialization method of separator */
69  SCIP_DECL_SEPAEXECLP ((*sepaexeclp)), /**< LP solution separation method of separator */
70  SCIP_DECL_SEPAEXECSOL ((*sepaexecsol)), /**< arbitrary primal solution separation method of separator */
71  SCIP_SEPADATA* sepadata /**< separator data */
72  )
73 {
74  SCIP_SEPA* sepa;
75 
76  SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeSepa", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
77 
78  /* check whether separator is already present */
79  if( SCIPfindSepa(scip, name) != NULL )
80  {
81  SCIPerrorMessage("separator <%s> already included.\n", name);
82  return SCIP_INVALIDDATA;
83  }
84 
85  SCIP_CALL( SCIPsepaCreate(&sepa, scip->set, scip->messagehdlr, scip->mem->setmem,
86  name, desc, priority, freq, maxbounddist, usessubscip, delay,
87  sepacopy, sepafree, sepainit, sepaexit, sepainitsol, sepaexitsol, sepaexeclp, sepaexecsol, sepadata) );
88  SCIP_CALL( SCIPsetIncludeSepa(scip->set, sepa) );
89 
90  return SCIP_OKAY;
91 }
92 
93 /** creates a separator and includes it in SCIP with its most fundamental callbacks. All non-fundamental
94  * (or optional) callbacks as, e.g., init and exit callbacks, will be set to NULL.
95  * Optional callbacks can be set via specific setter functions, see SCIPsetSepaInit(), SCIPsetSepaFree(),
96  * SCIPsetSepaInitsol(), SCIPsetSepaExitsol(), SCIPsetSepaCopy(), SCIPsetExit().
97  *
98  * @note if you want to set all callbacks with a single method call, consider using SCIPincludeSepa() instead
99  */
101  SCIP* scip, /**< SCIP data structure */
102  SCIP_SEPA** sepa, /**< reference to a separator, or NULL */
103  const char* name, /**< name of separator */
104  const char* desc, /**< description of separator */
105  int priority, /**< priority of separator (>= 0: before, < 0: after constraint handlers) */
106  int freq, /**< frequency for calling separator */
107  SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound compared
108  * to best node's dual bound for applying separation */
109  SCIP_Bool usessubscip, /**< does the separator use a secondary SCIP instance? */
110  SCIP_Bool delay, /**< should separator be delayed, if other separators found cuts? */
111  SCIP_DECL_SEPAEXECLP ((*sepaexeclp)), /**< LP solution separation method of separator */
112  SCIP_DECL_SEPAEXECSOL ((*sepaexecsol)), /**< arbitrary primal solution separation method of separator */
113  SCIP_SEPADATA* sepadata /**< separator data */
114  )
115 {
116  SCIP_SEPA* sepaptr;
117 
118  SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeSepaBasic", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
119 
120  /* check whether separator is already present */
121  if( SCIPfindSepa(scip, name) != NULL )
122  {
123  SCIPerrorMessage("separator <%s> already included.\n", name);
124  return SCIP_INVALIDDATA;
125  }
126 
127  SCIP_CALL( SCIPsepaCreate(&sepaptr, scip->set, scip->messagehdlr, scip->mem->setmem,
128  name, desc, priority, freq, maxbounddist, usessubscip, delay,
129  NULL, NULL, NULL, NULL, NULL, NULL, sepaexeclp, sepaexecsol, sepadata) );
130 
131  assert(sepaptr != NULL);
132 
133  SCIP_CALL( SCIPsetIncludeSepa(scip->set, sepaptr) );
134 
135  if( sepa != NULL)
136  *sepa = sepaptr;
137 
138  return SCIP_OKAY;
139 }
140 
141 /** sets copy method of separator */
143  SCIP* scip, /**< SCIP data structure */
144  SCIP_SEPA* sepa, /**< separator */
145  SCIP_DECL_SEPACOPY ((*sepacopy)) /**< copy method of separator or NULL if you don't want to copy your plugin into sub-SCIPs */
146  )
147 {
148  SCIP_CALL( SCIPcheckStage(scip, "SCIPsetSepaCopy", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
149 
150  assert(sepa != NULL);
151 
152  SCIPsepaSetCopy(sepa, sepacopy);
153 
154  return SCIP_OKAY;
155 }
156 
157 /** sets destructor method of separator */
159  SCIP* scip, /**< SCIP data structure */
160  SCIP_SEPA* sepa, /**< separator */
161  SCIP_DECL_SEPAFREE ((*sepafree)) /**< destructor of separator */
162  )
163 {
164  SCIP_CALL( SCIPcheckStage(scip, "SCIPsetSepaFree", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
165 
166  assert(sepa != NULL);
167 
168  SCIPsepaSetFree(sepa, sepafree);
169 
170  return SCIP_OKAY;
171 }
172 
173 /** sets initialization method of separator */
175  SCIP* scip, /**< SCIP data structure */
176  SCIP_SEPA* sepa, /**< separator */
177  SCIP_DECL_SEPAINIT ((*sepainit)) /**< initialize separator */
178  )
179 {
180  SCIP_CALL( SCIPcheckStage(scip, "SCIPsetSepaInit", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
181 
182  assert(sepa != NULL);
183 
184  SCIPsepaSetInit(sepa, sepainit);
185 
186  return SCIP_OKAY;
187 }
188 
189 /** sets deinitialization method of separator */
191  SCIP* scip, /**< SCIP data structure */
192  SCIP_SEPA* sepa, /**< separator */
193  SCIP_DECL_SEPAEXIT ((*sepaexit)) /**< deinitialize separator */
194  )
195 {
196  SCIP_CALL( SCIPcheckStage(scip, "SCIPsetSepaExit", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
197 
198  assert(sepa != NULL);
199 
200  SCIPsepaSetExit(sepa, sepaexit);
201 
202  return SCIP_OKAY;
203 }
204 
205 /** sets solving process initialization method of separator */
207  SCIP* scip, /**< SCIP data structure */
208  SCIP_SEPA* sepa, /**< separator */
209  SCIP_DECL_SEPAINITSOL ((*sepainitsol)) /**< solving process initialization method of separator */
210  )
211 {
212  SCIP_CALL( SCIPcheckStage(scip, "SCIPsetSepaInitsol", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
213 
214  assert(sepa != NULL);
215 
216  SCIPsepaSetInitsol(sepa, sepainitsol);
217 
218  return SCIP_OKAY;
219 }
220 
221 /** sets solving process deinitialization method of separator */
223  SCIP* scip, /**< SCIP data structure */
224  SCIP_SEPA* sepa, /**< separator */
225  SCIP_DECL_SEPAEXITSOL ((*sepaexitsol)) /**< solving process deinitialization method of separator */
226  )
227 {
228  SCIP_CALL( SCIPcheckStage(scip, "SCIPsetSepaExitsol", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
229 
230  assert(sepa != NULL);
231 
232  SCIPsepaSetExitsol(sepa, sepaexitsol);
233 
234  return SCIP_OKAY;
235 }
236 
237 /** returns the separator of the given name, or NULL if not existing */
239  SCIP* scip, /**< SCIP data structure */
240  const char* name /**< name of separator */
241  )
242 {
243  assert(scip != NULL);
244  assert(scip->set != NULL);
245  assert(name != NULL);
246 
247  return SCIPsetFindSepa(scip->set, name);
248 }
249 
250 /** returns the array of currently available separators */
252  SCIP* scip /**< SCIP data structure */
253  )
254 {
255  assert(scip != NULL);
256  assert(scip->set != NULL);
257 
258  SCIPsetSortSepas(scip->set);
259 
260  return scip->set->sepas;
261 }
262 
263 /** returns the number of currently available separators */
265  SCIP* scip /**< SCIP data structure */
266  )
267 {
268  assert(scip != NULL);
269  assert(scip->set != NULL);
270 
271  return scip->set->nsepas;
272 }
273 
274 /** sets the priority of a separator */
276  SCIP* scip, /**< SCIP data structure */
277  SCIP_SEPA* sepa, /**< separator */
278  int priority /**< new priority of the separator */
279  )
280 {
281  assert(scip != NULL);
282  assert(scip->set != NULL);
283 
284  SCIPsepaSetPriority(sepa, scip->set, priority);
285 
286  return SCIP_OKAY;
287 }
288 
289 /** declares separator to be a parent separator
290  *
291  * Parent separators generate cuts of several types. To distinguish these cuts, they create child separators, which are
292  * only needed to detect which cuts are applied.
293  */
295  SCIP* scip, /**< SCIP data structure */
296  SCIP_SEPA* sepa /**< separator */
297  )
298 {
299  assert(scip != NULL);
300  assert(sepa != NULL);
301 
303 }
304 
305 /** sets the parent separator
306  *
307  * Informs SCIP that the separator @p sepa depends on the parent separator @p parentsepa.
308  */
310  SCIP* scip, /**< SCIP data structure */
311  SCIP_SEPA* sepa, /**< separator */
312  SCIP_SEPA* parentsepa /**< parent separator */
313  )
314 {
315  assert(scip != NULL);
316  assert(sepa != NULL);
317 
318  SCIPsepaSetParentsepa(sepa, parentsepa);
319 }
320 
321 #undef SCIPgetSepaMinEfficacy
322 
323 /** gets value of minimal efficacy for a cut to enter the LP
324  *
325  * @pre This method can be called if @p scip is in one of the following stages:
326  * - \ref SCIP_STAGE_SOLVING
327  *
328  * @return value of "separating/minefficacyroot" if at root node, otherwise value of "separating/minefficacy"
329  */
331  SCIP* scip /**< SCIP data structure */
332  )
333 {
334  assert(scip != NULL);
335  assert(scip->tree != NULL);
336  assert(scip->set != NULL);
337 
338  SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetSepaMinEfficacy", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
339 
340  if( SCIPtreeGetCurrentDepth(scip->tree) != 0 )
341  return scip->set->sepa_minefficacyroot;
342  return scip->set->sepa_minefficacy;
343 }
void SCIPsepaSetFree(SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: sepa.c:658
internal methods for separators
SCIP_Real sepa_minefficacyroot
Definition: struct_set.h:534
internal methods for branch and bound tree
SCIP_SEPA * SCIPfindSepa(SCIP *scip, const char *name)
Definition: scip_sepa.c:238
void SCIPsetSepaParentsepa(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPA *parentsepa)
Definition: scip_sepa.c:309
#define FALSE
Definition: def.h:87
SCIP_SEPA ** sepas
Definition: struct_set.h:79
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_Real sepa_minefficacy
Definition: struct_set.h:533
int SCIPtreeGetCurrentDepth(SCIP_TREE *tree)
Definition: tree.c:8394
void SCIPsepaSetExit(SCIP_SEPA *sepa, SCIP_DECL_SEPAEXIT((*sepaexit)))
Definition: sepa.c:680
SCIP_RETCODE SCIPsetSepaPriority(SCIP *scip, SCIP_SEPA *sepa, int priority)
Definition: scip_sepa.c:275
#define SCIP_DECL_SEPAEXECLP(x)
Definition: type_sepa.h:127
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip_sepa.c:142
public methods for separator plugins
SCIP_RETCODE SCIPsetIncludeSepa(SCIP_SET *set, SCIP_SEPA *sepa)
Definition: set.c:4247
#define SCIP_DECL_SEPACOPY(x)
Definition: type_sepa.h:52
SCIP_MEM * mem
Definition: struct_scip.h:62
SCIP_RETCODE SCIPincludeSepa(SCIP *scip, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPACOPY((*sepacopy)), SCIP_DECL_SEPAFREE((*sepafree)), SCIP_DECL_SEPAINIT((*sepainit)), SCIP_DECL_SEPAEXIT((*sepaexit)), SCIP_DECL_SEPAINITSOL((*sepainitsol)), SCIP_DECL_SEPAEXITSOL((*sepaexitsol)), SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
Definition: scip_sepa.c:53
#define SCIPerrorMessage
Definition: pub_message.h:55
SCIP_RETCODE SCIPsetSepaExit(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXIT((*sepaexit)))
Definition: scip_sepa.c:190
SCIP_RETCODE SCIPcheckStage(SCIP *scip, const char *method, SCIP_Bool init, SCIP_Bool problem, SCIP_Bool transforming, SCIP_Bool transformed, SCIP_Bool initpresolve, SCIP_Bool presolving, SCIP_Bool exitpresolve, SCIP_Bool presolved, SCIP_Bool initsolve, SCIP_Bool solving, SCIP_Bool solved, SCIP_Bool exitsolve, SCIP_Bool freetrans, SCIP_Bool freescip)
Definition: debug.c:2177
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_SEPA * SCIPsetFindSepa(SCIP_SET *set, const char *name)
Definition: set.c:4271
SCIP_RETCODE SCIPsetSepaInitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAINITSOL((*sepainitsol)))
Definition: scip_sepa.c:206
SCIP_Real SCIPgetSepaMinEfficacy(SCIP *scip)
Definition: scip_sepa.c:330
void SCIPsepaSetExitsol(SCIP_SEPA *sepa, SCIP_DECL_SEPAEXITSOL((*sepaexitsol)))
Definition: sepa.c:702
internal methods for global SCIP settings
#define SCIP_CALL(x)
Definition: def.h:384
SCIP main data structure.
BMS_BLKMEM * setmem
Definition: struct_mem.h:39
void SCIPsetSepaIsParentsepa(SCIP *scip, SCIP_SEPA *sepa)
Definition: scip_sepa.c:294
int nsepas
Definition: struct_set.h:119
SCIP_RETCODE SCIPincludeSepaBasic(SCIP *scip, SCIP_SEPA **sepa, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
Definition: scip_sepa.c:100
void SCIPsepaSetCopy(SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: sepa.c:647
void SCIPsepaSetInitsol(SCIP_SEPA *sepa, SCIP_DECL_SEPAINITSOL((*sepainitsol)))
Definition: sepa.c:691
SCIP_RETCODE SCIPsetSepaExitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXITSOL((*sepaexitsol)))
Definition: scip_sepa.c:222
#define SCIP_Bool
Definition: def.h:84
#define SCIP_DECL_SEPAINIT(x)
Definition: type_sepa.h:68
methods for debugging
datastructures for block memory pools and memory buffers
#define SCIP_DECL_SEPAEXITSOL(x)
Definition: type_sepa.h:98
#define SCIP_DECL_SEPAEXECSOL(x)
Definition: type_sepa.h:157
void SCIPsepaSetPriority(SCIP_SEPA *sepa, SCIP_SET *set, int priority)
Definition: sepa.c:764
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip_sepa.c:158
SCIP_RETCODE SCIPsetSepaInit(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAINIT((*sepainit)))
Definition: scip_sepa.c:174
#define SCIP_DECL_SEPAEXIT(x)
Definition: type_sepa.h:76
#define SCIP_DECL_SEPAINITSOL(x)
Definition: type_sepa.h:87
SCIP_SET * set
Definition: struct_scip.h:63
public methods for message output
SCIP_MESSAGEHDLR * messagehdlr
Definition: struct_scip.h:66
#define SCIP_Real
Definition: def.h:177
void SCIPsepaSetParentsepa(SCIP_SEPA *sepa, SCIP_SEPA *parentsepa)
Definition: sepa.c:723
void SCIPsepaSetIsParentsepa(SCIP_SEPA *sepa)
Definition: sepa.c:713
SCIP_TREE * tree
Definition: struct_scip.h:86
SCIP_SEPA ** SCIPgetSepas(SCIP *scip)
Definition: scip_sepa.c:251
void SCIPsepaSetInit(SCIP_SEPA *sepa, SCIP_DECL_SEPAINIT((*sepainit)))
Definition: sepa.c:669
int SCIPgetNSepas(SCIP *scip)
Definition: scip_sepa.c:264
#define SCIP_CALL_ABORT(x)
Definition: def.h:363
void SCIPsetSortSepas(SCIP_SET *set)
Definition: set.c:4291
datastructures for global SCIP settings
#define SCIP_DECL_SEPAFREE(x)
Definition: type_sepa.h:60
struct SCIP_SepaData SCIP_SEPADATA
Definition: type_sepa.h:43
SCIP_RETCODE SCIPsepaCreate(SCIP_SEPA **sepa, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPACOPY((*sepacopy)), SCIP_DECL_SEPAFREE((*sepafree)), SCIP_DECL_SEPAINIT((*sepainit)), SCIP_DECL_SEPAEXIT((*sepaexit)), SCIP_DECL_SEPAINITSOL((*sepainitsol)), SCIP_DECL_SEPAEXITSOL((*sepaexitsol)), SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
Definition: sepa.c:194