1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file primal.c
17 * @ingroup OTHER_CFILES
18 * @brief methods for collecting primal CIP solutions and primal informations
19 * @author Tobias Achterberg
20 */
21
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23
24 #include <assert.h>
25
26 #include "scip/def.h"
27 #include "scip/set.h"
28 #include "scip/stat.h"
29 #include "scip/visual.h"
30 #include "scip/event.h"
31 #include "scip/lp.h"
32 #include "scip/var.h"
33 #include "scip/prob.h"
34 #include "scip/sol.h"
35 #include "scip/primal.h"
36 #include "scip/tree.h"
37 #include "scip/reopt.h"
38 #include "scip/disp.h"
39 #include "scip/struct_event.h"
40 #include "scip/pub_message.h"
41 #include "scip/pub_var.h"
42 #include "scip/scip_solvingstats.h"
43
44
45 /*
46 * memory growing methods for dynamically allocated arrays
47 */
48
49 /** ensures, that sols array can store at least num entries */
50 static
ensureSolsSize(SCIP_PRIMAL * primal,SCIP_SET * set,int num)51 SCIP_RETCODE ensureSolsSize(
52 SCIP_PRIMAL* primal, /**< primal data */
53 SCIP_SET* set, /**< global SCIP settings */
54 int num /**< minimum number of entries to store */
55 )
56 {
57 assert(primal->nsols <= primal->solssize);
58
59 if( num > primal->solssize )
60 {
61 int newsize;
62
63 newsize = SCIPsetCalcMemGrowSize(set, num);
64 SCIP_ALLOC( BMSreallocMemoryArray(&primal->sols, newsize) );
65 primal->solssize = newsize;
66 }
67 assert(num <= primal->solssize);
68
69 return SCIP_OKAY;
70 }
71
72 /** ensures, that partialsols array can store at least num entries */
73 static
ensurePartialsolsSize(SCIP_PRIMAL * primal,SCIP_SET * set,int num)74 SCIP_RETCODE ensurePartialsolsSize(
75 SCIP_PRIMAL* primal, /**< primal data */
76 SCIP_SET* set, /**< global SCIP settings */
77 int num /**< minimum number of entries to store */
78 )
79 {
80 assert(primal->npartialsols <= primal->partialsolssize);
81
82 if( num > primal->partialsolssize )
83 {
84 int newsize;
85
86 newsize = SCIPsetCalcMemGrowSize(set, num);
87 newsize = MIN(newsize, set->limit_maxorigsol);
88
89 SCIP_ALLOC( BMSreallocMemoryArray(&primal->partialsols, newsize) );
90 primal->partialsolssize = newsize;
91 }
92 assert(num <= primal->partialsolssize);
93
94 return SCIP_OKAY;
95 }
96
97 /** ensures, that existingsols array can store at least num entries */
98 static
ensureExistingsolsSize(SCIP_PRIMAL * primal,SCIP_SET * set,int num)99 SCIP_RETCODE ensureExistingsolsSize(
100 SCIP_PRIMAL* primal, /**< primal data */
101 SCIP_SET* set, /**< global SCIP settings */
102 int num /**< minimum number of entries to store */
103 )
104 {
105 assert(primal->nexistingsols <= primal->existingsolssize);
106
107 if( num > primal->existingsolssize )
108 {
109 int newsize;
110
111 newsize = SCIPsetCalcMemGrowSize(set, num);
112 SCIP_ALLOC( BMSreallocMemoryArray(&primal->existingsols, newsize) );
113 primal->existingsolssize = newsize;
114 }
115 assert(num <= primal->existingsolssize);
116
117 return SCIP_OKAY;
118 }
119
120 /** creates primal data */
SCIPprimalCreate(SCIP_PRIMAL ** primal)121 SCIP_RETCODE SCIPprimalCreate(
122 SCIP_PRIMAL** primal /**< pointer to primal data */
123 )
124 {
125 assert(primal != NULL);
126
127 SCIP_ALLOC( BMSallocMemory(primal) );
128 (*primal)->sols = NULL;
129 (*primal)->partialsols = NULL;
130 (*primal)->existingsols = NULL;
131 (*primal)->currentsol = NULL;
132 (*primal)->primalray = NULL;
133 (*primal)->solssize = 0;
134 (*primal)->partialsolssize = 0;
135 (*primal)->nsols = 0;
136 (*primal)->npartialsols = 0;
137 (*primal)->existingsolssize = 0;
138 (*primal)->nexistingsols = 0;
139 (*primal)->nsolsfound = 0;
140 (*primal)->nlimsolsfound = 0;
141 (*primal)->nbestsolsfound = 0;
142 (*primal)->nlimbestsolsfound = 0;
143 (*primal)->upperbound = SCIP_INVALID;
144 (*primal)->cutoffbound = SCIP_INVALID;
145 (*primal)->updateviolations = TRUE;
146
147 return SCIP_OKAY;
148 }
149
150 /** frees primal data */
SCIPprimalFree(SCIP_PRIMAL ** primal,BMS_BLKMEM * blkmem)151 SCIP_RETCODE SCIPprimalFree(
152 SCIP_PRIMAL** primal, /**< pointer to primal data */
153 BMS_BLKMEM* blkmem /**< block memory */
154 )
155 {
156 int s;
157
158 assert(primal != NULL);
159 assert(*primal != NULL);
160
161 /* free temporary solution for storing current solution */
162 if( (*primal)->currentsol != NULL )
163 {
164 SCIP_CALL( SCIPsolFree(&(*primal)->currentsol, blkmem, *primal) );
165 }
166
167 /* free solution for storing primal ray */
168 if( (*primal)->primalray != NULL )
169 {
170 SCIP_CALL( SCIPsolFree(&(*primal)->primalray, blkmem, *primal) );
171 }
172
173 /* free feasible primal CIP solutions */
174 for( s = 0; s < (*primal)->nsols; ++s )
175 {
176 SCIP_CALL( SCIPsolFree(&(*primal)->sols[s], blkmem, *primal) );
177 }
178 /* free partial CIP solutions */
179 for( s = 0; s < (*primal)->npartialsols; ++s )
180 {
181 SCIP_CALL( SCIPsolFree(&(*primal)->partialsols[s], blkmem, *primal) );
182 }
183 assert((*primal)->nexistingsols == 0);
184
185 BMSfreeMemoryArrayNull(&(*primal)->sols);
186 BMSfreeMemoryArrayNull(&(*primal)->partialsols);
187 BMSfreeMemoryArrayNull(&(*primal)->existingsols);
188 BMSfreeMemory(primal);
189
190 return SCIP_OKAY;
191 }
192
193 /** clears primal data */
SCIPprimalClear(SCIP_PRIMAL ** primal,BMS_BLKMEM * blkmem)194 SCIP_RETCODE SCIPprimalClear(
195 SCIP_PRIMAL** primal, /**< pointer to primal data */
196 BMS_BLKMEM* blkmem /**< block memory */
197 )
198 {
199 int s;
200
201 assert(primal != NULL);
202 assert(*primal != NULL);
203
204 /* free temporary solution for storing current solution */
205 if( (*primal)->currentsol != NULL )
206 {
207 SCIP_CALL( SCIPsolFree(&(*primal)->currentsol, blkmem, *primal) );
208 }
209
210 /* free solution for storing primal ray */
211 if( (*primal)->primalray != NULL )
212 {
213 SCIP_CALL( SCIPsolFree(&(*primal)->primalray, blkmem, *primal) );
214 }
215
216 /* free feasible primal CIP solutions */
217 for( s = 0; s < (*primal)->nsols; ++s )
218 {
219 SCIP_CALL( SCIPsolFree(&(*primal)->sols[s], blkmem, *primal) );
220 }
221
222 (*primal)->currentsol = NULL;
223 (*primal)->primalray = NULL;
224 (*primal)->nsols = 0;
225 (*primal)->nsolsfound = 0;
226 (*primal)->nlimsolsfound = 0;
227 (*primal)->nbestsolsfound = 0;
228 (*primal)->nlimbestsolsfound = 0;
229 (*primal)->upperbound = SCIP_INVALID;
230 (*primal)->cutoffbound = SCIP_INVALID;
231 (*primal)->updateviolations = TRUE;
232
233 return SCIP_OKAY;
234 }
235
236 /** sorts primal solutions by objective value */
237 static
sortPrimalSols(SCIP_PRIMAL * primal,SCIP_SET * set,SCIP_PROB * origprob,SCIP_PROB * transprob)238 void sortPrimalSols(
239 SCIP_PRIMAL* primal, /**< primal data */
240 SCIP_SET* set, /**< global SCIP settings */
241 SCIP_PROB* origprob, /**< original problem */
242 SCIP_PROB* transprob /**< transformed problem */
243 )
244 {
245 int i;
246
247 for( i = 1; i < primal->nsols; ++i )
248 {
249 SCIP_SOL* sol;
250 SCIP_Real objval;
251 int j;
252
253 sol = primal->sols[i];
254 objval = SCIPsolGetObj(sol, set, transprob, origprob);
255 for( j = i; j > 0 && objval < SCIPsolGetObj(primal->sols[j-1], set, transprob, origprob); --j )
256 primal->sols[j] = primal->sols[j-1];
257 primal->sols[j] = sol;
258 }
259
260 return;
261 }
262
263 /** sets the cutoff bound in primal data and in LP solver */
264 static
primalSetCutoffbound(SCIP_PRIMAL * primal,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_STAT * stat,SCIP_PROB * prob,SCIP_EVENTFILTER * eventfilter,SCIP_EVENTQUEUE * eventqueue,SCIP_TREE * tree,SCIP_REOPT * reopt,SCIP_LP * lp,SCIP_Real cutoffbound)265 SCIP_RETCODE primalSetCutoffbound(
266 SCIP_PRIMAL* primal, /**< primal data */
267 BMS_BLKMEM* blkmem, /**< block memory */
268 SCIP_SET* set, /**< global SCIP settings */
269 SCIP_STAT* stat, /**< problem statistics data */
270 SCIP_PROB* prob, /**< problem data */
271 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
272 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
273 SCIP_TREE* tree, /**< branch and bound tree */
274 SCIP_REOPT* reopt, /**< reoptimization data structure */
275 SCIP_LP* lp, /**< current LP data */
276 SCIP_Real cutoffbound /**< new cutoff bound */
277 )
278 {
279 assert(primal != NULL);
280 assert(cutoffbound <= SCIPsetInfinity(set));
281 assert(primal->upperbound == SCIP_INVALID || SCIPsetIsLE(set, cutoffbound, primal->upperbound)); /*lint !e777*/
282 assert(!SCIPtreeInRepropagation(tree));
283
284 SCIPsetDebugMsg(set, "changing cutoff bound from %g to %g\n", primal->cutoffbound, cutoffbound);
285
286 primal->cutoffbound = MIN(cutoffbound, primal->upperbound); /* get rid of numerical issues */
287
288 /* set cut off value in LP solver */
289 SCIP_CALL( SCIPlpSetCutoffbound(lp, set, prob, primal->cutoffbound) );
290
291 /* cut off leaves of the tree */
292 SCIP_CALL( SCIPtreeCutoff(tree, reopt, blkmem, set, stat, eventfilter, eventqueue, lp, primal->cutoffbound) );
293
294 return SCIP_OKAY;
295 }
296
297 /** sets the cutoff bound in primal data and in LP solver */
SCIPprimalSetCutoffbound(SCIP_PRIMAL * primal,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_STAT * stat,SCIP_EVENTFILTER * eventfilter,SCIP_EVENTQUEUE * eventqueue,SCIP_PROB * transprob,SCIP_PROB * origprob,SCIP_TREE * tree,SCIP_REOPT * reopt,SCIP_LP * lp,SCIP_Real cutoffbound,SCIP_Bool useforobjlimit)298 SCIP_RETCODE SCIPprimalSetCutoffbound(
299 SCIP_PRIMAL* primal, /**< primal data */
300 BMS_BLKMEM* blkmem, /**< block memory */
301 SCIP_SET* set, /**< global SCIP settings */
302 SCIP_STAT* stat, /**< problem statistics data */
303 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
304 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
305 SCIP_PROB* transprob, /**< transformed problem data */
306 SCIP_PROB* origprob, /**< original problem data */
307 SCIP_TREE* tree, /**< branch and bound tree */
308 SCIP_REOPT* reopt, /**< reoptimization data structure */
309 SCIP_LP* lp, /**< current LP data */
310 SCIP_Real cutoffbound, /**< new cutoff bound */
311 SCIP_Bool useforobjlimit /**< should the cutoff bound be used to update the objective limit, if
312 * better? */
313 )
314 {
315 assert(primal != NULL);
316 assert(cutoffbound <= SCIPsetInfinity(set));
317 assert(cutoffbound <= primal->upperbound);
318 assert(transprob != NULL);
319 assert(origprob != NULL);
320
321 if( cutoffbound < primal->cutoffbound )
322 {
323 if( useforobjlimit )
324 {
325 SCIP_Real objval;
326
327 objval = SCIPprobExternObjval(transprob, origprob, set, cutoffbound);
328
329 if( objval < SCIPprobGetObjlim(origprob, set) )
330 {
331 SCIPsetDebugMsg(set, "changing cutoff bound from %g to %g changes objective limit from %g to %g\n",
332 primal->cutoffbound, cutoffbound, SCIPprobGetObjlim(origprob, set), objval);
333 SCIPprobSetObjlim(origprob, objval);
334 SCIPprobSetObjlim(transprob, objval);
335 }
336 }
337
338 /* update cutoff bound */
339 SCIP_CALL( primalSetCutoffbound(primal, blkmem, set, stat, transprob, eventfilter, eventqueue, tree, reopt, lp, cutoffbound) );
340 }
341 else if( cutoffbound > primal->cutoffbound )
342 {
343 SCIPerrorMessage("invalid increase in cutoff bound\n");
344 return SCIP_INVALIDDATA;
345 }
346
347 return SCIP_OKAY;
348 }
349
350 /** sets upper bound in primal data and in LP solver */
351 static
primalSetUpperbound(SCIP_PRIMAL * primal,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_STAT * stat,SCIP_EVENTFILTER * eventfilter,SCIP_EVENTQUEUE * eventqueue,SCIP_PROB * prob,SCIP_TREE * tree,SCIP_REOPT * reopt,SCIP_LP * lp,SCIP_Real upperbound)352 SCIP_RETCODE primalSetUpperbound(
353 SCIP_PRIMAL* primal, /**< primal data */
354 BMS_BLKMEM* blkmem, /**< block memory */
355 SCIP_SET* set, /**< global SCIP settings */
356 SCIP_STAT* stat, /**< problem statistics data */
357 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
358 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
359 SCIP_PROB* prob, /**< transformed problem after presolve */
360 SCIP_TREE* tree, /**< branch and bound tree */
361 SCIP_REOPT* reopt, /**< reoptimization data structure */
362 SCIP_LP* lp, /**< current LP data */
363 SCIP_Real upperbound /**< new upper bound */
364 )
365 {
366 SCIP_Real cutoffbound;
367
368 assert(primal != NULL);
369 assert(stat != NULL);
370 assert(upperbound <= SCIPsetInfinity(set));
371 assert(upperbound <= primal->upperbound || stat->nnodes == 0);
372
373 SCIPsetDebugMsg(set, "changing upper bound from %g to %g\n", primal->upperbound, upperbound);
374
375 primal->upperbound = upperbound;
376
377 /* if objective value is always integral, the cutoff bound can be reduced to nearly the previous integer number */
378 if( SCIPprobIsObjIntegral(prob) && !SCIPsetIsInfinity(set, upperbound) )
379 {
380 SCIP_Real delta;
381
382 delta = SCIPsetCutoffbounddelta(set);
383
384 cutoffbound = SCIPsetFeasCeil(set, upperbound) - (1.0 - delta);
385 cutoffbound = MIN(cutoffbound, upperbound); /* SCIPsetFeasCeil() can increase bound by almost 1.0 due to numerics
386 * and very large upperbound value */
387 }
388 else
389 cutoffbound = upperbound;
390
391 /* update cutoff bound */
392 if( cutoffbound < primal->cutoffbound )
393 {
394 SCIP_CALL( primalSetCutoffbound(primal, blkmem, set, stat, prob, eventfilter, eventqueue, tree, reopt, lp, cutoffbound) );
395 }
396
397 /* update upper bound in visualization output */
398 if( SCIPtreeGetCurrentDepth(tree) >= 0 )
399 {
400 SCIPvisualUpperbound(stat->visual, set, stat, primal->upperbound);
401 }
402
403 return SCIP_OKAY;
404 }
405
406 /** sets upper bound in primal data and in LP solver */
SCIPprimalSetUpperbound(SCIP_PRIMAL * primal,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_STAT * stat,SCIP_EVENTFILTER * eventfilter,SCIP_EVENTQUEUE * eventqueue,SCIP_PROB * prob,SCIP_TREE * tree,SCIP_REOPT * reopt,SCIP_LP * lp,SCIP_Real upperbound)407 SCIP_RETCODE SCIPprimalSetUpperbound(
408 SCIP_PRIMAL* primal, /**< primal data */
409 BMS_BLKMEM* blkmem, /**< block memory */
410 SCIP_SET* set, /**< global SCIP settings */
411 SCIP_STAT* stat, /**< problem statistics data */
412 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
413 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
414 SCIP_PROB* prob, /**< transformed problem after presolve */
415 SCIP_TREE* tree, /**< branch and bound tree */
416 SCIP_REOPT* reopt, /**< reoptimization data structure */
417 SCIP_LP* lp, /**< current LP data */
418 SCIP_Real upperbound /**< new upper bound */
419 )
420 {
421 assert(primal != NULL);
422 assert(upperbound <= SCIPsetInfinity(set));
423
424 if( upperbound < primal->upperbound )
425 {
426 /* update primal bound */
427 SCIP_CALL( primalSetUpperbound(primal, blkmem, set, stat, eventfilter, eventqueue, prob, tree, reopt, lp, upperbound) );
428 }
429 else if( upperbound > primal->upperbound )
430 {
431 SCIPerrorMessage("invalid increase in upper bound\n");
432 return SCIP_INVALIDDATA;
433 }
434
435 return SCIP_OKAY;
436 }
437
438 /** updates upper bound and cutoff bound in primal data after a tightening of the problem's objective limit */
SCIPprimalUpdateObjlimit(SCIP_PRIMAL * primal,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_STAT * stat,SCIP_EVENTFILTER * eventfilter,SCIP_EVENTQUEUE * eventqueue,SCIP_PROB * transprob,SCIP_PROB * origprob,SCIP_TREE * tree,SCIP_REOPT * reopt,SCIP_LP * lp)439 SCIP_RETCODE SCIPprimalUpdateObjlimit(
440 SCIP_PRIMAL* primal, /**< primal data */
441 BMS_BLKMEM* blkmem, /**< block memory */
442 SCIP_SET* set, /**< global SCIP settings */
443 SCIP_STAT* stat, /**< problem statistics data */
444 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
445 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
446 SCIP_PROB* transprob, /**< transformed problem data */
447 SCIP_PROB* origprob, /**< original problem data */
448 SCIP_TREE* tree, /**< branch and bound tree */
449 SCIP_REOPT* reopt, /**< reoptimization data structure */
450 SCIP_LP* lp /**< current LP data */
451 )
452 {
453 SCIP_Real objlimit;
454 SCIP_Real inf;
455
456 assert(primal != NULL);
457
458 /* get internal objective limit */
459 objlimit = SCIPprobInternObjval(transprob, origprob, set, SCIPprobGetObjlim(origprob, set));
460 inf = SCIPsetInfinity(set);
461 objlimit = MIN(objlimit, inf);
462
463 /* update the cutoff bound */
464 if( objlimit < primal->cutoffbound )
465 {
466 SCIP_CALL( primalSetCutoffbound(primal, blkmem, set, stat, transprob, eventfilter, eventqueue, tree, reopt, lp, objlimit) );
467 }
468
469 /* set new upper bound (and decrease cutoff bound, if objective value is always integral) */
470 if( objlimit < primal->upperbound )
471 {
472 SCIP_CALL( primalSetUpperbound(primal, blkmem, set, stat, eventfilter, eventqueue, transprob, tree, reopt, lp, objlimit) );
473 }
474
475 return SCIP_OKAY;
476 }
477
478 /** recalculates upper bound and cutoff bound in primal data after a change of the problem's objective offset */
SCIPprimalUpdateObjoffset(SCIP_PRIMAL * primal,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_STAT * stat,SCIP_EVENTFILTER * eventfilter,SCIP_EVENTQUEUE * eventqueue,SCIP_PROB * transprob,SCIP_PROB * origprob,SCIP_TREE * tree,SCIP_REOPT * reopt,SCIP_LP * lp)479 SCIP_RETCODE SCIPprimalUpdateObjoffset(
480 SCIP_PRIMAL* primal, /**< primal data */
481 BMS_BLKMEM* blkmem, /**< block memory */
482 SCIP_SET* set, /**< global SCIP settings */
483 SCIP_STAT* stat, /**< problem statistics data */
484 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
485 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
486 SCIP_PROB* transprob, /**< tranformed problem data */
487 SCIP_PROB* origprob, /**< original problem data */
488 SCIP_TREE* tree, /**< branch and bound tree */
489 SCIP_REOPT* reopt, /**< reoptimization data structure */
490 SCIP_LP* lp /**< current LP data */
491 )
492 {
493 SCIP_Real upperbound;
494 SCIP_Real inf;
495
496 assert(primal != NULL);
497 assert(SCIPsetGetStage(set) <= SCIP_STAGE_PRESOLVED);
498
499 /* recalculate internal objective limit */
500 upperbound = SCIPprobInternObjval(transprob, origprob, set, SCIPprobGetObjlim(origprob, set));
501 inf = SCIPsetInfinity(set);
502 upperbound = MIN(upperbound, inf);
503
504 /* resort current primal solutions */
505 sortPrimalSols(primal, set, origprob, transprob);
506
507 /* compare objective limit to currently best solution */
508 if( primal->nsols > 0 )
509 {
510 SCIP_Real obj;
511
512 assert(SCIPsolIsOriginal(primal->sols[0]));
513 obj = SCIPsolGetObj(primal->sols[0], set, transprob, origprob);
514
515 upperbound = MIN(upperbound, obj);
516 }
517
518 /* invalidate old upper bound */
519 SCIP_CALL( primalSetUpperbound(primal, blkmem, set, stat, eventfilter, eventqueue, transprob, tree, reopt, lp, SCIPsetInfinity(set)) );
520
521 /* reset the cutoff bound
522 *
523 * @note we might need to relax the bound since in presolving the objective correction of an
524 * aggregation is still in progress
525 */
526 SCIP_CALL( primalSetCutoffbound(primal, blkmem, set, stat, transprob, eventfilter, eventqueue, tree, reopt, lp, upperbound) );
527
528 /* set new upper bound (and decrease cutoff bound, if objective value is always integral) */
529 SCIP_CALL( primalSetUpperbound(primal, blkmem, set, stat, eventfilter, eventqueue, transprob, tree, reopt, lp, upperbound) );
530
531 return SCIP_OKAY;
532 }
533
534 /** adds additional objective offset in original space to all existing solution (in original space) */
SCIPprimalAddOrigObjoffset(SCIP_PRIMAL * primal,SCIP_SET * set,SCIP_Real addval)535 void SCIPprimalAddOrigObjoffset(
536 SCIP_PRIMAL* primal, /**< primal data */
537 SCIP_SET* set, /**< global SCIP settings */
538 SCIP_Real addval /**< additional objective offset in original space */
539 )
540 {
541 int i;
542
543 assert(primal != NULL);
544 assert(set != NULL);
545 assert(SCIPsetGetStage(set) == SCIP_STAGE_PROBLEM);
546
547 #ifndef NDEBUG
548 assert(primal->nsols == 0 || SCIPsolGetOrigin(primal->sols[0]) == SCIP_SOLORIGIN_ORIGINAL);
549
550 /* check current order of primal solutions */
551 for( i = 1; i < primal->nsols; ++i )
552 {
553 assert(SCIPsolGetOrigin(primal->sols[i]) == SCIP_SOLORIGIN_ORIGINAL);
554 assert(SCIPsetIsLE(set, SCIPsolGetOrigObj(primal->sols[i-1]), SCIPsolGetOrigObj(primal->sols[i])));
555 }
556 #endif
557
558 /* check current order of primal solutions */
559 for( i = 0; i < primal->nexistingsols; ++i )
560 {
561 assert(primal->existingsols[i] != NULL);
562 SCIPsolOrigAddObjval(primal->existingsols[i], addval);
563 }
564 }
565
566 /** returns whether the current primal bound is justified with a feasible primal solution; if not, the primal bound
567 * was set from the user as objective limit
568 */
SCIPprimalUpperboundIsSol(SCIP_PRIMAL * primal,SCIP_SET * set,SCIP_PROB * transprob,SCIP_PROB * origprob)569 SCIP_Bool SCIPprimalUpperboundIsSol(
570 SCIP_PRIMAL* primal, /**< primal data */
571 SCIP_SET* set, /**< global SCIP settings */
572 SCIP_PROB* transprob, /**< tranformed problem data */
573 SCIP_PROB* origprob /**< original problem data */
574 )
575 {
576 assert(primal != NULL);
577
578 return (primal->nsols > 0 && SCIPsetIsEQ(set, primal->upperbound, SCIPsolGetObj(primal->sols[0], set, transprob, origprob)));
579 }
580
581 /** returns the primal ray thats proves unboundedness */
SCIPprimalGetRay(SCIP_PRIMAL * primal)582 SCIP_SOL* SCIPprimalGetRay(
583 SCIP_PRIMAL* primal /**< primal data */
584 )
585 {
586 assert(primal != NULL);
587
588 return primal->primalray;
589 }
590
591 /** update the primal ray thats proves unboundedness */
SCIPprimalUpdateRay(SCIP_PRIMAL * primal,SCIP_SET * set,SCIP_STAT * stat,SCIP_SOL * primalray,BMS_BLKMEM * blkmem)592 SCIP_RETCODE SCIPprimalUpdateRay(
593 SCIP_PRIMAL* primal, /**< primal data */
594 SCIP_SET* set, /**< global SCIP settings */
595 SCIP_STAT* stat, /**< dynamic SCIP statistics */
596 SCIP_SOL* primalray, /**< the new primal ray */
597 BMS_BLKMEM* blkmem /**< block memory */
598 )
599 {
600 assert(primal != NULL);
601 assert(set != NULL);
602 assert(stat != NULL);
603 assert(primalray != NULL);
604 assert(blkmem != NULL);
605
606 /* clear previously stored primal ray, if any */
607 if( primal->primalray != NULL )
608 {
609 SCIP_CALL( SCIPsolFree(&primal->primalray, blkmem, primal) );
610 }
611
612 assert(primal->primalray == NULL);
613
614 SCIP_CALL( SCIPsolCopy(&primal->primalray, blkmem, set, stat, primal, primalray) );
615
616 return SCIP_OKAY;
617 }
618
619 /** adds primal solution to solution storage at given position */
620 static
primalAddSol(SCIP_PRIMAL * primal,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_MESSAGEHDLR * messagehdlr,SCIP_STAT * stat,SCIP_PROB * origprob,SCIP_PROB * transprob,SCIP_TREE * tree,SCIP_REOPT * reopt,SCIP_LP * lp,SCIP_EVENTQUEUE * eventqueue,SCIP_EVENTFILTER * eventfilter,SCIP_SOL ** solptr,int insertpos,SCIP_Bool replace)621 SCIP_RETCODE primalAddSol(
622 SCIP_PRIMAL* primal, /**< primal data */
623 BMS_BLKMEM* blkmem, /**< block memory */
624 SCIP_SET* set, /**< global SCIP settings */
625 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
626 SCIP_STAT* stat, /**< problem statistics data */
627 SCIP_PROB* origprob, /**< original problem */
628 SCIP_PROB* transprob, /**< transformed problem after presolve */
629 SCIP_TREE* tree, /**< branch and bound tree */
630 SCIP_REOPT* reopt, /**< reoptimization data structure */
631 SCIP_LP* lp, /**< current LP data */
632 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
633 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
634 SCIP_SOL** solptr, /**< pointer to primal CIP solution */
635 int insertpos, /**< position in solution storage to add solution to */
636 SCIP_Bool replace /**< should the solution at insertpos be replaced by the new solution? */
637 )
638 {
639 SCIP_SOL* sol;
640 /* cppcheck-suppress unassignedVariable */
641 SCIP_EVENT event;
642 SCIP_Real obj;
643 int pos;
644
645 assert(primal != NULL);
646 assert(set != NULL);
647 assert(solptr != NULL);
648 assert(stat != NULL);
649 assert(transprob != NULL);
650 assert(origprob != NULL);
651 assert(0 <= insertpos && insertpos < set->limit_maxsol);
652 assert(tree == NULL || !SCIPtreeInRepropagation(tree));
653
654 sol = *solptr;
655 assert(sol != NULL);
656 obj = SCIPsolGetObj(sol, set, transprob, origprob);
657
658 SCIPsetDebugMsg(set, "insert primal solution %p with obj %g at position %d (replace=%u):\n",
659 (void*)sol, obj, insertpos, replace);
660
661 /* make sure that the primal bound is at least the lower bound */
662 if( ! SCIPsetIsInfinity(set, obj) && ! SCIPsetIsInfinity(set, -SCIPgetLowerbound(set->scip)) && SCIPsetIsFeasGT(set, SCIPgetLowerbound(set->scip), obj) )
663 {
664 if( origprob->objsense == SCIP_OBJSENSE_MINIMIZE )
665 {
666 SCIPmessagePrintWarning(messagehdlr, "Dual bound %g is larger than the objective of the primal solution %g. The solution might not be optimal.\n",
667 SCIPprobExternObjval(transprob, origprob, set, SCIPgetLowerbound(set->scip)), SCIPprobExternObjval(transprob, origprob, set, obj));
668 }
669 else
670 {
671 SCIPmessagePrintWarning(messagehdlr, "Dual bound %g is smaller than the objective of the primal solution %g. The solution might not be optimal.\n",
672 SCIPprobExternObjval(transprob, origprob, set, SCIPgetLowerbound(set->scip)), SCIPprobExternObjval(transprob, origprob, set, obj));
673 }
674 #ifdef WITH_DEBUG_SOLUTION
675 SCIPABORT();
676 #endif
677 }
678
679 SCIPdebug( SCIP_CALL( SCIPsolPrint(sol, set, messagehdlr, stat, transprob, NULL, NULL, FALSE, FALSE) ) );
680
681 #if 0 /* this is not a valid debug check, but can be used to track down numerical troubles */
682 #ifndef NDEBUG
683 /* check solution again completely
684 * it fail for different reasons:
685 * - in the LP solver, the feasibility tolerance is a relative measure against the row's norm
686 * - in SCIP, the feasibility tolerance is a relative measure against the row's rhs/lhs
687 * - the rhs/lhs of a row might drastically change during presolving when variables are fixed or (multi-)aggregated
688 */
689 if( !SCIPsolIsOriginal(sol) )
690 {
691 SCIP_Bool feasible;
692
693 SCIP_CALL( SCIPsolCheck(sol, set, messagehdlr, blkmem, stat, transprob, TRUE, TRUE, TRUE, TRUE, &feasible) );
694
695 if( !feasible )
696 {
697 SCIPerrorMessage("infeasible solution accepted:\n");
698 SCIP_CALL( SCIPsolPrint(sol, set, messagehdlr, stat, origprob, transprob, NULL, FALSE, FALSE) );
699 }
700 assert(feasible);
701 }
702 #endif
703 #endif
704
705 /* completely fill the solution's own value array to unlink it from the LP or pseudo solution */
706 SCIP_CALL( SCIPsolUnlink(sol, set, transprob) );
707
708 /* allocate memory for solution storage */
709 SCIP_CALL( ensureSolsSize(primal, set, set->limit_maxsol) );
710
711 /* if set->limit_maxsol was decreased in the meantime, free all solutions exceeding the limit */
712 for( pos = set->limit_maxsol; pos < primal->nsols; ++pos )
713 {
714 SCIP_CALL( SCIPsolFree(&primal->sols[pos], blkmem, primal) );
715 }
716 primal->nsols = MIN(primal->nsols, set->limit_maxsol);
717
718 /* if the solution should replace an existing one, free this solution, otherwise,
719 * free the last solution if the solution storage is full;
720 */
721 if( replace )
722 {
723 SCIP_CALL( SCIPsolTransform(primal->sols[insertpos], solptr, blkmem, set, primal) );
724 sol = primal->sols[insertpos];
725 }
726 else
727 {
728 if( primal->nsols == set->limit_maxsol )
729 {
730 SCIP_CALL( SCIPsolFree(&primal->sols[set->limit_maxsol - 1], blkmem, primal) );
731 }
732 else
733 {
734 primal->nsols = primal->nsols + 1;
735 assert(primal->nsols <= set->limit_maxsol);
736 }
737
738 /* move all solutions with worse objective value than the new solution */
739 for( pos = primal->nsols-1; pos > insertpos; --pos )
740 primal->sols[pos] = primal->sols[pos-1];
741
742 /* insert solution at correct position */
743 assert(0 <= insertpos && insertpos < primal->nsols);
744 primal->sols[insertpos] = sol;
745 primal->nsolsfound++;
746
747 /* check if solution is better than objective limit */
748 if( SCIPsetIsFeasLE(set, obj, SCIPprobInternObjval(transprob, origprob, set, SCIPprobGetObjlim(origprob, set))) )
749 primal->nlimsolsfound++;
750 }
751
752 /* if its the first primal solution, store the relevant statistics */
753 if( primal->nsolsfound == 1 )
754 {
755 SCIP_Real primalsolval;
756
757 stat->nnodesbeforefirst = SCIPsolGetNodenum(sol);
758 stat->nrunsbeforefirst = SCIPsolGetRunnum(sol);
759 stat->firstprimalheur = SCIPsolGetHeur(sol);
760 stat->firstprimaltime = SCIPsolGetTime(sol);
761 stat->firstprimaldepth = SCIPsolGetDepth(sol);
762
763 primalsolval = obj;
764 stat->firstprimalbound = SCIPprobExternObjval(transprob, origprob, set, primalsolval);
765
766 SCIPsetDebugMsg(set, "First Solution stored in problem specific statistics.\n");
767 SCIPsetDebugMsg(set, "-> %" SCIP_LONGINT_FORMAT " nodes, %d runs, %.2g time, %d depth, %.15g objective\n", stat->nnodesbeforefirst, stat->nrunsbeforefirst,
768 stat->firstprimaltime, stat->firstprimaldepth, stat->firstprimalbound);
769 }
770
771 SCIPsetDebugMsg(set, " -> stored at position %d of %d solutions, found %" SCIP_LONGINT_FORMAT " solutions\n",
772 insertpos, primal->nsols, primal->nsolsfound);
773
774 /* update the solution value sums in variables */
775 if( !SCIPsolIsOriginal(sol) )
776 {
777 SCIPsolUpdateVarsum(sol, set, stat, transprob,
778 (SCIP_Real)(primal->nsols - insertpos)/(SCIP_Real)(2.0*primal->nsols - 1.0));
779 }
780
781 /* change color of node in visualization output */
782 SCIPvisualFoundSolution(stat->visual, set, stat, SCIPtreeGetCurrentNode(tree), insertpos == 0 ? TRUE : FALSE, sol);
783
784 /* check, if the global upper bound has to be updated */
785 if( obj < primal->cutoffbound && insertpos == 0 )
786 {
787 /* update the upper bound */
788 SCIP_CALL( SCIPprimalSetUpperbound(primal, blkmem, set, stat, eventfilter, eventqueue, transprob, tree, reopt, lp, obj) );
789
790 /* issue BESTSOLFOUND event */
791 SCIP_CALL( SCIPeventChgType(&event, SCIP_EVENTTYPE_BESTSOLFOUND) );
792 primal->nbestsolsfound++;
793 stat->bestsolnode = stat->nnodes;
794 }
795 else
796 {
797 /* issue POORSOLFOUND event */
798 SCIP_CALL( SCIPeventChgType(&event, SCIP_EVENTTYPE_POORSOLFOUND) );
799 }
800 SCIP_CALL( SCIPeventChgSol(&event, sol) );
801 SCIP_CALL( SCIPeventProcess(&event, set, NULL, NULL, NULL, eventfilter) );
802
803 /* display node information line */
804 if( insertpos == 0 && !replace && set->stage >= SCIP_STAGE_SOLVING )
805 {
806 SCIP_CALL( SCIPdispPrintLine(set, messagehdlr, stat, NULL, TRUE, TRUE) );
807 }
808
809 /* if an original solution was added during solving, try to transfer it to the transformed space */
810 if( SCIPsolIsOriginal(sol) && SCIPsetGetStage(set) == SCIP_STAGE_SOLVING && set->misc_transorigsols )
811 {
812 SCIP_Bool added;
813
814 SCIP_CALL( SCIPprimalTransformSol(primal, sol, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt,
815 lp, eventqueue, eventfilter, NULL, NULL, 0, &added) );
816
817 SCIPsetDebugMsg(set, "original solution %p was successfully transferred to the transformed problem space\n",
818 (void*)sol);
819 } /*lint !e438*/
820
821 return SCIP_OKAY;
822 }
823
824 /** adds primal solution to solution storage at given position */
825 static
primalAddOrigSol(SCIP_PRIMAL * primal,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_PROB * prob,SCIP_SOL * sol,int insertpos)826 SCIP_RETCODE primalAddOrigSol(
827 SCIP_PRIMAL* primal, /**< primal data */
828 BMS_BLKMEM* blkmem, /**< block memory */
829 SCIP_SET* set, /**< global SCIP settings */
830 SCIP_PROB* prob, /**< original problem data */
831 SCIP_SOL* sol, /**< primal CIP solution */
832 int insertpos /**< position in solution storage to add solution to */
833 )
834 {
835 int pos;
836
837 assert(primal != NULL);
838 assert(set != NULL);
839 assert(prob != NULL);
840 assert(sol != NULL);
841 assert(0 <= insertpos && insertpos < set->limit_maxorigsol);
842 assert(!set->reopt_enable);
843
844 SCIPsetDebugMsg(set, "insert primal solution candidate %p with obj %g at position %d:\n", (void*)sol, SCIPsolGetOrigObj(sol), insertpos);
845
846 /* allocate memory for solution storage */
847 SCIP_CALL( ensureSolsSize(primal, set, set->limit_maxorigsol) );
848
849 /* if the solution storage is full, free the last solution(s)
850 * more than one solution may be freed, if set->limit_maxorigsol was decreased in the meantime
851 */
852 for( pos = set->limit_maxorigsol-1; pos < primal->nsols; ++pos )
853 {
854 SCIP_CALL( SCIPsolFree(&primal->sols[pos], blkmem, primal) );
855 }
856
857 /* insert solution at correct position */
858 primal->nsols = MIN(primal->nsols+1, set->limit_maxorigsol);
859 for( pos = primal->nsols-1; pos > insertpos; --pos )
860 primal->sols[pos] = primal->sols[pos-1];
861
862 assert(0 <= insertpos && insertpos < primal->nsols);
863 primal->sols[insertpos] = sol;
864 primal->nsolsfound++;
865
866 /* check if solution is better than objective limit */
867 if( SCIPsetIsFeasLE(set, SCIPsolGetOrigObj(sol), SCIPprobGetObjlim(prob, set)) )
868 primal->nlimsolsfound++;
869
870 SCIPsetDebugMsg(set, " -> stored at position %d of %d solutions, found %" SCIP_LONGINT_FORMAT " solutions\n",
871 insertpos, primal->nsols, primal->nsolsfound);
872
873 return SCIP_OKAY;
874 }
875
876 /** adds primal solution to solution storage */
877 static
primalAddOrigPartialSol(SCIP_PRIMAL * primal,SCIP_SET * set,SCIP_PROB * prob,SCIP_SOL * sol)878 SCIP_RETCODE primalAddOrigPartialSol(
879 SCIP_PRIMAL* primal, /**< primal data */
880 SCIP_SET* set, /**< global SCIP settings */
881 SCIP_PROB* prob, /**< original problem data */
882 SCIP_SOL* sol /**< primal CIP solution */
883 )
884 { /*lint --e{715}*/
885 assert(primal != NULL);
886 assert(set != NULL);
887 assert(prob != NULL);
888 assert(sol != NULL);
889
890 if( primal->npartialsols >= set->limit_maxorigsol )
891 {
892 SCIPerrorMessage("Cannot add partial solution to storage: limit reached.\n");
893 return SCIP_INVALIDCALL;
894 }
895
896 SCIPsetDebugMsg(set, "insert partial solution candidate %p:\n", (void*)sol);
897
898 /* allocate memory for solution storage */
899 SCIP_CALL( ensurePartialsolsSize(primal, set, primal->npartialsols+1) );
900
901 primal->partialsols[primal->npartialsols] = sol;
902 ++primal->npartialsols;
903
904 return SCIP_OKAY;
905 }
906
907 /** uses binary search to find position in solution storage */
908 static
primalSearchSolPos(SCIP_PRIMAL * primal,SCIP_SET * set,SCIP_PROB * transprob,SCIP_PROB * origprob,SCIP_SOL * sol)909 int primalSearchSolPos(
910 SCIP_PRIMAL* primal, /**< primal data */
911 SCIP_SET* set, /**< global SCIP settings */
912 SCIP_PROB* transprob, /**< tranformed problem data */
913 SCIP_PROB* origprob, /**< original problem data */
914 SCIP_SOL* sol /**< primal solution to search position for */
915 )
916 {
917 SCIP_SOL** sols;
918 SCIP_Real obj;
919 SCIP_Real middleobj;
920 int left;
921 int right;
922 int middle;
923
924 assert(primal != NULL);
925
926 obj = SCIPsolGetObj(sol, set, transprob, origprob);
927 sols = primal->sols;
928
929 left = -1;
930 right = primal->nsols;
931 while( left < right-1 )
932 {
933 middle = (left+right)/2;
934 assert(left < middle && middle < right);
935 assert(0 <= middle && middle < primal->nsols);
936
937 middleobj = SCIPsolGetObj(sols[middle], set, transprob, origprob);
938
939 if( obj < middleobj )
940 right = middle;
941 else
942 left = middle;
943 }
944 assert(left == right-1);
945
946 /* prefer solutions that live in the transformed space */
947 if( !SCIPsolIsOriginal(sol) )
948 {
949 while( right > 0 && SCIPsolIsOriginal(sols[right-1])
950 && SCIPsetIsEQ(set, SCIPsolGetObj(sols[right-1], set, transprob, origprob), obj) )
951 --right;
952 }
953
954 return right;
955 }
956
957 /** uses binary search to find position in solution storage */
958 static
primalSearchOrigSolPos(SCIP_PRIMAL * primal,SCIP_SOL * sol)959 int primalSearchOrigSolPos(
960 SCIP_PRIMAL* primal, /**< primal data */
961 SCIP_SOL* sol /**< primal solution to search position for */
962 )
963 {
964 SCIP_Real obj;
965 SCIP_Real middleobj;
966 int left;
967 int right;
968 int middle;
969
970 assert(primal != NULL);
971
972 obj = SCIPsolGetOrigObj(sol);
973
974 left = -1;
975 right = primal->nsols;
976 while( left < right-1 )
977 {
978 middle = (left+right)/2;
979 assert(left < middle && middle < right);
980 assert(0 <= middle && middle < primal->nsols);
981 middleobj = SCIPsolGetOrigObj(primal->sols[middle]);
982 if( obj < middleobj )
983 right = middle;
984 else
985 left = middle;
986 }
987 assert(left == right-1);
988
989 return right;
990 }
991
992 /** returns whether the given primal solution is already existent in the solution storage */
993 static
primalExistsSol(SCIP_PRIMAL * primal,SCIP_SET * set,SCIP_STAT * stat,SCIP_PROB * origprob,SCIP_PROB * transprob,SCIP_SOL * sol,int * insertpos,SCIP_Bool * replace)994 SCIP_Bool primalExistsSol(
995 SCIP_PRIMAL* primal, /**< primal data */
996 SCIP_SET* set, /**< global SCIP settings */
997 SCIP_STAT* stat, /**< problem statistics data */
998 SCIP_PROB* origprob, /**< original problem */
999 SCIP_PROB* transprob, /**< transformed problem after presolve */
1000 SCIP_SOL* sol, /**< primal solution to search position for */
1001 int* insertpos, /**< pointer to insertion position returned by primalSearchSolPos(); the
1002 * position might be changed if an existing solution should be replaced */
1003 SCIP_Bool* replace /**< pointer to store whether the solution at insertpos should be replaced */
1004 )
1005 {
1006 SCIP_Real obj;
1007 int i;
1008
1009 assert(primal != NULL);
1010 assert(insertpos != NULL);
1011 assert(replace != NULL);
1012 assert(0 <= (*insertpos) && (*insertpos) <= primal->nsols);
1013
1014 obj = SCIPsolGetObj(sol, set, transprob, origprob);
1015
1016 assert(primal->sols != NULL || primal->nsols == 0);
1017 assert(primal->sols != NULL || (*insertpos) == 0);
1018
1019 /* search in the better solutions */
1020 for( i = (*insertpos)-1; i >= 0; --i )
1021 {
1022 SCIP_Real solobj;
1023
1024 solobj = SCIPsolGetObj(primal->sols[i], set, transprob, origprob);
1025
1026 /* due to transferring the objective value of transformed solutions to the original space, small numerical errors might occur
1027 * which can lead to SCIPsetIsLE() failing in case of high absolute numbers
1028 */
1029 assert(SCIPsetIsLE(set, solobj, obj) || (REALABS(obj) > 1e+13 * SCIPsetEpsilon(set) && SCIPsetIsFeasLE(set, solobj, obj)));
1030
1031 if( SCIPsetIsLT(set, solobj, obj) )
1032 break;
1033
1034 if( SCIPsolsAreEqual(sol, primal->sols[i], set, stat, origprob, transprob) )
1035 {
1036 if( SCIPsolIsOriginal(primal->sols[i]) && !SCIPsolIsOriginal(sol) )
1037 {
1038 (*insertpos) = i;
1039 (*replace) = TRUE;
1040 }
1041 return TRUE;
1042 }
1043 }
1044
1045 /* search in the worse solutions */
1046 for( i = (*insertpos); i < primal->nsols; ++i )
1047 {
1048 SCIP_Real solobj;
1049
1050 solobj = SCIPsolGetObj(primal->sols[i], set, transprob, origprob);
1051
1052 /* due to transferring the objective value of transformed solutions to the original space, small numerical errors might occur
1053 * which can lead to SCIPsetIsLE() failing in case of high absolute numbers
1054 */
1055 assert( SCIPsetIsGE(set, solobj, obj) || (REALABS(obj) > 1e+13 * SCIPsetEpsilon(set) && SCIPsetIsFeasGE(set, solobj, obj)));
1056
1057 if( SCIPsetIsGT(set, solobj, obj) )
1058 break;
1059
1060 if( SCIPsolsAreEqual(sol, primal->sols[i], set, stat, origprob, transprob) )
1061 {
1062 if( SCIPsolIsOriginal(primal->sols[i]) && !SCIPsolIsOriginal(sol) )
1063 {
1064 (*insertpos) = i;
1065 (*replace) = TRUE;
1066 }
1067 return TRUE;
1068 }
1069 }
1070
1071 return FALSE;
1072 }
1073
1074 /** returns whether the given primal solution is already existent in the original solution candidate storage */
1075 static
primalExistsOrigSol(SCIP_PRIMAL * primal,SCIP_SET * set,SCIP_STAT * stat,SCIP_PROB * prob,SCIP_SOL * sol,int insertpos)1076 SCIP_Bool primalExistsOrigSol(
1077 SCIP_PRIMAL* primal, /**< primal data */
1078 SCIP_SET* set, /**< global SCIP settings */
1079 SCIP_STAT* stat, /**< problem statistics data */
1080 SCIP_PROB* prob, /**< original problem */
1081 SCIP_SOL* sol, /**< primal solution to search position for */
1082 int insertpos /**< insertion position returned by primalSearchOrigSolPos() */
1083 )
1084 {
1085 SCIP_Real obj;
1086 int i;
1087
1088 assert(primal != NULL);
1089 assert(0 <= insertpos && insertpos <= primal->nsols);
1090
1091 obj = SCIPsolGetOrigObj(sol);
1092
1093 /* search in the better solutions */
1094 for( i = insertpos-1; i >= 0; --i )
1095 {
1096 SCIP_Real solobj;
1097
1098 solobj = SCIPsolGetOrigObj(primal->sols[i]);
1099 assert( SCIPsetIsLE(set, solobj, obj) );
1100
1101 if( SCIPsetIsLT(set, solobj, obj) )
1102 break;
1103
1104 if( SCIPsolsAreEqual(sol, primal->sols[i], set, stat, prob, NULL) )
1105 return TRUE;
1106 }
1107
1108 /* search in the worse solutions */
1109 for( i = insertpos; i < primal->nsols; ++i )
1110 {
1111 SCIP_Real solobj;
1112
1113 solobj = SCIPsolGetOrigObj(primal->sols[i]);
1114 assert( SCIPsetIsGE(set, solobj, obj) );
1115
1116 if( SCIPsetIsGT(set, solobj, obj) )
1117 break;
1118
1119 if( SCIPsolsAreEqual(sol, primal->sols[i], set, stat, prob, NULL) )
1120 return TRUE;
1121 }
1122
1123 return FALSE;
1124 }
1125
1126 /** check if we are willing to check the solution for feasibility */
1127 static
solOfInterest(SCIP_PRIMAL * primal,SCIP_SET * set,SCIP_STAT * stat,SCIP_PROB * origprob,SCIP_PROB * transprob,SCIP_SOL * sol,int * insertpos,SCIP_Bool * replace)1128 SCIP_Bool solOfInterest(
1129 SCIP_PRIMAL* primal, /**< primal data */
1130 SCIP_SET* set, /**< global SCIP settings */
1131 SCIP_STAT* stat, /**< problem statistics data */
1132 SCIP_PROB* origprob, /**< original problem */
1133 SCIP_PROB* transprob, /**< transformed problem after presolve */
1134 SCIP_SOL* sol, /**< primal CIP solution */
1135 int* insertpos, /**< pointer to store the insert position of that solution */
1136 SCIP_Bool* replace /**< pointer to store whether the solution at insertpos should be replaced
1137 * (e.g., because it lives in the original space) */
1138 )
1139 {
1140 SCIP_Real obj;
1141
1142 obj = SCIPsolGetObj(sol, set, transprob, origprob);
1143
1144 /* check if we are willing to check worse solutions; a solution is better if the objective is smaller than the
1145 * current cutoff bound; solutions with infinite objective value are never accepted
1146 */
1147 if( (!set->misc_improvingsols || obj < primal->cutoffbound) && !SCIPsetIsInfinity(set, obj) )
1148 {
1149 /* find insert position for the solution */
1150 (*insertpos) = primalSearchSolPos(primal, set, transprob, origprob, sol);
1151 (*replace) = FALSE;
1152
1153 /* the solution should be added, if the insertpos is smaller than the maximum number of solutions to be stored
1154 * and it does not already exist or it does exist, but the existing solution should be replaced by the new one
1155 */
1156 if( (*insertpos) < set->limit_maxsol &&
1157 (!primalExistsSol(primal, set, stat, origprob, transprob, sol, insertpos, replace) || (*replace)) )
1158 return TRUE;
1159 }
1160
1161 return FALSE;
1162 }
1163
1164 /** check if we are willing to store the solution candidate for later checking */
1165 static
origsolOfInterest(SCIP_PRIMAL * primal,SCIP_SET * set,SCIP_STAT * stat,SCIP_PROB * origprob,SCIP_SOL * sol,int * insertpos)1166 SCIP_Bool origsolOfInterest(
1167 SCIP_PRIMAL* primal, /**< primal data */
1168 SCIP_SET* set, /**< global SCIP settings */
1169 SCIP_STAT* stat, /**< problem statistics data */
1170 SCIP_PROB* origprob, /**< original problem */
1171 SCIP_SOL* sol, /**< primal CIP solution */
1172 int* insertpos /**< pointer to store the insert position of that solution */
1173 )
1174 {
1175 assert(SCIPsolIsOriginal(sol));
1176
1177 /* find insert position for the solution */
1178 (*insertpos) = primalSearchOrigSolPos(primal, sol);
1179
1180 if( !set->reopt_enable && (*insertpos) < set->limit_maxorigsol && !primalExistsOrigSol(primal, set, stat, origprob, sol, *insertpos) )
1181 return TRUE;
1182
1183 return FALSE;
1184 }
1185
1186 /** adds primal solution to solution storage by copying it */
SCIPprimalAddSol(SCIP_PRIMAL * primal,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_MESSAGEHDLR * messagehdlr,SCIP_STAT * stat,SCIP_PROB * origprob,SCIP_PROB * transprob,SCIP_TREE * tree,SCIP_REOPT * reopt,SCIP_LP * lp,SCIP_EVENTQUEUE * eventqueue,SCIP_EVENTFILTER * eventfilter,SCIP_SOL * sol,SCIP_Bool * stored)1187 SCIP_RETCODE SCIPprimalAddSol(
1188 SCIP_PRIMAL* primal, /**< primal data */
1189 BMS_BLKMEM* blkmem, /**< block memory */
1190 SCIP_SET* set, /**< global SCIP settings */
1191 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1192 SCIP_STAT* stat, /**< problem statistics data */
1193 SCIP_PROB* origprob, /**< original problem */
1194 SCIP_PROB* transprob, /**< transformed problem after presolve */
1195 SCIP_TREE* tree, /**< branch and bound tree */
1196 SCIP_REOPT* reopt, /**< reoptimization data structure */
1197 SCIP_LP* lp, /**< current LP data */
1198 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1199 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
1200 SCIP_SOL* sol, /**< primal CIP solution */
1201 SCIP_Bool* stored /**< stores whether given solution was good enough to keep */
1202 )
1203 {
1204 SCIP_Bool replace;
1205 int insertpos;
1206
1207 assert(primal != NULL);
1208 assert(blkmem != NULL);
1209 assert(set != NULL);
1210 assert(messagehdlr != NULL);
1211 assert(stat != NULL);
1212 assert(origprob != NULL);
1213 assert(transprob != NULL);
1214 assert(tree != NULL);
1215 assert(lp != NULL);
1216 assert(eventqueue != NULL);
1217 assert(eventfilter != NULL);
1218 assert(sol != NULL);
1219 assert(stored != NULL);
1220
1221 insertpos = -1;
1222
1223 assert(!SCIPsolIsPartial(sol));
1224
1225 if( solOfInterest(primal, set, stat, origprob, transprob, sol, &insertpos, &replace) )
1226 {
1227 SCIP_SOL* solcopy;
1228 #ifdef SCIP_MORE_DEBUG
1229 int i;
1230 #endif
1231
1232 assert(insertpos >= 0 && insertpos < set->limit_maxsol);
1233
1234 /* create a copy of the solution */
1235 SCIP_CALL( SCIPsolCopy(&solcopy, blkmem, set, stat, primal, sol) );
1236
1237 /* insert copied solution into solution storage */
1238 SCIP_CALL( primalAddSol(primal, blkmem, set, messagehdlr, stat, origprob, transprob,
1239 tree, reopt, lp, eventqueue, eventfilter, &solcopy, insertpos, replace) );
1240 #ifdef SCIP_MORE_DEBUG
1241 for( i = 0; i < primal->nsols - 1; ++i )
1242 {
1243 assert(SCIPsetIsLE(set, SCIPsolGetObj(primal->sols[i], set, transprob, origprob), SCIPsolGetObj(primal->sols[i+1], set, transprob, origprob)));
1244 }
1245 #endif
1246 *stored = TRUE;
1247 }
1248 else
1249 *stored = FALSE;
1250
1251 return SCIP_OKAY;
1252 }
1253
1254 /** adds primal solution to solution storage, frees the solution afterwards */
SCIPprimalAddSolFree(SCIP_PRIMAL * primal,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_MESSAGEHDLR * messagehdlr,SCIP_STAT * stat,SCIP_PROB * origprob,SCIP_PROB * transprob,SCIP_TREE * tree,SCIP_REOPT * reopt,SCIP_LP * lp,SCIP_EVENTQUEUE * eventqueue,SCIP_EVENTFILTER * eventfilter,SCIP_SOL ** sol,SCIP_Bool * stored)1255 SCIP_RETCODE SCIPprimalAddSolFree(
1256 SCIP_PRIMAL* primal, /**< primal data */
1257 BMS_BLKMEM* blkmem, /**< block memory */
1258 SCIP_SET* set, /**< global SCIP settings */
1259 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1260 SCIP_STAT* stat, /**< problem statistics data */
1261 SCIP_PROB* origprob, /**< original problem */
1262 SCIP_PROB* transprob, /**< transformed problem after presolve */
1263 SCIP_TREE* tree, /**< branch and bound tree */
1264 SCIP_REOPT* reopt, /**< reoptimization data structure */
1265 SCIP_LP* lp, /**< current LP data */
1266 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1267 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
1268 SCIP_SOL** sol, /**< pointer to primal CIP solution; is cleared in function call */
1269 SCIP_Bool* stored /**< stores whether given solution was good enough to keep */
1270 )
1271 {
1272 SCIP_Bool replace;
1273 int insertpos;
1274
1275 assert(primal != NULL);
1276 assert(transprob != NULL);
1277 assert(origprob != NULL);
1278 assert(sol != NULL);
1279 assert(*sol != NULL);
1280 assert(stored != NULL);
1281
1282 insertpos = -1;
1283
1284 if( solOfInterest(primal, set, stat, origprob, transprob, *sol, &insertpos, &replace) )
1285 {
1286 assert(insertpos >= 0 && insertpos < set->limit_maxsol);
1287
1288 /* insert solution into solution storage */
1289 SCIP_CALL( primalAddSol(primal, blkmem, set, messagehdlr, stat, origprob, transprob,
1290 tree, reopt, lp, eventqueue, eventfilter, sol, insertpos, replace) );
1291
1292 /* clear the pointer, such that the user cannot access the solution anymore */
1293 *sol = NULL;
1294
1295 *stored = TRUE;
1296 }
1297 else
1298 {
1299 /* the solution is too bad -> free it immediately */
1300 SCIP_CALL( SCIPsolFree(sol, blkmem, primal) );
1301
1302 *stored = FALSE;
1303 }
1304 assert(*sol == NULL);
1305
1306 return SCIP_OKAY;
1307 }
1308
1309 /** adds primal solution to solution candidate storage of original problem space */
SCIPprimalAddOrigSol(SCIP_PRIMAL * primal,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_STAT * stat,SCIP_PROB * prob,SCIP_SOL * sol,SCIP_Bool * stored)1310 SCIP_RETCODE SCIPprimalAddOrigSol(
1311 SCIP_PRIMAL* primal, /**< primal data */
1312 BMS_BLKMEM* blkmem, /**< block memory */
1313 SCIP_SET* set, /**< global SCIP settings */
1314 SCIP_STAT* stat, /**< problem statistics data */
1315 SCIP_PROB* prob, /**< original problem data */
1316 SCIP_SOL* sol, /**< primal CIP solution; is cleared in function call */
1317 SCIP_Bool* stored /**< stores whether given solution was good enough to keep */
1318 )
1319 {
1320 int insertpos;
1321
1322 assert(primal != NULL);
1323 assert(blkmem != NULL);
1324 assert(set != NULL);
1325 assert(stat != NULL);
1326 assert(sol != NULL);
1327 assert(SCIPsolIsOriginal(sol));
1328 assert(stored != NULL);
1329
1330 insertpos = -1;
1331
1332 if( SCIPsolIsPartial(sol) )
1333 {
1334 SCIP_SOL* solcopy;
1335
1336 /* create a copy of the solution */
1337 SCIP_CALL( SCIPsolCopy(&solcopy, blkmem, set, stat, primal, sol) );
1338
1339 SCIP_CALL( primalAddOrigPartialSol(primal, set, prob, solcopy) );
1340
1341 *stored = TRUE;
1342 }
1343 else if( origsolOfInterest(primal, set, stat, prob, sol, &insertpos) )
1344 {
1345 SCIP_SOL* solcopy;
1346
1347 assert(insertpos >= 0 && insertpos < set->limit_maxorigsol);
1348 assert(!set->reopt_enable);
1349
1350 /* create a copy of the solution */
1351 SCIP_CALL( SCIPsolCopy(&solcopy, blkmem, set, stat, primal, sol) );
1352
1353 /* insert solution into solution storage */
1354 SCIP_CALL( primalAddOrigSol(primal, blkmem, set, prob, solcopy, insertpos) );
1355
1356 *stored = TRUE;
1357 }
1358 else
1359 *stored = FALSE;
1360
1361 return SCIP_OKAY;
1362 }
1363
1364 /** adds primal solution to solution candidate storage of original problem space, frees the solution afterwards */
SCIPprimalAddOrigSolFree(SCIP_PRIMAL * primal,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_STAT * stat,SCIP_PROB * prob,SCIP_SOL ** sol,SCIP_Bool * stored)1365 SCIP_RETCODE SCIPprimalAddOrigSolFree(
1366 SCIP_PRIMAL* primal, /**< primal data */
1367 BMS_BLKMEM* blkmem, /**< block memory */
1368 SCIP_SET* set, /**< global SCIP settings */
1369 SCIP_STAT* stat, /**< problem statistics data */
1370 SCIP_PROB* prob, /**< original problem data */
1371 SCIP_SOL** sol, /**< pointer to primal CIP solution; is cleared in function call */
1372 SCIP_Bool* stored /**< stores whether given solution was good enough to keep */
1373 )
1374 {
1375 int insertpos;
1376
1377 assert(primal != NULL);
1378 assert(sol != NULL);
1379 assert(*sol != NULL);
1380 assert(SCIPsolIsOriginal(*sol));
1381 assert(stored != NULL);
1382
1383 insertpos = -1;
1384
1385 if( SCIPsolIsPartial(*sol) )
1386 {
1387 /* insert solution into solution storage */
1388 SCIP_CALL( primalAddOrigPartialSol(primal, set, prob, *sol) );
1389
1390 /* clear the pointer, such that the user cannot access the solution anymore */
1391 *sol = NULL;
1392
1393 *stored = TRUE;
1394 }
1395 else if( origsolOfInterest(primal, set, stat, prob, *sol, &insertpos) )
1396 {
1397 assert(insertpos >= 0 && insertpos < set->limit_maxorigsol);
1398 assert(!set->reopt_enable);
1399
1400 /* insert solution into solution storage */
1401 SCIP_CALL( primalAddOrigSol(primal, blkmem, set, prob, *sol, insertpos) );
1402
1403 /* clear the pointer, such that the user cannot access the solution anymore */
1404 *sol = NULL;
1405
1406 *stored = TRUE;
1407 }
1408 else
1409 {
1410 /* the solution is too bad -> free it immediately */
1411 SCIP_CALL( SCIPsolFree(sol, blkmem, primal) );
1412
1413 *stored = FALSE;
1414 }
1415 assert(*sol == NULL);
1416
1417 return SCIP_OKAY;
1418 }
1419
1420 /** links temporary solution of primal data to current solution */
1421 static
primalLinkCurrentSol(SCIP_PRIMAL * primal,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_STAT * stat,SCIP_PROB * prob,SCIP_TREE * tree,SCIP_LP * lp,SCIP_HEUR * heur)1422 SCIP_RETCODE primalLinkCurrentSol(
1423 SCIP_PRIMAL* primal, /**< primal data */
1424 BMS_BLKMEM* blkmem, /**< block memory */
1425 SCIP_SET* set, /**< global SCIP settings */
1426 SCIP_STAT* stat, /**< problem statistics data */
1427 SCIP_PROB* prob, /**< transformed problem data */
1428 SCIP_TREE* tree, /**< branch and bound tree */
1429 SCIP_LP* lp, /**< current LP data */
1430 SCIP_HEUR* heur /**< heuristic that found the solution (or NULL if it's from the tree) */
1431 )
1432 {
1433 assert(primal != NULL);
1434
1435 if( primal->currentsol == NULL )
1436 {
1437 SCIP_CALL( SCIPsolCreateCurrentSol(&primal->currentsol, blkmem, set, stat, prob, primal, tree, lp, heur) );
1438 }
1439 else
1440 {
1441 SCIP_CALL( SCIPsolLinkCurrentSol(primal->currentsol, set, stat, prob, tree, lp) );
1442 SCIPsolSetHeur(primal->currentsol, heur);
1443 }
1444
1445 return SCIP_OKAY;
1446 }
1447
1448 /** adds current LP/pseudo solution to solution storage */
SCIPprimalAddCurrentSol(SCIP_PRIMAL * primal,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_MESSAGEHDLR * messagehdlr,SCIP_STAT * stat,SCIP_PROB * origprob,SCIP_PROB * transprob,SCIP_TREE * tree,SCIP_REOPT * reopt,SCIP_LP * lp,SCIP_EVENTQUEUE * eventqueue,SCIP_EVENTFILTER * eventfilter,SCIP_HEUR * heur,SCIP_Bool * stored)1449 SCIP_RETCODE SCIPprimalAddCurrentSol(
1450 SCIP_PRIMAL* primal, /**< primal data */
1451 BMS_BLKMEM* blkmem, /**< block memory */
1452 SCIP_SET* set, /**< global SCIP settings */
1453 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1454 SCIP_STAT* stat, /**< problem statistics data */
1455 SCIP_PROB* origprob, /**< original problem */
1456 SCIP_PROB* transprob, /**< transformed problem after presolve */
1457 SCIP_TREE* tree, /**< branch and bound tree */
1458 SCIP_REOPT* reopt, /**< reoptimization data structure */
1459 SCIP_LP* lp, /**< current LP data */
1460 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1461 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
1462 SCIP_HEUR* heur, /**< heuristic that found the solution (or NULL if it's from the tree) */
1463 SCIP_Bool* stored /**< stores whether given solution was good enough to keep */
1464 )
1465 {
1466 assert(primal != NULL);
1467
1468 /* link temporary solution to current solution */
1469 SCIP_CALL( primalLinkCurrentSol(primal, blkmem, set, stat, transprob, tree, lp, heur) );
1470
1471 /* add solution to solution storage */
1472 SCIP_CALL( SCIPprimalAddSol(primal, blkmem, set, messagehdlr, stat, origprob, transprob,
1473 tree, reopt, lp, eventqueue, eventfilter, primal->currentsol, stored) );
1474
1475 return SCIP_OKAY;
1476 }
1477
1478 /** checks primal solution; if feasible, adds it to storage by copying it */
SCIPprimalTrySol(SCIP_PRIMAL * primal,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_MESSAGEHDLR * messagehdlr,SCIP_STAT * stat,SCIP_PROB * origprob,SCIP_PROB * transprob,SCIP_TREE * tree,SCIP_REOPT * reopt,SCIP_LP * lp,SCIP_EVENTQUEUE * eventqueue,SCIP_EVENTFILTER * eventfilter,SCIP_SOL * sol,SCIP_Bool printreason,SCIP_Bool completely,SCIP_Bool checkbounds,SCIP_Bool checkintegrality,SCIP_Bool checklprows,SCIP_Bool * stored)1479 SCIP_RETCODE SCIPprimalTrySol(
1480 SCIP_PRIMAL* primal, /**< primal data */
1481 BMS_BLKMEM* blkmem, /**< block memory */
1482 SCIP_SET* set, /**< global SCIP settings */
1483 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1484 SCIP_STAT* stat, /**< problem statistics data */
1485 SCIP_PROB* origprob, /**< original problem */
1486 SCIP_PROB* transprob, /**< transformed problem after presolve */
1487 SCIP_TREE* tree, /**< branch and bound tree */
1488 SCIP_REOPT* reopt, /**< reoptimization data structure */
1489 SCIP_LP* lp, /**< current LP data */
1490 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1491 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
1492 SCIP_SOL* sol, /**< primal CIP solution */
1493 SCIP_Bool printreason, /**< Should all reasons of violations be printed? */
1494 SCIP_Bool completely, /**< Should all violations be checked? */
1495 SCIP_Bool checkbounds, /**< Should the bounds of the variables be checked? */
1496 SCIP_Bool checkintegrality, /**< Has integrality to be checked? */
1497 SCIP_Bool checklprows, /**< Do constraints represented by rows in the current LP have to be checked? */
1498 SCIP_Bool* stored /**< stores whether given solution was feasible and good enough to keep */
1499 )
1500 {
1501 SCIP_Bool feasible;
1502 SCIP_Bool replace;
1503 int insertpos;
1504
1505 assert(primal != NULL);
1506 assert(set != NULL);
1507 assert(transprob != NULL);
1508 assert(origprob != NULL);
1509 assert(tree != NULL);
1510 assert(sol != NULL);
1511 assert(stored != NULL);
1512
1513 /* if we want to solve exactly, the constraint handlers cannot rely on the LP's feasibility */
1514 checklprows = checklprows || set->misc_exactsolve;
1515
1516 insertpos = -1;
1517
1518 if( solOfInterest(primal, set, stat, origprob, transprob, sol, &insertpos, &replace) )
1519 {
1520 /* check solution for feasibility */
1521 SCIP_CALL( SCIPsolCheck(sol, set, messagehdlr, blkmem, stat, transprob, printreason, completely, checkbounds,
1522 checkintegrality, checklprows, &feasible) );
1523 }
1524 else
1525 feasible = FALSE;
1526
1527 if( feasible )
1528 {
1529 SCIP_SOL* solcopy;
1530
1531 assert(insertpos >= 0 && insertpos < set->limit_maxsol);
1532
1533 /* create a copy of the solution */
1534 SCIP_CALL( SCIPsolCopy(&solcopy, blkmem, set, stat, primal, sol) );
1535
1536 /* insert copied solution into solution storage */
1537 SCIP_CALL( primalAddSol(primal, blkmem, set, messagehdlr, stat, origprob, transprob,
1538 tree, reopt, lp, eventqueue, eventfilter, &solcopy, insertpos, replace) );
1539
1540 *stored = TRUE;
1541 }
1542 else
1543 *stored = FALSE;
1544
1545 return SCIP_OKAY;
1546 }
1547
1548 /** checks primal solution; if feasible, adds it to storage; solution is freed afterwards */
SCIPprimalTrySolFree(SCIP_PRIMAL * primal,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_MESSAGEHDLR * messagehdlr,SCIP_STAT * stat,SCIP_PROB * origprob,SCIP_PROB * transprob,SCIP_TREE * tree,SCIP_REOPT * reopt,SCIP_LP * lp,SCIP_EVENTQUEUE * eventqueue,SCIP_EVENTFILTER * eventfilter,SCIP_SOL ** sol,SCIP_Bool printreason,SCIP_Bool completely,SCIP_Bool checkbounds,SCIP_Bool checkintegrality,SCIP_Bool checklprows,SCIP_Bool * stored)1549 SCIP_RETCODE SCIPprimalTrySolFree(
1550 SCIP_PRIMAL* primal, /**< primal data */
1551 BMS_BLKMEM* blkmem, /**< block memory */
1552 SCIP_SET* set, /**< global SCIP settings */
1553 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1554 SCIP_STAT* stat, /**< problem statistics data */
1555 SCIP_PROB* origprob, /**< original problem */
1556 SCIP_PROB* transprob, /**< transformed problem after presolve */
1557 SCIP_TREE* tree, /**< branch and bound tree */
1558 SCIP_REOPT* reopt, /**< reoptimization data structure */
1559 SCIP_LP* lp, /**< current LP data */
1560 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1561 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
1562 SCIP_SOL** sol, /**< pointer to primal CIP solution; is cleared in function call */
1563 SCIP_Bool printreason, /**< Should all the reasons of violations be printed? */
1564 SCIP_Bool completely, /**< Should all violations be checked? */
1565 SCIP_Bool checkbounds, /**< Should the bounds of the variables be checked? */
1566 SCIP_Bool checkintegrality, /**< Has integrality to be checked? */
1567 SCIP_Bool checklprows, /**< Do constraints represented by rows in the current LP have to be checked? */
1568 SCIP_Bool* stored /**< stores whether solution was feasible and good enough to keep */
1569 )
1570 {
1571 SCIP_Bool feasible;
1572 SCIP_Bool replace;
1573 int insertpos;
1574
1575 assert(primal != NULL);
1576 assert(transprob != NULL);
1577 assert(origprob != NULL);
1578 assert(tree != NULL);
1579 assert(sol != NULL);
1580 assert(*sol != NULL);
1581 assert(stored != NULL);
1582
1583 *stored = FALSE;
1584
1585 /* if we want to solve exactly, the constraint handlers cannot rely on the LP's feasibility */
1586 checklprows = checklprows || set->misc_exactsolve;
1587
1588 insertpos = -1;
1589
1590 if( solOfInterest(primal, set, stat, origprob, transprob, *sol, &insertpos, &replace) )
1591 {
1592 /* check solution for feasibility */
1593 SCIP_CALL( SCIPsolCheck(*sol, set, messagehdlr, blkmem, stat, transprob, printreason, completely, checkbounds,
1594 checkintegrality, checklprows, &feasible) );
1595 }
1596 else
1597 feasible = FALSE;
1598
1599 if( feasible )
1600 {
1601 assert(insertpos >= 0 && insertpos < set->limit_maxsol);
1602
1603 /* insert solution into solution storage */
1604 SCIP_CALL( primalAddSol(primal, blkmem, set, messagehdlr, stat, origprob, transprob,
1605 tree, reopt, lp, eventqueue, eventfilter, sol, insertpos, replace) );
1606
1607 /* clear the pointer, such that the user cannot access the solution anymore */
1608 *sol = NULL;
1609 *stored = TRUE;
1610 }
1611 else
1612 {
1613 /* the solution is too bad or infeasible -> free it immediately */
1614 SCIP_CALL( SCIPsolFree(sol, blkmem, primal) );
1615 *stored = FALSE;
1616 }
1617 assert(*sol == NULL);
1618
1619 return SCIP_OKAY;
1620 }
1621
1622 /** checks current LP/pseudo solution; if feasible, adds it to storage */
SCIPprimalTryCurrentSol(SCIP_PRIMAL * primal,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_MESSAGEHDLR * messagehdlr,SCIP_STAT * stat,SCIP_PROB * origprob,SCIP_PROB * transprob,SCIP_TREE * tree,SCIP_REOPT * reopt,SCIP_LP * lp,SCIP_EVENTQUEUE * eventqueue,SCIP_EVENTFILTER * eventfilter,SCIP_HEUR * heur,SCIP_Bool printreason,SCIP_Bool completely,SCIP_Bool checkintegrality,SCIP_Bool checklprows,SCIP_Bool * stored)1623 SCIP_RETCODE SCIPprimalTryCurrentSol(
1624 SCIP_PRIMAL* primal, /**< primal data */
1625 BMS_BLKMEM* blkmem, /**< block memory */
1626 SCIP_SET* set, /**< global SCIP settings */
1627 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1628 SCIP_STAT* stat, /**< problem statistics data */
1629 SCIP_PROB* origprob, /**< original problem */
1630 SCIP_PROB* transprob, /**< transformed problem after presolve */
1631 SCIP_TREE* tree, /**< branch and bound tree */
1632 SCIP_REOPT* reopt, /**< reoptimization data structure */
1633 SCIP_LP* lp, /**< current LP data */
1634 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1635 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
1636 SCIP_HEUR* heur, /**< heuristic that found the solution (or NULL if it's from the tree) */
1637 SCIP_Bool printreason, /**< Should all reasons of violations be printed? */
1638 SCIP_Bool completely, /**< Should all violations be checked? */
1639 SCIP_Bool checkintegrality, /**< Has integrality to be checked? */
1640 SCIP_Bool checklprows, /**< Do constraints represented by rows in the current LP have to be checked? */
1641 SCIP_Bool* stored /**< stores whether given solution was good enough to keep */
1642 )
1643 {
1644 assert(primal != NULL);
1645
1646 /* link temporary solution to current solution */
1647 SCIP_CALL( primalLinkCurrentSol(primal, blkmem, set, stat, transprob, tree, lp, heur) );
1648
1649 /* add solution to solution storage */
1650 SCIP_CALL( SCIPprimalTrySol(primal, blkmem, set, messagehdlr, stat, origprob, transprob,
1651 tree, reopt, lp, eventqueue, eventfilter, primal->currentsol,
1652 printreason, completely, FALSE, checkintegrality, checklprows, stored) );
1653
1654 return SCIP_OKAY;
1655 }
1656
1657 /** inserts solution into the global array of all existing primal solutions */
SCIPprimalSolCreated(SCIP_PRIMAL * primal,SCIP_SET * set,SCIP_SOL * sol)1658 SCIP_RETCODE SCIPprimalSolCreated(
1659 SCIP_PRIMAL* primal, /**< primal data */
1660 SCIP_SET* set, /**< global SCIP settings */
1661 SCIP_SOL* sol /**< primal CIP solution */
1662 )
1663 {
1664 assert(primal != NULL);
1665 assert(sol != NULL);
1666 assert(SCIPsolGetPrimalIndex(sol) == -1);
1667
1668 /* allocate memory for solution storage */
1669 SCIP_CALL( ensureExistingsolsSize(primal, set, primal->nexistingsols+1) );
1670
1671 /* append solution */
1672 SCIPsolSetPrimalIndex(sol, primal->nexistingsols);
1673 primal->existingsols[primal->nexistingsols] = sol;
1674 primal->nexistingsols++;
1675
1676 return SCIP_OKAY;
1677 }
1678
1679 /** removes solution from the global array of all existing primal solutions */
SCIPprimalSolFreed(SCIP_PRIMAL * primal,SCIP_SOL * sol)1680 void SCIPprimalSolFreed(
1681 SCIP_PRIMAL* primal, /**< primal data */
1682 SCIP_SOL* sol /**< primal CIP solution */
1683 )
1684 {
1685 int idx;
1686
1687 assert(primal != NULL);
1688 assert(sol != NULL);
1689
1690 #ifndef NDEBUG
1691 for( idx = 0; idx < primal->nexistingsols; ++idx )
1692 {
1693 assert(idx == SCIPsolGetPrimalIndex(primal->existingsols[idx]));
1694 }
1695 #endif
1696
1697 /* remove solution */
1698 idx = SCIPsolGetPrimalIndex(sol);
1699 assert(0 <= idx && idx < primal->nexistingsols);
1700 assert(sol == primal->existingsols[idx]);
1701 if( idx < primal->nexistingsols-1 )
1702 {
1703 primal->existingsols[idx] = primal->existingsols[primal->nexistingsols-1];
1704 SCIPsolSetPrimalIndex(primal->existingsols[idx], idx);
1705 }
1706 primal->nexistingsols--;
1707 }
1708
1709 /** updates all existing primal solutions after a change in a variable's objective value */
SCIPprimalUpdateVarObj(SCIP_PRIMAL * primal,SCIP_VAR * var,SCIP_Real oldobj,SCIP_Real newobj)1710 void SCIPprimalUpdateVarObj(
1711 SCIP_PRIMAL* primal, /**< primal data */
1712 SCIP_VAR* var, /**< problem variable */
1713 SCIP_Real oldobj, /**< old objective value */
1714 SCIP_Real newobj /**< new objective value */
1715 )
1716 {
1717 int i;
1718
1719 assert(primal != NULL);
1720
1721 for( i = 0; i < primal->nexistingsols; ++i )
1722 {
1723 if( !SCIPsolIsOriginal(primal->existingsols[i]) )
1724 SCIPsolUpdateVarObj(primal->existingsols[i], var, oldobj, newobj);
1725 }
1726 }
1727
1728 /** retransforms all existing solutions to original problem space
1729 *
1730 * @note as a side effect, the objective value of the solutions can change (numerical errors)
1731 * so we update the objective cutoff value and upper bound accordingly
1732 */
SCIPprimalRetransformSolutions(SCIP_PRIMAL * primal,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_STAT * stat,SCIP_EVENTFILTER * eventfilter,SCIP_EVENTQUEUE * eventqueue,SCIP_PROB * origprob,SCIP_PROB * transprob,SCIP_TREE * tree,SCIP_REOPT * reopt,SCIP_LP * lp)1733 SCIP_RETCODE SCIPprimalRetransformSolutions(
1734 SCIP_PRIMAL* primal, /**< primal data */
1735 BMS_BLKMEM* blkmem, /**< block memory */
1736 SCIP_SET* set, /**< global SCIP settings */
1737 SCIP_STAT* stat, /**< problem statistics data */
1738 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
1739 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1740 SCIP_PROB* origprob, /**< original problem */
1741 SCIP_PROB* transprob, /**< transformed problem */
1742 SCIP_TREE* tree, /**< branch and bound tree */
1743 SCIP_REOPT* reopt, /**< reoptimization data structure */
1744 SCIP_LP* lp /**< current LP data */
1745 )
1746 {
1747 SCIP_Bool hasinfval;
1748 int i;
1749
1750 assert(primal != NULL);
1751
1752 for( i = 0; i < primal->nsols; ++i )
1753 {
1754 if( SCIPsolGetOrigin(primal->sols[i]) == SCIP_SOLORIGIN_ZERO )
1755 {
1756 SCIP_CALL( SCIPsolRetransform(primal->sols[i], set, stat, origprob, transprob, &hasinfval) );
1757 }
1758 }
1759
1760 sortPrimalSols(primal, set, origprob, transprob);
1761
1762 /* check if the global upper bound has to be updated
1763 * @todo we do not inform anybody about this change; if this leads to some
1764 * problem, a possible solution is to issue a BESTSOLFOUND event
1765 */
1766 if( primal->nsols > 0 )
1767 {
1768 SCIP_Real obj;
1769
1770 obj = SCIPsolGetObj(primal->sols[0], set, transprob, origprob);
1771 if( obj < primal->cutoffbound )
1772 {
1773 /* update the upper bound */
1774 SCIP_CALL( SCIPprimalSetUpperbound(primal, blkmem, set, stat, eventfilter, eventqueue, transprob, tree, reopt, lp, obj) );
1775 }
1776 }
1777
1778 return SCIP_OKAY;
1779 }
1780
1781 /** tries to transform original solution to the transformed problem space */
SCIPprimalTransformSol(SCIP_PRIMAL * primal,SCIP_SOL * sol,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_MESSAGEHDLR * messagehdlr,SCIP_STAT * stat,SCIP_PROB * origprob,SCIP_PROB * transprob,SCIP_TREE * tree,SCIP_REOPT * reopt,SCIP_LP * lp,SCIP_EVENTQUEUE * eventqueue,SCIP_EVENTFILTER * eventfilter,SCIP_Real * solvals,SCIP_Bool * solvalset,int solvalssize,SCIP_Bool * added)1782 SCIP_RETCODE SCIPprimalTransformSol(
1783 SCIP_PRIMAL* primal, /**< primal data */
1784 SCIP_SOL* sol, /**< primal solution */
1785 BMS_BLKMEM* blkmem, /**< block memory */
1786 SCIP_SET* set, /**< global SCIP settings */
1787 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1788 SCIP_STAT* stat, /**< problem statistics data */
1789 SCIP_PROB* origprob, /**< original problem */
1790 SCIP_PROB* transprob, /**< transformed problem after presolve */
1791 SCIP_TREE* tree, /**< branch and bound tree */
1792 SCIP_REOPT* reopt, /**< reoptimization data structure */
1793 SCIP_LP* lp, /**< current LP data */
1794 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1795 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
1796 SCIP_Real* solvals, /**< array for internal use to store solution values, or NULL;
1797 * if the method is called multiple times in a row, an array with size >=
1798 * number of active variables should be given for performance reasons */
1799 SCIP_Bool* solvalset, /**< array for internal use to store which solution values were set, or NULL;
1800 * if the method is called multiple times in a row, an array with size >=
1801 * number of active variables should be given for performance reasons */
1802 int solvalssize, /**< size of solvals and solvalset arrays, should be >= number of active
1803 * variables */
1804 SCIP_Bool* added /**< pointer to store whether the solution was added */
1805 )
1806 {
1807 SCIP_VAR** origvars;
1808 SCIP_VAR** transvars;
1809 SCIP_VAR* var;
1810 SCIP_Real* localsolvals;
1811 SCIP_Bool* localsolvalset;
1812 SCIP_Real solval;
1813 SCIP_Real scalar;
1814 SCIP_Real constant;
1815 SCIP_Bool localarrays;
1816 SCIP_Bool feasible;
1817 int norigvars;
1818 int ntransvars;
1819 int nvarsset;
1820 int v;
1821
1822 assert(origprob != NULL);
1823 assert(transprob != NULL);
1824 assert(SCIPsolIsOriginal(sol));
1825 assert(solvalssize == 0 || solvals != NULL);
1826 assert(solvalssize == 0 || solvalset != NULL);
1827
1828 origvars = origprob->vars;
1829 norigvars = origprob->nvars;
1830 transvars = transprob->vars;
1831 ntransvars = transprob->nvars;
1832 assert(solvalssize == 0 || solvalssize >= ntransvars);
1833
1834 SCIPsetDebugMsg(set, "try to transfer original solution %p with objective %g into the transformed problem space\n",
1835 (void*)sol, SCIPsolGetOrigObj(sol));
1836
1837 /* if no solvals and solvalset arrays are given, allocate local ones, otherwise use the given ones */
1838 localarrays = (solvalssize == 0);
1839 if( localarrays )
1840 {
1841 SCIP_CALL( SCIPsetAllocBufferArray(set, &localsolvals, ntransvars) );
1842 SCIP_CALL( SCIPsetAllocBufferArray(set, &localsolvalset, ntransvars) );
1843 }
1844 else
1845 {
1846 localsolvals = solvals;
1847 localsolvalset = solvalset;
1848 }
1849
1850 BMSclearMemoryArray(localsolvalset, ntransvars);
1851 feasible = TRUE;
1852 (*added) = FALSE;
1853 nvarsset = 0;
1854
1855 /* for each original variable, get the corresponding active, fixed or multi-aggregated variable;
1856 * if it resolves to an active variable, we set its solution value or check whether an already stored solution value
1857 * is consistent; if it resolves to a fixed variable, we check that the fixing matches the original solution value;
1858 * multi-aggregated variables are skipped, because their value is defined by setting solution values for the active
1859 * variables, anyway
1860 */
1861 for( v = 0; v < norigvars && feasible; ++v )
1862 {
1863 var = origvars[v];
1864
1865 solval = SCIPsolGetVal(sol, set, stat, var);
1866
1867 /* get corresponding active, fixed, or multi-aggregated variable */
1868 scalar = 1.0;
1869 constant = 0.0;
1870 SCIP_CALL( SCIPvarGetProbvarSum(&var, set, &scalar, &constant) );
1871 assert(SCIPvarIsActive(var) || SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED
1872 || SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR);
1873
1874 /* check whether the fixing corresponds to the solution value of the original variable */
1875 if( scalar == 0.0 )
1876 {
1877 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED ||
1878 (SCIPsetIsInfinity(set, constant) || SCIPsetIsInfinity(set, -constant)));
1879
1880 if( !SCIPsetIsEQ(set, solval, constant) )
1881 {
1882 SCIPsetDebugMsg(set, "original variable <%s> (solval=%g) resolves to fixed variable <%s> (original solval=%g)\n",
1883 SCIPvarGetName(origvars[v]), solval, SCIPvarGetName(var), constant);
1884 feasible = FALSE;
1885 }
1886 }
1887 else if( SCIPvarIsActive(var) )
1888 {
1889 /* if we already assigned a solution value to the transformed variable, check that it corresponds to the
1890 * value obtained from the currently regarded original variable
1891 */
1892 if( localsolvalset[SCIPvarGetProbindex(var)] )
1893 {
1894 if( !SCIPsetIsEQ(set, solval, scalar * localsolvals[SCIPvarGetProbindex(var)] + constant) )
1895 {
1896 SCIPsetDebugMsg(set, "original variable <%s> (solval=%g) resolves to active variable <%s> with assigned solval %g (original solval=%g)\n",
1897 SCIPvarGetName(origvars[v]), solval, SCIPvarGetName(var), localsolvals[SCIPvarGetProbindex(var)],
1898 scalar * localsolvals[SCIPvarGetProbindex(var)] + constant);
1899 feasible = FALSE;
1900 }
1901 }
1902 /* assign solution value to the transformed variable */
1903 else
1904 {
1905 assert(scalar != 0.0);
1906
1907 localsolvals[SCIPvarGetProbindex(var)] = (solval - constant) / scalar;
1908 localsolvalset[SCIPvarGetProbindex(var)] = TRUE;
1909 ++nvarsset;
1910 }
1911 }
1912 #ifndef NDEBUG
1913 /* we do not have to handle multi-aggregated variables here, since by assigning values to all active variabes,
1914 * we implicitly assign values to the multi-aggregated variables, too
1915 */
1916 else
1917 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR);
1918 #endif
1919 }
1920
1921 /* if the solution values of fixed and active variables lead to no contradiction, construct solution and try it */
1922 if( feasible )
1923 {
1924 SCIP_SOL* transsol;
1925
1926 SCIP_CALL( SCIPsolCreate(&transsol, blkmem, set, stat, primal, tree, SCIPsolGetHeur(sol)) );
1927
1928 /* set solution values for variables to which we assigned a value */
1929 for( v = 0; v < ntransvars; ++v )
1930 {
1931 if( localsolvalset[v] )
1932 {
1933 SCIP_CALL( SCIPsolSetVal(transsol, set, stat, tree, transvars[v], localsolvals[v]) );
1934 }
1935 }
1936
1937 SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob,
1938 tree, reopt, lp, eventqueue, eventfilter, &transsol, FALSE, FALSE, TRUE, TRUE, TRUE, added) );
1939
1940 SCIPsetDebugMsg(set, "solution transferred, %d/%d active variables set (stored=%u)\n", nvarsset, ntransvars, *added);
1941 }
1942 else
1943 (*added) = FALSE;
1944
1945 /* free local arrays, if needed */
1946 if( localarrays )
1947 {
1948 SCIPsetFreeBufferArray(set, &localsolvalset);
1949 SCIPsetFreeBufferArray(set, &localsolvals);
1950 }
1951
1952 return SCIP_OKAY;
1953 }
1954
1955
1956 /** is the updating of violations enabled for this problem? */
SCIPprimalUpdateViolations(SCIP_PRIMAL * primal)1957 SCIP_Bool SCIPprimalUpdateViolations(
1958 SCIP_PRIMAL* primal /**< problem data */
1959 )
1960 {
1961 assert(primal != NULL);
1962
1963 return primal->updateviolations;
1964 }
1965
1966 /** set whether the updating of violations is turned on */
SCIPprimalSetUpdateViolations(SCIP_PRIMAL * primal,SCIP_Bool updateviolations)1967 void SCIPprimalSetUpdateViolations(
1968 SCIP_PRIMAL* primal, /**< problem data */
1969 SCIP_Bool updateviolations /**< marks whether the updating of violations is turned on */
1970 )
1971 {
1972 assert(primal != NULL);
1973
1974 primal->updateviolations = updateviolations;
1975 }
1976