Scippy

SCIP

Solving Constraint Integer Programs

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