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-2016 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 email to 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 <assert.h>
24 
25 #include "scip/def.h"
26 #include "scip/set.h"
27 #include "scip/clock.h"
28 #include "scip/lp.h"
29 #include "scip/var.h"
30 #include "scip/prob.h"
31 #include "scip/tree.h"
32 #include "scip/pricestore.h"
33 #include "scip/pub_message.h"
34 
35 #include "scip/struct_pricestore.h"
36 
37 
38 
39 /*
40  * dynamic memory arrays
41  */
42 
43 /** resizes vars and score arrays to be able to store at least num entries */
44 static
46  SCIP_PRICESTORE* pricestore, /**< pricing storage */
47  SCIP_SET* set, /**< global SCIP settings */
48  int num /**< minimal number of slots in array */
49  )
50 {
51  assert(pricestore != NULL);
52  assert(set != NULL);
53 
54  if( num > pricestore->varssize )
55  {
56  int newsize;
57 
58  newsize = SCIPsetCalcMemGrowSize(set, num);
59  SCIP_ALLOC( BMSreallocMemoryArray(&pricestore->vars, newsize) );
60  SCIP_ALLOC( BMSreallocMemoryArray(&pricestore->scores, newsize) );
61  pricestore->varssize = newsize;
62  }
63  assert(num <= pricestore->varssize);
64 
65  return SCIP_OKAY;
66 }
67 
68 /** resizes bdviolvars arrays to be able to store at least num entries */
69 static
71  SCIP_PRICESTORE* pricestore, /**< pricing storage */
72  SCIP_SET* set, /**< global SCIP settings */
73  int num /**< minimal number of slots in array */
74  )
75 {
76  assert(pricestore != NULL);
77  assert(set != NULL);
78 
79  if( num > pricestore->bdviolvarssize )
80  {
81  int newsize;
82 
83  newsize = SCIPsetCalcMemGrowSize(set, num);
84  SCIP_ALLOC( BMSreallocMemoryArray(&pricestore->bdviolvars, newsize) );
85  SCIP_ALLOC( BMSreallocMemoryArray(&pricestore->bdviolvarslb, newsize) );
86  SCIP_ALLOC( BMSreallocMemoryArray(&pricestore->bdviolvarsub, newsize) );
87  pricestore->bdviolvarssize = newsize;
88  }
89  assert(num <= pricestore->bdviolvarssize);
90 
91  return SCIP_OKAY;
92 }
93 
94 
95 /** creates pricing storage */
97  SCIP_PRICESTORE** pricestore /**< pointer to store pricing storage */
98  )
99 {
100  assert(pricestore != NULL);
101 
102  SCIP_ALLOC( BMSallocMemory(pricestore) );
103 
104  SCIP_CALL( SCIPclockCreate(&(*pricestore)->probpricingtime, SCIP_CLOCKTYPE_DEFAULT) );
105  (*pricestore)->vars = NULL;
106  (*pricestore)->scores = NULL;
107  (*pricestore)->bdviolvars = NULL;
108  (*pricestore)->bdviolvarslb = NULL;
109  (*pricestore)->bdviolvarsub = NULL;
110  (*pricestore)->varssize = 0;
111  (*pricestore)->nvars = 0;
112  (*pricestore)->bdviolvarssize = 0;
113  (*pricestore)->nbdviolvars = 0;
114  (*pricestore)->naddedbdviolvars = 0;
115  (*pricestore)->nprobpricings = 0;
116  (*pricestore)->nprobvarsfound = 0;
117  (*pricestore)->nvarsfound = 0;
118  (*pricestore)->nvarsapplied = 0;
119  (*pricestore)->initiallp = FALSE;
120 
121  return SCIP_OKAY;
122 }
123 
124 /** frees pricing storage */
126  SCIP_PRICESTORE** pricestore /**< pointer to store pricing storage */
127  )
128 {
129  assert(pricestore != NULL);
130  assert(*pricestore != NULL);
131  assert((*pricestore)->nvars == 0);
132  assert((*pricestore)->nbdviolvars == 0);
133 
134  SCIPclockFree(&(*pricestore)->probpricingtime);
135  BMSfreeMemoryArrayNull(&(*pricestore)->vars);
136  BMSfreeMemoryArrayNull(&(*pricestore)->scores);
137  BMSfreeMemoryArrayNull(&(*pricestore)->bdviolvars);
138  BMSfreeMemoryArrayNull(&(*pricestore)->bdviolvarslb);
139  BMSfreeMemoryArrayNull(&(*pricestore)->bdviolvarsub);
140  BMSfreeMemory(pricestore);
141 
142  return SCIP_OKAY;
143 }
144 
145 /** informs pricing storage, that the setup of the initial LP starts now */
147  SCIP_PRICESTORE* pricestore /**< pricing storage */
148  )
149 {
150  assert(pricestore != NULL);
151  assert(!pricestore->initiallp);
152  assert(pricestore->nvars == 0);
153 
154  pricestore->initiallp = TRUE;
155 }
156 
157 /** informs pricing storage, that the setup of the initial LP is now finished */
159  SCIP_PRICESTORE* pricestore /**< pricing storage */
160  )
161 {
162  assert(pricestore != NULL);
163  assert(pricestore->initiallp);
164  assert(pricestore->nvars == 0);
165 
166  pricestore->initiallp = FALSE;
167 }
168 
169 /** adds variable to pricing storage and capture it */
171  SCIP_PRICESTORE* pricestore, /**< pricing storage */
172  BMS_BLKMEM* blkmem, /**< block memory */
173  SCIP_SET* set, /**< global SCIP settings */
174  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
175  SCIP_LP* lp, /**< LP data */
176  SCIP_VAR* var, /**< priced variable */
177  SCIP_Real score, /**< pricing score of variable (the larger, the better the variable) */
178  SCIP_Bool root /**< are we at the root node? */
179  )
180 {
181  int maxpricevars;
182  int v;
183 
184  assert(pricestore != NULL);
185  assert(set != NULL);
186  assert(var != NULL);
187 
188 #ifndef NDEBUG
189  /* check if we add this variables to the same scip, where we created it */
190  if( var->scip != set->scip )
191  {
192  SCIPerrorMessage("try to add a variable of another scip instance\n");
193  return SCIP_INVALIDDATA;
194  }
195 #endif
196 
197  SCIPdebugMessage("adding variable <%s> (lb=%g, ub=%g) to pricing storage (initiallp=%u)\n",
198  SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), pricestore->initiallp);
199 
200  if( pricestore->initiallp )
201  maxpricevars = INT_MAX;
202  else
203  {
204  pricestore->nvarsfound++;
205  maxpricevars = SCIPsetGetPriceMaxvars(set, root);
206  }
207  assert(maxpricevars >= 1);
208  assert(pricestore->nvars <= maxpricevars);
209 
210  /* check, if variable belongs to the best "maxpricevars" pricing variables */
211  if( pricestore->nvars < maxpricevars || score > pricestore->scores[maxpricevars-1] )
212  {
213  /* capture variable */
214  SCIPvarCapture(var);
215 
216  /* if the array consists of "maxpricevars" variables, release the worst variables */
217  if( pricestore->nvars == maxpricevars )
218  {
219  SCIP_CALL( SCIPvarRelease(&pricestore->vars[pricestore->nvars-1], blkmem, set, eventqueue, lp) );
220  pricestore->nvars--;
221  }
222  assert(pricestore->nvars < maxpricevars);
223 
224  /* get enough memory to store additional variable */
225  SCIP_CALL( pricestoreEnsureVarsMem(pricestore, set, pricestore->nvars+1) );
226  assert(pricestore->nvars <= pricestore->varssize);
227 
228  /* insert the variable at the correct position in sorted arrays */
229  for( v = pricestore->nvars; v > 0 && score > pricestore->scores[v-1]; --v )
230  {
231  pricestore->vars[v] = pricestore->vars[v-1];
232  pricestore->scores[v] = pricestore->scores[v-1];
233  }
234  pricestore->vars[v] = var;
235  pricestore->scores[v] = score;
236  pricestore->nvars++;
237  }
238 
239  return SCIP_OKAY;
240 }
241 
242 /** adds variable where zero violates the bounds to pricing storage, capture it */
244  SCIP_PRICESTORE* pricestore, /**< pricing storage */
245  BMS_BLKMEM* blkmem, /**< block memory */
246  SCIP_SET* set, /**< global SCIP settings */
247  SCIP_STAT* stat, /**< problem statistics */
248  SCIP_LP* lp, /**< LP data */
249  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
250  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
251  SCIP_VAR* var /**< variable, where zero violates the bounds */
252  )
253 {
254  assert(pricestore != NULL);
255  assert(set != NULL);
256  assert(var != NULL);
258  assert(pricestore->naddedbdviolvars <= pricestore->nbdviolvars);
259 
260  SCIPdebugMessage("zero violates bounds of <%s> (lb=%g, ub=%g)\n",
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  SCIPdebugMessage(" -> zero violates bounds of <%s> [%g,%g]\n",
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  SCIPdebugMessage(" -> 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  SCIPdebugMessage("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  SCIPdebugMessage(" <%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  SCIPdebugMessage(" <%s> reduced cost feasibility: %e\n", SCIPvarGetName(col->var), feasibility);
450  }
451 
452  /* the score is -feasibility / (#nonzeros in column + 1) to prefer short columns
453  * we must add variables with negative feasibility, but in order to not get a too large lower bound
454  * due to missing columns, we better also add variables, that have a very small feasibility
455  */
456  if( !SCIPsetIsPositive(set, feasibility) )
457  {
458  SCIP_CALL( SCIPpricestoreAddVar(pricestore, blkmem, set, eventqueue, lp, var, -feasibility / (col->len+1), root) );
459  pricestore->nprobvarsfound++;
460  nfoundvars++;
461  }
462  }
463  }
464  }
465  }
466 
467  /* stop timing */
468  SCIPclockStop(pricestore->probpricingtime, set);
469 
470  return SCIP_OKAY;
471 }
472 
473 /** adds priced variables to the LP */
475  SCIP_PRICESTORE* pricestore, /**< pricing storage */
476  BMS_BLKMEM* blkmem, /**< block memory buffers */
477  SCIP_SET* set, /**< global SCIP settings */
478  SCIP_STAT* stat, /**< dynamic problem statistics */
479  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
480  SCIP_PROB* prob, /**< transformed problem after presolve */
481  SCIP_TREE* tree, /**< branch and bound tree */
482  SCIP_LP* lp /**< LP data */
483  )
484 {
485  SCIP_VAR* var;
486  SCIP_COL* col;
487  int v;
488 
489  assert(pricestore != NULL);
490  assert(pricestore->naddedbdviolvars <= pricestore->nbdviolvars);
491  assert(set != NULL);
492  assert(prob != NULL);
493  assert(lp != NULL);
494  assert(tree != NULL);
495  assert(SCIPtreeIsFocusNodeLPConstructed(tree));
496 
497  SCIPdebugMessage("adding %d variables (%d bound violated and %d priced vars) to %d LP columns\n",
498  SCIPpricestoreGetNVars(pricestore), pricestore->nbdviolvars - pricestore->naddedbdviolvars,
499  pricestore->nvars, SCIPlpGetNCols(lp));
500 
501  /* add the variables with violated bounds to LP */
502  for( v = pricestore->naddedbdviolvars; v < pricestore->nbdviolvars; ++v )
503  {
504  var = pricestore->bdviolvars[v];
506  assert(SCIPvarGetProbindex(var) >= 0);
507  assert(var->nuses >= 2); /* at least used in pricing storage and in problem */
508 
510  {
511  /* transform loose variable into column variable */
512  SCIP_CALL( SCIPvarColumn(var, blkmem, set, stat, prob, lp) );
513  }
514  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
515 
516  col = SCIPvarGetCol(var);
517  assert(col != NULL);
518  assert(col->lppos == -1);
519  SCIPdebugMessage("adding bound violated variable <%s> (lb=%g, ub=%g)\n", SCIPvarGetName(var),
520  pricestore->bdviolvarslb[v], pricestore->bdviolvarsub[v]);
521  SCIP_CALL( SCIPlpAddCol(lp, set, col, SCIPtreeGetCurrentDepth(tree)) );
522 
523  if( !pricestore->initiallp )
524  pricestore->nvarsapplied++;
525  }
526  pricestore->naddedbdviolvars = pricestore->nbdviolvars;
527 
528  /* add the selected pricing variables to LP */
529  for( v = 0; v < pricestore->nvars; ++v )
530  {
531  var = pricestore->vars[v];
533  assert(SCIPvarGetProbindex(var) >= 0);
534  assert(var->nuses >= 2); /* at least used in pricing storage and in problem */
535 
536  /* transform variable into column variable, if needed */
538  {
539  SCIP_CALL( SCIPvarColumn(var, blkmem, set, stat, prob, lp) );
540  }
541  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
542 
543  col = SCIPvarGetCol(var);
544  assert(col != NULL);
545  assert(col->lppos == -1);
546  SCIPdebugMessage("adding priced variable <%s> (score=%g)\n", SCIPvarGetName(var), pricestore->scores[v]);
547  SCIP_CALL( SCIPlpAddCol(lp, set, col, SCIPtreeGetCurrentDepth(tree)) );
548 
549  /* release the variable */
550  SCIP_CALL( SCIPvarRelease(&pricestore->vars[v], blkmem, set, eventqueue, lp) );
551 
552  if( !pricestore->initiallp )
553  pricestore->nvarsapplied++;
554  }
555 
556  /* clear the pricing storage */
557  pricestore->nvars = 0;
558 
559  return SCIP_OKAY;
560 }
561 
562 /** reset variables' bounds violated by zero to its original value */
564  SCIP_PRICESTORE* pricestore, /**< pricing storage */
565  BMS_BLKMEM* blkmem, /**< block memory */
566  SCIP_SET* set, /**< global SCIP settings */
567  SCIP_STAT* stat, /**< problem statistics */
568  SCIP_LP* lp, /**< LP data */
569  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
570  SCIP_EVENTQUEUE* eventqueue /**< event queue */
571  )
572 {
573  SCIP_VAR* var;
574  int v;
575 
576  assert(pricestore != NULL);
577  assert(set != NULL);
578  assert(lp != NULL);
579  assert(pricestore->nvars == 0);
580  assert(pricestore->naddedbdviolvars == pricestore->nbdviolvars);
581 
582  /* reset variables' bounds, release them, and clear the boundviolation storage;
583  * the inference information is unimportant in these removals of temporary bound changes
584  */
585  for( v = 0; v < pricestore->nbdviolvars; ++v )
586  {
587  var = pricestore->bdviolvars[v];
588  assert(var != NULL);
589 
590  SCIPdebugMessage("resetting bounds of <%s> from [%g,%g] to [%g,%g]\n", var->name,
591  SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), pricestore->bdviolvarslb[v], pricestore->bdviolvarsub[v]);
592  SCIP_CALL( SCIPvarChgLbLocal(var, blkmem, set, stat, lp, branchcand, eventqueue, pricestore->bdviolvarslb[v]) );
593  SCIP_CALL( SCIPvarChgUbLocal(var, blkmem, set, stat, lp, branchcand, eventqueue, pricestore->bdviolvarsub[v]) );
594  SCIP_CALL( SCIPvarRelease(&pricestore->bdviolvars[v], blkmem, set, eventqueue, lp) );
595  }
596  pricestore->naddedbdviolvars = 0;
597  pricestore->nbdviolvars = 0;
598 
599  return SCIP_OKAY;
600 }
601 
602 /** gets number of variables in pricing storage */
604  SCIP_PRICESTORE* pricestore /**< pricing storage */
605  )
606 {
607  assert(pricestore != NULL);
608  assert(pricestore->nbdviolvars >= pricestore->naddedbdviolvars);
609 
610  return pricestore->nvars + pricestore->nbdviolvars - pricestore->naddedbdviolvars;
611 }
612 
613 /** gets number of variables in pricing storage whose bounds must be reset */
615  SCIP_PRICESTORE* pricestore /**< pricing storage */
616  )
617 {
618  assert(pricestore != NULL);
619  assert(pricestore->nbdviolvars >= pricestore->naddedbdviolvars);
620 
621  return pricestore->nbdviolvars - pricestore->naddedbdviolvars;
622 }
623 
624 /** gets time needed to price existing problem variables */
626  SCIP_PRICESTORE* pricestore /**< pricing storage */
627  )
628 {
629  assert(pricestore != NULL);
630 
631  return SCIPclockGetTime(pricestore->probpricingtime);
632 }
633 
634 /** gets total number of calls to problem variable pricing */
636  SCIP_PRICESTORE* pricestore /**< pricing storage */
637  )
638 {
639  assert(pricestore != NULL);
640 
641  return pricestore->nprobpricings;
642 }
643 
644 /** gets total number of times, a problem variable was priced in */
646  SCIP_PRICESTORE* pricestore /**< pricing storage */
647  )
648 {
649  assert(pricestore != NULL);
650 
651  return pricestore->nprobvarsfound;
652 }
653 
654 /** get total number of variables found so far in pricing */
656  SCIP_PRICESTORE* pricestore /**< pricing storage */
657  )
658 {
659  assert(pricestore != NULL);
660 
661  return pricestore->nvarsfound;
662 }
663 
664 /** get total number of variables priced into the LP so far */
666  SCIP_PRICESTORE* pricestore /**< pricing storage */
667  )
668 {
669  assert(pricestore != NULL);
670 
671  return pricestore->nvarsapplied;
672 }
673 
void SCIPpricestoreEndInitialLP(SCIP_PRICESTORE *pricestore)
Definition: pricestore.c:158
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16443
datastructures for storing priced variables
internal methods for branch and bound tree
char * name
Definition: struct_var.h:227
int SCIPpricestoreGetNVars(SCIP_PRICESTORE *pricestore)
Definition: pricestore.c:603
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:243
int SCIPpricestoreGetNProbvarsFound(SCIP_PRICESTORE *pricestore)
Definition: pricestore.c:645
SCIP_Real SCIPpricestoreGetProbPricingTime(SCIP_PRICESTORE *pricestore)
Definition: pricestore.c:625
internal methods for clocks and timing issues
SCIP_Bool SCIPsetIsPositive(SCIP_SET *set, SCIP_Real val)
Definition: set.c:5303
#define NULL
Definition: lpi_spx.cpp:130
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17113
SCIP_Bool SCIPcolIsInLP(SCIP_COL *col)
Definition: lp.c:18748
void SCIPclockStop(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:350
#define FALSE
Definition: def.h:56
int lppos
Definition: struct_lp.h:160
SCIP_Bool solved
Definition: struct_lp.h:338
void SCIPclockStart(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:280
SCIP_Bool SCIPsetIsZero(SCIP_SET *set, SCIP_Real val)
Definition: set.c:5292
#define TRUE
Definition: def.h:55
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define SCIP_CALL(x)
Definition: def.h:266
int SCIPtreeGetCurrentDepth(SCIP_TREE *tree)
Definition: tree.c:7957
SCIP_RETCODE SCIPpricestoreCreate(SCIP_PRICESTORE **pricestore)
Definition: pricestore.c:96
int SCIPsetCalcMemGrowSize(SCIP_SET *set, int num)
Definition: set.c:4766
#define SCIPdebugMessage
Definition: pub_message.h:77
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:16905
SCIP_Bool SCIPsetIsNegative(SCIP_SET *set, SCIP_Real val)
Definition: set.c:5314
SCIP_LPSOLSTAT SCIPlpGetSolstat(SCIP_LP *lp)
Definition: lp.c:15060
internal methods for LP management
SCIP_Bool SCIPtreeIsFocusNodeLPConstructed(SCIP_TREE *tree)
Definition: tree.c:7920
void SCIPpricestoreStartInitialLP(SCIP_PRICESTORE *pricestore)
Definition: pricestore.c:146
int SCIPpricestoreGetNBoundResets(SCIP_PRICESTORE *pricestore)
Definition: pricestore.c:614
int SCIPlpGetNCols(SCIP_LP *lp)
Definition: lp.c:19178
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16562
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:7455
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:665
internal methods for storing and manipulating the main problem
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_RETCODE SCIPlpAddCol(SCIP_LP *lp, SCIP_SET *set, SCIP_COL *col, int depth)
Definition: lp.c:8963
SCIP_RETCODE SCIPvarRelease(SCIP_VAR **var, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
Definition: var.c:2752
SCIP_CLOCK * probpricingtime
#define BMSallocMemory(ptr)
Definition: memory.h:74
SCIP_Real SCIPclockGetTime(SCIP_CLOCK *clck)
Definition: clock.c:428
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:16771
internal methods for global SCIP settings
#define BMSreallocMemoryArray(ptr, num)
Definition: memory.h:82
#define BMSfreeMemory(ptr)
Definition: memory.h:100
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:7581
SCIP_RETCODE SCIPpricestoreFree(SCIP_PRICESTORE **pricestore)
Definition: pricestore.c:125
SCIP_RETCODE SCIPclockCreate(SCIP_CLOCK **clck, SCIP_CLOCKTYPE clocktype)
Definition: clock.c:160
#define BMSfreeMemoryArrayNull(ptr)
Definition: memory.h:103
internal methods for problem variables
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17123
int len
Definition: struct_lp.h:157
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:474
#define SCIP_Bool
Definition: def.h:53
void SCIPvarCapture(SCIP_VAR *var)
Definition: var.c:2740
SCIP_Real * scores
SCIP_Real SCIPvarGetBestBoundLocal(SCIP_VAR *var)
Definition: var.c:17143
void SCIPclockFree(SCIP_CLOCK **clck)
Definition: clock.c:175
SCIP_Real * bdviolvarslb
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
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:170
int nuses
Definition: struct_var.h:254
SCIP_Bool SCIPtreeHasCurrentNodeLP(SCIP_TREE *tree)
Definition: tree.c:7984
int ncolvars
Definition: struct_prob.h:65
SCIP * scip
Definition: struct_var.h:199
static SCIP_RETCODE pricestoreEnsureVarsMem(SCIP_PRICESTORE *pricestore, SCIP_SET *set, int num)
Definition: pricestore.c:45
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:563
int SCIPpricestoreGetNVarsFound(SCIP_PRICESTORE *pricestore)
Definition: pricestore.c:655
int lpipos
Definition: struct_lp.h:161
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:3389
public methods for message output
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:16750
static SCIP_RETCODE pricestoreEnsureBdviolvarsMem(SCIP_PRICESTORE *pricestore, SCIP_SET *set, int num)
Definition: pricestore.c:70
#define SCIP_Real
Definition: def.h:127
SCIP_VAR ** vars
Definition: struct_prob.h:54
SCIP_Real SCIPcolGetFarkasValue(SCIP_COL *col, SCIP_STAT *stat, SCIP_LP *lp)
Definition: lp.c:3967
SCIP_Real * bdviolvarsub
SCIP_VAR * var
Definition: struct_lp.h:148
SCIP_Real SCIPcolGetFeasibility(SCIP_COL *col, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp)
Definition: lp.c:3782
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:392
int SCIPcolGetNNonz(SCIP_COL *col)
Definition: lp.c:18759
#define SCIP_ALLOC(x)
Definition: def.h:277
int SCIPsetGetPriceMaxvars(SCIP_SET *set, SCIP_Bool root)
Definition: set.c:4908
int SCIPpricestoreGetNProbPricings(SCIP_PRICESTORE *pricestore)
Definition: pricestore.c:635