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