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