Scippy

SCIP

Solving Constraint Integer Programs

scip_presol.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-2019 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 scip_presol.c
17  * @brief public methods for presolving plugins
18  * @author Tobias Achterberg
19  * @author Timo Berthold
20  * @author Gerald Gamrath
21  * @author Robert Lion Gottwald
22  * @author Stefan Heinz
23  * @author Gregor Hendel
24  * @author Thorsten Koch
25  * @author Alexander Martin
26  * @author Marc Pfetsch
27  * @author Michael Winkler
28  * @author Kati Wolter
29  *
30  * @todo check all SCIP_STAGE_* switches, and include the new stages TRANSFORMED and INITSOLVE
31  */
32 
33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34 
35 #include <ctype.h>
36 #include <stdarg.h>
37 #include <assert.h>
38 #include <string.h>
39 #if defined(_WIN32) || defined(_WIN64)
40 #else
41 #include <strings.h> /*lint --e{766}*/
42 #endif
43 
44 
45 #include "lpi/lpi.h"
46 #include "nlpi/exprinterpret.h"
47 #include "nlpi/nlpi.h"
48 #include "scip/benders.h"
49 #include "scip/benderscut.h"
50 #include "scip/branch.h"
51 #include "scip/branch_nodereopt.h"
52 #include "scip/clock.h"
53 #include "scip/compr.h"
54 #include "scip/concsolver.h"
55 #include "scip/concurrent.h"
56 #include "scip/conflict.h"
57 #include "scip/conflictstore.h"
58 #include "scip/cons.h"
59 #include "scip/cons_linear.h"
60 #include "scip/cutpool.h"
61 #include "scip/cuts.h"
62 #include "scip/debug.h"
63 #include "scip/def.h"
64 #include "scip/dialog.h"
65 #include "scip/dialog_default.h"
66 #include "scip/disp.h"
67 #include "scip/event.h"
68 #include "scip/heur.h"
69 #include "scip/heur_ofins.h"
70 #include "scip/heur_reoptsols.h"
72 #include "scip/heuristics.h"
73 #include "scip/history.h"
74 #include "scip/implics.h"
75 #include "scip/interrupt.h"
76 #include "scip/lp.h"
77 #include "scip/mem.h"
78 #include "scip/message_default.h"
79 #include "scip/misc.h"
80 #include "scip/nlp.h"
81 #include "scip/nodesel.h"
82 #include "scip/paramset.h"
83 #include "scip/presol.h"
84 #include "scip/presolve.h"
85 #include "scip/pricer.h"
86 #include "scip/pricestore.h"
87 #include "scip/primal.h"
88 #include "scip/prob.h"
89 #include "scip/prop.h"
90 #include "scip/reader.h"
91 #include "scip/relax.h"
92 #include "scip/reopt.h"
93 #include "scip/retcode.h"
94 #include "scip/scipbuildflags.h"
95 #include "scip/scipcoreplugins.h"
96 #include "scip/scipgithash.h"
97 #include "scip/sepa.h"
98 #include "scip/sepastore.h"
99 #include "scip/set.h"
100 #include "scip/sol.h"
101 #include "scip/solve.h"
102 #include "scip/stat.h"
103 #include "scip/syncstore.h"
104 #include "scip/table.h"
105 #include "scip/tree.h"
106 #include "scip/var.h"
107 #include "scip/visual.h"
108 #include "xml/xml.h"
109 
110 #include "scip/scip_presol.h"
111 
112 #include "scip/pub_message.h"
113 
114 
115 /* In debug mode, we include the SCIP's structure in scip.c, such that no one can access
116  * this structure except the interface methods in scip.c.
117  * In optimized mode, the structure is included in scip.h, because some of the methods
118  * are implemented as defines for performance reasons (e.g. the numerical comparisons)
119  */
120 #ifndef NDEBUG
121 #include "scip/struct_scip.h"
122 #endif
123 
124 /** creates a presolver and includes it in SCIP.
125  *
126  * @note method has all presolver callbacks as arguments and is thus changed every time a new
127  * callback is added
128  * in future releases; consider using SCIPincludePresolBasic() and setter functions
129  * if you seek for a method which is less likely to change in future releases
130  */
132  SCIP* scip, /**< SCIP data structure */
133  const char* name, /**< name of presolver */
134  const char* desc, /**< description of presolver */
135  int priority, /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
136  int maxrounds, /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
137  SCIP_PRESOLTIMING timing, /**< timing mask of the presolver */
138  SCIP_DECL_PRESOLCOPY ((*presolcopy)), /**< copy method of presolver or NULL if you don't want to copy your plugin into sub-SCIPs */
139  SCIP_DECL_PRESOLFREE ((*presolfree)), /**< destructor of presolver to free user data (called when SCIP is exiting) */
140  SCIP_DECL_PRESOLINIT ((*presolinit)), /**< initialization method of presolver (called after problem was transformed) */
141  SCIP_DECL_PRESOLEXIT ((*presolexit)), /**< deinitialization method of presolver (called before transformed problem is freed) */
142  SCIP_DECL_PRESOLINITPRE((*presolinitpre)),/**< presolving initialization method of presolver (called when presolving is about to begin) */
143  SCIP_DECL_PRESOLEXITPRE((*presolexitpre)),/**< presolving deinitialization method of presolver (called after presolving has been finished) */
144  SCIP_DECL_PRESOLEXEC ((*presolexec)), /**< execution method of presolver */
145  SCIP_PRESOLDATA* presoldata /**< presolver data */
146  )
147 {
148  SCIP_PRESOL* presol;
149 
150  SCIP_CALL( SCIPcheckStage(scip, "SCIPincludePresol", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
151 
152  /* check whether presolver is already present */
153  if( SCIPfindPresol(scip, name) != NULL )
154  {
155  SCIPerrorMessage("presolver <%s> already included.\n", name);
156  return SCIP_INVALIDDATA;
157  }
158 
159  SCIP_CALL( SCIPpresolCreate(&presol, scip->set, scip->messagehdlr, scip->mem->setmem, name, desc, priority,
160  maxrounds, timing, presolcopy,
161  presolfree, presolinit, presolexit, presolinitpre, presolexitpre, presolexec, presoldata) );
162  SCIP_CALL( SCIPsetIncludePresol(scip->set, presol) );
163 
164  return SCIP_OKAY;
165 }
166 
167 /** creates a presolver and includes it in SCIP with its fundamental callback. All non-fundamental (or optional)
168  * callbacks as, e.g., init and exit callbacks, will be set to NULL. Optional callbacks can be set via specific setter
169  * functions. These are SCIPsetPresolCopy(), SCIPsetPresolFree(), SCIPsetPresolInit(), SCIPsetPresolExit(),
170  * SCIPsetPresolInitpre(), and SCIPsetPresolExitPre().
171  *
172  * @note if you want to set all callbacks with a single method call, consider using SCIPincludePresol() instead
173  */
175  SCIP* scip, /**< SCIP data structure */
176  SCIP_PRESOL** presolptr, /**< reference to presolver, or NULL */
177  const char* name, /**< name of presolver */
178  const char* desc, /**< description of presolver */
179  int priority, /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
180  int maxrounds, /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
181  SCIP_PRESOLTIMING timing, /**< timing mask of the presolver */
182  SCIP_DECL_PRESOLEXEC ((*presolexec)), /**< execution method of presolver */
183  SCIP_PRESOLDATA* presoldata /**< presolver data */
184  )
185 {
186  SCIP_PRESOL* presol;
187 
188  SCIP_CALL( SCIPcheckStage(scip, "SCIPincludePresolBasic", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
189 
190  /* check whether presolver is already present */
191  if( SCIPfindPresol(scip, name) != NULL )
192  {
193  SCIPerrorMessage("presolver <%s> already included.\n", name);
194  return SCIP_INVALIDDATA;
195  }
196 
197  SCIP_CALL( SCIPpresolCreate(&presol, scip->set, scip->messagehdlr, scip->mem->setmem, name, desc, priority, maxrounds, timing,
198  NULL,
199  NULL, NULL, NULL, NULL, NULL, presolexec, presoldata) );
200  SCIP_CALL( SCIPsetIncludePresol(scip->set, presol) );
201 
202  if( presolptr != NULL )
203  *presolptr = presol;
204 
205  return SCIP_OKAY;
206 }
207 
208 /** sets copy method of presolver */
210  SCIP* scip, /**< SCIP data structure */
211  SCIP_PRESOL* presol, /**< presolver */
212  SCIP_DECL_PRESOLCOPY ((*presolcopy)) /**< copy method of presolver or NULL if you don't want to copy your plugin into sub-SCIPs */
213  )
214 {
215  SCIP_CALL( SCIPcheckStage(scip, "SCIPsetPresolCopy", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
216 
217  assert(presol != NULL);
218 
219  SCIPpresolSetCopy(presol, presolcopy);
220 
221  return SCIP_OKAY;
222 }
223 
224 /** sets destructor method of presolver */
226  SCIP* scip, /**< SCIP data structure */
227  SCIP_PRESOL* presol, /**< presolver */
228  SCIP_DECL_PRESOLFREE ((*presolfree)) /**< destructor of presolver */
229  )
230 {
231  SCIP_CALL( SCIPcheckStage(scip, "SCIPsetPresolFree", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
232 
233  assert(presol != NULL);
234 
235  SCIPpresolSetFree(presol, presolfree);
236 
237  return SCIP_OKAY;
238 }
239 
240 /** sets initialization method of presolver */
242  SCIP* scip, /**< SCIP data structure */
243  SCIP_PRESOL* presol, /**< presolver */
244  SCIP_DECL_PRESOLINIT ((*presolinit)) /**< initialize presolver */
245  )
246 {
247  SCIP_CALL( SCIPcheckStage(scip, "SCIPsetPresolInit", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
248 
249  assert(presol != NULL);
250 
251  SCIPpresolSetInit(presol, presolinit);
252 
253  return SCIP_OKAY;
254 }
255 
256 /** sets deinitialization method of presolver */
258  SCIP* scip, /**< SCIP data structure */
259  SCIP_PRESOL* presol, /**< presolver */
260  SCIP_DECL_PRESOLEXIT ((*presolexit)) /**< deinitialize presolver */
261  )
262 {
263  SCIP_CALL( SCIPcheckStage(scip, "SCIPsetPresolExit", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
264 
265  assert(presol != NULL);
266 
267  SCIPpresolSetExit(presol, presolexit);
268 
269  return SCIP_OKAY;
270 }
271 
272 /** sets solving process initialization method of presolver */
274  SCIP* scip, /**< SCIP data structure */
275  SCIP_PRESOL* presol, /**< presolver */
276  SCIP_DECL_PRESOLINITPRE ((*presolinitpre))/**< solving process initialization method of presolver */
277  )
278 {
279  SCIP_CALL( SCIPcheckStage(scip, "SCIPsetPresolInitpre", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
280 
281  assert(presol != NULL);
282 
283  SCIPpresolSetInitpre(presol, presolinitpre);
284 
285  return SCIP_OKAY;
286 }
287 
288 /** sets solving process deinitialization method of presolver */
290  SCIP* scip, /**< SCIP data structure */
291  SCIP_PRESOL* presol, /**< presolver */
292  SCIP_DECL_PRESOLEXITPRE ((*presolexitpre))/**< solving process deinitialization method of presolver */
293  )
294 {
295  SCIP_CALL( SCIPcheckStage(scip, "SCIPsetPresolExitpre", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
296 
297  assert(presol != NULL);
298 
299  SCIPpresolSetExitpre(presol, presolexitpre);
300 
301  return SCIP_OKAY;
302 }
303 
304 /** returns the presolver of the given name, or NULL if not existing */
306  SCIP* scip, /**< SCIP data structure */
307  const char* name /**< name of presolver */
308  )
309 {
310  assert(scip != NULL);
311  assert(scip->set != NULL);
312  assert(name != NULL);
313 
314  return SCIPsetFindPresol(scip->set, name);
315 }
316 
317 /** returns the array of currently available presolvers */
319  SCIP* scip /**< SCIP data structure */
320  )
321 {
322  assert(scip != NULL);
323  assert(scip->set != NULL);
324 
325  SCIPsetSortPresols(scip->set);
326 
327  return scip->set->presols;
328 }
329 
330 /** returns the number of currently available presolvers */
332  SCIP* scip /**< SCIP data structure */
333  )
334 {
335  assert(scip != NULL);
336  assert(scip->set != NULL);
337 
338  return scip->set->npresols;
339 }
340 
341 /** sets the priority of a presolver */
343  SCIP* scip, /**< SCIP data structure */
344  SCIP_PRESOL* presol, /**< presolver */
345  int priority /**< new priority of the presolver */
346  )
347 {
348  assert(scip != NULL);
349  assert(scip->set != NULL);
350 
351  SCIPpresolSetPriority(presol, scip->set, priority);
352 
353  return SCIP_OKAY;
354 }
SCIP_RETCODE SCIPsetIncludePresol(SCIP_SET *set, SCIP_PRESOL *presol)
Definition: set.c:3974
internal methods for separators
SCIP_RETCODE SCIPincludePresolBasic(SCIP *scip, SCIP_PRESOL **presolptr, const char *name, const char *desc, int priority, int maxrounds, SCIP_PRESOLTIMING timing, SCIP_DECL_PRESOLEXEC((*presolexec)), SCIP_PRESOLDATA *presoldata)
Definition: scip_presol.c:174
struct SCIP_PresolData SCIP_PRESOLDATA
Definition: type_presol.h:37
#define NULL
Definition: def.h:246
internal methods for managing events
default message handler
trivialnegation primal heuristic
internal methods for storing primal CIP solutions
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
Definition: scip_presol.c:225
methods to interpret (evaluate) an expression tree "fast"
internal methods for branch and bound tree
SCIP_RETCODE SCIPsetPresolExit(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLEXIT((*presolexit)))
Definition: scip_presol.c:257
methods for implications, variable bounds, and cliques
internal methods for clocks and timing issues
internal methods for NLPI solver interfaces
void SCIPpresolSetPriority(SCIP_PRESOL *presol, SCIP_SET *set, int priority)
Definition: presol.c:629
#define SCIP_DECL_PRESOLINITPRE(x)
Definition: type_presol.h:84
interface methods for specific LP solvers
internal methods for displaying statistics tables
#define FALSE
Definition: def.h:72
#define SCIP_DECL_PRESOLCOPY(x)
Definition: type_presol.h:46
public methods for presolving plugins
methods for the aggregation rows
internal methods for Benders&#39; decomposition
#define TRUE
Definition: def.h:71
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_PRESOL * SCIPsetFindPresol(SCIP_SET *set, const char *name)
Definition: set.c:3997
methods commonly used by primal heuristics
internal methods for branching rules and branching candidate storage
datastructures for concurrent solvers
internal methods for handling parameter settings
int SCIPgetNPresols(SCIP *scip)
Definition: scip_presol.c:331
SCIP_PRESOL ** presols
Definition: struct_set.h:75
methods for creating output for visualization tools (VBC, BAK)
nodereopt branching rule
internal methods for LP management
internal methods for branching and inference history
internal methods for collecting primal CIP solutions and primal informations
internal methods for propagators
SCIP_RETCODE SCIPpresolCreate(SCIP_PRESOL **presol, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int priority, int maxrounds, SCIP_PRESOLTIMING timing, SCIP_DECL_PRESOLCOPY((*presolcopy)), SCIP_DECL_PRESOLFREE((*presolfree)), SCIP_DECL_PRESOLINIT((*presolinit)), SCIP_DECL_PRESOLEXIT((*presolexit)), SCIP_DECL_PRESOLINITPRE((*presolinitpre)), SCIP_DECL_PRESOLEXITPRE((*presolexitpre)), SCIP_DECL_PRESOLEXEC((*presolexec)), SCIP_PRESOLDATA *presoldata)
Definition: presol.c:170
#define SCIP_DECL_PRESOLEXEC(x)
Definition: type_presol.h:153
SCIP_MEM * mem
Definition: struct_scip.h:61
git hash methods
internal methods for storing and manipulating the main problem
#define SCIPerrorMessage
Definition: pub_message.h:45
#define SCIP_DECL_PRESOLFREE(x)
Definition: type_presol.h:54
methods for block memory pools and memory buffers
#define SCIP_DECL_PRESOLEXIT(x)
Definition: type_presol.h:70
register additional core functionality that is designed as plugins
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:2010
internal methods for presolvers
SCIP_RETCODE SCIPsetPresolInit(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLINIT((*presolinit)))
Definition: scip_presol.c:241
internal methods for NLP management
SCIP_PRESOL * SCIPfindPresol(SCIP *scip, const char *name)
Definition: scip_presol.c:305
SCIP_RETCODE SCIPincludePresol(SCIP *scip, const char *name, const char *desc, int priority, int maxrounds, SCIP_PRESOLTIMING timing, SCIP_DECL_PRESOLCOPY((*presolcopy)), SCIP_DECL_PRESOLFREE((*presolfree)), SCIP_DECL_PRESOLINIT((*presolinit)), SCIP_DECL_PRESOLEXIT((*presolexit)), SCIP_DECL_PRESOLINITPRE((*presolinitpre)), SCIP_DECL_PRESOLEXITPRE((*presolexitpre)), SCIP_DECL_PRESOLEXEC((*presolexec)), SCIP_PRESOLDATA *presoldata)
Definition: scip_presol.c:131
internal miscellaneous methods
SCIP_RETCODE SCIPsetPresolPriority(SCIP *scip, SCIP_PRESOL *presol, int priority)
Definition: scip_presol.c:342
internal methods for node selectors and node priority queues
internal methods for variable pricers
internal methods for global SCIP settings
internal methods for storing conflicts
#define SCIP_CALL(x)
Definition: def.h:358
unsigned int SCIP_PRESOLTIMING
Definition: type_timing.h:52
SCIP main data structure.
BMS_BLKMEM * setmem
Definition: struct_mem.h:39
internal methods for storing priced variables
internal methods for relaxators
void SCIPpresolSetInitpre(SCIP_PRESOL *presol, SCIP_DECL_PRESOLINITPRE((*presolinitpre)))
Definition: presol.c:567
internal methods for storing separated cuts
SCIP_RETCODE SCIPsetPresolInitpre(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLINITPRE((*presolinitpre)))
Definition: scip_presol.c:273
methods commonly used for presolving
methods for catching the user CTRL-C interrupt
internal methods for problem variables
data structures and methods for collecting reoptimization information
the function declarations for the synchronization store
internal methods for user interface dialog
#define SCIP_DECL_PRESOLEXITPRE(x)
Definition: type_presol.h:102
void SCIPpresolSetFree(SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
Definition: presol.c:534
internal methods for input file readers
#define SCIP_DECL_PRESOLINIT(x)
Definition: type_presol.h:62
methods for debugging
void SCIPpresolSetInit(SCIP_PRESOL *presol, SCIP_DECL_PRESOLINIT((*presolinit)))
Definition: presol.c:545
reoptsols primal heuristic
internal methods for storing cuts in a cut pool
void SCIPpresolSetExit(SCIP_PRESOL *presol, SCIP_DECL_PRESOLEXIT((*presolexit)))
Definition: presol.c:556
Constraint handler for linear constraints in their most general form, .
helper functions for concurrent scip solvers
internal methods for return codes for SCIP methods
SCIP_PRESOL ** SCIPgetPresols(SCIP *scip)
Definition: scip_presol.c:318
internal methods for conflict analysis
void SCIPsetSortPresols(SCIP_SET *set)
Definition: set.c:4017
internal methods for tree compressions
internal methods for main solving loop and node processing
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip_presol.c:209
SCIP_SET * set
Definition: struct_scip.h:62
public methods for message output
void SCIPpresolSetCopy(SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: presol.c:523
SCIP_MESSAGEHDLR * messagehdlr
Definition: struct_scip.h:65
default user interface dialog
internal methods for problem statistics
internal methods for constraints and constraint handlers
declarations for XML parsing
build flags methods
common defines and data types used in all packages of SCIP
internal methods for primal heuristics
int npresols
Definition: struct_set.h:106
internal methods for Benders&#39; decomposition cuts
SCIP_RETCODE SCIPsetPresolExitpre(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLEXITPRE((*presolexitpre)))
Definition: scip_presol.c:289
internal methods for displaying runtime statistics
void SCIPpresolSetExitpre(SCIP_PRESOL *presol, SCIP_DECL_PRESOLEXITPRE((*presolexitpre)))
Definition: presol.c:578
OFINS - Objective Function Induced Neighborhood Search - a primal heuristic for reoptimization.