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   pricestore.c
26   	 * @ingroup OTHER_CFILES
27   	 * @brief  methods for storing priced variables
28   	 * @author Tobias Achterberg
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#include "scip/clock.h"
34   	#include "scip/lp.h"
35   	#include "scip/pricestore.h"
36   	#include "scip/pub_lp.h"
37   	#include "scip/pub_message.h"
38   	#include "scip/pub_var.h"
39   	#include "scip/set.h"
40   	#include "scip/struct_lp.h"
41   	#include "scip/struct_pricestore.h"
42   	#include "scip/struct_prob.h"
43   	#include "scip/struct_set.h"
44   	#include "scip/struct_var.h"
45   	#include "scip/tree.h"
46   	#include "scip/var.h"
47   	
48   	
49   	
50   	/*
51   	 * dynamic memory arrays
52   	 */
53   	
54   	/** resizes vars and score arrays to be able to store at least num entries */
55   	static
56   	SCIP_RETCODE pricestoreEnsureVarsMem(
57   	   SCIP_PRICESTORE*      pricestore,         /**< pricing storage */
58   	   SCIP_SET*             set,                /**< global SCIP settings */
59   	   int                   num                 /**< minimal number of slots in array */
60   	   )
61   	{
62   	   assert(pricestore != NULL);
63   	   assert(set != NULL);
64   	
65   	   if( num > pricestore->varssize )
66   	   {
67   	      int newsize;
68   	
69   	      newsize = SCIPsetCalcMemGrowSize(set, num);
70   	      SCIP_ALLOC( BMSreallocMemoryArray(&pricestore->vars, newsize) );
71   	      SCIP_ALLOC( BMSreallocMemoryArray(&pricestore->scores, newsize) );
72   	      pricestore->varssize = newsize;
73   	   }
74   	   assert(num <= pricestore->varssize);
75   	
76   	   return SCIP_OKAY;
77   	}
78   	
79   	/** resizes bdviolvars arrays to be able to store at least num entries */
80   	static
81   	SCIP_RETCODE pricestoreEnsureBdviolvarsMem(
82   	   SCIP_PRICESTORE*      pricestore,         /**< pricing storage */
83   	   SCIP_SET*             set,                /**< global SCIP settings */
84   	   int                   num                 /**< minimal number of slots in array */
85   	   )
86   	{
87   	   assert(pricestore != NULL);
88   	   assert(set != NULL);
89   	
90   	   if( num > pricestore->bdviolvarssize )
91   	   {
92   	      int newsize;
93   	
94   	      newsize = SCIPsetCalcMemGrowSize(set, num);
95   	      SCIP_ALLOC( BMSreallocMemoryArray(&pricestore->bdviolvars, newsize) );
96   	      SCIP_ALLOC( BMSreallocMemoryArray(&pricestore->bdviolvarslb, newsize) );
97   	      SCIP_ALLOC( BMSreallocMemoryArray(&pricestore->bdviolvarsub, newsize) );
98   	      pricestore->bdviolvarssize = newsize;
99   	   }
100  	   assert(num <= pricestore->bdviolvarssize);
101  	
102  	   return SCIP_OKAY;
103  	}
104  	
105  	
106  	/** creates pricing storage */
107  	SCIP_RETCODE SCIPpricestoreCreate(
108  	   SCIP_PRICESTORE**     pricestore          /**< pointer to store pricing storage */
109  	   )
110  	{
111  	   assert(pricestore != NULL);
112  	
113  	   SCIP_ALLOC( BMSallocMemory(pricestore) );
114  	
115  	   SCIP_CALL( SCIPclockCreate(&(*pricestore)->probpricingtime, SCIP_CLOCKTYPE_DEFAULT) );
116  	   (*pricestore)->vars = NULL;
117  	   (*pricestore)->scores = NULL;
118  	   (*pricestore)->bdviolvars = NULL;
119  	   (*pricestore)->bdviolvarslb = NULL;
120  	   (*pricestore)->bdviolvarsub = NULL;
121  	   (*pricestore)->varssize = 0;
122  	   (*pricestore)->nvars = 0;
123  	   (*pricestore)->bdviolvarssize = 0;
124  	   (*pricestore)->nbdviolvars = 0;
125  	   (*pricestore)->naddedbdviolvars = 0;
126  	   (*pricestore)->nprobpricings = 0;
127  	   (*pricestore)->nprobvarsfound = 0;
128  	   (*pricestore)->nvarsfound = 0;
129  	   (*pricestore)->nvarsapplied = 0;
130  	   (*pricestore)->initiallp = FALSE;
131  	
132  	   return SCIP_OKAY;
133  	}
134  	
135  	/** frees pricing storage */
136  	SCIP_RETCODE SCIPpricestoreFree(
137  	   SCIP_PRICESTORE**     pricestore          /**< pointer to store pricing storage */
138  	   )
139  	{
140  	   assert(pricestore != NULL);
141  	   assert(*pricestore != NULL);
142  	   assert((*pricestore)->nvars == 0);
143  	   assert((*pricestore)->nbdviolvars == 0);
144  	
145  	   SCIPclockFree(&(*pricestore)->probpricingtime);
146  	   BMSfreeMemoryArrayNull(&(*pricestore)->vars);
147  	   BMSfreeMemoryArrayNull(&(*pricestore)->scores);
148  	   BMSfreeMemoryArrayNull(&(*pricestore)->bdviolvars);
149  	   BMSfreeMemoryArrayNull(&(*pricestore)->bdviolvarslb);
150  	   BMSfreeMemoryArrayNull(&(*pricestore)->bdviolvarsub);
151  	   BMSfreeMemory(pricestore);
152  	
153  	   return SCIP_OKAY;
154  	}
155  	
156  	/** informs pricing storage, that the setup of the initial LP starts now */
157  	void SCIPpricestoreStartInitialLP(
158  	   SCIP_PRICESTORE*      pricestore          /**< pricing storage */
159  	   )
160  	{
161  	   assert(pricestore != NULL);
162  	   assert(!pricestore->initiallp);
163  	   assert(pricestore->nvars == 0);
164  	
165  	   pricestore->initiallp = TRUE;
166  	}
167  	
168  	/** informs pricing storage, that the setup of the initial LP is now finished */
169  	void SCIPpricestoreEndInitialLP(
170  	   SCIP_PRICESTORE*      pricestore          /**< pricing storage */
171  	   )
172  	{
173  	   assert(pricestore != NULL);
174  	   assert(pricestore->initiallp);
175  	   assert(pricestore->nvars == 0);
176  	
177  	   pricestore->initiallp = FALSE;
178  	}
179  	
180  	/** adds variable to pricing storage and capture it */
181  	SCIP_RETCODE SCIPpricestoreAddVar(
182  	   SCIP_PRICESTORE*      pricestore,         /**< pricing storage */
183  	   BMS_BLKMEM*           blkmem,             /**< block memory */
184  	   SCIP_SET*             set,                /**< global SCIP settings */
185  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
186  	   SCIP_LP*              lp,                 /**< LP data */
187  	   SCIP_VAR*             var,                /**< priced variable */
188  	   SCIP_Real             score,              /**< pricing score of variable (the larger, the better the variable) */
189  	   SCIP_Bool             root                /**< are we at the root node? */
190  	   )
191  	{
192  	   int maxpricevars;
193  	   int v;
194  	
195  	   assert(pricestore != NULL);
196  	   assert(set != NULL);
197  	   assert(var != NULL);
198  	
199  	#ifndef NDEBUG
200  	   /* check if we add this variables to the same scip, where we created it */
201  	   if( var->scip != set->scip )
202  	   {
203  	      SCIPerrorMessage("try to add a variable of another scip instance\n");
204  	      return SCIP_INVALIDDATA;
205  	   }
206  	#endif
207  	
208  	   SCIPsetDebugMsg(set, "adding variable <%s> (lb=%g, ub=%g) to pricing storage (initiallp=%u)\n",
209  	      SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), pricestore->initiallp);
210  	
211  	   if( pricestore->initiallp )
212  	      maxpricevars = INT_MAX;
213  	   else
214  	   {
215  	      pricestore->nvarsfound++;
216  	      maxpricevars = SCIPsetGetPriceMaxvars(set, root);
217  	   }
218  	   assert(maxpricevars >= 1);
219  	   assert(pricestore->nvars <= maxpricevars);
220  	
221  	   /* check, if variable belongs to the best "maxpricevars" pricing variables */
222  	   if( pricestore->nvars < maxpricevars || score > pricestore->scores[maxpricevars-1] )
223  	   {
224  	      /* capture variable */
225  	      SCIPvarCapture(var);
226  	
227  	      /* if the array consists of "maxpricevars" variables, release the worst variables */
228  	      if( pricestore->nvars == maxpricevars )
229  	      {
230  	         SCIP_CALL( SCIPvarRelease(&pricestore->vars[pricestore->nvars-1], blkmem, set, eventqueue, lp) );
231  	         pricestore->nvars--;
232  	      }
233  	      assert(pricestore->nvars < maxpricevars);
234  	
235  	      /* get enough memory to store additional variable */
236  	      SCIP_CALL( pricestoreEnsureVarsMem(pricestore, set, pricestore->nvars+1) );
237  	      assert(pricestore->nvars <= pricestore->varssize);
238  	
239  	      /* insert the variable at the correct position in sorted arrays */
240  	      for( v = pricestore->nvars; v > 0 && score > pricestore->scores[v-1]; --v )
241  	      {
242  	         pricestore->vars[v] = pricestore->vars[v-1];
243  	         pricestore->scores[v] = pricestore->scores[v-1];
244  	      }
245  	      pricestore->vars[v] = var;
246  	      pricestore->scores[v] = score;
247  	      pricestore->nvars++;
248  	   }
249  	
250  	   return SCIP_OKAY;
251  	}
252  	
253  	/** adds variable where zero violates the bounds to pricing storage, capture it */
254  	SCIP_RETCODE SCIPpricestoreAddBdviolvar(
255  	   SCIP_PRICESTORE*      pricestore,         /**< pricing storage */
256  	   BMS_BLKMEM*           blkmem,             /**< block memory */
257  	   SCIP_SET*             set,                /**< global SCIP settings */
258  	   SCIP_STAT*            stat,               /**< problem statistics */
259  	   SCIP_LP*              lp,                 /**< LP data */
260  	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
261  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
262  	   SCIP_VAR*             var                 /**< variable, where zero violates the bounds */
263  	   )
264  	{
265  	   assert(pricestore != NULL);
266  	   assert(set != NULL);
267  	   assert(var != NULL);
268  	   assert(SCIPsetIsPositive(set, SCIPvarGetLbLocal(var)) || SCIPsetIsNegative(set, SCIPvarGetUbLocal(var)));
269  	   assert(pricestore->naddedbdviolvars <= pricestore->nbdviolvars);
270  	
271  	   SCIPsetDebugMsg(set, "zero violates bounds of <%s> (lb=%g, ub=%g)\n", SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var));
272  	
273  	   if( !pricestore->initiallp )
274  	      pricestore->nvarsfound++;
275  	
276  	   /* get enough memory to store additional variable */
277  	   SCIP_CALL( pricestoreEnsureBdviolvarsMem(pricestore, set, pricestore->nbdviolvars+1) );
278  	   assert(pricestore->nbdviolvars <= pricestore->bdviolvarssize);
279  	
280  	   /* capture variable */
281  	   SCIPvarCapture(var);
282  	
283  	   /* insert variable in bdviolvars arrays */
284  	   pricestore->bdviolvars[pricestore->nbdviolvars] = var;
285  	   pricestore->bdviolvarslb[pricestore->nbdviolvars] = SCIPvarGetLbLocal(var);
286  	   pricestore->bdviolvarsub[pricestore->nbdviolvars] = SCIPvarGetUbLocal(var);
287  	   pricestore->nbdviolvars++;
288  	
289  	   /* Temporarily set bounds, such that zero is feasible, because we don't want to destroy
290  	    * dual feasibility (by adding columns) and primal feasibility (by introducing violated bounds)
291  	    * at the same time.
292  	    * The correct bounds must be reset with a call to SCIPpricestoreResetBounds().
293  	    * The inference information is unimportant for this temporary bound change.
294  	    */
295  	   if( SCIPsetIsPositive(set, SCIPvarGetLbLocal(var)) )
296  	   {
297  	      SCIP_CALL( SCIPvarChgLbLocal(var, blkmem, set, stat, lp, branchcand, eventqueue, 0.0) );
298  	   }
299  	   else
300  	   {
301  	      SCIP_CALL( SCIPvarChgUbLocal(var, blkmem, set, stat, lp, branchcand, eventqueue, 0.0) );
302  	   }
303  	
304  	   return SCIP_OKAY;
305  	}
306  	
307  	/** adds given problem variable to pricing storage, if zero is not best bound w.r.t. objective function */
308  	static
309  	SCIP_RETCODE addBoundViolated(
310  	   SCIP_PRICESTORE*      pricestore,         /**< pricing storage */
311  	   BMS_BLKMEM*           blkmem,             /**< block memory buffers */
312  	   SCIP_SET*             set,                /**< global SCIP settings */
313  	   SCIP_STAT*            stat,               /**< dynamic problem statistics */
314  	   SCIP_TREE*            tree,               /**< branch and bound tree */
315  	   SCIP_LP*              lp,                 /**< LP data */
316  	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
317  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
318  	   SCIP_VAR*             var,                /**< problem variable */
319  	   SCIP_Bool*            added               /**< pointer to store whether variable was added to pricing storage */
320  	   )
321  	{
322  	   assert(tree != NULL);
323  	   assert(added != NULL);
324  	
325  	   *added = FALSE;
326  	
327  	   /* add variable, if zero is not feasible within the bounds */
328  	   if( SCIPsetIsPositive(set, SCIPvarGetLbLocal(var)) || SCIPsetIsNegative(set, SCIPvarGetUbLocal(var)) )
329  	   {
330  	      SCIPsetDebugMsg(set, " -> zero violates bounds of <%s> [%g,%g]\n", SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var));
331  	      SCIP_CALL( SCIPpricestoreAddBdviolvar(pricestore, blkmem, set, stat, lp, branchcand, eventqueue, var) );
332  	      *added = TRUE;
333  	   }
334  	   else
335  	   {
336  	      SCIP_Real bestbound;
337  	
338  	      /* add variable, if zero is not best bound w.r.t. objective function */
339  	      bestbound = SCIPvarGetBestBoundLocal(var);
340  	      if( !SCIPsetIsZero(set, bestbound) )
341  	      {
342  	         SCIPsetDebugMsg(set, " -> best bound of <%s> [%g,%g] is not zero but %g\n",
343  	            SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), bestbound);
344  	         SCIP_CALL( SCIPpricestoreAddVar(pricestore, blkmem, set, eventqueue, lp, var, 
345  	               -SCIPvarGetObj(var) * bestbound, (SCIPtreeGetCurrentDepth(tree) == 0)) );
346  	         *added = TRUE;
347  	      }
348  	   }
349  	
350  	   return SCIP_OKAY;
351  	}
352  	
353  	/** adds problem variables with negative reduced costs to pricing storage */
354  	SCIP_RETCODE SCIPpricestoreAddProbVars(
355  	   SCIP_PRICESTORE*      pricestore,         /**< pricing storage */
356  	   BMS_BLKMEM*           blkmem,             /**< block memory buffers */
357  	   SCIP_SET*             set,                /**< global SCIP settings */
358  	   SCIP_STAT*            stat,               /**< dynamic problem statistics */
359  	   SCIP_PROB*            prob,               /**< transformed problem after presolve */
360  	   SCIP_TREE*            tree,               /**< branch and bound tree */
361  	   SCIP_LP*              lp,                 /**< LP data */
362  	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
363  	   SCIP_EVENTQUEUE*      eventqueue          /**< event queue */
364  	   )
365  	{
366  	   SCIP_VAR* var;
367  	   SCIP_COL* col;
368  	   SCIP_Bool root;
369  	   SCIP_Bool added;
370  	   int v;
371  	   int abortpricevars;
372  	   int maxpricevars;
373  	   int nfoundvars;
374  	
375  	   assert(pricestore != NULL);
376  	   assert(set != NULL);
377  	   assert(stat != NULL);
378  	   assert(prob != NULL);
379  	   assert(lp != NULL);
380  	   assert(lp->solved);
381  	   assert(tree != NULL);
382  	   assert(SCIPtreeHasCurrentNodeLP(tree));
383  	   assert(prob->nvars >= SCIPlpGetNCols(lp));
384  	
385  	   /* if all problem variables of status COLUMN are already in the LP, nothing has to be done */
386  	   if( prob->ncolvars == SCIPlpGetNCols(lp) )
387  	      return SCIP_OKAY;
388  	
389  	   root = (SCIPtreeGetCurrentDepth(tree) == 0);
390  	   maxpricevars = SCIPsetGetPriceMaxvars(set, root);
391  	   assert(maxpricevars >= 1);
392  	   abortpricevars = (int)(set->price_abortfac * maxpricevars);
393  	   assert(abortpricevars >= maxpricevars);
394  	
395  	   /**@todo test pricing: is abortpricevars a good idea? -> like strong branching, lookahead, ... */
396  	
397  	   pricestore->nprobpricings++;
398  	
399  	   /* start timing */
400  	   SCIPclockStart(pricestore->probpricingtime, set);
401  	
402  	   /* price already existing problem variables */
403  	   nfoundvars = 0;
404  	   for( v = 0; v < prob->nvars && nfoundvars < abortpricevars; ++v )
405  	   {
406  	      var = prob->vars[v];
407  	      if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN )
408  	      {
409  	         col = SCIPvarGetCol(var);
410  	         assert(col != NULL);
411  	         assert(col->var == var);
412  	         assert(col->len >= 0);
413  	         assert(col->lppos >= -1);
414  	         assert(col->lpipos >= -1);
415  	         assert(SCIPcolIsInLP(col) == (col->lpipos >= 0));
416  	
417  	         if( !SCIPcolIsInLP(col) )
418  	         {
419  	            SCIPsetDebugMsg(set, "price column variable <%s> in bounds [%g,%g]\n",
420  	               SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var));
421  	
422  	            /* add variable to pricing storage, if zero is not best bound w.r.t. objective function */
423  	            SCIP_CALL( addBoundViolated(pricestore, blkmem, set, stat, tree, lp, branchcand, eventqueue, var, &added) );
424  	
425  	            if( added )
426  	            {
427  	               pricestore->nprobvarsfound++;
428  	               nfoundvars++;
429  	            }
430  	            else if( SCIPcolGetNNonz(col) > 0 )
431  	            {
432  	               SCIP_Real feasibility;
433  	
434  	               /* a column not in LP that doesn't have zero in its bounds was added by bound checking above */
435  	               assert(!SCIPsetIsPositive(set, SCIPvarGetLbLocal(col->var)));
436  	               assert(!SCIPsetIsNegative(set, SCIPvarGetUbLocal(col->var)));
437  	
438  	               if( SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_INFEASIBLE )
439  	               {
440  	                  /* The LP was proven infeasible, so we have an infeasibility proof by the dual Farkas multipliers y.
441  	                   * The valid inequality  y^T A x >= y^T b  is violated by all x, especially by the (for this
442  	                   * inequality most feasible solution) x' defined by 
443  	                   *    x'_i = ub_i, if y^T A_i > 0
444  	                   *    x'_i = lb_i, if y^T A_i <= 0.
445  	                   * Pricing in this case means to add variables i with positive Farkas value, i.e. y^T A_i x'_i > 0
446  	                   */
447  	                  feasibility = -SCIPcolGetFarkasValue(col, stat, lp);
448  	                  SCIPsetDebugMsg(set, "  <%s> Farkas feasibility: %e\n", SCIPvarGetName(col->var), feasibility);
449  	               }
450  	               else
451  	               {
452  	                  /* The dual LP is feasible, and we have a feasible dual solution. Pricing in this case means to
453  	                   * add variables with negative feasibility, that is
454  	                   *  - positive reduced costs for variables with negative lower bound
455  	                   *  - negative reduced costs for variables with positive upper bound
456  	                   */
457  	                  feasibility = SCIPcolGetFeasibility(col, set, stat, lp);
458  	                  SCIPsetDebugMsg(set, "  <%s> reduced cost feasibility: %e\n", SCIPvarGetName(col->var), feasibility);
459  	               }
460  	
461  	               /* add variable if feasibility is negative, i.e., the reduced costs are negative */
462  	               if( !SCIPsetIsPositive(set, feasibility) )
463  	               {
464  	                  SCIP_CALL( SCIPpricestoreAddVar(pricestore, blkmem, set, eventqueue, lp, var, -feasibility / (col->len+1), root) );
465  	                  pricestore->nprobvarsfound++;
466  	                  nfoundvars++;
467  	               }
468  	            }
469  	         }
470  	      }
471  	   }
472  	
473  	   /* stop timing */
474  	   SCIPclockStop(pricestore->probpricingtime, set);
475  	
476  	   return SCIP_OKAY;
477  	}
478  	
479  	/** adds priced variables to the LP */
480  	SCIP_RETCODE SCIPpricestoreApplyVars(
481  	   SCIP_PRICESTORE*      pricestore,         /**< pricing storage */
482  	   BMS_BLKMEM*           blkmem,             /**< block memory buffers */
483  	   SCIP_SET*             set,                /**< global SCIP settings */
484  	   SCIP_STAT*            stat,               /**< dynamic problem statistics */
485  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
486  	   SCIP_PROB*            prob,               /**< transformed problem after presolve */
487  	   SCIP_TREE*            tree,               /**< branch and bound tree */
488  	   SCIP_LP*              lp                  /**< LP data */
489  	   )
490  	{
491  	   SCIP_VAR* var;
492  	   SCIP_COL* col;
493  	   int v;
494  	
495  	   assert(pricestore != NULL);
496  	   assert(pricestore->naddedbdviolvars <= pricestore->nbdviolvars);
497  	   assert(set != NULL);
498  	   assert(prob != NULL);
499  	   assert(lp != NULL);
500  	   assert(tree != NULL);
501  	   assert(SCIPtreeIsFocusNodeLPConstructed(tree));
502  	
503  	   SCIPsetDebugMsg(set, "adding %d variables (%d bound violated and %d priced vars) to %d LP columns\n",
504  	      SCIPpricestoreGetNVars(pricestore), pricestore->nbdviolvars - pricestore->naddedbdviolvars,
505  	      pricestore->nvars, SCIPlpGetNCols(lp));
506  	
507  	   /* add the variables with violated bounds to LP */
508  	   for( v = pricestore->naddedbdviolvars; v < pricestore->nbdviolvars; ++v )
509  	   {
510  	      var = pricestore->bdviolvars[v];
511  	      assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
512  	      assert(SCIPvarGetProbindex(var) >= 0);
513  	      assert(var->nuses >= 2); /* at least used in pricing storage and in problem */
514  	
515  	      if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE )
516  	      {
517  	         /* transform loose variable into column variable */
518  	         SCIP_CALL( SCIPvarColumn(var, blkmem, set, stat, prob, lp) );
519  	      }
520  	      assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
521  	
522  	      col = SCIPvarGetCol(var);
523  	      assert(col != NULL);
524  	      assert(col->lppos == -1);
525  	      SCIPsetDebugMsg(set, "adding bound violated variable <%s> (lb=%g, ub=%g)\n", SCIPvarGetName(var),
526  	         pricestore->bdviolvarslb[v], pricestore->bdviolvarsub[v]);
527  	      SCIP_CALL( SCIPlpAddCol(lp, set, col, SCIPtreeGetCurrentDepth(tree)) );
528  	
529  	      if( !pricestore->initiallp )
530  	         pricestore->nvarsapplied++;
531  	   }
532  	   pricestore->naddedbdviolvars = pricestore->nbdviolvars;
533  	
534  	   /* add the selected pricing variables to LP */
535  	   for( v = 0; v < pricestore->nvars; ++v )
536  	   {
537  	      var = pricestore->vars[v];
538  	      assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
539  	      assert(SCIPvarGetProbindex(var) >= 0);
540  	      assert(var->nuses >= 2); /* at least used in pricing storage and in problem */
541  	
542  	      /* transform variable into column variable, if needed */
543  	      if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE )
544  	      {
545  	         SCIP_CALL( SCIPvarColumn(var, blkmem, set, stat, prob, lp) );
546  	      }
547  	      assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
548  	
549  	      col = SCIPvarGetCol(var);
550  	      assert(col != NULL);
551  	      assert(col->lppos == -1);
552  	      SCIPsetDebugMsg(set, "adding priced variable <%s> (score=%g)\n", SCIPvarGetName(var), pricestore->scores[v]);
553  	      SCIP_CALL( SCIPlpAddCol(lp, set, col, SCIPtreeGetCurrentDepth(tree)) );
554  	
555  	      /* release the variable */
556  	      SCIP_CALL( SCIPvarRelease(&pricestore->vars[v], blkmem, set, eventqueue, lp) );
557  	
558  	      if( !pricestore->initiallp )
559  	         pricestore->nvarsapplied++;
560  	   }
561  	
562  	   /* clear the pricing storage */
563  	   pricestore->nvars = 0;
564  	
565  	   return SCIP_OKAY;
566  	}
567  	
568  	/** reset variables' bounds violated by zero to its original value */
569  	SCIP_RETCODE SCIPpricestoreResetBounds(
570  	   SCIP_PRICESTORE*      pricestore,         /**< pricing storage */
571  	   BMS_BLKMEM*           blkmem,             /**< block memory */
572  	   SCIP_SET*             set,                /**< global SCIP settings */
573  	   SCIP_STAT*            stat,               /**< problem statistics */
574  	   SCIP_LP*              lp,                 /**< LP data */
575  	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
576  	   SCIP_EVENTQUEUE*      eventqueue          /**< event queue */
577  	   )
578  	{
579  	   SCIP_VAR* var;
580  	   int v;
581  	
582  	   assert(pricestore != NULL);
583  	   assert(set != NULL);
584  	   assert(lp != NULL);
585  	   assert(pricestore->nvars == 0);
586  	   assert(pricestore->naddedbdviolvars == pricestore->nbdviolvars);
587  	
588  	   /* reset variables' bounds, release them, and clear the boundviolation storage;
589  	    * the inference information is unimportant in these removals of temporary bound changes
590  	    */
591  	   for( v = 0; v < pricestore->nbdviolvars; ++v )
592  	   {
593  	      var = pricestore->bdviolvars[v];
594  	      assert(var != NULL);
595  	
596  	      SCIPsetDebugMsg(set, "resetting bounds of <%s> from [%g,%g] to [%g,%g]\n", var->name,
597  	         SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), pricestore->bdviolvarslb[v], pricestore->bdviolvarsub[v]);
598  	      SCIP_CALL( SCIPvarChgLbLocal(var, blkmem, set, stat, lp, branchcand, eventqueue, pricestore->bdviolvarslb[v]) );
599  	      SCIP_CALL( SCIPvarChgUbLocal(var, blkmem, set, stat, lp, branchcand, eventqueue, pricestore->bdviolvarsub[v]) );
600  	      SCIP_CALL( SCIPvarRelease(&pricestore->bdviolvars[v], blkmem, set, eventqueue, lp) );
601  	   }
602  	   pricestore->naddedbdviolvars = 0;
603  	   pricestore->nbdviolvars = 0;
604  	
605  	   return SCIP_OKAY;
606  	}
607  	
608  	/** gets number of variables in pricing storage */
609  	int SCIPpricestoreGetNVars(
610  	   SCIP_PRICESTORE*      pricestore          /**< pricing storage */
611  	   )
612  	{
613  	   assert(pricestore != NULL);
614  	   assert(pricestore->nbdviolvars >= pricestore->naddedbdviolvars);
615  	
616  	   return pricestore->nvars + pricestore->nbdviolvars - pricestore->naddedbdviolvars;
617  	}
618  	
619  	/** gets number of variables in pricing storage whose bounds must be reset */
620  	int SCIPpricestoreGetNBoundResets(
621  	   SCIP_PRICESTORE*      pricestore          /**< pricing storage */
622  	   )
623  	{
624  	   assert(pricestore != NULL);
625  	   assert(pricestore->nbdviolvars >= pricestore->naddedbdviolvars);
626  	
627  	   return pricestore->nbdviolvars - pricestore->naddedbdviolvars;
628  	}
629  	
630  	/** gets time needed to price existing problem variables */
631  	SCIP_Real SCIPpricestoreGetProbPricingTime(
632  	   SCIP_PRICESTORE*      pricestore          /**< pricing storage */
633  	   )
634  	{
635  	   assert(pricestore != NULL);
636  	
637  	   return SCIPclockGetTime(pricestore->probpricingtime);
638  	}
639  	
640  	/** gets total number of calls to problem variable pricing */
641  	int SCIPpricestoreGetNProbPricings(
642  	   SCIP_PRICESTORE*      pricestore          /**< pricing storage */
643  	   )
644  	{
645  	   assert(pricestore != NULL);
646  	
647  	   return pricestore->nprobpricings;
648  	}
649  	
650  	/** gets total number of times, a problem variable was priced in */
651  	int SCIPpricestoreGetNProbvarsFound(
652  	   SCIP_PRICESTORE*      pricestore          /**< pricing storage */
653  	   )
654  	{
655  	   assert(pricestore != NULL);
656  	
657  	   return pricestore->nprobvarsfound;
658  	}
659  	
660  	/** get total number of variables found so far in pricing */
661  	int SCIPpricestoreGetNVarsFound(
662  	   SCIP_PRICESTORE*      pricestore          /**< pricing storage */
663  	   )
664  	{
665  	   assert(pricestore != NULL);
666  	
667  	   return pricestore->nvarsfound;
668  	}
669  	
670  	/** get total number of variables priced into the LP so far */
671  	int SCIPpricestoreGetNVarsApplied(
672  	   SCIP_PRICESTORE*      pricestore          /**< pricing storage */
673  	   )
674  	{
675  	   assert(pricestore != NULL);
676  	
677  	   return pricestore->nvarsapplied;
678  	}
679  	
680