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-2020 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
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
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 */
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 */
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 */
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 */
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 */
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 */
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);
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
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 */
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 */
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];
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",
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 
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 */
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];
503  assert(SCIPvarGetProbindex(var) >= 0);
504  assert(var->nuses >= 2); /* at least used in pricing storage and in problem */
505 
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];
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
663  SCIP_PRICESTORE* pricestore /**< pricing storage */
664  )
665 {
666  assert(pricestore != NULL);
667 
668  return pricestore->nvarsapplied;
669 }
670 
SCIP_EXPORT SCIP_Real SCIPvarGetBestBoundLocal(SCIP_VAR *var)
Definition: var.c:17753
void SCIPpricestoreEndInitialLP(SCIP_PRICESTORE *pricestore)
Definition: pricestore.c:160
data structures for storing priced variables
#define BMSfreeMemoryArrayNull(ptr)
Definition: memory.h:140
internal methods for branch and bound tree
char * name
Definition: struct_var.h:226
int SCIPpricestoreGetNVars(SCIP_PRICESTORE *pricestore)
Definition: pricestore.c:600
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:245
int SCIPpricestoreGetNProbvarsFound(SCIP_PRICESTORE *pricestore)
Definition: pricestore.c:642
SCIP_Real SCIPpricestoreGetProbPricingTime(SCIP_PRICESTORE *pricestore)
Definition: pricestore.c:622
internal methods for clocks and timing issues
SCIP_Bool SCIPsetIsPositive(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6110
int SCIPcolGetNNonz(SCIP_COL *col)
Definition: lp.c:16988
void SCIPclockStop(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:351
#define FALSE
Definition: def.h:73
int lppos
Definition: struct_lp.h:163
SCIP_EXPORT SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17515
SCIP_Bool solved
Definition: struct_lp.h:357
void SCIPclockStart(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:281
SCIP_Bool SCIPsetIsZero(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6099
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
int SCIPtreeGetCurrentDepth(SCIP_TREE *tree)
Definition: tree.c:8389
SCIP_RETCODE SCIPpricestoreCreate(SCIP_PRICESTORE **pricestore)
Definition: pricestore.c:98
int SCIPsetCalcMemGrowSize(SCIP_SET *set, int num)
Definition: set.c:5580
public methods for problem variables
SCIP_EXPORT SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17136
SCIP_Bool SCIPsetIsNegative(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6121
#define BMSfreeMemory(ptr)
Definition: memory.h:137
SCIP_LPSOLSTAT SCIPlpGetSolstat(SCIP_LP *lp)
Definition: lp.c:13047
internal methods for LP management
Definition: heur_padm.c:125
SCIP_Bool SCIPtreeIsFocusNodeLPConstructed(SCIP_TREE *tree)
Definition: tree.c:8352
void SCIPpricestoreStartInitialLP(SCIP_PRICESTORE *pricestore)
Definition: pricestore.c:148
int SCIPpricestoreGetNBoundResets(SCIP_PRICESTORE *pricestore)
Definition: pricestore.c:611
int SCIPlpGetNCols(SCIP_LP *lp)
Definition: lp.c:17437
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:7779
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:300
int SCIPpricestoreGetNVarsApplied(SCIP_PRICESTORE *pricestore)
Definition: pricestore.c:662
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17017
#define SCIPerrorMessage
Definition: pub_message.h:55
SCIP_RETCODE SCIPlpAddCol(SCIP_LP *lp, SCIP_SET *set, SCIP_COL *col, int depth)
Definition: lp.c:9436
SCIP_RETCODE SCIPvarRelease(SCIP_VAR **var, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
Definition: var.c:2786
SCIP_CLOCK * probpricingtime
SCIP_Real SCIPclockGetTime(SCIP_CLOCK *clck)
Definition: clock.c:429
#define NULL
Definition: lpi_spx1.cpp:155
internal methods for global SCIP settings
#define SCIP_CALL(x)
Definition: def.h:364
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:7906
SCIP_RETCODE SCIPpricestoreFree(SCIP_PRICESTORE **pricestore)
Definition: pricestore.c:127
SCIP_RETCODE SCIPclockCreate(SCIP_CLOCK **clck, SCIP_CLOCKTYPE clocktype)
Definition: clock.c:161
SCIP_EXPORT SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:17381
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:471
#define SCIP_Bool
Definition: def.h:70
void SCIPvarCapture(SCIP_VAR *var)
Definition: var.c:2774
SCIP_Real * scores
void SCIPclockFree(SCIP_CLOCK **clck)
Definition: clock.c:176
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:345
#define SCIPsetDebugMsg
Definition: set.h:1721
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:172
int nuses
Definition: struct_var.h:253
SCIP_Bool SCIPtreeHasCurrentNodeLP(SCIP_TREE *tree)
Definition: tree.c:8406
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17723
int ncolvars
Definition: struct_prob.h:66
SCIP * scip
Definition: struct_var.h:278
datastructures for storing and manipulating the main problem
static SCIP_RETCODE pricestoreEnsureVarsMem(SCIP_PRICESTORE *pricestore, SCIP_SET *set, int num)
Definition: pricestore.c:47
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17733
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:560
int SCIPpricestoreGetNVarsFound(SCIP_PRICESTORE *pricestore)
Definition: pricestore.c:652
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:3474
SCIP_Bool SCIPcolIsInLP(SCIP_COL *col)
Definition: lp.c:16977
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:72
#define SCIP_Real
Definition: def.h:163
SCIP_VAR ** vars
Definition: struct_prob.h:55
SCIP_Real SCIPcolGetFarkasValue(SCIP_COL *col, SCIP_STAT *stat, SCIP_LP *lp)
Definition: lp.c:4150
#define BMSallocMemory(ptr)
Definition: memory.h:111
#define BMSreallocMemoryArray(ptr, num)
Definition: memory.h:119
SCIP_Real * bdviolvarsub
SCIP_VAR * var
Definition: struct_lp.h:151
SCIP_EXPORT int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17360
SCIP_Real SCIPcolGetFeasibility(SCIP_COL *col, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp)
Definition: lp.c:3965
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:429
#define SCIP_ALLOC(x)
Definition: def.h:375
datastructures for global SCIP settings
int SCIPsetGetPriceMaxvars(SCIP_SET *set, SCIP_Bool root)
Definition: set.c:5705
int SCIPpricestoreGetNProbPricings(SCIP_PRICESTORE *pricestore)
Definition: pricestore.c:632