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