1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 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_solve.c
17 * @ingroup OTHER_CFILES
18 * @brief public solving methods
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 "blockmemshell/memory.h"
37 #include "scip/branch.h"
38 #include "scip/clock.h"
39 #include "scip/compr.h"
40 #include "scip/concsolver.h"
41 #include "scip/concurrent.h"
42 #include "scip/conflict.h"
43 #include "scip/conflictstore.h"
44 #include "scip/cons.h"
45 #include "scip/cutpool.h"
46 #include "scip/dcmp.h"
47 #include "scip/debug.h"
48 #include "scip/event.h"
49 #include "scip/implics.h"
50 #include "scip/interrupt.h"
51 #include "scip/lp.h"
52 #include "scip/nlp.h"
53 #include "scip/presol.h"
54 #include "scip/pricestore.h"
55 #include "scip/primal.h"
56 #include "scip/prob.h"
57 #include "scip/prop.h"
58 #include "scip/pub_branch.h"
59 #include "scip/pub_compr.h"
60 #include "scip/pub_cons.h"
61 #include "scip/pub_heur.h"
62 #include "scip/pub_message.h"
63 #include "scip/pub_misc.h"
64 #include "scip/pub_misc_select.h"
65 #include "scip/pub_presol.h"
66 #include "scip/pub_prop.h"
67 #include "scip/pub_sol.h"
68 #include "scip/pub_var.h"
69 #include "scip/relax.h"
70 #include "scip/reopt.h"
71 #include "scip/scip_benders.h"
72 #include "scip/scip_branch.h"
73 #include "scip/scip_concurrent.h"
74 #include "scip/scip_cons.h"
75 #include "scip/scip_general.h"
76 #include "scip/scip_mem.h"
77 #include "scip/scip_message.h"
78 #include "scip/scip_numerics.h"
79 #include "scip/scip_param.h"
80 #include "scip/scip_prob.h"
81 #include "scip/scip_randnumgen.h"
82 #include "scip/scip_sol.h"
83 #include "scip/scip_solve.h"
84 #include "scip/scip_solvingstats.h"
85 #include "scip/scip_timing.h"
86 #include "scip/scip_tree.h"
87 #include "scip/scip_var.h"
88 #include "scip/sepastore.h"
89 #include "scip/set.h"
90 #include "scip/sol.h"
91 #include "scip/solve.h"
92 #include "scip/stat.h"
93 #include "scip/struct_event.h"
94 #include "scip/struct_mem.h"
95 #include "scip/struct_primal.h"
96 #include "scip/struct_prob.h"
97 #include "scip/struct_scip.h"
98 #include "scip/struct_set.h"
99 #include "scip/struct_stat.h"
100 #include "scip/struct_tree.h"
101 #include "scip/syncstore.h"
102 #include "scip/tree.h"
103 #include "scip/var.h"
104 #include "scip/visual.h"
105
106 /** checks solution for feasibility in original problem without adding it to the solution store; to improve the
107 * performance we use the following order when checking for violations:
108 *
109 * 1. variable bounds
110 * 2. constraint handlers with positive or zero priority that don't need constraints (e.g. integral constraint handler)
111 * 3. original constraints
112 * 4. constraint handlers with negative priority that don't need constraints (e.g. Benders' decomposition constraint handler)
113 */
114 static
checkSolOrig(SCIP * scip,SCIP_SOL * sol,SCIP_Bool * feasible,SCIP_Bool printreason,SCIP_Bool completely,SCIP_Bool checkbounds,SCIP_Bool checkintegrality,SCIP_Bool checklprows,SCIP_Bool checkmodifiable)115 SCIP_RETCODE checkSolOrig(
116 SCIP* scip, /**< SCIP data structure */
117 SCIP_SOL* sol, /**< primal CIP solution */
118 SCIP_Bool* feasible, /**< stores whether given solution is feasible */
119 SCIP_Bool printreason, /**< Should the reason for the violation be printed? */
120 SCIP_Bool completely, /**< Should all violations be checked? */
121 SCIP_Bool checkbounds, /**< Should the bounds of the variables be checked? */
122 SCIP_Bool checkintegrality, /**< Has integrality to be checked? */
123 SCIP_Bool checklprows, /**< Do constraints represented by rows in the current LP have to be checked? */
124 SCIP_Bool checkmodifiable /**< have modifiable constraint to be checked? */
125 )
126 {
127 SCIP_RESULT result;
128 int v;
129 int c;
130 int h;
131
132 assert(scip != NULL);
133 assert(sol != NULL);
134 assert(feasible != NULL);
135
136 SCIP_CALL( SCIPcheckStage(scip, "checkSolOrig", FALSE, TRUE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE) );
137
138 *feasible = TRUE;
139
140 SCIPsolResetViolations(sol);
141
142 if( !printreason )
143 completely = FALSE;
144
145 /* check bounds */
146 if( checkbounds )
147 {
148 for( v = 0; v < scip->origprob->nvars; ++v )
149 {
150 SCIP_VAR* var;
151 SCIP_Real solval;
152 SCIP_Real lb;
153 SCIP_Real ub;
154
155 var = scip->origprob->vars[v];
156 solval = SCIPsolGetVal(sol, scip->set, scip->stat, var);
157
158 lb = SCIPvarGetLbOriginal(var);
159 ub = SCIPvarGetUbOriginal(var);
160
161 SCIPupdateSolBoundViolation(scip, sol, lb - solval, SCIPrelDiff(lb, solval));
162 SCIPupdateSolBoundViolation(scip, sol, solval - ub, SCIPrelDiff(solval, ub));
163
164 if( SCIPsetIsFeasLT(scip->set, solval, lb) || SCIPsetIsFeasGT(scip->set, solval, ub) )
165 {
166 *feasible = FALSE;
167
168 if( printreason )
169 {
170 SCIPmessagePrintInfo(scip->messagehdlr, "solution violates original bounds of variable <%s> [%g,%g] solution value <%g>\n",
171 SCIPvarGetName(var), lb, ub, solval);
172 }
173
174 if( !completely )
175 return SCIP_OKAY;
176 }
177 }
178 }
179
180 /* call constraint handlers with positive or zero check priority that don't need constraints */
181 for( h = 0; h < scip->set->nconshdlrs; ++h )
182 {
183 if( SCIPconshdlrGetCheckPriority(scip->set->conshdlrs[h]) >= 0 )
184 {
185 if( !SCIPconshdlrNeedsCons(scip->set->conshdlrs[h]) )
186 {
187 SCIP_CALL( SCIPconshdlrCheck(scip->set->conshdlrs[h], scip->mem->probmem, scip->set, scip->stat, sol,
188 checkintegrality, checklprows, printreason, completely, &result) );
189
190 if( result != SCIP_FEASIBLE )
191 {
192 *feasible = FALSE;
193
194 if( !completely )
195 return SCIP_OKAY;
196 }
197 }
198 }
199 /* constraint handlers are sorted by priority, so we can break when reaching the first one with negative priority */
200 else
201 break;
202 }
203
204 /* check original constraints
205 *
206 * in general modifiable constraints can not be checked, because the variables to fulfill them might be missing in
207 * the original problem; however, if the solution comes from a heuristic during presolving modifiable constraints
208 * have to be checked;
209 */
210 for( c = 0; c < scip->origprob->nconss; ++c )
211 {
212 if( SCIPconsIsChecked(scip->origprob->conss[c]) && (checkmodifiable || !SCIPconsIsModifiable(scip->origprob->conss[c])) )
213 {
214 /* check solution */
215 SCIP_CALL( SCIPconsCheck(scip->origprob->conss[c], scip->set, sol,
216 checkintegrality, checklprows, printreason, &result) );
217
218 if( result != SCIP_FEASIBLE )
219 {
220 *feasible = FALSE;
221
222 if( !completely )
223 return SCIP_OKAY;
224 }
225 }
226 }
227
228 /* call constraint handlers with negative check priority that don't need constraints;
229 * continue with the first constraint handler with negative priority which caused us to break in the above loop */
230 for( ; h < scip->set->nconshdlrs; ++h )
231 {
232 assert(SCIPconshdlrGetCheckPriority(scip->set->conshdlrs[h]) < 0);
233 if( !SCIPconshdlrNeedsCons(scip->set->conshdlrs[h]) )
234 {
235 SCIP_CALL( SCIPconshdlrCheck(scip->set->conshdlrs[h], scip->mem->probmem, scip->set, scip->stat, sol,
236 checkintegrality, checklprows, printreason, completely, &result) );
237
238 if( result != SCIP_FEASIBLE )
239 {
240 *feasible = FALSE;
241
242 if( !completely )
243 return SCIP_OKAY;
244 }
245 }
246 }
247
248 return SCIP_OKAY;
249 }
250
251 /** calculates number of nonzeros in problem */
252 static
calcNonZeros(SCIP * scip,SCIP_Longint * nchecknonzeros,SCIP_Longint * nactivenonzeros,SCIP_Bool * approxchecknonzeros,SCIP_Bool * approxactivenonzeros)253 SCIP_RETCODE calcNonZeros(
254 SCIP* scip, /**< SCIP data structure */
255 SCIP_Longint* nchecknonzeros, /**< pointer to store number of non-zeros in all check constraints */
256 SCIP_Longint* nactivenonzeros, /**< pointer to store number of non-zeros in all active constraints */
257 SCIP_Bool* approxchecknonzeros,/**< pointer to store if the number of non-zeros in all check constraints
258 * is only a lowerbound
259 */
260 SCIP_Bool* approxactivenonzeros/**< pointer to store if the number of non-zeros in all active constraints
261 * is only a lowerbound
262 */
263 )
264 {
265 SCIP_CONS** conss;
266 SCIP_Bool success;
267 SCIP_Bool ischeck;
268 int nconss;
269 int nvars;
270 int c;
271 int h;
272
273 *nchecknonzeros = 0LL;
274 *nactivenonzeros = 0LL;
275 *approxchecknonzeros = FALSE;
276 *approxactivenonzeros = FALSE;
277
278 /* computes number of non-zeros over all active constraints */
279 for( h = scip->set->nconshdlrs - 1; h >= 0; --h )
280 {
281 nconss = SCIPconshdlrGetNActiveConss(scip->set->conshdlrs[h]);
282
283 if( nconss > 0 )
284 {
285 conss = SCIPconshdlrGetConss(scip->set->conshdlrs[h]);
286
287 /* calculate all active constraints */
288 for( c = nconss - 1; c >= 0; --c )
289 {
290 SCIP_CALL( SCIPconsGetNVars(conss[c], scip->set, &nvars, &success) );
291 ischeck = SCIPconsIsChecked(conss[c]);
292
293 if( !success )
294 {
295 *approxactivenonzeros = TRUE;
296 if( ischeck )
297 *approxchecknonzeros = TRUE;
298 }
299 else
300 {
301 *nactivenonzeros += nvars;
302 if( ischeck )
303 *nchecknonzeros += nvars;
304 }
305 }
306 }
307
308 /* add nonzeros on inactive check constraints */
309 nconss = SCIPconshdlrGetNCheckConss(scip->set->conshdlrs[h]);
310 if( nconss > 0 )
311 {
312 conss = SCIPconshdlrGetCheckConss(scip->set->conshdlrs[h]);
313
314 for( c = nconss - 1; c >= 0; --c )
315 {
316 if( !SCIPconsIsActive(conss[c]) )
317 {
318 SCIP_CALL( SCIPconsGetNVars(conss[c], scip->set, &nvars, &success) );
319
320 if( !success )
321 *approxchecknonzeros = TRUE;
322 else
323 *nchecknonzeros += nvars;
324 }
325 }
326 }
327 }
328
329 return SCIP_OKAY;
330 }
331
332
333 /** initializes solving data structures and transforms problem
334 *
335 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
336 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
337 *
338 * @pre This method can be called if @p scip is in one of the following stages:
339 * - \ref SCIP_STAGE_PROBLEM
340 * - \ref SCIP_STAGE_TRANSFORMED
341 * - \ref SCIP_STAGE_INITPRESOLVE
342 * - \ref SCIP_STAGE_PRESOLVING
343 * - \ref SCIP_STAGE_EXITPRESOLVE
344 * - \ref SCIP_STAGE_PRESOLVED
345 * - \ref SCIP_STAGE_INITSOLVE
346 * - \ref SCIP_STAGE_SOLVING
347 * - \ref SCIP_STAGE_SOLVED
348 * - \ref SCIP_STAGE_EXITSOLVE
349 * - \ref SCIP_STAGE_FREETRANS
350 * - \ref SCIP_STAGE_FREE
351 *
352 * @post When calling this method in the \ref SCIP_STAGE_PROBLEM stage, the \SCIP stage is changed to \ref
353 * SCIP_STAGE_TRANSFORMED; otherwise, the stage is not changed
354 *
355 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
356 */
SCIPtransformProb(SCIP * scip)357 SCIP_RETCODE SCIPtransformProb(
358 SCIP* scip /**< SCIP data structure */
359 )
360 {
361 SCIP_Longint oldnsolsfound;
362 int nfeassols;
363 int ncandsols;
364 int h;
365 int s;
366
367 SCIP_CALL( SCIPcheckStage(scip, "SCIPtransformProb", FALSE, TRUE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE) );
368
369 /* check, if the problem was already transformed */
370 if( scip->set->stage >= SCIP_STAGE_TRANSFORMED )
371 return SCIP_OKAY;
372
373 assert(scip->stat->status == SCIP_STATUS_UNKNOWN);
374
375 /* check, if a node selector exists */
376 if( SCIPsetGetNodesel(scip->set, scip->stat) == NULL )
377 {
378 SCIPerrorMessage("no node selector available\n");
379 return SCIP_PLUGINNOTFOUND;
380 }
381
382 /* call garbage collector on original problem and parameter settings memory spaces */
383 BMSgarbagecollectBlockMemory(scip->mem->setmem);
384 BMSgarbagecollectBlockMemory(scip->mem->probmem);
385
386 /* remember number of constraints */
387 SCIPprobMarkNConss(scip->origprob);
388
389 /* switch stage to TRANSFORMING */
390 scip->set->stage = SCIP_STAGE_TRANSFORMING;
391
392 /* mark statistics before solving */
393 SCIPstatMark(scip->stat);
394
395 /* init solve data structures */
396 SCIP_CALL( SCIPeventfilterCreate(&scip->eventfilter, scip->mem->probmem) );
397 SCIP_CALL( SCIPeventqueueCreate(&scip->eventqueue) );
398 SCIP_CALL( SCIPbranchcandCreate(&scip->branchcand) );
399 SCIP_CALL( SCIPlpCreate(&scip->lp, scip->set, scip->messagehdlr, scip->stat, SCIPprobGetName(scip->origprob)) );
400 SCIP_CALL( SCIPprimalCreate(&scip->primal) );
401 SCIP_CALL( SCIPtreeCreate(&scip->tree, scip->mem->probmem, scip->set, SCIPsetGetNodesel(scip->set, scip->stat)) );
402 SCIP_CALL( SCIPrelaxationCreate(&scip->relaxation, scip->mem->probmem, scip->set, scip->stat, scip->primal, scip->tree) );
403 SCIP_CALL( SCIPconflictCreate(&scip->conflict, scip->mem->probmem, scip->set) );
404 SCIP_CALL( SCIPcliquetableCreate(&scip->cliquetable, scip->set, scip->mem->probmem) );
405
406 /* copy problem in solve memory */
407 SCIP_CALL( SCIPprobTransform(scip->origprob, scip->mem->probmem, scip->set, scip->stat, scip->primal, scip->tree,
408 scip->reopt, scip->lp, scip->branchcand, scip->eventfilter, scip->eventqueue, scip->conflictstore,
409 &scip->transprob) );
410
411 /* switch stage to TRANSFORMED */
412 scip->set->stage = SCIP_STAGE_TRANSFORMED;
413
414 /* check, whether objective value is always integral by inspecting the problem, if it is the case adjust the
415 * cutoff bound if primal solution is already known
416 */
417 SCIP_CALL( SCIPprobCheckObjIntegral(scip->transprob, scip->origprob, scip->mem->probmem, scip->set, scip->stat, scip->primal,
418 scip->tree, scip->reopt, scip->lp, scip->eventfilter, scip->eventqueue) );
419
420 /* if possible, scale objective function such that it becomes integral with gcd 1 */
421 SCIP_CALL( SCIPprobScaleObj(scip->transprob, scip->origprob, scip->mem->probmem, scip->set, scip->stat, scip->primal,
422 scip->tree, scip->reopt, scip->lp, scip->eventfilter, scip->eventqueue) );
423
424 /* check solution of solution candidate storage */
425 nfeassols = 0;
426 ncandsols = scip->origprimal->nsols;
427 oldnsolsfound = 0;
428
429 /* update upper bound and cutoff bound due to objective limit in primal data */
430 SCIP_CALL( SCIPprimalUpdateObjlimit(scip->primal, scip->mem->probmem, scip->set, scip->stat, scip->eventfilter,
431 scip->eventqueue, scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp) );
432
433 if( !scip->set->reopt_enable && scip->set->nactivebenders == 0 )
434 {
435 oldnsolsfound = scip->primal->nsolsfound;
436 for( s = scip->origprimal->nsols - 1; s >= 0; --s )
437 {
438 SCIP_Bool feasible;
439 SCIP_SOL* sol;
440
441 sol = scip->origprimal->sols[s];
442
443 /* recompute objective function, since the objective might have changed in the meantime */
444 SCIPsolRecomputeObj(sol, scip->set, scip->stat, scip->origprob);
445
446 /* SCIPprimalTrySol() can only be called on transformed solutions; therefore check solutions in original problem
447 * including modifiable constraints
448 */
449 SCIP_CALL( checkSolOrig(scip, sol, &feasible,
450 (scip->set->disp_verblevel >= SCIP_VERBLEVEL_HIGH ? scip->set->misc_printreason : FALSE),
451 FALSE, TRUE, TRUE, TRUE, TRUE) );
452
453 if( feasible )
454 {
455 SCIP_Real abssolobj;
456
457 abssolobj = REALABS(SCIPsolGetObj(sol, scip->set, scip->transprob, scip->origprob));
458
459 /* we do not want to add solutions with objective value +infinity */
460 if( !SCIPisInfinity(scip, abssolobj) )
461 {
462 SCIP_SOL* bestsol = SCIPgetBestSol(scip);
463 SCIP_Bool stored;
464
465 /* add primal solution to solution storage by copying it */
466 SCIP_CALL( SCIPprimalAddSol(scip->primal, scip->mem->probmem, scip->set, scip->messagehdlr, scip->stat, scip->origprob, scip->transprob,
467 scip->tree, scip->reopt, scip->lp, scip->eventqueue, scip->eventfilter, sol, &stored) );
468
469 if( stored )
470 {
471 nfeassols++;
472
473 if( bestsol != SCIPgetBestSol(scip) )
474 SCIPstoreSolutionGap(scip);
475 }
476 }
477 }
478
479 SCIP_CALL( SCIPsolFree(&sol, scip->mem->probmem, scip->origprimal) );
480 scip->origprimal->nsols--;
481 }
482 }
483
484 assert(scip->origprimal->nsols == 0);
485
486 scip->stat->nexternalsolsfound += scip->primal->nsolsfound - oldnsolsfound;
487
488 if( nfeassols > 0 )
489 {
490 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH,
491 "%d/%d feasible solution%s given by solution candidate storage, new primal bound %.6e\n\n",
492 nfeassols, ncandsols, (nfeassols > 1 ? "s" : ""), SCIPgetSolOrigObj(scip, SCIPgetBestSol(scip)));
493 }
494 else if( ncandsols > 0 && !scip->set->reopt_enable )
495 {
496 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH,
497 "all %d solutions given by solution candidate storage are infeasible\n\n", ncandsols);
498 }
499
500 /* print transformed problem statistics */
501 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL,
502 "transformed problem has %d variables (%d bin, %d int, %d impl, %d cont) and %d constraints\n",
503 scip->transprob->nvars, scip->transprob->nbinvars, scip->transprob->nintvars, scip->transprob->nimplvars,
504 scip->transprob->ncontvars, scip->transprob->nconss);
505
506 for( h = 0; h < scip->set->nconshdlrs; ++h )
507 {
508 int nactiveconss;
509
510 nactiveconss = SCIPconshdlrGetNActiveConss(scip->set->conshdlrs[h]);
511 if( nactiveconss > 0 )
512 {
513 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL,
514 "%7d constraints of type <%s>\n", nactiveconss, SCIPconshdlrGetName(scip->set->conshdlrs[h]));
515 }
516 }
517 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL, "\n");
518
519 {
520 SCIP_Real maxnonzeros;
521 SCIP_Longint nchecknonzeros;
522 SCIP_Longint nactivenonzeros;
523 SCIP_Bool approxchecknonzeros;
524 SCIP_Bool approxactivenonzeros;
525
526 /* determine number of non-zeros */
527 maxnonzeros = (SCIP_Real)SCIPgetNConss(scip) * SCIPgetNVars(scip);
528 maxnonzeros = MAX(maxnonzeros, 1.0);
529 SCIP_CALL( calcNonZeros(scip, &nchecknonzeros, &nactivenonzeros, &approxchecknonzeros, &approxactivenonzeros) );
530 scip->stat->nnz = nactivenonzeros;
531 scip->stat->avgnnz = (SCIPgetNConss(scip) == 0 ? 0.0 : (SCIP_Real) nactivenonzeros / ((SCIP_Real) SCIPgetNConss(scip)));
532
533 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL,
534 "original problem has %s%" SCIP_LONGINT_FORMAT " active (%g%%) nonzeros and %s%" SCIP_LONGINT_FORMAT " (%g%%) check nonzeros\n",
535 approxactivenonzeros ? "more than " : "", nactivenonzeros, nactivenonzeros/maxnonzeros * 100,
536 approxchecknonzeros ? "more than " : "", nchecknonzeros, nchecknonzeros/maxnonzeros * 100);
537 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL, "\n");
538 }
539
540 /* call initialization methods of plugins */
541 SCIP_CALL( SCIPsetInitPlugins(scip->set, scip->mem->probmem, scip->stat) );
542
543 /* in case the permutation seed is different to 0, permute the transformed problem */
544 if( scip->set->random_permutationseed > 0 )
545 {
546 SCIP_Bool permuteconss;
547 SCIP_Bool permutevars;
548 int permutationseed;
549
550 permuteconss = scip->set->random_permuteconss;
551 permutevars = scip->set->random_permutevars;
552 permutationseed = scip->set->random_permutationseed;
553
554 SCIP_CALL( SCIPpermuteProb(scip, (unsigned int)permutationseed, permuteconss, permutevars, permutevars, permutevars, permutevars) );
555 }
556
557 if( scip->set->misc_estimexternmem )
558 {
559 if( scip->set->limit_memory < (SCIP_Real)SCIP_MEM_NOLIMIT )
560 {
561 SCIP_Longint memused = SCIPgetMemUsed(scip);
562
563 /* if the memory limit is set, we take 1% as the minimum external memory storage */
564 scip->stat->externmemestim = MAX(memused, (SCIP_Longint) (0.01 * scip->set->limit_memory * 1048576.0));
565 }
566 else
567 scip->stat->externmemestim = SCIPgetMemUsed(scip);
568 SCIPdebugMsg(scip, "external memory usage estimated to %" SCIP_LONGINT_FORMAT " byte\n", scip->stat->externmemestim);
569 }
570
571 return SCIP_OKAY;
572 }
573
574 /** initializes presolving */
575 static
initPresolve(SCIP * scip)576 SCIP_RETCODE initPresolve(
577 SCIP* scip /**< SCIP data structure */
578 )
579 {
580 #ifndef NDEBUG
581 size_t nusedbuffers;
582 size_t nusedcleanbuffers;
583 #endif
584
585 assert(scip != NULL);
586 assert(scip->mem != NULL);
587 assert(scip->set != NULL);
588 assert(scip->stat != NULL);
589 assert(scip->transprob != NULL);
590 assert(scip->set->stage == SCIP_STAGE_TRANSFORMED);
591
592 /* retransform all existing solutions to original problem space, because the transformed problem space may
593 * get modified in presolving and the solutions may become invalid for the transformed problem
594 */
595 SCIP_CALL( SCIPprimalRetransformSolutions(scip->primal, scip->mem->probmem, scip->set, scip->stat, scip->eventfilter,
596 scip->eventqueue, scip->origprob, scip->transprob, scip->tree, scip->reopt, scip->lp) );
597
598 /* reset statistics for presolving and current branch and bound run */
599 SCIPstatResetPresolving(scip->stat, scip->set, scip->transprob, scip->origprob);
600
601 /* increase number of branch and bound runs */
602 scip->stat->nruns++;
603
604 /* remember problem size of previous run */
605 scip->stat->prevrunnvars = scip->transprob->nvars;
606
607 /* switch stage to INITPRESOLVE */
608 scip->set->stage = SCIP_STAGE_INITPRESOLVE;
609
610 /* create temporary presolving root node */
611 SCIP_CALL( SCIPtreeCreatePresolvingRoot(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->messagehdlr,
612 scip->stat, scip->transprob, scip->origprob, scip->primal, scip->lp, scip->branchcand, scip->conflict,
613 scip->conflictstore, scip->eventfilter, scip->eventqueue, scip->cliquetable) );
614
615 /* GCG wants to perform presolving during the reading process of a file reader;
616 * hence the number of used buffers does not need to be zero, however, it should not
617 * change by calling SCIPsetInitprePlugins()
618 */
619 #ifndef NDEBUG
620 nusedbuffers = BMSgetNUsedBufferMemory(SCIPbuffer(scip));
621 nusedcleanbuffers = BMSgetNUsedBufferMemory(SCIPcleanbuffer(scip));
622 #endif
623
624 /* inform plugins that the presolving is abound to begin */
625 SCIP_CALL( SCIPsetInitprePlugins(scip->set, scip->mem->probmem, scip->stat) );
626 assert(BMSgetNUsedBufferMemory(SCIPbuffer(scip)) == nusedbuffers);
627 assert(BMSgetNUsedBufferMemory(SCIPcleanbuffer(scip)) == nusedcleanbuffers);
628
629 /* delete the variables from the problems that were marked to be deleted */
630 SCIP_CALL( SCIPprobPerformVarDeletions(scip->transprob, scip->mem->probmem, scip->set, scip->stat, scip->eventqueue, scip->cliquetable, scip->lp, scip->branchcand) );
631
632 /* switch stage to PRESOLVING */
633 scip->set->stage = SCIP_STAGE_PRESOLVING;
634
635 return SCIP_OKAY;
636 }
637
638 /** deinitializes presolving */
639 static
exitPresolve(SCIP * scip,SCIP_Bool solved,SCIP_Bool * infeasible)640 SCIP_RETCODE exitPresolve(
641 SCIP* scip, /**< SCIP data structure */
642 SCIP_Bool solved, /**< is problem already solved? */
643 SCIP_Bool* infeasible /**< pointer to store if the clique clean up detects an infeasibility */
644 )
645 {
646 #ifndef NDEBUG
647 size_t nusedbuffers;
648 size_t nusedcleanbuffers;
649 #endif
650
651 assert(scip != NULL);
652 assert(scip->mem != NULL);
653 assert(scip->set != NULL);
654 assert(scip->stat != NULL);
655 assert(scip->transprob != NULL);
656 assert(scip->set->stage == SCIP_STAGE_PRESOLVING);
657 assert(infeasible != NULL);
658
659 *infeasible = FALSE;
660
661 /* switch stage to EXITPRESOLVE */
662 scip->set->stage = SCIP_STAGE_EXITPRESOLVE;
663
664 if( !solved )
665 {
666 SCIP_VAR** vars;
667 int nvars;
668 int v;
669
670 /* flatten all variables */
671 vars = SCIPgetFixedVars(scip);
672 nvars = SCIPgetNFixedVars(scip);
673 assert(nvars == 0 || vars != NULL);
674
675 for( v = nvars - 1; v >= 0; --v )
676 {
677 SCIP_VAR* var;
678 #ifndef NDEBUG
679 SCIP_VAR** multvars;
680 int i;
681 #endif
682 var = vars[v]; /*lint !e613*/
683 assert(var != NULL);
684
685 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR )
686 {
687 /* flattens aggregation graph of multi-aggregated variable in order to avoid exponential recursion later-on */
688 SCIP_CALL( SCIPvarFlattenAggregationGraph(var, scip->mem->probmem, scip->set, scip->eventqueue) );
689
690 #ifndef NDEBUG
691 multvars = SCIPvarGetMultaggrVars(var);
692 for( i = SCIPvarGetMultaggrNVars(var) - 1; i >= 0; --i)
693 assert(SCIPvarGetStatus(multvars[i]) != SCIP_VARSTATUS_MULTAGGR);
694 #endif
695 }
696 }
697 }
698
699 /* exitPresolve() might be called during the reading process of a file reader;
700 * hence the number of used buffers does not need to be zero, however, it should not
701 * change by calling SCIPsetExitprePlugins() or SCIPprobExitPresolve()
702 */
703 #ifndef NDEBUG
704 nusedbuffers = BMSgetNUsedBufferMemory(SCIPbuffer(scip));
705 nusedcleanbuffers = BMSgetNUsedBufferMemory(SCIPcleanbuffer(scip));
706 #endif
707
708 /* inform plugins that the presolving is finished, and perform final modifications */
709 SCIP_CALL( SCIPsetExitprePlugins(scip->set, scip->mem->probmem, scip->stat) );
710 assert(BMSgetNUsedBufferMemory(SCIPbuffer(scip)) == nusedbuffers);
711 assert(BMSgetNUsedBufferMemory(SCIPcleanbuffer(scip)) == nusedcleanbuffers);
712
713 /* remove empty and single variable cliques from the clique table, and convert all two variable cliques
714 * into implications
715 * delete the variables from the problems that were marked to be deleted
716 */
717 if( !solved )
718 {
719 int nlocalbdchgs = 0;
720
721 SCIP_CALL( SCIPprobPerformVarDeletions(scip->transprob, scip->mem->probmem, scip->set, scip->stat, scip->eventqueue,
722 scip->cliquetable, scip->lp, scip->branchcand) );
723
724 SCIP_CALL( SCIPcliquetableCleanup(scip->cliquetable, scip->mem->probmem, scip->set, scip->stat, scip->transprob,
725 scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, &nlocalbdchgs,
726 infeasible) );
727
728 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL,
729 "clique table cleanup detected %d bound changes%s\n", nlocalbdchgs, *infeasible ? " and infeasibility" : "");
730 }
731
732 /* exit presolving */
733 SCIP_CALL( SCIPprobExitPresolve(scip->transprob, scip->set) );
734 assert(BMSgetNUsedBufferMemory(SCIPbuffer(scip)) == nusedbuffers);
735 assert(BMSgetNUsedBufferMemory(SCIPcleanbuffer(scip)) == nusedcleanbuffers);
736
737 if( !solved )
738 {
739 /* check, whether objective value is always integral by inspecting the problem, if it is the case adjust the
740 * cutoff bound if primal solution is already known
741 */
742 SCIP_CALL( SCIPprobCheckObjIntegral(scip->transprob, scip->origprob, scip->mem->probmem, scip->set, scip->stat, scip->primal,
743 scip->tree, scip->reopt, scip->lp, scip->eventfilter, scip->eventqueue) );
744
745 /* if possible, scale objective function such that it becomes integral with gcd 1 */
746 SCIP_CALL( SCIPprobScaleObj(scip->transprob, scip->origprob, scip->mem->probmem, scip->set, scip->stat, scip->primal,
747 scip->tree, scip->reopt, scip->lp, scip->eventfilter, scip->eventqueue) );
748
749 scip->stat->lastlowerbound = SCIPprobInternObjval(scip->transprob, scip->origprob, scip->set, scip->transprob->dualbound);
750
751 /* we need to update the primal dual integral here to update the last{upper/dual}bound values after a restart */
752 if( scip->set->misc_calcintegral )
753 {
754 SCIPstatUpdatePrimalDualIntegrals(scip->stat, scip->set, scip->transprob, scip->origprob, SCIPgetUpperbound(scip), SCIPgetLowerbound(scip) );
755 }
756 }
757
758 /* free temporary presolving root node */
759 SCIP_CALL( SCIPtreeFreePresolvingRoot(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->messagehdlr,
760 scip->stat, scip->transprob, scip->origprob, scip->primal, scip->lp, scip->branchcand, scip->conflict,
761 scip->conflictstore, scip->eventfilter, scip->eventqueue, scip->cliquetable) );
762
763 /* switch stage to PRESOLVED */
764 scip->set->stage = SCIP_STAGE_PRESOLVED;
765
766 return SCIP_OKAY;
767 }
768
769 /** applies one round of presolving with the given presolving timing
770 *
771 * This method will always be called with presoltiming fast first. It iterates over all presolvers, propagators, and
772 * constraint handlers and calls their presolving callbacks with timing fast. If enough reductions are found, it
773 * returns and the next presolving round will be started (again with timing fast). If the fast presolving does not
774 * find enough reductions, this methods calls itself recursively with presoltiming medium. Again, it calls the
775 * presolving callbacks of all presolvers, propagators, and constraint handlers with timing medium. If enough
776 * reductions are found, it returns and the next presolving round will be started (with timing fast). Otherwise, it is
777 * called recursively with presoltiming exhaustive. In exhaustive presolving, presolvers, propagators, and constraint
778 * handlers are called w.r.t. their priority, but this time, we stop as soon as enough reductions were found and do not
779 * necessarily call all presolving methods. If we stop, we return and another presolving round is started with timing
780 * fast.
781 *
782 * @todo check if we want to do the following (currently disabled):
783 * In order to avoid calling the same expensive presolving methods again and again (which is possibly ineffective
784 * for the current instance), we continue the loop for exhaustive presolving where we stopped it the last time. The
785 * {presol/prop/cons}start pointers are used to this end: they provide the plugins to start the loop with in the
786 * current presolving round (if we reach exhaustive presolving), and are updated in this case to the next ones to be
787 * called in the next round. In case we reach the end of the loop in exhaustive presolving, we call the method again
788 * with exhaustive timing, now starting with the first presolving steps in the loop until we reach the ones we started
789 * the last call with. This way, we won't stop until all exhaustive presolvers were called without finding enough
790 * reductions (in sum).
791 */
792 static
presolveRound(SCIP * scip,SCIP_PRESOLTIMING * timing,SCIP_Bool * unbounded,SCIP_Bool * infeasible,SCIP_Bool lastround,int * presolstart,int presolend,int * propstart,int propend,int * consstart,int consend)793 SCIP_RETCODE presolveRound(
794 SCIP* scip, /**< SCIP data structure */
795 SCIP_PRESOLTIMING* timing, /**< pointer to current presolving timing */
796 SCIP_Bool* unbounded, /**< pointer to store whether presolving detected unboundedness */
797 SCIP_Bool* infeasible, /**< pointer to store whether presolving detected infeasibility */
798 SCIP_Bool lastround, /**< is this the last presolving round due to a presolving round limit? */
799 int* presolstart, /**< pointer to get the presolver to start exhaustive presolving with in
800 * the current round and store the one to start with in the next round */
801 int presolend, /**< last presolver to treat in exhaustive presolving */
802 int* propstart, /**< pointer to get the propagator to start exhaustive presolving with in
803 * the current round and store the one to start with in the next round */
804 int propend, /**< last propagator to treat in exhaustive presolving */
805 int* consstart, /**< pointer to get the constraint handler to start exhaustive presolving with in
806 * the current round and store the one to start with in the next round */
807 int consend /**< last constraint handler to treat in exhaustive presolving */
808 )
809 {
810 SCIP_RESULT result;
811 SCIP_EVENT event;
812 SCIP_Bool aborted;
813 SCIP_Bool lastranpresol;
814 #if 0
815 int oldpresolstart = 0;
816 int oldpropstart = 0;
817 int oldconsstart = 0;
818 #endif
819 int priopresol;
820 int prioprop;
821 int i;
822 int j;
823 int k;
824 #ifndef NDEBUG
825 size_t nusedbuffers;
826 size_t nusedcleanbuffers;
827 #endif
828
829 assert(scip != NULL);
830 assert(scip->set != NULL);
831 assert(unbounded != NULL);
832 assert(infeasible != NULL);
833 assert(presolstart != NULL);
834 assert(propstart != NULL);
835 assert(consstart != NULL);
836
837 assert((presolend == scip->set->npresols && propend == scip->set->nprops && consend == scip->set->nconshdlrs)
838 || (*presolstart == 0 && *propstart == 0 && *consstart == 0));
839
840 *unbounded = FALSE;
841 *infeasible = FALSE;
842 aborted = FALSE;
843
844 assert( scip->set->propspresolsorted );
845
846 /* GCG wants to perform presolving during the reading process of a file reader;
847 * hence the number of used buffers does not need to be zero, however, it should not
848 * change by calling the presolving callbacks
849 */
850 #ifndef NDEBUG
851 nusedbuffers = BMSgetNUsedBufferMemory(SCIPbuffer(scip));
852 nusedcleanbuffers = BMSgetNUsedBufferMemory(SCIPcleanbuffer(scip));
853 #endif
854
855 if( *timing == SCIP_PRESOLTIMING_EXHAUSTIVE )
856 {
857 /* In exhaustive presolving, we continue the loop where we stopped last time to avoid calling the same
858 * (possibly ineffective) presolving step again and again. If we reach the end of the arrays of presolvers,
859 * propagators, and constraint handlers without having made enough reductions, we start again from the beginning
860 */
861 i = *presolstart;
862 j = *propstart;
863 k = *consstart;
864 #if 0
865 oldpresolstart = i;
866 oldpropstart = j;
867 oldconsstart = k;
868 #endif
869 if( i >= presolend && j >= propend && k >= consend )
870 return SCIP_OKAY;
871
872 if( i == 0 && j == 0 && k == 0 )
873 ++(scip->stat->npresolroundsext);
874 }
875 else
876 {
877 /* in fast and medium presolving, we always iterate over all presolvers, propagators, and constraint handlers */
878 assert(presolend == scip->set->npresols);
879 assert(propend == scip->set->nprops);
880 assert(consend == scip->set->nconshdlrs);
881
882 i = 0;
883 j = 0;
884 k = 0;
885
886 if( *timing == SCIP_PRESOLTIMING_FAST )
887 ++(scip->stat->npresolroundsfast);
888 if( *timing == SCIP_PRESOLTIMING_MEDIUM )
889 ++(scip->stat->npresolroundsmed);
890 }
891
892 SCIPdebugMsg(scip, "starting presolving round %d (%d/%d/%d), timing = %u\n",
893 scip->stat->npresolrounds, scip->stat->npresolroundsfast, scip->stat->npresolroundsmed,
894 scip->stat->npresolroundsext, *timing);
895
896 /* call included presolvers with nonnegative priority */
897 while( !(*unbounded) && !(*infeasible) && !aborted && (i < presolend || j < propend) )
898 {
899 if( i < presolend )
900 priopresol = SCIPpresolGetPriority(scip->set->presols[i]);
901 else
902 priopresol = -1;
903
904 if( j < propend )
905 prioprop = SCIPpropGetPresolPriority(scip->set->props_presol[j]);
906 else
907 prioprop = -1;
908
909 /* call next propagator */
910 if( prioprop >= priopresol )
911 {
912 /* only presolving methods which have non-negative priority will be called before constraint handlers */
913 if( prioprop < 0 )
914 break;
915
916 SCIPdebugMsg(scip, "executing presolving of propagator <%s>\n", SCIPpropGetName(scip->set->props_presol[j]));
917 SCIP_CALL( SCIPpropPresol(scip->set->props_presol[j], scip->set, *timing, scip->stat->npresolrounds,
918 &scip->stat->npresolfixedvars, &scip->stat->npresolaggrvars, &scip->stat->npresolchgvartypes,
919 &scip->stat->npresolchgbds, &scip->stat->npresoladdholes, &scip->stat->npresoldelconss,
920 &scip->stat->npresoladdconss, &scip->stat->npresolupgdconss, &scip->stat->npresolchgcoefs,
921 &scip->stat->npresolchgsides, &result) );
922 assert(BMSgetNUsedBufferMemory(SCIPbuffer(scip)) == nusedbuffers);
923 assert(BMSgetNUsedBufferMemory(SCIPcleanbuffer(scip)) == nusedcleanbuffers);
924
925 lastranpresol = FALSE;
926 ++j;
927 }
928 /* call next presolver */
929 else
930 {
931 /* only presolving methods which have non-negative priority will be called before constraint handlers */
932 if( priopresol < 0 )
933 break;
934
935 SCIPdebugMsg(scip, "executing presolver <%s>\n", SCIPpresolGetName(scip->set->presols[i]));
936 SCIP_CALL( SCIPpresolExec(scip->set->presols[i], scip->set, *timing, scip->stat->npresolrounds,
937 &scip->stat->npresolfixedvars, &scip->stat->npresolaggrvars, &scip->stat->npresolchgvartypes,
938 &scip->stat->npresolchgbds, &scip->stat->npresoladdholes, &scip->stat->npresoldelconss,
939 &scip->stat->npresoladdconss, &scip->stat->npresolupgdconss, &scip->stat->npresolchgcoefs,
940 &scip->stat->npresolchgsides, &result) );
941 assert(BMSgetNUsedBufferMemory(SCIPbuffer(scip)) == nusedbuffers);
942 assert(BMSgetNUsedBufferMemory(SCIPcleanbuffer(scip)) == nusedcleanbuffers);
943
944 lastranpresol = TRUE;
945 ++i;
946 }
947
948 if( result == SCIP_CUTOFF )
949 {
950 *infeasible = TRUE;
951
952 if( lastranpresol )
953 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL,
954 "presolver <%s> detected infeasibility\n", SCIPpresolGetName(scip->set->presols[i-1]));
955 else
956 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL,
957 "propagator <%s> detected infeasibility\n", SCIPpropGetName(scip->set->props_presol[j-1]));
958 }
959 else if( result == SCIP_UNBOUNDED )
960 {
961 *unbounded = TRUE;
962
963 if( lastranpresol )
964 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL,
965 "presolver <%s> detected unboundedness (or infeasibility)\n", SCIPpresolGetName(scip->set->presols[i-1]));
966 else
967 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL,
968 "propagator <%s> detected unboundedness (or infeasibility)\n", SCIPpropGetName(scip->set->props_presol[j-1]));
969 }
970
971 /* delete the variables from the problems that were marked to be deleted */
972 SCIP_CALL( SCIPprobPerformVarDeletions(scip->transprob, scip->mem->probmem, scip->set, scip->stat, scip->eventqueue, scip->cliquetable, scip->lp,
973 scip->branchcand) );
974
975 SCIPdebugMsg(scip, "presolving callback returned result <%d>\n", result);
976
977 /* if we work off the exhaustive presolvers, we stop immediately if a reduction was found */
978 if( (*timing == SCIP_PRESOLTIMING_EXHAUSTIVE) && !lastround && !SCIPisPresolveFinished(scip) )
979 {
980 assert(*consstart == 0);
981
982 if( lastranpresol )
983 {
984 *presolstart = i + 1;
985 *propstart = j;
986 }
987 else
988 {
989 *presolstart = i;
990 *propstart = j + 1;
991 }
992 aborted = TRUE;
993
994 break;
995 }
996 }
997
998 /* call presolve methods of constraint handlers */
999 while( k < consend && !(*unbounded) && !(*infeasible) && !aborted )
1000 {
1001 SCIPdebugMsg(scip, "executing presolve method of constraint handler <%s>\n",
1002 SCIPconshdlrGetName(scip->set->conshdlrs[k]));
1003 SCIP_CALL( SCIPconshdlrPresolve(scip->set->conshdlrs[k], scip->mem->probmem, scip->set, scip->stat,
1004 *timing, scip->stat->npresolrounds,
1005 &scip->stat->npresolfixedvars, &scip->stat->npresolaggrvars, &scip->stat->npresolchgvartypes,
1006 &scip->stat->npresolchgbds, &scip->stat->npresoladdholes, &scip->stat->npresoldelconss,
1007 &scip->stat->npresoladdconss, &scip->stat->npresolupgdconss, &scip->stat->npresolchgcoefs,
1008 &scip->stat->npresolchgsides, &result) );
1009 assert(BMSgetNUsedBufferMemory(SCIPbuffer(scip)) == nusedbuffers);
1010 assert(BMSgetNUsedBufferMemory(SCIPcleanbuffer(scip)) == nusedcleanbuffers);
1011
1012 ++k;
1013
1014 if( result == SCIP_CUTOFF )
1015 {
1016 *infeasible = TRUE;
1017 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL,
1018 "constraint handler <%s> detected infeasibility\n", SCIPconshdlrGetName(scip->set->conshdlrs[k-1]));
1019 }
1020 else if( result == SCIP_UNBOUNDED )
1021 {
1022 *unbounded = TRUE;
1023 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL,
1024 "constraint handler <%s> detected unboundedness (or infeasibility)\n",
1025 SCIPconshdlrGetName(scip->set->conshdlrs[k-1]));
1026 }
1027
1028 /* delete the variables from the problems that were marked to be deleted */
1029 SCIP_CALL( SCIPprobPerformVarDeletions(scip->transprob, scip->mem->probmem, scip->set, scip->stat, scip->eventqueue, scip->cliquetable, scip->lp,
1030 scip->branchcand) );
1031
1032 SCIPdebugMsg(scip, "presolving callback returned with result <%d>\n", result);
1033
1034 /* if we work off the exhaustive presolvers, we stop immediately if a reduction was found */
1035 if( (*timing == SCIP_PRESOLTIMING_EXHAUSTIVE) && !lastround && !SCIPisPresolveFinished(scip) )
1036 {
1037 *presolstart = i;
1038 *propstart = j;
1039 *consstart = k + 1;
1040 aborted = TRUE;
1041
1042 break;
1043 }
1044 }
1045
1046 assert( scip->set->propspresolsorted );
1047
1048 /* call included presolvers with negative priority */
1049 while( !(*unbounded) && !(*infeasible) && !aborted && (i < presolend || j < propend) )
1050 {
1051 if( i < scip->set->npresols )
1052 priopresol = SCIPpresolGetPriority(scip->set->presols[i]);
1053 else
1054 priopresol = -INT_MAX;
1055
1056 if( j < scip->set->nprops )
1057 prioprop = SCIPpropGetPresolPriority(scip->set->props_presol[j]);
1058 else
1059 prioprop = -INT_MAX;
1060
1061 /* choose presolving */
1062 if( prioprop >= priopresol )
1063 {
1064 assert(prioprop <= 0);
1065
1066 SCIPdebugMsg(scip, "executing presolving of propagator <%s>\n", SCIPpropGetName(scip->set->props_presol[j]));
1067 SCIP_CALL( SCIPpropPresol(scip->set->props_presol[j], scip->set, *timing, scip->stat->npresolrounds,
1068 &scip->stat->npresolfixedvars, &scip->stat->npresolaggrvars, &scip->stat->npresolchgvartypes,
1069 &scip->stat->npresolchgbds, &scip->stat->npresoladdholes, &scip->stat->npresoldelconss,
1070 &scip->stat->npresoladdconss, &scip->stat->npresolupgdconss, &scip->stat->npresolchgcoefs,
1071 &scip->stat->npresolchgsides, &result) );
1072 assert(BMSgetNUsedBufferMemory(SCIPbuffer(scip)) == nusedbuffers);
1073 assert(BMSgetNUsedBufferMemory(SCIPcleanbuffer(scip)) == nusedcleanbuffers);
1074
1075 lastranpresol = FALSE;
1076 ++j;
1077 }
1078 else
1079 {
1080 assert(priopresol < 0);
1081
1082 SCIPdebugMsg(scip, "executing presolver <%s>\n", SCIPpresolGetName(scip->set->presols[i]));
1083 SCIP_CALL( SCIPpresolExec(scip->set->presols[i], scip->set, *timing, scip->stat->npresolrounds,
1084 &scip->stat->npresolfixedvars, &scip->stat->npresolaggrvars, &scip->stat->npresolchgvartypes,
1085 &scip->stat->npresolchgbds, &scip->stat->npresoladdholes, &scip->stat->npresoldelconss,
1086 &scip->stat->npresoladdconss, &scip->stat->npresolupgdconss, &scip->stat->npresolchgcoefs,
1087 &scip->stat->npresolchgsides, &result) );
1088 assert(BMSgetNUsedBufferMemory(SCIPbuffer(scip)) == nusedbuffers);
1089 assert(BMSgetNUsedBufferMemory(SCIPcleanbuffer(scip)) == nusedcleanbuffers);
1090
1091 lastranpresol = TRUE;
1092 ++i;
1093 }
1094
1095 if( result == SCIP_CUTOFF )
1096 {
1097 *infeasible = TRUE;
1098
1099 if( lastranpresol )
1100 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL,
1101 "presolver <%s> detected infeasibility\n", SCIPpresolGetName(scip->set->presols[i-1]));
1102 else
1103 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL,
1104 "propagator <%s> detected infeasibility\n", SCIPpropGetName(scip->set->props_presol[j-1]));
1105 }
1106 else if( result == SCIP_UNBOUNDED )
1107 {
1108 *unbounded = TRUE;
1109
1110 if( lastranpresol )
1111 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL,
1112 "presolver <%s> detected unboundedness (or infeasibility)\n", SCIPpresolGetName(scip->set->presols[i-1]));
1113 else
1114 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL,
1115 "propagator <%s> detected unboundedness (or infeasibility)\n", SCIPpropGetName(scip->set->props_presol[j-1]));
1116 }
1117
1118 /* delete the variables from the problems that were marked to be deleted */
1119 SCIP_CALL( SCIPprobPerformVarDeletions(scip->transprob, scip->mem->probmem, scip->set, scip->stat, scip->eventqueue, scip->cliquetable, scip->lp,
1120 scip->branchcand) );
1121
1122 SCIPdebugMsg(scip, "presolving callback return with result <%d>\n", result);
1123
1124 /* if we work off the exhaustive presolvers, we stop immediately if a reduction was found */
1125 if( (*timing == SCIP_PRESOLTIMING_EXHAUSTIVE) && !lastround && !SCIPisPresolveFinished(scip) )
1126 {
1127 assert(k == consend);
1128
1129 if( lastranpresol )
1130 {
1131 *presolstart = i + 1;
1132 *propstart = j;
1133 }
1134 else
1135 {
1136 *presolstart = i;
1137 *propstart = j + 1;
1138 }
1139 *consstart = k;
1140
1141 break;
1142 }
1143 }
1144
1145 /* remove empty and single variable cliques from the clique table */
1146 if( !(*unbounded) && !(*infeasible) )
1147 {
1148 int nlocalbdchgs = 0;
1149
1150 SCIP_CALL( SCIPcliquetableCleanup(scip->cliquetable, scip->mem->probmem, scip->set, scip->stat, scip->transprob,
1151 scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, &nlocalbdchgs,
1152 infeasible) );
1153
1154 if( nlocalbdchgs > 0 || *infeasible )
1155 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL,
1156 "clique table cleanup detected %d bound changes%s\n", nlocalbdchgs, *infeasible ? " and infeasibility" : "");
1157
1158 scip->stat->npresolfixedvars += nlocalbdchgs;
1159
1160 if( !*infeasible && scip->set->nheurs > 0 )
1161 {
1162 /* call primal heuristics that are applicable during presolving */
1163 SCIP_Bool foundsol;
1164
1165 SCIPdebugMsg(scip, "calling primal heuristics during presolving\n");
1166
1167 /* call primal heuristics */
1168 SCIP_CALL( SCIPprimalHeuristics(scip->set, scip->stat, scip->transprob, scip->primal, NULL, NULL, NULL,
1169 SCIP_HEURTIMING_DURINGPRESOLLOOP, FALSE, &foundsol, unbounded) );
1170
1171 /* output a message, if a solution was found */
1172 if( foundsol )
1173 {
1174 SCIP_SOL* sol;
1175
1176 assert(SCIPgetNSols(scip) > 0);
1177 sol = SCIPgetBestSol(scip);
1178 assert(sol != NULL);
1179 assert(SCIPgetSolOrigObj(scip,sol) != SCIP_INVALID); /*lint !e777*/
1180
1181 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH,
1182 "feasible solution found by %s heuristic after %.1f seconds, objective value %.6e\n",
1183 SCIPheurGetName(SCIPsolGetHeur(sol)), SCIPgetSolvingTime(scip), SCIPgetSolOrigObj(scip, sol));
1184 }
1185 }
1186 }
1187
1188 if( !(*unbounded) && !(*infeasible) )
1189 {
1190 /* call more expensive presolvers */
1191 if( (SCIPisPresolveFinished(scip) || lastround) )
1192 {
1193 if( *timing != SCIP_PRESOLTIMING_FINAL )
1194 {
1195 assert((*timing == SCIP_PRESOLTIMING_FAST) || (*timing == SCIP_PRESOLTIMING_MEDIUM) || (*timing == SCIP_PRESOLTIMING_EXHAUSTIVE));
1196
1197 SCIPdebugMsg(scip, "not enough reductions in %s presolving, running %s presolving now...\n",
1198 *timing == SCIP_PRESOLTIMING_FAST ? "fast" : *timing == SCIP_PRESOLTIMING_MEDIUM ? "medium" : "exhaustive",
1199 *timing == SCIP_PRESOLTIMING_FAST ? "medium" : *timing == SCIP_PRESOLTIMING_MEDIUM ? "exhaustive" : "final");
1200
1201 /* increase timing */
1202 *timing = ((*timing == SCIP_PRESOLTIMING_FAST) ? SCIP_PRESOLTIMING_MEDIUM : (*timing == SCIP_PRESOLTIMING_MEDIUM) ? SCIP_PRESOLTIMING_EXHAUSTIVE : SCIP_PRESOLTIMING_FINAL);
1203
1204 /* computational experiments showed that always starting the loop of exhaustive presolvers from the beginning
1205 * performs better than continuing from the last processed presolver. Therefore, we start from 0, but keep
1206 * the mechanisms to possibly change this back later.
1207 * @todo try starting from the last processed exhaustive presolver
1208 */
1209 *presolstart = 0;
1210 *propstart = 0;
1211 *consstart = 0;
1212
1213 SCIP_CALL( presolveRound(scip, timing, unbounded, infeasible, lastround, presolstart, presolend,
1214 propstart, propend, consstart, consend) );
1215 }
1216 #if 0
1217 /* run remaining exhaustive presolvers (if we did not start from the beginning anyway) */
1218 else if( (oldpresolstart > 0 || oldpropstart > 0 || oldconsstart > 0) && presolend == scip->set->npresols
1219 && propend == scip->set->nprops && consend == scip->set->nconshdlrs )
1220 {
1221 int newpresolstart = 0;
1222 int newpropstart = 0;
1223 int newconsstart = 0;
1224
1225 SCIPdebugMsg(scip, "reached end of exhaustive presolving loop, starting from the beginning...\n");
1226
1227 SCIP_CALL( presolveRound(scip, timing, unbounded, infeasible, lastround, &newpresolstart,
1228 oldpresolstart, &newpropstart, oldpropstart, &newconsstart, oldconsstart) );
1229
1230 *presolstart = newpresolstart;
1231 *propstart = newpropstart;
1232 *consstart = newconsstart;
1233 }
1234 #endif
1235 }
1236 }
1237
1238 /* issue PRESOLVEROUND event */
1239 SCIP_CALL( SCIPeventChgType(&event, SCIP_EVENTTYPE_PRESOLVEROUND) );
1240 SCIP_CALL( SCIPeventProcess(&event, scip->set, NULL, NULL, NULL, scip->eventfilter) );
1241
1242 return SCIP_OKAY;
1243 }
1244
1245
1246 /** loops through the included presolvers and constraint's presolve methods, until changes are too few */
1247 static
presolve(SCIP * scip,SCIP_Bool * unbounded,SCIP_Bool * infeasible,SCIP_Bool * vanished)1248 SCIP_RETCODE presolve(
1249 SCIP* scip, /**< SCIP data structure */
1250 SCIP_Bool* unbounded, /**< pointer to store whether presolving detected unboundedness */
1251 SCIP_Bool* infeasible, /**< pointer to store whether presolving detected infeasibility */
1252 SCIP_Bool* vanished /**< pointer to store whether the problem vanished in presolving */
1253 )
1254 {
1255 SCIP_PRESOLTIMING presoltiming;
1256 SCIP_Bool finished;
1257 SCIP_Bool stopped;
1258 SCIP_Bool lastround;
1259 int presolstart = 0;
1260 int propstart = 0;
1261 int consstart = 0;
1262 #ifndef NDEBUG
1263 size_t nusedbuffers;
1264 size_t nusedcleanbuffers;
1265 #endif
1266
1267 assert(scip != NULL);
1268 assert(scip->mem != NULL);
1269 assert(scip->primal != NULL);
1270 assert(scip->set != NULL);
1271 assert(scip->stat != NULL);
1272 assert(scip->transprob != NULL);
1273 assert(scip->set->stage == SCIP_STAGE_TRANSFORMED || scip->set->stage == SCIP_STAGE_PRESOLVING);
1274 assert(unbounded != NULL);
1275 assert(infeasible != NULL);
1276
1277 *unbounded = FALSE;
1278 *vanished = FALSE;
1279
1280 /* GCG wants to perform presolving during the reading process of a file reader;
1281 * hence the number of used buffers does not need to be zero, however, it should
1282 * be the same again after presolve is finished
1283 */
1284 #ifndef NDEBUG
1285 nusedbuffers = BMSgetNUsedBufferMemory(SCIPbuffer(scip));
1286 nusedcleanbuffers = BMSgetNUsedBufferMemory(SCIPcleanbuffer(scip));
1287 #endif
1288
1289 /* switch status to unknown */
1290 scip->stat->status = SCIP_STATUS_UNKNOWN;
1291
1292 /* update upper bound and cutoff bound due to objective limit in primal data */
1293 SCIP_CALL( SCIPprimalUpdateObjlimit(scip->primal, scip->mem->probmem, scip->set, scip->stat, scip->eventfilter,
1294 scip->eventqueue, scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp) );
1295
1296 /* start presolving timer */
1297 SCIPclockStart(scip->stat->presolvingtime, scip->set);
1298 SCIPclockStart(scip->stat->presolvingtimeoverall, scip->set);
1299
1300 /* initialize presolving */
1301 if( scip->set->stage == SCIP_STAGE_TRANSFORMED )
1302 {
1303 SCIP_CALL( initPresolve(scip) );
1304 }
1305 assert(scip->set->stage == SCIP_STAGE_PRESOLVING);
1306
1307 /* call primal heuristics that are applicable before presolving */
1308 if( scip->set->nheurs > 0 )
1309 {
1310 SCIP_Bool foundsol;
1311
1312 SCIPdebugMsg(scip, "calling primal heuristics before presolving\n");
1313
1314 /* call primal heuristics */
1315 SCIP_CALL( SCIPprimalHeuristics(scip->set, scip->stat, scip->transprob, scip->primal, NULL, NULL, NULL,
1316 SCIP_HEURTIMING_BEFOREPRESOL, FALSE, &foundsol, unbounded) );
1317
1318 /* output a message, if a solution was found */
1319 if( foundsol )
1320 {
1321 SCIP_SOL* sol;
1322
1323 assert(SCIPgetNSols(scip) > 0);
1324 sol = SCIPgetBestSol(scip);
1325 assert(sol != NULL);
1326 assert(SCIPgetSolOrigObj(scip,sol) != SCIP_INVALID); /*lint !e777*/
1327
1328 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH,
1329 "feasible solution found by %s heuristic after %.1f seconds, objective value %.6e\n",
1330 SCIPheurGetName(SCIPsolGetHeur(sol)), SCIPgetSolvingTime(scip), SCIPgetSolOrigObj(scip, sol));
1331 }
1332 }
1333
1334 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH, "presolving:\n");
1335
1336 *infeasible = FALSE;
1337 *unbounded = (*unbounded) || (SCIPgetNSols(scip) > 0 && SCIPisInfinity(scip, -SCIPgetSolOrigObj(scip, SCIPgetBestSol(scip))));
1338
1339 finished = (scip->set->presol_maxrounds != -1 && scip->stat->npresolrounds >= scip->set->presol_maxrounds)
1340 || (*unbounded) || (scip->set->reopt_enable && scip->stat->nreoptruns >= 1);
1341 stopped = SCIPsolveIsStopped(scip->set, scip->stat, TRUE);
1342
1343 /* perform presolving rounds */
1344 while( !finished && !stopped )
1345 {
1346 /* store current number of reductions */
1347 scip->stat->lastnpresolfixedvars = scip->stat->npresolfixedvars;
1348 scip->stat->lastnpresolaggrvars = scip->stat->npresolaggrvars;
1349 scip->stat->lastnpresolchgvartypes = scip->stat->npresolchgvartypes;
1350 scip->stat->lastnpresolchgbds = scip->stat->npresolchgbds;
1351 scip->stat->lastnpresoladdholes = scip->stat->npresoladdholes;
1352 scip->stat->lastnpresoldelconss = scip->stat->npresoldelconss;
1353 scip->stat->lastnpresoladdconss = scip->stat->npresoladdconss;
1354 scip->stat->lastnpresolupgdconss = scip->stat->npresolupgdconss;
1355 scip->stat->lastnpresolchgcoefs = scip->stat->npresolchgcoefs;
1356 scip->stat->lastnpresolchgsides = scip->stat->npresolchgsides;
1357 #ifdef SCIP_DISABLED_CODE
1358 scip->stat->lastnpresolimplications = scip->stat->nimplications;
1359 scip->stat->lastnpresolcliques = SCIPcliquetableGetNCliques(scip->cliquetable);
1360 #endif
1361
1362 /* set presolving flag */
1363 scip->stat->performpresol = TRUE;
1364
1365 /* sort propagators */
1366 SCIPsetSortPropsPresol(scip->set);
1367
1368 /* sort presolvers by priority */
1369 SCIPsetSortPresols(scip->set);
1370
1371 /* check if this will be the last presolving round (in that case, we want to run all presolvers) */
1372 lastround = (scip->set->presol_maxrounds == -1 ? FALSE : (scip->stat->npresolrounds + 1 >= scip->set->presol_maxrounds));
1373
1374 presoltiming = SCIP_PRESOLTIMING_FAST;
1375
1376 /* perform the presolving round by calling the presolvers, propagators, and constraint handlers */
1377 assert(!(*unbounded));
1378 assert(!(*infeasible));
1379 SCIP_CALL( presolveRound(scip, &presoltiming, unbounded, infeasible, lastround,
1380 &presolstart, scip->set->npresols, &propstart, scip->set->nprops, &consstart, scip->set->nconshdlrs) );
1381
1382 /* check, if we should abort presolving due to not enough changes in the last round */
1383 finished = SCIPisPresolveFinished(scip) || presoltiming == SCIP_PRESOLTIMING_FINAL;
1384
1385 SCIPdebugMsg(scip, "presolving round %d returned with unbounded = %u, infeasible = %u, finished = %u\n", scip->stat->npresolrounds, *unbounded, *infeasible, finished);
1386
1387 /* check whether problem is infeasible or unbounded */
1388 finished = finished || *unbounded || *infeasible;
1389
1390 /* increase round number */
1391 scip->stat->npresolrounds++;
1392
1393 if( !finished )
1394 {
1395 /* print presolving statistics */
1396 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH,
1397 "(round %d, %-11s %d del vars, %d del conss, %d add conss, %d chg bounds, %d chg sides, %d chg coeffs, %d upgd conss, %d impls, %d clqs\n",
1398 scip->stat->npresolrounds, ( presoltiming == SCIP_PRESOLTIMING_FAST ? "fast)" :
1399 (presoltiming == SCIP_PRESOLTIMING_MEDIUM ? "medium)" :
1400 (presoltiming == SCIP_PRESOLTIMING_EXHAUSTIVE ?"exhaustive)" :
1401 "final)")) ),
1402 scip->stat->npresolfixedvars + scip->stat->npresolaggrvars,
1403 scip->stat->npresoldelconss, scip->stat->npresoladdconss,
1404 scip->stat->npresolchgbds, scip->stat->npresolchgsides,
1405 scip->stat->npresolchgcoefs, scip->stat->npresolupgdconss,
1406 scip->stat->nimplications, SCIPcliquetableGetNCliques(scip->cliquetable));
1407 }
1408
1409 /* abort if time limit was reached or user interrupted */
1410 stopped = SCIPsolveIsStopped(scip->set, scip->stat, TRUE);
1411 }
1412
1413 /* first change status of scip, so that all plugins in their exitpre callbacks can ask SCIP for the correct status */
1414 if( *infeasible )
1415 {
1416 /* switch status to OPTIMAL */
1417 if( scip->primal->nlimsolsfound > 0 )
1418 {
1419 scip->stat->status = SCIP_STATUS_OPTIMAL;
1420 }
1421 else /* switch status to INFEASIBLE */
1422 scip->stat->status = SCIP_STATUS_INFEASIBLE;
1423 }
1424 else if( *unbounded )
1425 {
1426 if( scip->primal->nsols >= 1 ) /* switch status to UNBOUNDED */
1427 scip->stat->status = SCIP_STATUS_UNBOUNDED;
1428 else /* switch status to INFORUNBD */
1429 scip->stat->status = SCIP_STATUS_INFORUNBD;
1430 }
1431 /* if no variables and constraints are present, we try to add the empty solution (constraint handlers with needscons
1432 * flag FALSE could theoretically reject it); if no active pricers could create variables later, we conclude
1433 * optimality or infeasibility */
1434 else if( scip->transprob->nvars == 0 && scip->transprob->nconss == 0 )
1435 {
1436 SCIP_SOL* sol;
1437 SCIP_Bool stored;
1438
1439 SCIP_CALL( SCIPcreateSol(scip, &sol, NULL) );
1440 SCIP_CALL( SCIPtrySolFree(scip, &sol, FALSE, FALSE, FALSE, FALSE, FALSE, &stored) );
1441
1442 if( scip->set->nactivepricers == 0 )
1443 {
1444 if( scip->primal->nlimsolsfound > 0 )
1445 scip->stat->status = SCIP_STATUS_OPTIMAL;
1446 else
1447 scip->stat->status = SCIP_STATUS_INFEASIBLE;
1448
1449 *vanished = TRUE;
1450 }
1451 }
1452
1453 /* deinitialize presolving */
1454 if( finished && (!stopped || *unbounded || *infeasible || *vanished) )
1455 {
1456 SCIP_Real maxnonzeros;
1457 SCIP_Longint nchecknonzeros;
1458 SCIP_Longint nactivenonzeros;
1459 SCIP_Bool approxchecknonzeros;
1460 SCIP_Bool approxactivenonzeros;
1461 SCIP_Bool infeas;
1462
1463 SCIP_CALL( exitPresolve(scip, *unbounded || *infeasible || *vanished, &infeas) );
1464 *infeasible = *infeasible || infeas;
1465
1466 assert(scip->set->stage == SCIP_STAGE_PRESOLVED);
1467
1468 /* resort variables if we are not already done (unless variable permutation was explicitly activated) */
1469 if( !scip->set->random_permutevars && !(*infeasible) && !(*unbounded) && !(*vanished) )
1470 {
1471 /* (Re)Sort the variables, which appear in the four categories (binary, integer, implicit, continuous) after
1472 * presolve with respect to their original index (within their categories). Adjust the problem index afterwards
1473 * which is supposed to reflect the position in the variable array. This additional (re)sorting is supposed to
1474 * get more robust against the order presolving fixed variables. (We also reobtain a possible block structure
1475 * induced by the user model)
1476 */
1477 SCIPprobResortVars(scip->transprob);
1478 }
1479
1480 /* determine number of non-zeros */
1481 maxnonzeros = (SCIP_Real)SCIPgetNConss(scip) * SCIPgetNVars(scip);
1482 maxnonzeros = MAX(maxnonzeros, 1.0);
1483 SCIP_CALL( calcNonZeros(scip, &nchecknonzeros, &nactivenonzeros, &approxchecknonzeros, &approxactivenonzeros) );
1484 scip->stat->nnz = nactivenonzeros;
1485
1486 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL, "\n");
1487 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL,
1488 "presolved problem has %s%" SCIP_LONGINT_FORMAT " active (%g%%) nonzeros and %s%" SCIP_LONGINT_FORMAT " (%g%%) check nonzeros\n",
1489 approxactivenonzeros ? "more than " : "", nactivenonzeros, nactivenonzeros/maxnonzeros * 100,
1490 approxchecknonzeros ? "more than " : "", nchecknonzeros, nchecknonzeros/maxnonzeros * 100);
1491 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL, "\n");
1492 }
1493 assert(BMSgetNUsedBufferMemory(SCIPbuffer(scip)) == nusedbuffers);
1494 assert(BMSgetNUsedBufferMemory(SCIPcleanbuffer(scip)) == nusedcleanbuffers);
1495
1496 /* stop presolving time */
1497 SCIPclockStop(scip->stat->presolvingtime, scip->set);
1498 SCIPclockStop(scip->stat->presolvingtimeoverall, scip->set);
1499
1500 /* print presolving statistics */
1501 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_NORMAL,
1502 "presolving (%d rounds: %d fast, %d medium, %d exhaustive):\n", scip->stat->npresolrounds,
1503 scip->stat->npresolroundsfast, scip->stat->npresolroundsmed, scip->stat->npresolroundsext);
1504 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_NORMAL,
1505 " %d deleted vars, %d deleted constraints, %d added constraints, %d tightened bounds, %d added holes, %d changed sides, %d changed coefficients\n",
1506 scip->stat->npresolfixedvars + scip->stat->npresolaggrvars, scip->stat->npresoldelconss, scip->stat->npresoladdconss,
1507 scip->stat->npresolchgbds, scip->stat->npresoladdholes, scip->stat->npresolchgsides, scip->stat->npresolchgcoefs);
1508 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_NORMAL,
1509 " %d implications, %d cliques\n", scip->stat->nimplications, SCIPcliquetableGetNCliques(scip->cliquetable));
1510
1511 /* remember number of constraints */
1512 SCIPprobMarkNConss(scip->transprob);
1513
1514 return SCIP_OKAY;
1515 }
1516
1517 /** tries to transform original solutions to the transformed problem space */
1518 static
transformSols(SCIP * scip)1519 SCIP_RETCODE transformSols(
1520 SCIP* scip /**< SCIP data structure */
1521 )
1522 {
1523 SCIP_SOL** sols;
1524 SCIP_SOL** scipsols;
1525 SCIP_SOL* sol;
1526 SCIP_Real* solvals;
1527 SCIP_Bool* solvalset;
1528 SCIP_Bool added;
1529 SCIP_Longint oldnsolsfound;
1530 int nsols;
1531 int ntransvars;
1532 int naddedsols;
1533 int s;
1534
1535 nsols = SCIPgetNSols(scip);
1536 oldnsolsfound = scip->primal->nsolsfound;
1537
1538 /* no solution to transform */
1539 if( nsols == 0 )
1540 return SCIP_OKAY;
1541
1542 SCIPdebugMsg(scip, "try to transfer %d original solutions into the transformed problem space\n", nsols);
1543
1544 ntransvars = scip->transprob->nvars;
1545 naddedsols = 0;
1546
1547 /* It might happen, that the added transferred solution does not equal the corresponding original one, which might
1548 * result in the array of solutions being changed. Thus we temporarily copy the array and traverse it in reverse
1549 * order to ensure that the regarded solution in the copied array was not already freed when new solutions were added
1550 * and the worst solutions were freed.
1551 */
1552 scipsols = SCIPgetSols(scip);
1553 SCIP_CALL( SCIPduplicateBufferArray(scip, &sols, scipsols, nsols) );
1554 SCIP_CALL( SCIPallocBufferArray(scip, &solvals, ntransvars) );
1555 SCIP_CALL( SCIPallocBufferArray(scip, &solvalset, ntransvars) );
1556
1557 for( s = nsols-1; s >= 0; --s )
1558 {
1559 sol = sols[s];
1560
1561 /* it might happen that a transferred original solution has a better objective than its original counterpart
1562 * (e.g., because multi-aggregated variables get another value, but the solution is still feasible);
1563 * in this case, it might happen that the solution is not an original one and we just skip this solution
1564 */
1565 if( !SCIPsolIsOriginal(sol) )
1566 continue;
1567
1568 SCIP_CALL( SCIPprimalTransformSol(scip->primal, sol, scip->mem->probmem, scip->set, scip->messagehdlr, scip->stat,
1569 scip->origprob, scip->transprob, scip->tree, scip->reopt, scip->lp, scip->eventqueue, scip->eventfilter, solvals,
1570 solvalset, ntransvars, &added) );
1571
1572 if( added )
1573 ++naddedsols;
1574 }
1575
1576 if( naddedsols > 0 )
1577 {
1578 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
1579 "transformed %d/%d original solutions to the transformed problem space\n",
1580 naddedsols, nsols);
1581
1582 scip->stat->nexternalsolsfound += scip->primal->nsolsfound - oldnsolsfound;
1583 }
1584
1585 SCIPfreeBufferArray(scip, &solvalset);
1586 SCIPfreeBufferArray(scip, &solvals);
1587 SCIPfreeBufferArray(scip, &sols);
1588
1589 return SCIP_OKAY;
1590 }
1591
1592 /** initializes solution process data structures */
1593 static
initSolve(SCIP * scip,SCIP_Bool solved)1594 SCIP_RETCODE initSolve(
1595 SCIP* scip, /**< SCIP data structure */
1596 SCIP_Bool solved /**< is problem already solved? */
1597 )
1598 {
1599 assert(scip != NULL);
1600 assert(scip->mem != NULL);
1601 assert(scip->set != NULL);
1602 assert(scip->stat != NULL);
1603 assert(scip->nlp == NULL);
1604 assert(scip->set->stage == SCIP_STAGE_PRESOLVED);
1605
1606 /**@todo check whether other methodscan be skipped if problem has been solved */
1607 /* if problem has been solved, several time consuming tasks must not be performed */
1608 if( !solved )
1609 {
1610 /* reset statistics for current branch and bound run */
1611 SCIPstatResetCurrentRun(scip->stat, scip->set, scip->transprob, scip->origprob, solved);
1612 SCIPstatEnforceLPUpdates(scip->stat);
1613
1614 /* LP is empty anyway; mark empty LP to be solved and update validsollp counter */
1615 SCIP_CALL( SCIPlpReset(scip->lp, scip->mem->probmem, scip->set, scip->stat, scip->eventqueue, scip->eventfilter) );
1616
1617 /* update upper bound and cutoff bound due to objective limit in primal data */
1618 SCIP_CALL( SCIPprimalUpdateObjlimit(scip->primal, scip->mem->probmem, scip->set, scip->stat, scip->eventfilter,
1619 scip->eventqueue, scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp) );
1620 }
1621
1622 /* switch stage to INITSOLVE */
1623 scip->set->stage = SCIP_STAGE_INITSOLVE;
1624
1625 /* initialize NLP if there are nonlinearities */
1626 if( scip->transprob->nlpenabled && !scip->set->nlp_disable )
1627 {
1628 SCIPdebugMsg(scip, "constructing empty NLP\n");
1629
1630 SCIP_CALL( SCIPnlpCreate(&scip->nlp, scip->mem->probmem, scip->set, scip->stat, SCIPprobGetName(scip->transprob), scip->transprob->nvars) );
1631 assert(scip->nlp != NULL);
1632
1633 SCIP_CALL( SCIPnlpAddVars(scip->nlp, scip->mem->probmem, scip->set, scip->transprob->nvars, scip->transprob->vars) );
1634 }
1635
1636 /* possibly create visualization output file */
1637 SCIP_CALL( SCIPvisualInit(scip->stat->visual, scip->mem->probmem, scip->set, scip->messagehdlr) );
1638
1639 /* initialize solution process data structures */
1640 SCIP_CALL( SCIPpricestoreCreate(&scip->pricestore) );
1641 SCIP_CALL( SCIPsepastoreCreate(&scip->sepastore, scip->mem->probmem, scip->set) );
1642 SCIP_CALL( SCIPsepastoreCreate(&scip->sepastoreprobing, scip->mem->probmem, scip->set) );
1643 SCIP_CALL( SCIPcutpoolCreate(&scip->cutpool, scip->mem->probmem, scip->set, scip->set->sepa_cutagelimit, TRUE) );
1644 SCIP_CALL( SCIPcutpoolCreate(&scip->delayedcutpool, scip->mem->probmem, scip->set, scip->set->sepa_cutagelimit, FALSE) );
1645 SCIP_CALL( SCIPtreeCreateRoot(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->eventfilter, scip->eventqueue,
1646 scip->lp) );
1647
1648 /* update dual bound of the root node if a valid dual bound is at hand */
1649 if( scip->transprob->dualbound < SCIP_INVALID )
1650 {
1651 SCIP_Real internobjval = SCIPprobInternObjval(scip->transprob, scip->origprob, scip->set, scip->transprob->dualbound);
1652
1653 scip->stat->lastlowerbound = internobjval;
1654
1655 SCIPnodeUpdateLowerbound(SCIPtreeGetRootNode(scip->tree), scip->stat, scip->set, scip->tree, scip->transprob,
1656 scip->origprob, internobjval);
1657 }
1658
1659 /* try to transform original solutions to the transformed problem space */
1660 if( scip->set->misc_transorigsols )
1661 {
1662 SCIP_CALL( transformSols(scip) );
1663 }
1664
1665 /* inform the transformed problem that the branch and bound process starts now */
1666 SCIP_CALL( SCIPprobInitSolve(scip->transprob, scip->set) );
1667
1668 /* transform the decomposition storage */
1669 SCIP_CALL( SCIPtransformDecompstore(scip) );
1670
1671 /* inform plugins that the branch and bound process starts now */
1672 SCIP_CALL( SCIPsetInitsolPlugins(scip->set, scip->mem->probmem, scip->stat) );
1673
1674 /* remember number of constraints */
1675 SCIPprobMarkNConss(scip->transprob);
1676
1677 /* if all variables are known, calculate a trivial primal bound by setting all variables to their worst bound */
1678 if( scip->set->nactivepricers == 0 )
1679 {
1680 SCIP_VAR* var;
1681 SCIP_Real obj;
1682 SCIP_Real objbound;
1683 SCIP_Real bd;
1684 int v;
1685
1686 objbound = 0.0;
1687 for( v = 0; v < scip->transprob->nvars && !SCIPsetIsInfinity(scip->set, objbound); ++v )
1688 {
1689 var = scip->transprob->vars[v];
1690 obj = SCIPvarGetObj(var);
1691 if( !SCIPsetIsZero(scip->set, obj) )
1692 {
1693 bd = SCIPvarGetWorstBoundGlobal(var);
1694 if( SCIPsetIsInfinity(scip->set, REALABS(bd)) )
1695 objbound = SCIPsetInfinity(scip->set);
1696 else
1697 objbound += obj * bd;
1698 }
1699 }
1700
1701 /* adjust primal bound, such that solution with worst bound may be found */
1702 if( objbound + SCIPsetCutoffbounddelta(scip->set) != objbound ) /*lint !e777*/
1703 objbound += SCIPsetCutoffbounddelta(scip->set);
1704 /* if objbound is very large, adding the cutoffbounddelta may not change the number; in this case, we are using
1705 * SCIPnextafter to ensure that the cutoffbound is really larger than the best possible solution value
1706 */
1707 else
1708 objbound = SCIPnextafter(objbound, SCIP_REAL_MAX);
1709
1710 /* update cutoff bound */
1711 if( !SCIPsetIsInfinity(scip->set, objbound) && SCIPsetIsLT(scip->set, objbound, scip->primal->cutoffbound) )
1712 {
1713 /* adjust cutoff bound */
1714 SCIP_CALL( SCIPprimalSetCutoffbound(scip->primal, scip->mem->probmem, scip->set, scip->stat, scip->eventfilter,
1715 scip->eventqueue, scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, objbound, FALSE) );
1716 }
1717 }
1718
1719 /* switch stage to SOLVING */
1720 scip->set->stage = SCIP_STAGE_SOLVING;
1721
1722 return SCIP_OKAY;
1723 }
1724
1725 /** frees solution process data structures */
1726 static
freeSolve(SCIP * scip,SCIP_Bool restart)1727 SCIP_RETCODE freeSolve(
1728 SCIP* scip, /**< SCIP data structure */
1729 SCIP_Bool restart /**< was this free solve call triggered by a restart? */
1730 )
1731 {
1732 assert(scip != NULL);
1733 assert(scip->mem != NULL);
1734 assert(scip->set != NULL);
1735 assert(scip->stat != NULL);
1736 assert(scip->set->stage == SCIP_STAGE_SOLVING || scip->set->stage == SCIP_STAGE_SOLVED);
1737
1738 /* mark that we are currently restarting */
1739 if( restart )
1740 {
1741 scip->stat->inrestart = TRUE;
1742
1743 /* copy the current dual bound into the problem data structure such that it can be used initialize the new search
1744 * tree
1745 */
1746 SCIPprobUpdateDualbound(scip->transprob, SCIPgetDualbound(scip));
1747 }
1748
1749 /* remove focus from the current focus node */
1750 if( SCIPtreeGetFocusNode(scip->tree) != NULL )
1751 {
1752 SCIP_NODE* node = NULL;
1753 SCIP_Bool cutoff;
1754
1755 SCIP_CALL( SCIPnodeFocus(&node, scip->mem->probmem, scip->set, scip->messagehdlr, scip->stat, scip->transprob,
1756 scip->origprob, scip->primal, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->conflict,
1757 scip->conflictstore, scip->eventfilter, scip->eventqueue, scip->cliquetable, &cutoff, FALSE, TRUE) );
1758 assert(!cutoff);
1759 }
1760
1761 /* switch stage to EXITSOLVE */
1762 scip->set->stage = SCIP_STAGE_EXITSOLVE;
1763
1764 /* cleanup the conflict storage */
1765 SCIP_CALL( SCIPconflictstoreClean(scip->conflictstore, scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->reopt) );
1766
1767 /* inform plugins that the branch and bound process is finished */
1768 SCIP_CALL( SCIPsetExitsolPlugins(scip->set, scip->mem->probmem, scip->stat, restart) );
1769
1770 /* free the NLP, if there is one, and reset the flags indicating nonlinearity */
1771 if( scip->nlp != NULL )
1772 {
1773 SCIP_CALL( SCIPnlpFree(&scip->nlp, scip->mem->probmem, scip->set, scip->eventqueue, scip->lp) );
1774 }
1775 scip->transprob->nlpenabled = FALSE;
1776
1777 /* clear the LP, and flush the changes to clear the LP of the solver */
1778 SCIP_CALL( SCIPlpReset(scip->lp, scip->mem->probmem, scip->set, scip->stat, scip->eventqueue, scip->eventfilter) );
1779 SCIPlpInvalidateRootObjval(scip->lp);
1780
1781 /* resets the debug environment */
1782 SCIP_CALL( SCIPdebugReset(scip->set) ); /*lint !e506 !e774*/
1783
1784 /* clear all row references in internal data structures */
1785 SCIP_CALL( SCIPcutpoolClear(scip->cutpool, scip->mem->probmem, scip->set, scip->lp) );
1786 SCIP_CALL( SCIPcutpoolClear(scip->delayedcutpool, scip->mem->probmem, scip->set, scip->lp) );
1787
1788 /* we have to clear the tree prior to the problem deinitialization, because the rows stored in the forks and
1789 * subroots have to be released
1790 */
1791 SCIP_CALL( SCIPtreeClear(scip->tree, scip->mem->probmem, scip->set, scip->stat, scip->eventfilter, scip->eventqueue, scip->lp) );
1792
1793 SCIPexitSolveDecompstore(scip);
1794
1795 /* deinitialize transformed problem */
1796 SCIP_CALL( SCIPprobExitSolve(scip->transprob, scip->mem->probmem, scip->set, scip->eventqueue, scip->lp, restart) );
1797
1798 /* free solution process data structures */
1799 SCIP_CALL( SCIPcutpoolFree(&scip->cutpool, scip->mem->probmem, scip->set, scip->lp) );
1800 SCIP_CALL( SCIPcutpoolFree(&scip->delayedcutpool, scip->mem->probmem, scip->set, scip->lp) );
1801 SCIP_CALL( SCIPsepastoreFree(&scip->sepastoreprobing, scip->mem->probmem) );
1802 SCIP_CALL( SCIPsepastoreFree(&scip->sepastore, scip->mem->probmem) );
1803 SCIP_CALL( SCIPpricestoreFree(&scip->pricestore) );
1804
1805 /* possibly close visualization output file */
1806 SCIPvisualExit(scip->stat->visual, scip->set, scip->messagehdlr);
1807
1808 /* reset statistics for current branch and bound run */
1809 if( scip->stat->status == SCIP_STATUS_INFEASIBLE || scip->stat->status == SCIP_STATUS_OPTIMAL || scip->stat->status == SCIP_STATUS_UNBOUNDED || scip->stat->status == SCIP_STATUS_INFORUNBD )
1810 SCIPstatResetCurrentRun(scip->stat, scip->set, scip->transprob, scip->origprob, TRUE);
1811 else
1812 SCIPstatResetCurrentRun(scip->stat, scip->set, scip->transprob, scip->origprob, FALSE);
1813
1814 /* switch stage to TRANSFORMED */
1815 scip->set->stage = SCIP_STAGE_TRANSFORMED;
1816
1817 /* restart finished */
1818 assert( ! restart || scip->stat->inrestart );
1819 scip->stat->inrestart = FALSE;
1820
1821 return SCIP_OKAY;
1822 }
1823
1824 /** frees solution process data structures when reoptimization is used
1825 *
1826 * in contrast to a freeSolve() this method will preserve the transformed problem such that another presolving round
1827 * after changing the problem (modifying the objective function) is not necessary.
1828 */
1829 static
freeReoptSolve(SCIP * scip)1830 SCIP_RETCODE freeReoptSolve(
1831 SCIP* scip /**< SCIP data structure */
1832 )
1833 {
1834 assert(scip != NULL);
1835 assert(scip->mem != NULL);
1836 assert(scip->set != NULL);
1837 assert(scip->stat != NULL);
1838 assert(scip->set->stage == SCIP_STAGE_SOLVING || scip->set->stage == SCIP_STAGE_SOLVED);
1839
1840 /* remove focus from the current focus node */
1841 if( SCIPtreeGetFocusNode(scip->tree) != NULL )
1842 {
1843 SCIP_NODE* node = NULL;
1844 SCIP_Bool cutoff;
1845
1846 SCIP_CALL( SCIPnodeFocus(&node, scip->mem->probmem, scip->set, scip->messagehdlr, scip->stat, scip->transprob,
1847 scip->origprob, scip->primal, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->conflict,
1848 scip->conflictstore, scip->eventfilter, scip->eventqueue, scip->cliquetable, &cutoff, FALSE, TRUE) );
1849 assert(!cutoff);
1850 }
1851
1852 /* mark current stats, such that new solve begins with the var/col/row indices from the previous run */
1853 SCIPstatMark(scip->stat);
1854
1855 /* switch stage to EXITSOLVE */
1856 scip->set->stage = SCIP_STAGE_EXITSOLVE;
1857
1858 /* deinitialize conflict store */
1859 SCIP_CALL( SCIPconflictstoreClear(scip->conflictstore, scip->mem->probmem, scip->set, scip->stat, scip->reopt) );
1860
1861 /* invalidate the dual bound */
1862 SCIPprobInvalidateDualbound(scip->transprob);
1863
1864 /* inform plugins that the branch and bound process is finished */
1865 SCIP_CALL( SCIPsetExitsolPlugins(scip->set, scip->mem->probmem, scip->stat, FALSE) );
1866
1867 /* call exit methods of plugins */
1868 SCIP_CALL( SCIPsetExitPlugins(scip->set, scip->mem->probmem, scip->stat) );
1869
1870 /* free the NLP, if there is one, and reset the flags indicating nonlinearity */
1871 if( scip->nlp != NULL )
1872 {
1873 SCIP_CALL( SCIPnlpFree(&scip->nlp, scip->mem->probmem, scip->set, scip->eventqueue, scip->lp) );
1874 }
1875 scip->transprob->nlpenabled = FALSE;
1876
1877 /* clear the LP, and flush the changes to clear the LP of the solver */
1878 SCIP_CALL( SCIPlpReset(scip->lp, scip->mem->probmem, scip->set, scip->stat, scip->eventqueue, scip->eventfilter) );
1879 SCIPlpInvalidateRootObjval(scip->lp);
1880
1881 /* resets the debug environment */
1882 SCIP_CALL( SCIPdebugReset(scip->set) ); /*lint !e506 !e774*/
1883
1884 /* clear all row references in internal data structures */
1885 SCIP_CALL( SCIPcutpoolClear(scip->cutpool, scip->mem->probmem, scip->set, scip->lp) );
1886 SCIP_CALL( SCIPcutpoolClear(scip->delayedcutpool, scip->mem->probmem, scip->set, scip->lp) );
1887
1888 /* we have to clear the tree prior to the problem deinitialization, because the rows stored in the forks and
1889 * subroots have to be released
1890 */
1891 SCIP_CALL( SCIPtreeClear(scip->tree, scip->mem->probmem, scip->set, scip->stat, scip->eventfilter, scip->eventqueue, scip->lp) );
1892
1893 /* deinitialize transformed problem */
1894 SCIP_CALL( SCIPprobExitSolve(scip->transprob, scip->mem->probmem, scip->set, scip->eventqueue, scip->lp, FALSE) );
1895
1896 /* free solution process data structures */
1897 SCIP_CALL( SCIPrelaxationFree(&scip->relaxation) );
1898
1899 SCIP_CALL( SCIPcutpoolFree(&scip->cutpool, scip->mem->probmem, scip->set, scip->lp) );
1900 SCIP_CALL( SCIPcutpoolFree(&scip->delayedcutpool, scip->mem->probmem, scip->set, scip->lp) );
1901 SCIP_CALL( SCIPsepastoreFree(&scip->sepastoreprobing, scip->mem->probmem) );
1902 SCIP_CALL( SCIPsepastoreFree(&scip->sepastore, scip->mem->probmem) );
1903 SCIP_CALL( SCIPpricestoreFree(&scip->pricestore) );
1904
1905 /* possibly close visualization output file */
1906 SCIPvisualExit(scip->stat->visual, scip->set, scip->messagehdlr);
1907
1908 /* reset statistics for current branch and bound run */
1909 SCIPstatResetCurrentRun(scip->stat, scip->set, scip->transprob, scip->origprob, FALSE);
1910
1911 /* switch stage to PRESOLVED */
1912 scip->set->stage = SCIP_STAGE_PRESOLVED;
1913
1914 /* restart finished */
1915 scip->stat->inrestart = FALSE;
1916
1917 /* reset solving specific paramters */
1918 if( scip->set->reopt_enable )
1919 {
1920 assert(scip->reopt != NULL);
1921 SCIP_CALL( SCIPreoptReset(scip->reopt, scip->set, scip->mem->probmem) );
1922 }
1923
1924 /* free the debug solution which might live in transformed primal data structure */
1925 SCIP_CALL( SCIPprimalClear(&scip->primal, scip->mem->probmem) );
1926
1927 if( scip->set->misc_resetstat )
1928 {
1929 /* reset statistics to the point before the problem was transformed */
1930 SCIPstatReset(scip->stat, scip->set, scip->transprob, scip->origprob);
1931 }
1932 else
1933 {
1934 /* even if statistics are not completely reset, a partial reset of the primal-dual integral is necessary */
1935 SCIPstatResetPrimalDualIntegrals(scip->stat, scip->set, TRUE);
1936 }
1937
1938 /* reset objective limit */
1939 SCIP_CALL( SCIPsetObjlimit(scip, SCIP_INVALID) );
1940
1941 return SCIP_OKAY;
1942 }
1943
1944 /** free transformed problem */
1945 static
freeTransform(SCIP * scip)1946 SCIP_RETCODE freeTransform(
1947 SCIP* scip /**< SCIP data structure */
1948 )
1949 {
1950 SCIP_Bool reducedfree;
1951
1952 assert(scip != NULL);
1953 assert(scip->mem != NULL);
1954 assert(scip->stat != NULL);
1955 assert(scip->set->stage == SCIP_STAGE_TRANSFORMED || scip->set->stage == SCIP_STAGE_PRESOLVING ||
1956 (scip->set->stage == SCIP_STAGE_PRESOLVED && scip->set->reopt_enable));
1957
1958 /* If the following evaluates to true, SCIPfreeReoptSolve() has already called the exit-callbacks of the plugins.
1959 * We can skip calling some of the following methods. This can happen if a new objective function was
1960 * installed but the solve was not started.
1961 */
1962 reducedfree = (scip->set->stage == SCIP_STAGE_PRESOLVED && scip->set->reopt_enable);
1963
1964 if( !reducedfree )
1965 {
1966 /* call exit methods of plugins */
1967 SCIP_CALL( SCIPsetExitPlugins(scip->set, scip->mem->probmem, scip->stat) );
1968 }
1969
1970 /* copy best primal solutions to original solution candidate list */
1971 if( !scip->set->reopt_enable && scip->set->limit_maxorigsol > 0 && scip->set->misc_transsolsorig && scip->set->nactivebenders == 0 )
1972 {
1973 SCIP_Bool stored;
1974 SCIP_Bool hasinfval;
1975 int maxsols;
1976 int nsols;
1977 int s;
1978
1979 assert(scip->origprimal->nsols == 0);
1980
1981 nsols = scip->primal->nsols;
1982 maxsols = scip->set->limit_maxorigsol;
1983 stored = TRUE;
1984 s = 0;
1985
1986 /* iterate over all solutions as long as the original solution candidate store size limit is not reached */
1987 while( s < nsols && scip->origprimal->nsols < maxsols )
1988 {
1989 SCIP_SOL* sol;
1990
1991 sol = scip->primal->sols[s];
1992 assert(sol != NULL);
1993
1994 if( !SCIPsolIsOriginal(sol) )
1995 {
1996 /* retransform solution into the original problem space */
1997 SCIP_CALL( SCIPsolRetransform(sol, scip->set, scip->stat, scip->origprob, scip->transprob, &hasinfval) );
1998 }
1999 else
2000 hasinfval = FALSE;
2001
2002 /* removing infinite fixings is turned off by the corresponding parameter */
2003 if( !scip->set->misc_finitesolstore )
2004 hasinfval = FALSE;
2005
2006 if( !hasinfval )
2007 {
2008 /* add solution to original candidate solution storage */
2009 SCIP_CALL( SCIPprimalAddOrigSol(scip->origprimal, scip->mem->probmem, scip->set, scip->stat, scip->origprob, sol, &stored) );
2010 }
2011 else
2012 {
2013 SCIP_SOL* newsol;
2014 SCIP_Bool success;
2015
2016 SCIP_CALL( SCIPcreateFiniteSolCopy(scip, &newsol, sol, &success) );
2017
2018 /* infinite fixing could be removed */
2019 if( newsol != NULL )
2020 {
2021 /* add solution to original candidate solution storage; we must not use SCIPprimalAddOrigSolFree()
2022 * because we want to create a copy of the solution in the origprimal solution store, but newsol was
2023 * created in the (transformed) primal
2024 */
2025 SCIP_CALL( SCIPprimalAddOrigSol(scip->origprimal, scip->mem->probmem, scip->set, scip->stat, scip->origprob, newsol, &stored) );
2026
2027 /* free solution in (transformed) primal where it was created */
2028 SCIP_CALL( SCIPsolFree(&newsol, scip->mem->probmem, scip->primal) );
2029 }
2030 }
2031 ++s;
2032 }
2033
2034 if( scip->origprimal->nsols > 1 )
2035 {
2036 SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
2037 "stored the %d best primal solutions in the original solution candidate list\n", scip->origprimal->nsols);
2038 }
2039 else if( scip->origprimal->nsols == 1 )
2040 {
2041 SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
2042 "stored the best primal solution in the original solution candidate list\n");
2043 }
2044 }
2045
2046 /* switch stage to FREETRANS */
2047 scip->set->stage = SCIP_STAGE_FREETRANS;
2048
2049 /* reset solving specific paramters */
2050 assert(!scip->set->reopt_enable || scip->reopt != NULL);
2051 if( scip->set->reopt_enable && scip->reopt != NULL )
2052 {
2053 SCIP_CALL( SCIPreoptReset(scip->reopt, scip->set, scip->mem->probmem) );
2054 }
2055
2056 if( !reducedfree )
2057 {
2058 /* clear the conflict store
2059 *
2060 * since the conflict store can contain transformed constraints we need to remove them. the store will be finally
2061 * freed in SCIPfreeProb().
2062 */
2063 SCIP_CALL( SCIPconflictstoreClear(scip->conflictstore, scip->mem->probmem, scip->set, scip->stat, scip->reopt) );
2064 }
2065
2066 /* free transformed problem data structures */
2067 SCIP_CALL( SCIPprobFree(&scip->transprob, scip->messagehdlr, scip->mem->probmem, scip->set, scip->stat, scip->eventqueue, scip->lp) );
2068 SCIP_CALL( SCIPcliquetableFree(&scip->cliquetable, scip->mem->probmem) );
2069 SCIP_CALL( SCIPconflictFree(&scip->conflict, scip->mem->probmem) );
2070
2071 if( !reducedfree )
2072 {
2073 SCIP_CALL( SCIPrelaxationFree(&scip->relaxation) );
2074 }
2075 SCIP_CALL( SCIPtreeFree(&scip->tree, scip->mem->probmem, scip->set, scip->stat, scip->eventfilter, scip->eventqueue, scip->lp) );
2076
2077 /* free the debug solution which might live in transformed primal data structure */
2078 SCIP_CALL( SCIPdebugFreeSol(scip->set) ); /*lint !e506 !e774*/
2079 SCIP_CALL( SCIPprimalFree(&scip->primal, scip->mem->probmem) );
2080
2081 SCIP_CALL( SCIPlpFree(&scip->lp, scip->mem->probmem, scip->set, scip->eventqueue, scip->eventfilter) );
2082 SCIP_CALL( SCIPbranchcandFree(&scip->branchcand) );
2083 SCIP_CALL( SCIPeventfilterFree(&scip->eventfilter, scip->mem->probmem, scip->set) );
2084 SCIP_CALL( SCIPeventqueueFree(&scip->eventqueue) );
2085
2086 if( scip->set->misc_resetstat && !reducedfree )
2087 {
2088 /* reset statistics to the point before the problem was transformed */
2089 SCIPstatReset(scip->stat, scip->set, scip->transprob, scip->origprob);
2090 }
2091 else
2092 {
2093 /* even if statistics are not completely reset, a partial reset of the primal-dual integral is necessary */
2094 SCIPstatResetPrimalDualIntegrals(scip->stat, scip->set, TRUE);
2095 }
2096
2097 /* switch stage to PROBLEM */
2098 scip->set->stage = SCIP_STAGE_PROBLEM;
2099
2100 /* reset objective limit */
2101 SCIP_CALL( SCIPsetObjlimit(scip, SCIP_INVALID) );
2102
2103 /* reset original variable's local and global bounds to their original values */
2104 SCIP_CALL( SCIPprobResetBounds(scip->origprob, scip->mem->probmem, scip->set, scip->stat) );
2105
2106 return SCIP_OKAY;
2107 }
2108
2109 /** displays most relevant statistics after problem was solved */
2110 static
displayRelevantStats(SCIP * scip)2111 SCIP_RETCODE displayRelevantStats(
2112 SCIP* scip /**< SCIP data structure */
2113 )
2114 {
2115 assert(scip != NULL);
2116
2117 /* display most relevant statistics */
2118 if( scip->set->disp_verblevel >= SCIP_VERBLEVEL_NORMAL && scip->set->disp_relevantstats )
2119 {
2120 SCIP_Bool objlimitreached = FALSE;
2121
2122 /* We output that the objective limit has been reached if the problem has been solved, no solution respecting the
2123 * objective limit has been found (nlimsolsfound == 0) and the primal bound is finite. Note that it still might be
2124 * that the original problem is infeasible, even without the objective limit, i.e., we cannot be sure that we
2125 * actually reached the objective limit. */
2126 if( SCIPgetStage(scip) == SCIP_STAGE_SOLVED && scip->primal->nlimsolsfound == 0 && ! SCIPisInfinity(scip, SCIPgetPrimalbound(scip)) )
2127 objlimitreached = TRUE;
2128
2129 SCIPmessagePrintInfo(scip->messagehdlr, "\n");
2130 SCIPmessagePrintInfo(scip->messagehdlr, "SCIP Status : ");
2131 SCIP_CALL( SCIPprintStage(scip, NULL) );
2132 SCIPmessagePrintInfo(scip->messagehdlr, "\n");
2133 if( scip->set->reopt_enable )
2134 SCIPmessagePrintInfo(scip->messagehdlr, "Solving Time (sec) : %.2f (over %d runs: %.2f)\n", SCIPclockGetTime(scip->stat->solvingtime), scip->stat->nreoptruns, SCIPclockGetTime(scip->stat->solvingtimeoverall));
2135 else
2136 SCIPmessagePrintInfo(scip->messagehdlr, "Solving Time (sec) : %.2f\n", SCIPclockGetTime(scip->stat->solvingtime));
2137 if( scip->stat->nruns > 1 )
2138 SCIPmessagePrintInfo(scip->messagehdlr, "Solving Nodes : %" SCIP_LONGINT_FORMAT " (total of %" SCIP_LONGINT_FORMAT " nodes in %d runs)\n",
2139 scip->stat->nnodes, scip->stat->ntotalnodes, scip->stat->nruns);
2140 else if( scip->set->reopt_enable )
2141 {
2142 SCIP_BRANCHRULE* branchrule;
2143
2144 branchrule = SCIPfindBranchrule(scip, "nodereopt");
2145 assert(branchrule != NULL);
2146
2147 SCIPmessagePrintInfo(scip->messagehdlr, "Solving Nodes : %" SCIP_LONGINT_FORMAT " (%" SCIP_LONGINT_FORMAT " reactivated)\n", scip->stat->nnodes, SCIPbranchruleGetNChildren(branchrule));
2148 }
2149 else
2150 SCIPmessagePrintInfo(scip->messagehdlr, "Solving Nodes : %" SCIP_LONGINT_FORMAT "\n", scip->stat->nnodes);
2151 if( scip->set->stage >= SCIP_STAGE_TRANSFORMED && scip->set->stage <= SCIP_STAGE_EXITSOLVE )
2152 {
2153 if( objlimitreached )
2154 {
2155 SCIPmessagePrintInfo(scip->messagehdlr, "Primal Bound : %+.14e (objective limit, %" SCIP_LONGINT_FORMAT " solutions",
2156 SCIPgetPrimalbound(scip), scip->primal->nsolsfound);
2157 if( scip->primal->nsolsfound > 0 )
2158 {
2159 SCIPmessagePrintInfo(scip->messagehdlr, ", best solution %+.14e", SCIPgetSolOrigObj(scip, SCIPgetBestSol(scip)));
2160 }
2161 SCIPmessagePrintInfo(scip->messagehdlr, ")\n");
2162 }
2163 else
2164 {
2165 char limsolstring[SCIP_MAXSTRLEN];
2166 if( scip->primal->nsolsfound != scip->primal->nlimsolsfound )
2167 (void) SCIPsnprintf(limsolstring, SCIP_MAXSTRLEN, ", %" SCIP_LONGINT_FORMAT " respecting the objective limit", scip->primal->nlimsolsfound);
2168 else
2169 (void) SCIPsnprintf(limsolstring, SCIP_MAXSTRLEN,"");
2170
2171 SCIPmessagePrintInfo(scip->messagehdlr, "Primal Bound : %+.14e (%" SCIP_LONGINT_FORMAT " solutions%s)\n",
2172 SCIPgetPrimalbound(scip), scip->primal->nsolsfound, limsolstring);
2173 }
2174 }
2175 if( scip->set->stage >= SCIP_STAGE_SOLVING && scip->set->stage <= SCIP_STAGE_SOLVED )
2176 {
2177 SCIPmessagePrintInfo(scip->messagehdlr, "Dual Bound : %+.14e\n", SCIPgetDualbound(scip));
2178
2179 SCIPmessagePrintInfo(scip->messagehdlr, "Gap : ");
2180 if( SCIPsetIsInfinity(scip->set, SCIPgetGap(scip)) )
2181 SCIPmessagePrintInfo(scip->messagehdlr, "infinite\n");
2182 else
2183 SCIPmessagePrintInfo(scip->messagehdlr, "%.2f %%\n", 100.0*SCIPgetGap(scip));
2184 }
2185
2186 /* check solution for feasibility in original problem */
2187 if( scip->set->stage >= SCIP_STAGE_TRANSFORMED )
2188 {
2189 SCIP_SOL* sol;
2190
2191 sol = SCIPgetBestSol(scip);
2192 if( sol != NULL )
2193 {
2194 SCIP_Real checkfeastolfac;
2195 SCIP_Real oldfeastol;
2196 SCIP_Bool dispallviols;
2197 SCIP_Bool feasible;
2198
2199 oldfeastol = SCIPfeastol(scip);
2200 SCIP_CALL( SCIPgetRealParam(scip, "numerics/checkfeastolfac", &checkfeastolfac) );
2201 SCIP_CALL( SCIPgetBoolParam(scip, "display/allviols", &dispallviols) );
2202
2203 /* scale feasibility tolerance by set->num_checkfeastolfac */
2204 if( !SCIPisEQ(scip, checkfeastolfac, 1.0) )
2205 {
2206 SCIP_CALL( SCIPchgFeastol(scip, oldfeastol * checkfeastolfac) );
2207 }
2208
2209 SCIP_CALL( SCIPcheckSolOrig(scip, sol, &feasible, TRUE, dispallviols) );
2210
2211 /* restore old feasibilty tolerance */
2212 if( !SCIPisEQ(scip, checkfeastolfac, 1.0) )
2213 {
2214 SCIP_CALL( SCIPchgFeastol(scip, oldfeastol) );
2215 }
2216
2217 if( !feasible )
2218 {
2219 SCIPmessagePrintInfo(scip->messagehdlr, "best solution is not feasible in original problem\n");
2220 }
2221 }
2222 }
2223 }
2224
2225 return SCIP_OKAY;
2226 }
2227
2228 /** calls compression based on the reoptimization structure after the presolving */
2229 static
compressReoptTree(SCIP * scip)2230 SCIP_RETCODE compressReoptTree(
2231 SCIP* scip /**< global SCIP settings */
2232 )
2233 {
2234 SCIP_RESULT result;
2235 int c;
2236 int noldnodes;
2237 int nnewnodes;
2238
2239 result = SCIP_DIDNOTFIND;
2240
2241 noldnodes = SCIPreoptGetNNodes(scip->reopt, scip->tree->root);
2242
2243 /* do not run if there exists only the root node */
2244 if( noldnodes <= 1 )
2245 return SCIP_OKAY;
2246
2247 /* do not run a tree compression if the problem contains (implicit) integer variables */
2248 if( scip->transprob->nintvars > 0 || scip->transprob->nimplvars > 0 )
2249 return SCIP_OKAY;
2250
2251 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH,
2252 "tree compression:\n");
2253 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH,
2254 " given tree has %d nodes.\n", noldnodes);
2255
2256 /* sort compressions by priority */
2257 SCIPsetSortComprs(scip->set);
2258
2259 for(c = 0; c < scip->set->ncomprs; c++)
2260 {
2261 assert(result == SCIP_DIDNOTFIND || result == SCIP_DIDNOTRUN);
2262
2263 /* call tree compression technique */
2264 SCIP_CALL( SCIPcomprExec(scip->set->comprs[c], scip->set, scip->reopt, &result) );
2265
2266 if( result == SCIP_SUCCESS )
2267 {
2268 nnewnodes = SCIPreoptGetNNodes(scip->reopt, scip->tree->root);
2269 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH,
2270 " <%s> compressed the search tree to %d nodes (rate %g).\n", SCIPcomprGetName(scip->set->comprs[c]),
2271 nnewnodes, ((SCIP_Real)nnewnodes)/noldnodes);
2272
2273 break;
2274 }
2275 }
2276
2277 if( result != SCIP_SUCCESS )
2278 {
2279 assert(result == SCIP_DIDNOTFIND || result == SCIP_DIDNOTRUN);
2280 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH,
2281 " search tree could not be compressed.\n");
2282 }
2283
2284 return SCIP_OKAY;
2285 }
2286
2287 /* prepare all plugins and data structures for a reoptimization run */
2288 static
prepareReoptimization(SCIP * scip)2289 SCIP_RETCODE prepareReoptimization(
2290 SCIP* scip /**< SCIP data structure */
2291 )
2292 {
2293 SCIP_Bool reoptrestart;
2294
2295 assert(scip != NULL);
2296 assert(scip->set->reopt_enable);
2297
2298 /* @ todo: we could check if the problem is feasible, eg, by backtracking */
2299
2300 /* increase number of reopt_runs */
2301 ++scip->stat->nreoptruns;
2302
2303 /* inform the reoptimization plugin that a new iteration starts */
2304 SCIP_CALL( SCIPreoptAddRun(scip->reopt, scip->set, scip->mem->probmem, scip->origprob->vars,
2305 scip->origprob->nvars, scip->set->limit_maxsol) );
2306
2307 /* check whether we need to add globally valid constraints */
2308 if( scip->set->reopt_sepaglbinfsubtrees || scip->set->reopt_sepabestsol )
2309 {
2310 SCIP_CALL( SCIPreoptApplyGlbConss(scip, scip->reopt, scip->set, scip->stat, scip->mem->probmem) );
2311 }
2312
2313 /* after presolving the problem the first time we remember all global bounds and active constraints. bounds and
2314 * constraints will be restored within SCIPreoptInstallBounds() and SCIPreoptResetActiveConss().
2315 */
2316 if( scip->stat->nreoptruns == 1 )
2317 {
2318 assert(scip->set->stage == SCIP_STAGE_PRESOLVED);
2319
2320 SCIP_CALL( SCIPreoptSaveGlobalBounds(scip->reopt, scip->transprob, scip->mem->probmem) );
2321
2322 SCIP_CALL( SCIPreoptSaveActiveConss(scip->reopt, scip->set, scip->transprob, scip->mem->probmem) );
2323 }
2324 /* we are at least in the second run */
2325 else
2326 {
2327 assert(scip->transprob != NULL);
2328
2329 SCIP_CALL( SCIPreoptMergeVarHistory(scip->reopt, scip->set, scip->stat, scip->origprob->vars, scip->origprob->nvars) );
2330
2331 SCIP_CALL( SCIPrelaxationCreate(&scip->relaxation, scip->mem->probmem, scip->set, scip->stat, scip->primal,
2332 scip->tree) );
2333
2334 /* mark statistics before solving */
2335 SCIPstatMark(scip->stat);
2336
2337 SCIPbranchcandInvalidate(scip->branchcand);
2338
2339 SCIP_CALL( SCIPreoptResetActiveConss(scip->reopt, scip->set, scip->stat) );
2340
2341 /* check whether we want to restart the tree search */
2342 SCIP_CALL( SCIPreoptCheckRestart(scip->reopt, scip->set, scip->mem->probmem, NULL, scip->transprob->vars,
2343 scip->transprob->nvars, &reoptrestart) );
2344
2345 /* call initialization methods of plugins */
2346 SCIP_CALL( SCIPsetInitPlugins(scip->set, scip->mem->probmem, scip->stat) );
2347
2348 /* install globally valid lower and upper bounds */
2349 SCIP_CALL( SCIPreoptInstallBounds(scip->reopt, scip->set, scip->stat, scip->transprob, scip->lp, scip->branchcand,
2350 scip->eventqueue, scip->cliquetable, scip->mem->probmem) );
2351
2352 /* check, whether objective value is always integral by inspecting the problem, if it is the case adjust the
2353 * cutoff bound if primal solution is already known
2354 */
2355 SCIP_CALL( SCIPprobCheckObjIntegral(scip->transprob, scip->origprob, scip->mem->probmem, scip->set, scip->stat,
2356 scip->primal, scip->tree, scip->reopt, scip->lp, scip->eventfilter, scip->eventqueue) );
2357
2358 /* if possible, scale objective function such that it becomes integral with gcd 1 */
2359 SCIP_CALL( SCIPprobScaleObj(scip->transprob, scip->origprob, scip->mem->probmem, scip->set, scip->stat, scip->primal,
2360 scip->tree, scip->reopt, scip->lp, scip->eventfilter, scip->eventqueue) );
2361
2362 SCIPlpRecomputeLocalAndGlobalPseudoObjval(scip->lp, scip->set, scip->transprob);
2363 }
2364
2365 /* try to compress the search tree */
2366 if( scip->set->compr_enable )
2367 {
2368 SCIP_CALL( compressReoptTree(scip) );
2369 }
2370
2371 return SCIP_OKAY;
2372 }
2373
2374 /** transforms and presolves problem
2375 *
2376 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
2377 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
2378 *
2379 * @pre This method can be called if @p scip is in one of the following stages:
2380 * - \ref SCIP_STAGE_PROBLEM
2381 * - \ref SCIP_STAGE_TRANSFORMED
2382 * - \ref SCIP_STAGE_PRESOLVING
2383 * - \ref SCIP_STAGE_PRESOLVED
2384 * - \ref SCIP_STAGE_SOLVED
2385 *
2386 * @post After calling this method \SCIP reaches one of the following stages:
2387 * - \ref SCIP_STAGE_PRESOLVING if the presolving process was interrupted
2388 * - \ref SCIP_STAGE_PRESOLVED if the presolving process was finished and did not solve the problem
2389 * - \ref SCIP_STAGE_SOLVED if the problem was solved during presolving
2390 *
2391 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
2392 */
SCIPpresolve(SCIP * scip)2393 SCIP_RETCODE SCIPpresolve(
2394 SCIP* scip /**< SCIP data structure */
2395 )
2396 {
2397 SCIP_Bool unbounded;
2398 SCIP_Bool infeasible;
2399 SCIP_Bool vanished;
2400
2401 SCIP_CALL( SCIPcheckStage(scip, "SCIPpresolve", FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE) );
2402
2403 /* start solving timer */
2404 SCIPclockStart(scip->stat->solvingtime, scip->set);
2405 SCIPclockStart(scip->stat->solvingtimeoverall, scip->set);
2406
2407 /* capture the CTRL-C interrupt */
2408 if( scip->set->misc_catchctrlc )
2409 SCIPinterruptCapture(scip->interrupt);
2410
2411 /* reset the user interrupt flag */
2412 scip->stat->userinterrupt = FALSE;
2413
2414 switch( scip->set->stage )
2415 {
2416 case SCIP_STAGE_PROBLEM:
2417 /* initialize solving data structures and transform problem */
2418 SCIP_CALL( SCIPtransformProb(scip) );
2419 assert(scip->set->stage == SCIP_STAGE_TRANSFORMED);
2420
2421 /*lint -fallthrough*/
2422
2423 case SCIP_STAGE_TRANSFORMED:
2424 case SCIP_STAGE_PRESOLVING:
2425 /* presolve problem */
2426 SCIP_CALL( presolve(scip, &unbounded, &infeasible, &vanished) );
2427 assert(scip->set->stage == SCIP_STAGE_PRESOLVED || scip->set->stage == SCIP_STAGE_PRESOLVING);
2428
2429 if( infeasible || unbounded || vanished )
2430 {
2431 assert(scip->set->stage == SCIP_STAGE_PRESOLVED);
2432
2433 /* initialize solving process data structures to be able to switch to SOLVED stage */
2434 SCIP_CALL( initSolve(scip, TRUE) );
2435
2436 /* switch stage to SOLVED */
2437 scip->set->stage = SCIP_STAGE_SOLVED;
2438
2439 /* print solution message */
2440 switch( scip->stat->status )/*lint --e{788}*/
2441 {
2442 case SCIP_STATUS_OPTIMAL:
2443 /* remove the root node from the tree, s.t. the lower bound is set to +infinity ???????????? (see initSolve())*/
2444 SCIP_CALL( SCIPtreeClear(scip->tree, scip->mem->probmem, scip->set, scip->stat, scip->eventfilter, scip->eventqueue, scip->lp) );
2445 break;
2446
2447 case SCIP_STATUS_INFEASIBLE:
2448 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_NORMAL,
2449 "presolving detected infeasibility\n");
2450 break;
2451
2452 case SCIP_STATUS_UNBOUNDED:
2453 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_NORMAL,
2454 "presolving detected unboundedness\n");
2455 break;
2456
2457 case SCIP_STATUS_INFORUNBD:
2458 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_NORMAL,
2459 "presolving detected unboundedness (or infeasibility)\n");
2460 break;
2461
2462 default:
2463 /* note that this is in an internal SCIP error since the status is corrupted */
2464 SCIPerrorMessage("invalid SCIP status <%d>\n", scip->stat->status);
2465 SCIPABORT();
2466 return SCIP_ERROR; /*lint !e527*/
2467 }
2468 }
2469 else if( scip->set->stage == SCIP_STAGE_PRESOLVED )
2470 {
2471 int h;
2472
2473 /* print presolved problem statistics */
2474 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_NORMAL,
2475 "presolved problem has %d variables (%d bin, %d int, %d impl, %d cont) and %d constraints\n",
2476 scip->transprob->nvars, scip->transprob->nbinvars, scip->transprob->nintvars, scip->transprob->nimplvars,
2477 scip->transprob->ncontvars, scip->transprob->nconss);
2478
2479 for( h = 0; h < scip->set->nconshdlrs; ++h )
2480 {
2481 int nactiveconss;
2482
2483 nactiveconss = SCIPconshdlrGetNActiveConss(scip->set->conshdlrs[h]);
2484 if( nactiveconss > 0 )
2485 {
2486 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH,
2487 "%7d constraints of type <%s>\n", nactiveconss, SCIPconshdlrGetName(scip->set->conshdlrs[h]));
2488 }
2489 }
2490
2491 if( SCIPprobIsObjIntegral(scip->transprob) )
2492 {
2493 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH,
2494 "transformed objective value is always integral (scale: %.15g)\n", scip->transprob->objscale);
2495 }
2496 }
2497 else
2498 {
2499 assert(scip->set->stage == SCIP_STAGE_PRESOLVING);
2500 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH, "presolving was interrupted.\n");
2501 }
2502
2503 /* display timing statistics */
2504 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH,
2505 "Presolving Time: %.2f\n", SCIPclockGetTime(scip->stat->presolvingtime));
2506 break;
2507
2508 case SCIP_STAGE_PRESOLVED:
2509 case SCIP_STAGE_SOLVED:
2510 break;
2511
2512 default:
2513 SCIPerrorMessage("invalid SCIP stage <%d>\n", scip->set->stage);
2514 return SCIP_INVALIDCALL;
2515 } /*lint !e788*/
2516
2517 /* release the CTRL-C interrupt */
2518 if( scip->set->misc_catchctrlc )
2519 SCIPinterruptRelease(scip->interrupt);
2520
2521 /* stop solving timer */
2522 SCIPclockStop(scip->stat->solvingtime, scip->set);
2523 SCIPclockStop(scip->stat->solvingtimeoverall, scip->set);
2524
2525 if( scip->set->stage == SCIP_STAGE_SOLVED )
2526 {
2527 /* display most relevant statistics */
2528 SCIP_CALL( displayRelevantStats(scip) );
2529 }
2530
2531 return SCIP_OKAY;
2532 }
2533
2534 /** transforms, presolves, and solves problem
2535 *
2536 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
2537 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
2538 *
2539 * @pre This method can be called if @p scip is in one of the following stages:
2540 * - \ref SCIP_STAGE_PROBLEM
2541 * - \ref SCIP_STAGE_TRANSFORMED
2542 * - \ref SCIP_STAGE_PRESOLVING
2543 * - \ref SCIP_STAGE_PRESOLVED
2544 * - \ref SCIP_STAGE_SOLVING
2545 * - \ref SCIP_STAGE_SOLVED
2546 *
2547 * @post After calling this method \SCIP reaches one of the following stages depending on if and when the solution
2548 * process was interrupted:
2549 * - \ref SCIP_STAGE_PRESOLVING if the solution process was interrupted during presolving
2550 * - \ref SCIP_STAGE_SOLVING if the solution process was interrupted during the tree search
2551 * - \ref SCIP_STAGE_SOLVED if the solving process was not interrupted
2552 *
2553 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
2554 */
SCIPsolve(SCIP * scip)2555 SCIP_RETCODE SCIPsolve(
2556 SCIP* scip /**< SCIP data structure */
2557 )
2558 {
2559 SCIP_Bool statsprinted = FALSE;
2560 SCIP_Bool restart;
2561
2562 SCIP_CALL( SCIPcheckStage(scip, "SCIPsolve", FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) );
2563
2564 /* if the stage is already SCIP_STAGE_SOLVED do nothing */
2565 if( scip->set->stage == SCIP_STAGE_SOLVED )
2566 return SCIP_OKAY;
2567
2568 if( scip->stat->status == SCIP_STATUS_INFEASIBLE || scip->stat->status == SCIP_STATUS_OPTIMAL || scip->stat->status == SCIP_STATUS_UNBOUNDED || scip->stat->status == SCIP_STATUS_INFORUNBD )
2569 {
2570 SCIPwarningMessage(scip, "SCIPsolve() was called, but problem is already solved\n");
2571 return SCIP_OKAY;
2572 }
2573
2574 /* check, if a node selector exists */
2575 if( SCIPsetGetNodesel(scip->set, scip->stat) == NULL )
2576 {
2577 SCIPerrorMessage("no node selector available\n");
2578 return SCIP_PLUGINNOTFOUND;
2579 }
2580
2581 /* check, if an integrality constraint handler exists if there are integral variables */
2582 if( (SCIPgetNBinVars(scip) >= 0 || SCIPgetNIntVars(scip) >= 0) && SCIPfindConshdlr(scip, "integral") == NULL )
2583 {
2584 SCIPwarningMessage(scip, "integrality constraint handler not available\n");
2585 }
2586
2587 /* initialize presolving flag (may be modified in SCIPpresolve()) */
2588 scip->stat->performpresol = FALSE;
2589
2590 /* if a decomposition exists and Benders' decomposition has been enabled, then a decomposition is performed */
2591 if( scip->set->stage == SCIP_STAGE_PROBLEM && SCIPdecompstoreGetNOrigDecomps(scip->decompstore) > 0
2592 && scip->set->decomp_applybenders && SCIPgetNActiveBenders(scip) == 0 )
2593 {
2594 int decompindex = 0;
2595
2596 /* applying the Benders' decomposition */
2597 SCIP_CALL( SCIPapplyBendersDecomposition(scip, decompindex) );
2598 }
2599
2600 /* start solving timer */
2601 SCIPclockStart(scip->stat->solvingtime, scip->set);
2602 SCIPclockStart(scip->stat->solvingtimeoverall, scip->set);
2603
2604 /* capture the CTRL-C interrupt */
2605 if( scip->set->misc_catchctrlc )
2606 SCIPinterruptCapture(scip->interrupt);
2607
2608 /* reset the user interrupt flag */
2609 scip->stat->userinterrupt = FALSE;
2610
2611 /* automatic restarting loop */
2612 restart = scip->stat->userrestart;
2613
2614 do
2615 {
2616 if( restart )
2617 {
2618 /* free the solving process data in order to restart */
2619 assert(scip->set->stage == SCIP_STAGE_SOLVING);
2620 if( scip->stat->userrestart )
2621 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL,
2622 "(run %d, node %" SCIP_LONGINT_FORMAT ") performing user restart\n",
2623 scip->stat->nruns, scip->stat->nnodes);
2624 else
2625 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL,
2626 "(run %d, node %" SCIP_LONGINT_FORMAT ") restarting after %d global fixings of integer variables\n",
2627 scip->stat->nruns, scip->stat->nnodes, scip->stat->nrootintfixingsrun);
2628 /* an extra blank line should be printed separately since the buffer message handler only handles up to one line
2629 * correctly */
2630 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\n");
2631 /* reset relaxation solution, so that the objective value is recomputed from scratch next time, using the new
2632 * fixings which may be produced during the presolving after the restart */
2633 SCIP_CALL( SCIPclearRelaxSolVals(scip, NULL) );
2634
2635 SCIP_CALL( freeSolve(scip, TRUE) );
2636 assert(scip->set->stage == SCIP_STAGE_TRANSFORMED);
2637 }
2638 restart = FALSE;
2639 scip->stat->userrestart = FALSE;
2640
2641 switch( scip->set->stage )
2642 {
2643 case SCIP_STAGE_PROBLEM:
2644 case SCIP_STAGE_TRANSFORMED:
2645 case SCIP_STAGE_PRESOLVING:
2646 /* initialize solving data structures, transform and problem */
2647
2648 SCIP_CALL( SCIPpresolve(scip) );
2649 /* remember that we already printed the relevant statistics */
2650 if( scip->set->stage == SCIP_STAGE_SOLVED )
2651 statsprinted = TRUE;
2652
2653 if( scip->set->stage == SCIP_STAGE_SOLVED || scip->set->stage == SCIP_STAGE_PRESOLVING )
2654 break;
2655 assert(scip->set->stage == SCIP_STAGE_PRESOLVED);
2656
2657 /*lint -fallthrough*/
2658
2659 case SCIP_STAGE_PRESOLVED:
2660 /* check if reoptimization is enabled and global constraints are saved */
2661 if( scip->set->reopt_enable )
2662 {
2663 SCIP_CALL( prepareReoptimization(scip) );
2664 }
2665
2666 /* initialize solving process data structures */
2667 SCIP_CALL( initSolve(scip, FALSE) );
2668 assert(scip->set->stage == SCIP_STAGE_SOLVING);
2669 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_NORMAL, "\n");
2670
2671 /*lint -fallthrough*/
2672
2673 case SCIP_STAGE_SOLVING:
2674 /* reset display */
2675 SCIPstatResetDisplay(scip->stat);
2676
2677 /* continue solution process */
2678 SCIP_CALL( SCIPsolveCIP(scip->mem->probmem, scip->set, scip->messagehdlr, scip->stat, scip->mem, scip->origprob, scip->transprob,
2679 scip->primal, scip->tree, scip->reopt, scip->lp, scip->relaxation, scip->pricestore, scip->sepastore,
2680 scip->cutpool, scip->delayedcutpool, scip->branchcand, scip->conflict, scip->conflictstore,
2681 scip->eventfilter, scip->eventqueue, scip->cliquetable, &restart) );
2682
2683 /* detect, whether problem is solved */
2684 if( SCIPtreeGetNNodes(scip->tree) == 0 && SCIPtreeGetCurrentNode(scip->tree) == NULL )
2685 {
2686 assert(scip->stat->status == SCIP_STATUS_OPTIMAL
2687 || scip->stat->status == SCIP_STATUS_INFEASIBLE
2688 || scip->stat->status == SCIP_STATUS_UNBOUNDED
2689 || scip->stat->status == SCIP_STATUS_INFORUNBD);
2690 assert(!restart);
2691
2692 /* tree is empty, and no current node exists -> problem is solved */
2693 scip->set->stage = SCIP_STAGE_SOLVED;
2694 }
2695 break;
2696
2697 case SCIP_STAGE_SOLVED:
2698 assert(scip->stat->status == SCIP_STATUS_OPTIMAL
2699 || scip->stat->status == SCIP_STATUS_INFEASIBLE
2700 || scip->stat->status == SCIP_STATUS_UNBOUNDED
2701 || scip->stat->status == SCIP_STATUS_INFORUNBD);
2702
2703 break;
2704
2705 default:
2706 SCIPerrorMessage("invalid SCIP stage <%d>\n", scip->set->stage);
2707 return SCIP_INVALIDCALL;
2708 } /*lint !e788*/
2709 }
2710 while( restart && !SCIPsolveIsStopped(scip->set, scip->stat, TRUE) );
2711
2712 /* we have to store all unprocessed nodes if reoptimization is enabled */
2713 if( scip->set->reopt_enable && scip->set->stage != SCIP_STAGE_PRESOLVING
2714 && SCIPsolveIsStopped(scip->set, scip->stat, TRUE) )
2715 {
2716 /* save unprocessed nodes */
2717 if( SCIPgetNNodesLeft(scip) > 0 )
2718 {
2719 SCIP_NODE** leaves;
2720 SCIP_NODE** children;
2721 SCIP_NODE** siblings;
2722 int nleaves;
2723 int nchildren;
2724 int nsiblings;
2725
2726 /* get all open leave nodes */
2727 SCIP_CALL( SCIPgetLeaves(scip, &leaves, &nleaves) );
2728
2729 /* get all open children nodes */
2730 SCIP_CALL( SCIPgetChildren(scip, &children, &nchildren) );
2731
2732 /* get all open sibling nodes */
2733 SCIP_CALL( SCIPgetSiblings(scip, &siblings, &nsiblings) );
2734
2735 /* add all open node to the reoptimization tree */
2736 SCIP_CALL( SCIPreoptSaveOpenNodes(scip->reopt, scip->set, scip->lp, scip->mem->probmem, leaves, nleaves,
2737 children, nchildren, siblings, nsiblings) );
2738 }
2739 }
2740
2741 /* release the CTRL-C interrupt */
2742 if( scip->set->misc_catchctrlc )
2743 SCIPinterruptRelease(scip->interrupt);
2744
2745 if( scip->set->reopt_enable )
2746 {
2747 /* save found solutions */
2748 int nsols;
2749 int s;
2750
2751 nsols = scip->set->reopt_savesols == -1 ? INT_MAX : MAX(scip->set->reopt_savesols, 1);
2752 nsols = MIN(scip->primal->nsols, nsols);
2753
2754 for( s = 0; s < nsols; s++ )
2755 {
2756 SCIP_SOL* sol;
2757 SCIP_Bool added;
2758
2759 sol = scip->primal->sols[s];
2760 assert(sol != NULL);
2761
2762 if( !SCIPsolIsOriginal(sol) )
2763 {
2764 SCIP_Bool hasinfval;
2765
2766 /* retransform solution into the original problem space */
2767 SCIP_CALL( SCIPsolRetransform(sol, scip->set, scip->stat, scip->origprob, scip->transprob, &hasinfval) );
2768 }
2769
2770 if( SCIPsolGetNodenum(sol) > 0 || SCIPsolGetHeur(sol) != NULL || (s == 0 && scip->set->reopt_sepabestsol) )
2771 {
2772 /* if the best solution should be separated, we must not store it in the solution tree */
2773 if( s == 0 && scip->set->reopt_sepabestsol )
2774 {
2775 SCIP_CALL( SCIPreoptAddOptSol(scip->reopt, sol, scip->mem->probmem, scip->set, scip->stat, scip->origprimal,
2776 scip->origprob->vars, scip->origprob->nvars) );
2777 }
2778 /* add solution to solution tree */
2779 else
2780 {
2781 SCIPdebugMsg(scip, "try to add solution to the solution tree:\n");
2782 SCIPdebug( SCIP_CALL( SCIPsolPrint(sol, scip->set, scip->messagehdlr, scip->stat, scip->origprob, \
2783 scip->transprob, NULL, FALSE, FALSE) ); );
2784
2785 SCIP_CALL( SCIPreoptAddSol(scip->reopt, scip->set, scip->stat, scip->origprimal, scip->mem->probmem,
2786 sol, s == 0, &added, scip->origprob->vars, scip->origprob->nvars, scip->stat->nreoptruns) );
2787 }
2788 }
2789 }
2790
2791 SCIPdebugMsg(scip, "-> saved %d solution.\n", nsols);
2792
2793 /* store variable history */
2794 if( scip->set->reopt_storevarhistory )
2795 {
2796 SCIP_CALL( SCIPreoptUpdateVarHistory(scip->reopt, scip->set, scip->stat, scip->mem->probmem,
2797 scip->origprob->vars, scip->origprob->nvars) );
2798 }
2799 }
2800
2801 /* stop solving timer */
2802 SCIPclockStop(scip->stat->solvingtime, scip->set);
2803 SCIPclockStop(scip->stat->solvingtimeoverall, scip->set);
2804
2805 /* decrease time limit during reoptimization */
2806 if( scip->set->reopt_enable && scip->set->reopt_commontimelimit )
2807 {
2808 SCIP_Real timelimit;
2809 SCIP_Real usedtime;
2810
2811 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
2812 usedtime = SCIPgetSolvingTime(scip);
2813 timelimit = timelimit - usedtime;
2814 timelimit = MAX(0, timelimit);
2815
2816 SCIP_CALL( SCIPsetRealParam(scip, "limits/time", timelimit) );
2817 }
2818
2819 if( !statsprinted )
2820 {
2821 /* display most relevant statistics */
2822 SCIP_CALL( displayRelevantStats(scip) );
2823 }
2824
2825 return SCIP_OKAY;
2826 }
2827
2828 /** transforms, presolves, and solves problem using the configured concurrent solvers
2829 *
2830 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
2831 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
2832 *
2833 * @pre This method can be called if @p scip is in one of the following stages:
2834 * - \ref SCIP_STAGE_PROBLEM
2835 * - \ref SCIP_STAGE_TRANSFORMED
2836 * - \ref SCIP_STAGE_PRESOLVING
2837 * - \ref SCIP_STAGE_PRESOLVED
2838 * - \ref SCIP_STAGE_SOLVING
2839 * - \ref SCIP_STAGE_SOLVED
2840 *
2841 * @post After calling this method \SCIP reaches one of the following stages depending on if and when the solution
2842 * process was interrupted:
2843 * - \ref SCIP_STAGE_PRESOLVING if the solution process was interrupted during presolving
2844 * - \ref SCIP_STAGE_SOLVING if the solution process was interrupted during the tree search
2845 * - \ref SCIP_STAGE_SOLVED if the solving process was not interrupted
2846 *
2847 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
2848 *
2849 * @deprecated Please use SCIPsolveConcurrent() instead.
2850 */
SCIPsolveParallel(SCIP * scip)2851 SCIP_RETCODE SCIPsolveParallel(
2852 SCIP* scip /**< SCIP data structure */
2853 )
2854 {
2855 SCIP_CALL( SCIPcheckStage(scip, "SCIPsolveParallel", FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) );
2856
2857 return SCIPsolveConcurrent(scip);
2858 }
2859
2860 /** transforms, presolves, and solves problem using the configured concurrent solvers
2861 *
2862 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
2863 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
2864 *
2865 * @pre This method can be called if @p scip is in one of the following stages:
2866 * - \ref SCIP_STAGE_PROBLEM
2867 * - \ref SCIP_STAGE_TRANSFORMED
2868 * - \ref SCIP_STAGE_PRESOLVING
2869 * - \ref SCIP_STAGE_PRESOLVED
2870 * - \ref SCIP_STAGE_SOLVING
2871 * - \ref SCIP_STAGE_SOLVED
2872 *
2873 * @post After calling this method \SCIP reaches one of the following stages depending on if and when the solution
2874 * process was interrupted:
2875 * - \ref SCIP_STAGE_PRESOLVING if the solution process was interrupted during presolving
2876 * - \ref SCIP_STAGE_SOLVING if the solution process was interrupted during the tree search
2877 * - \ref SCIP_STAGE_SOLVED if the solving process was not interrupted
2878 *
2879 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
2880 */
SCIPsolveConcurrent(SCIP * scip)2881 SCIP_RETCODE SCIPsolveConcurrent(
2882 SCIP* scip /**< SCIP data structure */
2883 )
2884 {
2885 #ifdef TPI_NONE
2886 SCIPinfoMessage(scip, NULL, "SCIP was compiled without task processing interface. Parallel solve not possible\n");
2887 return SCIP_OKAY;
2888 #else
2889 SCIP_RETCODE retcode;
2890 int i;
2891 SCIP_RANDNUMGEN* rndgen;
2892 int minnthreads;
2893 int maxnthreads;
2894
2895 SCIP_CALL( SCIPcheckStage(scip, "SCIPsolveConcurrent", FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) );
2896
2897 SCIP_CALL( SCIPsetIntParam(scip, "timing/clocktype", SCIP_CLOCKTYPE_WALL) );
2898
2899 minnthreads = scip->set->parallel_minnthreads;
2900 maxnthreads = scip->set->parallel_maxnthreads;
2901
2902 if( minnthreads > maxnthreads )
2903 {
2904 SCIPerrorMessage("minimum number of threads greater than maximum number of threads\n");
2905 return SCIP_INVALIDDATA;
2906 }
2907 if( scip->concurrent == NULL )
2908 {
2909 int nconcsolvertypes;
2910 SCIP_CONCSOLVERTYPE** concsolvertypes;
2911 SCIP_Longint nthreads;
2912 SCIP_Real memorylimit;
2913 int* solvertypes;
2914 SCIP_Longint* weights;
2915 SCIP_Real* prios;
2916 int ncandsolvertypes;
2917 SCIP_Real prefpriosum;
2918
2919 /* check if concurrent solve is configured to presolve the problem
2920 * before setting up the concurrent solvers
2921 */
2922 if( scip->set->concurrent_presolvebefore )
2923 {
2924 /* if yes, then presolve the problem */
2925 SCIP_CALL( SCIPpresolve(scip) );
2926 if( SCIPgetStatus(scip) >= SCIP_STATUS_OPTIMAL )
2927 return SCIP_OKAY;
2928 }
2929 else
2930 {
2931 SCIP_Bool infeas;
2932
2933 /* if not, transform the problem and switch stage to presolved */
2934 SCIP_CALL( SCIPtransformProb(scip) );
2935 SCIP_CALL( initPresolve(scip) );
2936 SCIP_CALL( exitPresolve(scip, TRUE, &infeas) );
2937 assert(!infeas);
2938 }
2939
2940 /* the presolving must have run into a limit, so we stop here */
2941 if( scip->set->stage < SCIP_STAGE_PRESOLVED )
2942 {
2943 SCIP_CALL( displayRelevantStats(scip) );
2944 return SCIP_OKAY;
2945 }
2946
2947 nthreads = INT_MAX;
2948 /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
2949 memorylimit = scip->set->limit_memory;
2950 if( memorylimit < SCIP_MEM_NOLIMIT )
2951 {
2952 memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
2953 memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
2954 /* estimate maximum number of copies that be created based on memory limit */
2955 nthreads = MAX(1, memorylimit / (4.0*SCIPgetMemExternEstim(scip)/1048576.0));
2956 SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "estimated a maximum of %lli threads based on memory limit\n", nthreads);
2957 }
2958 nconcsolvertypes = SCIPgetNConcsolverTypes(scip);
2959 concsolvertypes = SCIPgetConcsolverTypes(scip);
2960
2961 if( minnthreads > nthreads )
2962 {
2963 SCIP_CALL( initSolve(scip, TRUE) );
2964 scip->stat->status = SCIP_STATUS_MEMLIMIT;
2965 SCIPsyncstoreSetSolveIsStopped(SCIPgetSyncstore(scip), TRUE);
2966 SCIPwarningMessage(scip, "requested minimum number of threads could not be satisfied with given memory limit\n");
2967 SCIP_CALL( displayRelevantStats(scip) );
2968 return SCIP_OKAY;
2969 }
2970
2971 if( nthreads == 1 )
2972 {
2973 SCIPwarningMessage(scip, "can only use 1 thread, doing sequential solve instead\n");
2974 SCIP_CALL( SCIPfreeConcurrent(scip) );
2975 return SCIPsolve(scip);
2976 }
2977 nthreads = MIN(nthreads, maxnthreads);
2978 SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "using %lli threads for concurrent solve\n", nthreads);
2979
2980 /* now set up nthreads many concurrent solvers that will be used for the concurrent solve
2981 * using the preferred priorities of each concurrent solver
2982 */
2983 prefpriosum = 0.0;
2984 for( i = 0; i < nconcsolvertypes; ++i )
2985 prefpriosum += SCIPconcsolverTypeGetPrefPrio(concsolvertypes[i]);
2986
2987 ncandsolvertypes = 0;
2988 SCIP_CALL( SCIPallocBufferArray(scip, &solvertypes, nthreads + nconcsolvertypes) );
2989 SCIP_CALL( SCIPallocBufferArray(scip, &weights, nthreads + nconcsolvertypes) );
2990 SCIP_CALL( SCIPallocBufferArray(scip, &prios, nthreads + nconcsolvertypes) );
2991 for( i = 0; i < nconcsolvertypes; ++i )
2992 {
2993 int j;
2994 SCIP_Real prio;
2995 prio = nthreads * SCIPconcsolverTypeGetPrefPrio(concsolvertypes[i]) / prefpriosum;
2996 while( prio > 0.0 )
2997 {
2998 j = ncandsolvertypes++;
2999 assert(j < 2*nthreads);
3000 weights[j] = 1;
3001 solvertypes[j] = i;
3002 prios[j] = MIN(1.0, prio);
3003 prio = prio - 1.0;
3004 }
3005 }
3006 /* select nthreads many concurrent solver types to create instances
3007 * according to the preferred prioriteis the user has set
3008 * This basically corresponds to a knapsack problem
3009 * with unit weights and capacity nthreads, where the profits are
3010 * the unrounded fraction of the total number of threads to be used.
3011 */
3012 SCIPselectDownRealInt(prios, solvertypes, nthreads, ncandsolvertypes);
3013
3014 SCIP_CALL( SCIPcreateRandom(scip, &rndgen, (unsigned) scip->set->concurrent_initseed, TRUE) );
3015 for( i = 0; i < nthreads; ++i )
3016 {
3017 SCIP_CONCSOLVER* concsolver;
3018
3019 SCIP_CALL( SCIPconcsolverCreateInstance(scip->set, concsolvertypes[solvertypes[i]], &concsolver) );
3020 if( scip->set->concurrent_changeseeds && SCIPgetNConcurrentSolvers(scip) > 1 )
3021 SCIP_CALL( SCIPconcsolverInitSeeds(concsolver, SCIPrandomGetInt(rndgen, 0, INT_MAX)) );
3022 }
3023 SCIPfreeRandom(scip, &rndgen);
3024 SCIPfreeBufferArray(scip, &prios);
3025 SCIPfreeBufferArray(scip, &weights);
3026 SCIPfreeBufferArray(scip, &solvertypes);
3027
3028 assert(SCIPgetNConcurrentSolvers(scip) == nthreads);
3029
3030 SCIP_CALL( SCIPsyncstoreInit(scip) );
3031 }
3032
3033 if( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVED )
3034 {
3035 /* switch stage to solving */
3036 SCIP_CALL( initSolve(scip, TRUE) );
3037 }
3038
3039 SCIPclockStart(scip->stat->solvingtime, scip->set);
3040 retcode = SCIPconcurrentSolve(scip);
3041 SCIPclockStop(scip->stat->solvingtime, scip->set);
3042 SCIP_CALL( displayRelevantStats(scip) );
3043
3044 return retcode;
3045 #endif
3046 }
3047
3048 /** include specific heuristics and branching rules for reoptimization
3049 *
3050 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
3051 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
3052 *
3053 * @pre This method can be called if @p scip is in one of the following stages:
3054 * - \ref SCIP_STAGE_PROBLEM
3055 */
SCIPenableReoptimization(SCIP * scip,SCIP_Bool enable)3056 SCIP_RETCODE SCIPenableReoptimization(
3057 SCIP* scip, /**< SCIP data structure */
3058 SCIP_Bool enable /**< enable reoptimization (TRUE) or disable it (FALSE) */
3059 )
3060 {
3061 assert(scip != NULL);
3062
3063 /* we want to skip if nothing has changed */
3064 if( (enable && scip->set->reopt_enable && scip->reopt != NULL)
3065 || (!enable && !scip->set->reopt_enable && scip->reopt == NULL) )
3066 return SCIP_OKAY;
3067
3068 /* check stage and throw an error if we try to disable reoptimization during the solving process.
3069 *
3070 * @note the case that we will disable the reoptimization and have already performed presolving can only happen if
3071 * we are try to solve a general MIP
3072 *
3073 * @note this fix is only for the bugfix release 3.2.1, in the next major release reoptimization can be used for
3074 * general MIPs, too.
3075 */
3076 if( scip->set->stage > SCIP_STAGE_PROBLEM && !(!enable && scip->set->stage == SCIP_STAGE_PRESOLVED) )
3077 {
3078 SCIPerrorMessage("Reoptimization cannot be %s after starting the (pre)solving process.\n", enable ? "enabled" : "disabled");
3079 return SCIP_INVALIDCALL;
3080 }
3081
3082 /* if the current stage is SCIP_STAGE_PROBLEM we have to include the heuristics and branching rule */
3083 if( scip->set->stage == SCIP_STAGE_PROBLEM || (!enable && scip->set->stage == SCIP_STAGE_PRESOLVED) )
3084 {
3085 /* initialize all reoptimization data structures */
3086 if( enable && scip->reopt == NULL )
3087 {
3088 /* set enable flag */
3089 scip->set->reopt_enable = enable;
3090
3091 SCIP_CALL( SCIPreoptCreate(&scip->reopt, scip->set, scip->mem->probmem) );
3092 SCIP_CALL( SCIPsetSetReoptimizationParams(scip->set, scip->messagehdlr) );
3093 }
3094 /* disable all reoptimization plugins and free the structure if necessary */
3095 else if( (!enable && scip->reopt != NULL) || (!enable && scip->set->reopt_enable && scip->reopt == NULL) )
3096 {
3097 /* set enable flag */
3098 scip->set->reopt_enable = enable;
3099
3100 if( scip->reopt != NULL )
3101 {
3102 SCIP_CALL( SCIPreoptFree(&(scip->reopt), scip->set, scip->origprimal, scip->mem->probmem) );
3103 assert(scip->reopt == NULL);
3104 }
3105 SCIP_CALL( SCIPsetSetReoptimizationParams(scip->set, scip->messagehdlr) );
3106 }
3107 }
3108 else
3109 {
3110 /* set enable flag */
3111 scip->set->reopt_enable = enable;
3112 }
3113
3114 return SCIP_OKAY;
3115 }
3116
3117 /** save bound change based on dual information in the reoptimization tree
3118 *
3119 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
3120 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
3121 *
3122 * @pre This method can be called if @p scip is in one of the following stages:
3123 * - \ref SCIP_STAGE_SOLVING
3124 * - \ref SCIP_STAGE_SOLVED
3125 */
SCIPaddReoptDualBndchg(SCIP * scip,SCIP_NODE * node,SCIP_VAR * var,SCIP_Real newbound,SCIP_Real oldbound)3126 SCIP_RETCODE SCIPaddReoptDualBndchg(
3127 SCIP* scip, /**< SCIP data structure */
3128 SCIP_NODE* node, /**< node of the search tree */
3129 SCIP_VAR* var, /**< variable whose bound changed */
3130 SCIP_Real newbound, /**< new bound of the variable */
3131 SCIP_Real oldbound /**< old bound of the variable */
3132 )
3133 {
3134 SCIP_CALL( SCIPcheckStage(scip, "SCIPaddReoptDualBndchg", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) );
3135
3136 assert(SCIPsetIsFeasLT(scip->set, newbound, oldbound) || SCIPsetIsFeasGT(scip->set, newbound, oldbound));
3137
3138 SCIP_CALL( SCIPreoptAddDualBndchg(scip->reopt, scip->set, scip->mem->probmem, node, var, newbound, oldbound) );
3139
3140 return SCIP_OKAY;
3141 }
3142
3143 /** returns the optimal solution of the last iteration or NULL of none exists */
SCIPgetReoptLastOptSol(SCIP * scip)3144 SCIP_SOL* SCIPgetReoptLastOptSol(
3145 SCIP* scip /**< SCIP data structure */
3146 )
3147 {
3148 SCIP_SOL* sol;
3149
3150 assert(scip != NULL);
3151
3152 sol = NULL;
3153
3154 if( scip->set->reopt_enable && scip->stat->nreoptruns > 1 )
3155 {
3156 sol = SCIPreoptGetLastBestSol(scip->reopt);
3157 }
3158
3159 return sol;
3160 }
3161
3162 /** returns the objective coefficent of a given variable in a previous iteration
3163 *
3164 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
3165 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
3166 *
3167 * @pre This method can be called if @p scip is in one of the following stages:
3168 * - \ref SCIP_STAGE_PRESOLVING
3169 * - \ref SCIP_STAGE_SOLVING
3170 */
SCIPgetReoptOldObjCoef(SCIP * scip,SCIP_VAR * var,int run,SCIP_Real * objcoef)3171 SCIP_RETCODE SCIPgetReoptOldObjCoef(
3172 SCIP* scip, /**< SCIP data structure */
3173 SCIP_VAR* var, /**< variable */
3174 int run, /**< number of the run */
3175 SCIP_Real* objcoef /**< pointer to store the objective coefficient */
3176 )
3177 {
3178 assert(scip != NULL);
3179 assert(var != NULL);
3180 assert(0 < run && run <= scip->stat->nreoptruns);
3181
3182 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetReoptOldObjCoef", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
3183
3184 if( SCIPvarIsOriginal(var) )
3185 *objcoef = SCIPreoptGetOldObjCoef(scip->reopt, run, SCIPvarGetIndex(var));
3186 else
3187 {
3188 SCIP_VAR* origvar;
3189 SCIP_Real constant;
3190 SCIP_Real scalar;
3191
3192 assert(SCIPvarIsActive(var));
3193
3194 origvar = var;
3195 constant = 0.0;
3196 scalar = 1.0;
3197
3198 SCIP_CALL( SCIPvarGetOrigvarSum(&origvar, &scalar, &constant) );
3199 assert(origvar != NULL);
3200 assert(SCIPvarIsOriginal(origvar));
3201
3202 *objcoef = SCIPreoptGetOldObjCoef(scip->reopt, run, SCIPvarGetIndex(origvar));
3203 }
3204 return SCIP_OKAY;
3205 }
3206
3207 /** frees branch and bound tree and all solution process data; statistics, presolving data and transformed problem is
3208 * preserved
3209 *
3210 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
3211 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
3212 *
3213 * @pre This method can be called if @p scip is in one of the following stages:
3214 * - \ref SCIP_STAGE_INIT
3215 * - \ref SCIP_STAGE_PROBLEM
3216 * - \ref SCIP_STAGE_TRANSFORMED
3217 * - \ref SCIP_STAGE_PRESOLVING
3218 * - \ref SCIP_STAGE_PRESOLVED
3219 * - \ref SCIP_STAGE_SOLVING
3220 * - \ref SCIP_STAGE_SOLVED
3221 *
3222 * @post If this method is called in \SCIP stage \ref SCIP_STAGE_INIT or \ref SCIP_STAGE_PROBLEM, the stage of
3223 * \SCIP is not changed; otherwise, the \SCIP stage is changed to \ref SCIP_STAGE_TRANSFORMED
3224 *
3225 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
3226 */
SCIPfreeSolve(SCIP * scip,SCIP_Bool restart)3227 SCIP_RETCODE SCIPfreeSolve(
3228 SCIP* scip, /**< SCIP data structure */
3229 SCIP_Bool restart /**< should certain data be preserved for improved restarting? */
3230 )
3231 {
3232 SCIP_CALL( SCIPcheckStage(scip, "SCIPfreeSolve", TRUE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) );
3233
3234 switch( scip->set->stage )
3235 {
3236 case SCIP_STAGE_INIT:
3237 case SCIP_STAGE_TRANSFORMED:
3238 case SCIP_STAGE_PROBLEM:
3239 return SCIP_OKAY;
3240
3241 case SCIP_STAGE_PRESOLVING:
3242 {
3243 SCIP_Bool infeasible;
3244
3245 assert(scip->stat->status != SCIP_STATUS_INFEASIBLE);
3246 assert(scip->stat->status != SCIP_STATUS_INFORUNBD);
3247 assert(scip->stat->status != SCIP_STATUS_UNBOUNDED);
3248 assert(scip->stat->status != SCIP_STATUS_OPTIMAL);
3249
3250 /* exit presolving */
3251 SCIP_CALL( exitPresolve(scip, FALSE, &infeasible) );
3252 assert(scip->set->stage == SCIP_STAGE_PRESOLVED);
3253 }
3254
3255 /*lint -fallthrough*/
3256 case SCIP_STAGE_PRESOLVED:
3257 /* switch stage to TRANSFORMED */
3258 scip->set->stage = SCIP_STAGE_TRANSFORMED;
3259 return SCIP_OKAY;
3260
3261 case SCIP_STAGE_SOLVING:
3262 case SCIP_STAGE_SOLVED:
3263 /* free solution process data structures */
3264 SCIP_CALL( freeSolve(scip, restart) );
3265 assert(scip->set->stage == SCIP_STAGE_TRANSFORMED);
3266 return SCIP_OKAY;
3267
3268 default:
3269 SCIPerrorMessage("invalid SCIP stage <%d>\n", scip->set->stage);
3270 return SCIP_INVALIDCALL;
3271 } /*lint !e788*/
3272 }
3273
3274 /** frees branch and bound tree and all solution process data; statistics, presolving data and transformed problem is
3275 * preserved
3276 *
3277 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
3278 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
3279 *
3280 * @pre This method can be called if @p scip is in one of the following stages:
3281 * - \ref SCIP_STAGE_INIT
3282 * - \ref SCIP_STAGE_PROBLEM
3283 * - \ref SCIP_STAGE_TRANSFORMED
3284 * - \ref SCIP_STAGE_PRESOLVING
3285 * - \ref SCIP_STAGE_PRESOLVED
3286 * - \ref SCIP_STAGE_SOLVING
3287 * - \ref SCIP_STAGE_SOLVED
3288 *
3289 * @post If this method is called in \SCIP stage \ref SCIP_STAGE_INIT, \ref SCIP_STAGE_TRANSFORMED or \ref SCIP_STAGE_PROBLEM,
3290 * the stage of \SCIP is not changed; otherwise, the \SCIP stage is changed to \ref SCIP_STAGE_PRESOLVED.
3291 *
3292 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
3293 */
SCIPfreeReoptSolve(SCIP * scip)3294 SCIP_RETCODE SCIPfreeReoptSolve(
3295 SCIP* scip /**< SCIP data structure */
3296 )
3297 {
3298 SCIP_CALL( SCIPcheckStage(scip, "SCIPfreeReoptSolve", TRUE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) );
3299
3300 switch( scip->set->stage )
3301 {
3302 case SCIP_STAGE_INIT:
3303 case SCIP_STAGE_TRANSFORMED:
3304 case SCIP_STAGE_PRESOLVED:
3305 case SCIP_STAGE_PROBLEM:
3306 return SCIP_OKAY;
3307
3308 case SCIP_STAGE_PRESOLVING:
3309 {
3310 SCIP_Bool infeasible;
3311
3312 assert(scip->stat->status != SCIP_STATUS_INFEASIBLE);
3313 assert(scip->stat->status != SCIP_STATUS_INFORUNBD);
3314 assert(scip->stat->status != SCIP_STATUS_UNBOUNDED);
3315 assert(scip->stat->status != SCIP_STATUS_OPTIMAL);
3316
3317 /* exit presolving */
3318 SCIP_CALL( exitPresolve(scip, FALSE, &infeasible) );
3319 assert(scip->set->stage == SCIP_STAGE_PRESOLVED);
3320
3321 return SCIP_OKAY;
3322 }
3323
3324 case SCIP_STAGE_SOLVING:
3325 case SCIP_STAGE_SOLVED:
3326 /* free solution process data structures */
3327 SCIP_CALL( freeReoptSolve(scip) );
3328 assert(scip->set->stage == SCIP_STAGE_PRESOLVED);
3329 return SCIP_OKAY;
3330
3331 default:
3332 SCIPerrorMessage("invalid SCIP stage <%d>\n", scip->set->stage);
3333 return SCIP_INVALIDCALL;
3334 } /*lint !e788*/
3335 }
3336
3337 /** frees all solution process data including presolving and transformed problem, only original problem is kept
3338 *
3339 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
3340 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
3341 *
3342 * @pre This method can be called if @p scip is in one of the following stages:
3343 * - \ref SCIP_STAGE_INIT
3344 * - \ref SCIP_STAGE_PROBLEM
3345 * - \ref SCIP_STAGE_TRANSFORMED
3346 * - \ref SCIP_STAGE_PRESOLVING
3347 * - \ref SCIP_STAGE_PRESOLVED
3348 * - \ref SCIP_STAGE_SOLVING
3349 * - \ref SCIP_STAGE_SOLVED
3350 *
3351 * @post After calling this method \SCIP reaches one of the following stages:
3352 * - \ref SCIP_STAGE_INIT if the method was called from \SCIP stage \ref SCIP_STAGE_INIT
3353 * - \ref SCIP_STAGE_PROBLEM if the method was called from any other of the allowed stages
3354 *
3355 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
3356 */
SCIPfreeTransform(SCIP * scip)3357 SCIP_RETCODE SCIPfreeTransform(
3358 SCIP* scip /**< SCIP data structure */
3359 )
3360 {
3361 SCIP_CALL( SCIPcheckStage(scip, "SCIPfreeTransform", TRUE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) );
3362
3363 /* release variables and constraints captured by reoptimization */
3364 if( scip->reopt != NULL )
3365 {
3366 SCIP_CALL( SCIPreoptReleaseData(scip->reopt, scip->set, scip->mem->probmem) );
3367 }
3368
3369 switch( scip->set->stage )
3370 {
3371 case SCIP_STAGE_INIT:
3372 case SCIP_STAGE_PROBLEM:
3373 return SCIP_OKAY;
3374
3375 case SCIP_STAGE_PRESOLVING:
3376 {
3377 SCIP_Bool infeasible;
3378
3379 assert(scip->stat->status != SCIP_STATUS_INFEASIBLE);
3380 assert(scip->stat->status != SCIP_STATUS_INFORUNBD);
3381 assert(scip->stat->status != SCIP_STATUS_UNBOUNDED);
3382 assert(scip->stat->status != SCIP_STATUS_OPTIMAL);
3383
3384 /* exit presolving */
3385 SCIP_CALL( exitPresolve(scip, FALSE, &infeasible) );
3386 assert(scip->set->stage == SCIP_STAGE_PRESOLVED);
3387 }
3388
3389 /*lint -fallthrough*/
3390 case SCIP_STAGE_PRESOLVED:
3391 case SCIP_STAGE_SOLVING:
3392 case SCIP_STAGE_SOLVED:
3393 /* the solve was already freed, we directly go to freeTransform() */
3394 if( !scip->set->reopt_enable || scip->set->stage != SCIP_STAGE_PRESOLVED )
3395 {
3396 /* free solution process data */
3397 SCIP_CALL( SCIPfreeSolve(scip, FALSE) );
3398 assert(scip->set->stage == SCIP_STAGE_TRANSFORMED);
3399 }
3400 /*lint -fallthrough*/
3401
3402 case SCIP_STAGE_TRANSFORMED:
3403 /* free transformed problem data structures */
3404 SCIP_CALL( freeTransform(scip) );
3405 assert(scip->set->stage == SCIP_STAGE_PROBLEM);
3406 return SCIP_OKAY;
3407
3408 default:
3409 SCIPerrorMessage("invalid SCIP stage <%d>\n", scip->set->stage);
3410 return SCIP_INVALIDCALL;
3411 } /*lint !e788*/
3412 }
3413
3414 /** informs \SCIP that the solving process should be interrupted as soon as possible (e.g., after the current node has
3415 * been solved)
3416 *
3417 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
3418 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
3419 *
3420 * @pre This method can be called if @p scip is in one of the following stages:
3421 * - \ref SCIP_STAGE_PROBLEM
3422 * - \ref SCIP_STAGE_TRANSFORMING
3423 * - \ref SCIP_STAGE_TRANSFORMED
3424 * - \ref SCIP_STAGE_INITPRESOLVE
3425 * - \ref SCIP_STAGE_PRESOLVING
3426 * - \ref SCIP_STAGE_EXITPRESOLVE
3427 * - \ref SCIP_STAGE_PRESOLVED
3428 * - \ref SCIP_STAGE_SOLVING
3429 * - \ref SCIP_STAGE_SOLVED
3430 * - \ref SCIP_STAGE_EXITSOLVE
3431 * - \ref SCIP_STAGE_FREETRANS
3432 *
3433 * @note the \SCIP stage does not get changed
3434 */
SCIPinterruptSolve(SCIP * scip)3435 SCIP_RETCODE SCIPinterruptSolve(
3436 SCIP* scip /**< SCIP data structure */
3437 )
3438 {
3439 SCIP_CALL( SCIPcheckStage(scip, "SCIPinterruptSolve", FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, TRUE, TRUE, TRUE, TRUE, FALSE) );
3440
3441 /* set the userinterrupt flag */
3442 scip->stat->userinterrupt = TRUE;
3443
3444 return SCIP_OKAY;
3445 }
3446
3447 /** informs SCIP that the solving process should be restarted as soon as possible (e.g., after the current node has
3448 * been solved)
3449 *
3450 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
3451 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
3452 *
3453 * @pre This method can be called if @p scip is in one of the following stages:
3454 * - \ref SCIP_STAGE_INITPRESOLVE
3455 * - \ref SCIP_STAGE_PRESOLVING
3456 * - \ref SCIP_STAGE_EXITPRESOLVE
3457 * - \ref SCIP_STAGE_SOLVING
3458 *
3459 * @note the \SCIP stage does not get changed
3460 */
SCIPrestartSolve(SCIP * scip)3461 SCIP_RETCODE SCIPrestartSolve(
3462 SCIP* scip /**< SCIP data structure */
3463 )
3464 {
3465 SCIP_CALL( SCIPcheckStage(scip, "SCIPrestartSolve", FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
3466
3467 /* set the userrestart flag */
3468 scip->stat->userrestart = TRUE;
3469
3470 return SCIP_OKAY;
3471 }
3472
3473 /** returns whether reoptimization is enabled or not */
SCIPisReoptEnabled(SCIP * scip)3474 SCIP_Bool SCIPisReoptEnabled(
3475 SCIP* scip /**< SCIP data structure */
3476 )
3477 {
3478 assert(scip != NULL);
3479
3480 return scip->set->reopt_enable;
3481 }
3482
3483 /** returns the stored solutions corresponding to a given run */
SCIPgetReoptSolsRun(SCIP * scip,int run,SCIP_SOL ** sols,int solssize,int * nsols)3484 SCIP_RETCODE SCIPgetReoptSolsRun(
3485 SCIP* scip, /**< SCIP data structure */
3486 int run, /**< number of the run */
3487 SCIP_SOL** sols, /**< array to store solutions */
3488 int solssize, /**< size of the array */
3489 int* nsols /**< pointer to store number of solutions */
3490 )
3491 {
3492 assert(scip != NULL);
3493 assert(sols != NULL);
3494 assert(solssize > 0);
3495
3496 if( scip->set->reopt_enable )
3497 {
3498 assert(run > 0 && run <= scip->stat->nreoptruns);
3499 SCIP_CALL( SCIPreoptGetSolsRun(scip->reopt, run, sols, solssize, nsols) );
3500 }
3501 else
3502 {
3503 *nsols = 0;
3504 }
3505
3506 return SCIP_OKAY;
3507 }
3508
3509 /** mark all stored solutions as not updated */
SCIPresetReoptSolMarks(SCIP * scip)3510 void SCIPresetReoptSolMarks(
3511 SCIP* scip /**< SCIP data structure */
3512 )
3513 {
3514 assert(scip != NULL);
3515 assert(scip->set->reopt_enable);
3516 assert(scip->reopt != NULL);
3517
3518 if( scip->set->reopt_enable )
3519 {
3520 assert(scip->reopt != NULL);
3521 SCIPreoptResetSolMarks(scip->reopt);
3522 }
3523 }
3524
3525 /** check if the reoptimization process should be restarted
3526 *
3527 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
3528 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
3529 *
3530 * @pre This method can be called if @p scip is in one of the following stages:
3531 * - \ref SCIP_STAGE_TRANSFORMED
3532 * - \ref SCIP_STAGE_SOLVING
3533 */
SCIPcheckReoptRestart(SCIP * scip,SCIP_NODE * node,SCIP_Bool * restart)3534 SCIP_RETCODE SCIPcheckReoptRestart(
3535 SCIP* scip, /**< SCIP data structure */
3536 SCIP_NODE* node, /**< current node of the branch and bound tree (or NULL) */
3537 SCIP_Bool* restart /**< pointer to store of the reoptimitation process should be restarted */
3538 )
3539 {
3540 assert(scip != NULL);
3541 assert(scip->set->reopt_enable);
3542 assert(scip->reopt != NULL);
3543
3544 SCIP_CALL( SCIPcheckStage(scip, "SCIPcheckReoptRestart", FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
3545
3546 SCIP_CALL( SCIPreoptCheckRestart(scip->reopt, scip->set, scip->mem->probmem, node, scip->transprob->vars,
3547 scip->transprob->nvars, restart) );
3548
3549 return SCIP_OKAY;
3550 }
3551
3552 /** returns whether we are in the restarting phase
3553 *
3554 * @return TRUE, if we are in the restarting phase; FALSE, otherwise
3555 *
3556 * @pre This method can be called if @p scip is in one of the following stages:
3557 * - \ref SCIP_STAGE_INITPRESOLVE
3558 * - \ref SCIP_STAGE_PRESOLVING
3559 * - \ref SCIP_STAGE_EXITPRESOLVE
3560 * - \ref SCIP_STAGE_PRESOLVED
3561 * - \ref SCIP_STAGE_INITSOLVE
3562 * - \ref SCIP_STAGE_SOLVING
3563 * - \ref SCIP_STAGE_SOLVED
3564 * - \ref SCIP_STAGE_EXITSOLVE
3565 * - \ref SCIP_STAGE_FREETRANS
3566 */
SCIPisInRestart(SCIP * scip)3567 SCIP_Bool SCIPisInRestart(
3568 SCIP* scip /**< SCIP data structure */
3569 )
3570 {
3571 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPisInRestart", FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE) );
3572
3573 /* return the restart status */
3574 return scip->stat->inrestart;
3575 }
3576