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