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-2025 Zuse Institute Berlin (ZIB) */
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 * @pre This method can be called if SCIP is in one of the following stages:
57 * - \ref SCIP_STAGE_INIT
58 * - \ref SCIP_STAGE_PROBLEM
59 *
60 * @note method has all separator callbacks as arguments and is thus changed every time a new
61 * callback is added
62 * in future releases; consider using SCIPincludeSepaBasic() and setter functions
63 * if you seek for a method which is less likely to change in future releases
64 */
66 SCIP* scip, /**< SCIP data structure */
67 const char* name, /**< name of separator */
68 const char* desc, /**< description of separator */
69 int priority, /**< priority of separator (>= 0: before, < 0: after constraint handlers) */
70 int freq, /**< frequency for calling separator */
71 SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound compared
72 * to best node's dual bound for applying separation */
73 SCIP_Bool usessubscip, /**< does the separator use a secondary SCIP instance? */
74 SCIP_Bool delay, /**< should separator be delayed, if other separators found cuts? */
75 SCIP_DECL_SEPACOPY ((*sepacopy)), /**< copy method of separator or NULL if you don't want to copy your plugin into sub-SCIPs */
76 SCIP_DECL_SEPAFREE ((*sepafree)), /**< destructor of separator */
77 SCIP_DECL_SEPAINIT ((*sepainit)), /**< initialize separator */
78 SCIP_DECL_SEPAEXIT ((*sepaexit)), /**< deinitialize separator */
79 SCIP_DECL_SEPAINITSOL ((*sepainitsol)), /**< solving process initialization method of separator */
80 SCIP_DECL_SEPAEXITSOL ((*sepaexitsol)), /**< solving process deinitialization method of separator */
81 SCIP_DECL_SEPAEXECLP ((*sepaexeclp)), /**< LP solution separation method of separator */
82 SCIP_DECL_SEPAEXECSOL ((*sepaexecsol)), /**< arbitrary primal solution separation method of separator */
83 SCIP_SEPADATA* sepadata /**< separator data */
84 )
85{
86 SCIP_SEPA* sepa;
87
89
90 /* check whether separator is already present */
91 if( SCIPfindSepa(scip, name) != NULL )
92 {
93 SCIPerrorMessage("separator <%s> already included.\n", name);
94 return SCIP_INVALIDDATA;
95 }
96
97 SCIP_CALL( SCIPsepaCreate(&sepa, scip->set, scip->messagehdlr, scip->mem->setmem,
98 name, desc, priority, freq, maxbounddist, usessubscip, delay,
99 sepacopy, sepafree, sepainit, sepaexit, sepainitsol, sepaexitsol, sepaexeclp, sepaexecsol, sepadata) );
100 SCIP_CALL( SCIPsetIncludeSepa(scip->set, sepa) );
101
102 return SCIP_OKAY;
103}
104
105/** creates a separator and includes it in SCIP with its most fundamental callbacks. All non-fundamental
106 * (or optional) callbacks as, e.g., init and exit callbacks, will be set to NULL.
107 * Optional callbacks can be set via specific setter functions, see SCIPsetSepaInit(), SCIPsetSepaFree(),
108 * SCIPsetSepaInitsol(), SCIPsetSepaExitsol(), SCIPsetSepaCopy(), SCIPsetExit().
109 * @pre This method can be called if SCIP is in one of the following stages:
110 * - \ref SCIP_STAGE_INIT
111 * - \ref SCIP_STAGE_PROBLEM
112 *
113 * @note if you want to set all callbacks with a single method call, consider using SCIPincludeSepa() instead
114 */
116 SCIP* scip, /**< SCIP data structure */
117 SCIP_SEPA** sepa, /**< reference to a separator, or NULL */
118 const char* name, /**< name of separator */
119 const char* desc, /**< description of separator */
120 int priority, /**< priority of separator (>= 0: before, < 0: after constraint handlers) */
121 int freq, /**< frequency for calling separator */
122 SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound compared
123 * to best node's dual bound for applying separation */
124 SCIP_Bool usessubscip, /**< does the separator use a secondary SCIP instance? */
125 SCIP_Bool delay, /**< should separator be delayed, if other separators found cuts? */
126 SCIP_DECL_SEPAEXECLP ((*sepaexeclp)), /**< LP solution separation method of separator */
127 SCIP_DECL_SEPAEXECSOL ((*sepaexecsol)), /**< arbitrary primal solution separation method of separator */
128 SCIP_SEPADATA* sepadata /**< separator data */
129 )
130{
131 SCIP_SEPA* sepaptr;
132
133 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeSepaBasic", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
134
135 /* check whether separator is already present */
136 if( SCIPfindSepa(scip, name) != NULL )
137 {
138 SCIPerrorMessage("separator <%s> already included.\n", name);
139 return SCIP_INVALIDDATA;
140 }
141
142 SCIP_CALL( SCIPsepaCreate(&sepaptr, scip->set, scip->messagehdlr, scip->mem->setmem,
143 name, desc, priority, freq, maxbounddist, usessubscip, delay,
144 NULL, NULL, NULL, NULL, NULL, NULL, sepaexeclp, sepaexecsol, sepadata) );
145
146 assert(sepaptr != NULL);
147
148 SCIP_CALL( SCIPsetIncludeSepa(scip->set, sepaptr) );
149
150 if( sepa != NULL)
151 *sepa = sepaptr;
152
153 return SCIP_OKAY;
154}
155
156/** sets copy method of separator */
158 SCIP* scip, /**< SCIP data structure */
159 SCIP_SEPA* sepa, /**< separator */
160 SCIP_DECL_SEPACOPY ((*sepacopy)) /**< copy method of separator or NULL if you don't want to copy your plugin into sub-SCIPs */
161 )
162{
164
165 assert(sepa != NULL);
166
167 SCIPsepaSetCopy(sepa, sepacopy);
168
169 return SCIP_OKAY;
170}
171
172/** sets destructor method of separator */
174 SCIP* scip, /**< SCIP data structure */
175 SCIP_SEPA* sepa, /**< separator */
176 SCIP_DECL_SEPAFREE ((*sepafree)) /**< destructor of separator */
177 )
178{
180
181 assert(sepa != NULL);
182
183 SCIPsepaSetFree(sepa, sepafree);
184
185 return SCIP_OKAY;
186}
187
188/** sets initialization method of separator */
190 SCIP* scip, /**< SCIP data structure */
191 SCIP_SEPA* sepa, /**< separator */
192 SCIP_DECL_SEPAINIT ((*sepainit)) /**< initialize separator */
193 )
194{
196
197 assert(sepa != NULL);
198
199 SCIPsepaSetInit(sepa, sepainit);
200
201 return SCIP_OKAY;
202}
203
204/** sets deinitialization method of separator */
206 SCIP* scip, /**< SCIP data structure */
207 SCIP_SEPA* sepa, /**< separator */
208 SCIP_DECL_SEPAEXIT ((*sepaexit)) /**< deinitialize separator */
209 )
210{
212
213 assert(sepa != NULL);
214
215 SCIPsepaSetExit(sepa, sepaexit);
216
217 return SCIP_OKAY;
218}
219
220/** sets solving process initialization method of separator */
222 SCIP* scip, /**< SCIP data structure */
223 SCIP_SEPA* sepa, /**< separator */
224 SCIP_DECL_SEPAINITSOL ((*sepainitsol)) /**< solving process initialization method of separator */
225 )
226{
228
229 assert(sepa != NULL);
230
231 SCIPsepaSetInitsol(sepa, sepainitsol);
232
233 return SCIP_OKAY;
234}
235
236/** sets solving process deinitialization method of separator */
238 SCIP* scip, /**< SCIP data structure */
239 SCIP_SEPA* sepa, /**< separator */
240 SCIP_DECL_SEPAEXITSOL ((*sepaexitsol)) /**< solving process deinitialization method of separator */
241 )
242{
244
245 assert(sepa != NULL);
246
247 SCIPsepaSetExitsol(sepa, sepaexitsol);
248
249 return SCIP_OKAY;
250}
251
252/** returns the separator of the given name, or NULL if not existing */
254 SCIP* scip, /**< SCIP data structure */
255 const char* name /**< name of separator */
256 )
257{
258 assert(scip != NULL);
259 assert(scip->set != NULL);
260 assert(name != NULL);
261
262 return SCIPsetFindSepa(scip->set, name);
263}
264
265/** returns the array of currently available separators */
267 SCIP* scip /**< SCIP data structure */
268 )
269{
270 assert(scip != NULL);
271 assert(scip->set != NULL);
272
274
275 return scip->set->sepas;
276}
277
278/** returns the number of currently available separators */
280 SCIP* scip /**< SCIP data structure */
281 )
282{
283 assert(scip != NULL);
284 assert(scip->set != NULL);
285
286 return scip->set->nsepas;
287}
288
289/** sets the priority of a separator */
291 SCIP* scip, /**< SCIP data structure */
292 SCIP_SEPA* sepa, /**< separator */
293 int priority /**< new priority of the separator */
294 )
295{
296 assert(scip != NULL);
297 assert(scip->set != NULL);
298
299 SCIPsepaSetPriority(sepa, scip->set, priority);
300
301 return SCIP_OKAY;
302}
303
304/** declares separator to be a parent separator
305 *
306 * Parent separators generate cuts of several types. To distinguish these cuts, they create child separators, which are
307 * only needed to detect which cuts are applied.
308 */
310 SCIP* scip, /**< SCIP data structure */
311 SCIP_SEPA* sepa /**< separator */
312 )
313{
314 assert(scip != NULL);
315 assert(sepa != NULL);
316
318}
319
320/** sets the parent separator
321 *
322 * Informs SCIP that the separator @p sepa depends on the parent separator @p parentsepa.
323 */
325 SCIP* scip, /**< SCIP data structure */
326 SCIP_SEPA* sepa, /**< separator */
327 SCIP_SEPA* parentsepa /**< parent separator */
328 )
329{
330 assert(scip != NULL);
331 assert(sepa != NULL);
332
333 SCIPsepaSetParentsepa(sepa, parentsepa);
334}
335
336#undef SCIPgetSepaMinEfficacy
337
338/** gets value of minimal efficacy for a cut to enter the LP
339 *
340 * @pre This method can be called if @p scip is in one of the following stages:
341 * - \ref SCIP_STAGE_SOLVING
342 *
343 * @return value of "separating/minefficacyroot" if at root node, otherwise value of "separating/minefficacy"
344 */
346 SCIP* scip /**< SCIP data structure */
347 )
348{
349 assert(scip != NULL);
350 assert(scip->tree != NULL);
351 assert(scip->set != NULL);
352
354
355 if( SCIPtreeGetCurrentDepth(scip->tree) != 0 )
356 return scip->set->sepa_minefficacyroot;
357 return scip->set->sepa_minefficacy;
358}
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:2203
methods for debugging
#define NULL
Definition: def.h:266
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:172
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIP_CALL_ABORT(x)
Definition: def.h:352
#define SCIP_CALL(x)
Definition: def.h:373
SCIP_RETCODE SCIPsetSepaExit(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXIT((*sepaexit)))
Definition: scip_sepa.c:205
int SCIPgetNSepas(SCIP *scip)
Definition: scip_sepa.c:279
SCIP_RETCODE SCIPsetSepaInitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAINITSOL((*sepainitsol)))
Definition: scip_sepa.c:221
SCIP_Real SCIPgetSepaMinEfficacy(SCIP *scip)
Definition: scip_sepa.c:345
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:115
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip_sepa.c:173
SCIP_RETCODE SCIPsetSepaPriority(SCIP *scip, SCIP_SEPA *sepa, int priority)
Definition: scip_sepa.c:290
SCIP_SEPA * SCIPfindSepa(SCIP *scip, const char *name)
Definition: scip_sepa.c:253
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:65
SCIP_RETCODE SCIPsetSepaExitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXITSOL((*sepaexitsol)))
Definition: scip_sepa.c:237
SCIP_SEPA ** SCIPgetSepas(SCIP *scip)
Definition: scip_sepa.c:266
void SCIPsetSepaIsParentsepa(SCIP *scip, SCIP_SEPA *sepa)
Definition: scip_sepa.c:309
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip_sepa.c:157
void SCIPsetSepaParentsepa(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPA *parentsepa)
Definition: scip_sepa.c:324
SCIP_RETCODE SCIPsetSepaInit(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAINIT((*sepainit)))
Definition: scip_sepa.c:189
public methods for message output
#define SCIPerrorMessage
Definition: pub_message.h:64
public methods for separator plugins
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
void SCIPsepaSetInit(SCIP_SEPA *sepa, SCIP_DECL_SEPAINIT((*sepainit)))
Definition: sepa.c:678
void SCIPsepaSetParentsepa(SCIP_SEPA *sepa, SCIP_SEPA *parentsepa)
Definition: sepa.c:732
void SCIPsepaSetInitsol(SCIP_SEPA *sepa, SCIP_DECL_SEPAINITSOL((*sepainitsol)))
Definition: sepa.c:700
void SCIPsepaSetFree(SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: sepa.c:667
void SCIPsepaSetCopy(SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: sepa.c:656
void SCIPsepaSetExit(SCIP_SEPA *sepa, SCIP_DECL_SEPAEXIT((*sepaexit)))
Definition: sepa.c:689
void SCIPsepaSetIsParentsepa(SCIP_SEPA *sepa)
Definition: sepa.c:722
void SCIPsepaSetPriority(SCIP_SEPA *sepa, SCIP_SET *set, int priority)
Definition: sepa.c:773
void SCIPsepaSetExitsol(SCIP_SEPA *sepa, SCIP_DECL_SEPAEXITSOL((*sepaexitsol)))
Definition: sepa.c:711
internal methods for separators
SCIP_RETCODE SCIPsetIncludeSepa(SCIP_SET *set, SCIP_SEPA *sepa)
Definition: set.c:4226
void SCIPsetSortSepas(SCIP_SET *set)
Definition: set.c:4270
SCIP_SEPA * SCIPsetFindSepa(SCIP_SET *set, const char *name)
Definition: set.c:4250
internal methods for global SCIP settings
datastructures for block memory pools and memory buffers
SCIP main data structure.
datastructures for global SCIP settings
int SCIPtreeGetCurrentDepth(SCIP_TREE *tree)
Definition: tree.c:8503
internal methods for branch and bound tree
@ SCIP_INVALIDDATA
Definition: type_retcode.h:52
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
struct SCIP_SepaData SCIP_SEPADATA
Definition: type_sepa.h:52
#define SCIP_DECL_SEPAINITSOL(x)
Definition: type_sepa.h:96
#define SCIP_DECL_SEPAEXECSOL(x)
Definition: type_sepa.h:166
#define SCIP_DECL_SEPAEXECLP(x)
Definition: type_sepa.h:136
#define SCIP_DECL_SEPAFREE(x)
Definition: type_sepa.h:69
#define SCIP_DECL_SEPAEXITSOL(x)
Definition: type_sepa.h:107
#define SCIP_DECL_SEPAEXIT(x)
Definition: type_sepa.h:85
#define SCIP_DECL_SEPACOPY(x)
Definition: type_sepa.h:61
#define SCIP_DECL_SEPAINIT(x)
Definition: type_sepa.h:77