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