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-2017 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  SCIPsetDebugMsg(set, "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  SCIPsetDebugMsg(set, "zero violates bounds of <%s> (lb=%g, ub=%g)\n", SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var));
261 
262  if( !pricestore->initiallp )
263  pricestore->nvarsfound++;
264 
265  /* get enough memory to store additional variable */
266  SCIP_CALL( pricestoreEnsureBdviolvarsMem(pricestore, set, pricestore->nbdviolvars+1) );
267  assert(pricestore->nbdviolvars <= pricestore->bdviolvarssize);
268 
269  /* capture variable */
270  SCIPvarCapture(var);
271 
272  /* insert variable in bdviolvars arrays */
273  pricestore->bdviolvars[pricestore->nbdviolvars] = var;
274  pricestore->bdviolvarslb[pricestore->nbdviolvars] = SCIPvarGetLbLocal(var);
275  pricestore->bdviolvarsub[pricestore->nbdviolvars] = SCIPvarGetUbLocal(var);
276  pricestore->nbdviolvars++;
277 
278  /* Temporarily set bounds, such that zero is feasible, because we don't want to destroy
279  * dual feasibility (by adding columns) and primal feasibility (by introducing violated bounds)
280  * at the same time.
281  * The correct bounds must be reset with a call to SCIPpricestoreResetBounds().
282  * The inference information is unimportant for this temporary bound change.
283  */
284  if( SCIPsetIsPositive(set, SCIPvarGetLbLocal(var)) )
285  {
286  SCIP_CALL( SCIPvarChgLbLocal(var, blkmem, set, stat, lp, branchcand, eventqueue, 0.0) );
287  }
288  else
289  {
290  SCIP_CALL( SCIPvarChgUbLocal(var, blkmem, set, stat, lp, branchcand, eventqueue, 0.0) );
291  }
292 
293  return SCIP_OKAY;
294 }
295 
296 /** adds given problem variable to pricing storage, if zero is not best bound w.r.t. objective function */
297 static
299  SCIP_PRICESTORE* pricestore, /**< pricing storage */
300  BMS_BLKMEM* blkmem, /**< block memory buffers */
301  SCIP_SET* set, /**< global SCIP settings */
302  SCIP_STAT* stat, /**< dynamic problem statistics */
303  SCIP_TREE* tree, /**< branch and bound tree */
304  SCIP_LP* lp, /**< LP data */
305  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
306  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
307  SCIP_VAR* var, /**< problem variable */
308  SCIP_Bool* added /**< pointer to store whether variable was added to pricing storage */
309  )
310 {
311  assert(tree != NULL);
312  assert(added != NULL);
313 
314  *added = FALSE;
315 
316  /* add variable, if zero is not feasible within the bounds */
318  {
319  SCIPsetDebugMsg(set, " -> zero violates bounds of <%s> [%g,%g]\n", SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var));
320  SCIP_CALL( SCIPpricestoreAddBdviolvar(pricestore, blkmem, set, stat, lp, branchcand, eventqueue, var) );
321  *added = TRUE;
322  }
323  else
324  {
325  SCIP_Real bestbound;
326 
327  /* add variable, if zero is not best bound w.r.t. objective function */
328  bestbound = SCIPvarGetBestBoundLocal(var);
329  if( !SCIPsetIsZero(set, bestbound) )
330  {
331  SCIPsetDebugMsg(set, " -> best bound of <%s> [%g,%g] is not zero but %g\n",
332  SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), bestbound);
333  SCIP_CALL( SCIPpricestoreAddVar(pricestore, blkmem, set, eventqueue, lp, var,
334  -SCIPvarGetObj(var) * bestbound, (SCIPtreeGetCurrentDepth(tree) == 0)) );
335  *added = TRUE;
336  }
337  }
338 
339  return SCIP_OKAY;
340 }
341 
342 /** adds problem variables with negative reduced costs to pricing storage */
344  SCIP_PRICESTORE* pricestore, /**< pricing storage */
345  BMS_BLKMEM* blkmem, /**< block memory buffers */
346  SCIP_SET* set, /**< global SCIP settings */
347  SCIP_STAT* stat, /**< dynamic problem statistics */
348  SCIP_PROB* prob, /**< transformed problem after presolve */
349  SCIP_TREE* tree, /**< branch and bound tree */
350  SCIP_LP* lp, /**< LP data */
351  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
352  SCIP_EVENTQUEUE* eventqueue /**< event queue */
353  )
354 {
355  SCIP_VAR* var;
356  SCIP_COL* col;
357  SCIP_Bool root;
358  SCIP_Bool added;
359  int v;
360  int abortpricevars;
361  int maxpricevars;
362  int nfoundvars;
363 
364  assert(pricestore != NULL);
365  assert(set != NULL);
366  assert(stat != NULL);
367  assert(prob != NULL);
368  assert(lp != NULL);
369  assert(lp->solved);
370  assert(tree != NULL);
371  assert(SCIPtreeHasCurrentNodeLP(tree));
372  assert(prob->nvars >= SCIPlpGetNCols(lp));
373 
374  /* if all problem variables of status COLUMN are already in the LP, nothing has to be done */
375  if( prob->ncolvars == SCIPlpGetNCols(lp) )
376  return SCIP_OKAY;
377 
378  root = (SCIPtreeGetCurrentDepth(tree) == 0);
379  maxpricevars = SCIPsetGetPriceMaxvars(set, root);
380  assert(maxpricevars >= 1);
381  abortpricevars = (int)(set->price_abortfac * maxpricevars);
382  assert(abortpricevars >= maxpricevars);
383 
384  /**@todo test pricing: is abortpricevars a good idea? -> like strong branching, lookahead, ... */
385 
386  pricestore->nprobpricings++;
387 
388  /* start timing */
389  SCIPclockStart(pricestore->probpricingtime, set);
390 
391  /* price already existing problem variables */
392  nfoundvars = 0;
393  for( v = 0; v < prob->nvars && nfoundvars < abortpricevars; ++v )
394  {
395  var = prob->vars[v];
397  {
398  col = SCIPvarGetCol(var);
399  assert(col != NULL);
400  assert(col->var == var);
401  assert(col->len >= 0);
402  assert(col->lppos >= -1);
403  assert(col->lpipos >= -1);
404  assert(SCIPcolIsInLP(col) == (col->lpipos >= 0));
405 
406  if( !SCIPcolIsInLP(col) )
407  {
408  SCIPsetDebugMsg(set, "price column variable <%s> in bounds [%g,%g]\n",
410 
411  /* add variable to pricing storage, if zero is not best bound w.r.t. objective function */
412  SCIP_CALL( addBoundViolated(pricestore, blkmem, set, stat, tree, lp, branchcand, eventqueue, var, &added) );
413 
414  if( added )
415  {
416  pricestore->nprobvarsfound++;
417  nfoundvars++;
418  }
419  else if( SCIPcolGetNNonz(col) > 0 )
420  {
421  SCIP_Real feasibility;
422 
423  /* a column not in LP that doesn't have zero in its bounds was added by bound checking above */
424  assert(!SCIPsetIsPositive(set, SCIPvarGetLbLocal(col->var)));
425  assert(!SCIPsetIsNegative(set, SCIPvarGetUbLocal(col->var)));
426 
428  {
429  /* The LP was proven infeasible, so we have an infeasibility proof by the dual Farkas multipliers y.
430  * The valid inequality y^T A x >= y^T b is violated by all x, especially by the (for this
431  * inequality most feasible solution) x' defined by
432  * x'_i = ub_i, if y^T A_i > 0
433  * x'_i = lb_i, if y^T A_i <= 0.
434  * Pricing in this case means to add variables i with positive Farkas value, i.e. y^T A_i x'_i > 0
435  */
436  feasibility = -SCIPcolGetFarkasValue(col, stat, lp);
437  SCIPsetDebugMsg(set, " <%s> Farkas feasibility: %e\n", SCIPvarGetName(col->var), feasibility);
438  }
439  else
440  {
441  /* The dual LP is feasible, and we have a feasible dual solution. Pricing in this case means to
442  * add variables with negative feasibility, that is
443  * - positive reduced costs for variables with negative lower bound
444  * - negative reduced costs for variables with positive upper bound
445  */
446  feasibility = SCIPcolGetFeasibility(col, set, stat, lp);
447  SCIPsetDebugMsg(set, " <%s> reduced cost feasibility: %e\n", SCIPvarGetName(col->var), feasibility);
448  }
449 
450  /* the score is -feasibility / (#nonzeros in column + 1) to prefer short columns
451  * we must add variables with negative feasibility, but in order to not get a too large lower bound
452  * due to missing columns, we better also add variables, that have a very small feasibility
453  */
454  if( !SCIPsetIsPositive(set, feasibility) )
455  {
456  SCIP_CALL( SCIPpricestoreAddVar(pricestore, blkmem, set, eventqueue, lp, var, -feasibility / (col->len+1), root) );
457  pricestore->nprobvarsfound++;
458  nfoundvars++;
459  }
460  }
461  }
462  }
463  }
464 
465  /* stop timing */
466  SCIPclockStop(pricestore->probpricingtime, set);
467 
468  return SCIP_OKAY;
469 }
470 
471 /** adds priced variables to the LP */
473  SCIP_PRICESTORE* pricestore, /**< pricing storage */
474  BMS_BLKMEM* blkmem, /**< block memory buffers */
475  SCIP_SET* set, /**< global SCIP settings */
476  SCIP_STAT* stat, /**< dynamic problem statistics */
477  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
478  SCIP_PROB* prob, /**< transformed problem after presolve */
479  SCIP_TREE* tree, /**< branch and bound tree */
480  SCIP_LP* lp /**< LP data */
481  )
482 {
483  SCIP_VAR* var;
484  SCIP_COL* col;
485  int v;
486 
487  assert(pricestore != NULL);
488  assert(pricestore->naddedbdviolvars <= pricestore->nbdviolvars);
489  assert(set != NULL);
490  assert(prob != NULL);
491  assert(lp != NULL);
492  assert(tree != NULL);
493  assert(SCIPtreeIsFocusNodeLPConstructed(tree));
494 
495  SCIPsetDebugMsg(set, "adding %d variables (%d bound violated and %d priced vars) to %d LP columns\n",
496  SCIPpricestoreGetNVars(pricestore), pricestore->nbdviolvars - pricestore->naddedbdviolvars,
497  pricestore->nvars, SCIPlpGetNCols(lp));
498 
499  /* add the variables with violated bounds to LP */
500  for( v = pricestore->naddedbdviolvars; v < pricestore->nbdviolvars; ++v )
501  {
502  var = pricestore->bdviolvars[v];
504  assert(SCIPvarGetProbindex(var) >= 0);
505  assert(var->nuses >= 2); /* at least used in pricing storage and in problem */
506 
508  {
509  /* transform loose variable into column variable */
510  SCIP_CALL( SCIPvarColumn(var, blkmem, set, stat, prob, lp) );
511  }
512  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
513 
514  col = SCIPvarGetCol(var);
515  assert(col != NULL);
516  assert(col->lppos == -1);
517  SCIPsetDebugMsg(set, "adding bound violated variable <%s> (lb=%g, ub=%g)\n", SCIPvarGetName(var),
518  pricestore->bdviolvarslb[v], pricestore->bdviolvarsub[v]);
519  SCIP_CALL( SCIPlpAddCol(lp, set, col, SCIPtreeGetCurrentDepth(tree)) );
520 
521  if( !pricestore->initiallp )
522  pricestore->nvarsapplied++;
523  }
524  pricestore->naddedbdviolvars = pricestore->nbdviolvars;
525 
526  /* add the selected pricing variables to LP */
527  for( v = 0; v < pricestore->nvars; ++v )
528  {
529  var = pricestore->vars[v];
531  assert(SCIPvarGetProbindex(var) >= 0);
532  assert(var->nuses >= 2); /* at least used in pricing storage and in problem */
533 
534  /* transform variable into column variable, if needed */
536  {
537  SCIP_CALL( SCIPvarColumn(var, blkmem, set, stat, prob, lp) );
538  }
539  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
540 
541  col = SCIPvarGetCol(var);
542  assert(col != NULL);
543  assert(col->lppos == -1);
544  SCIPsetDebugMsg(set, "adding priced variable <%s> (score=%g)\n", SCIPvarGetName(var), pricestore->scores[v]);
545  SCIP_CALL( SCIPlpAddCol(lp, set, col, SCIPtreeGetCurrentDepth(tree)) );
546 
547  /* release the variable */
548  SCIP_CALL( SCIPvarRelease(&pricestore->vars[v], blkmem, set, eventqueue, lp) );
549 
550  if( !pricestore->initiallp )
551  pricestore->nvarsapplied++;
552  }
553 
554  /* clear the pricing storage */
555  pricestore->nvars = 0;
556 
557  return SCIP_OKAY;
558 }
559 
560 /** reset variables' bounds violated by zero to its original value */
562  SCIP_PRICESTORE* pricestore, /**< pricing storage */
563  BMS_BLKMEM* blkmem, /**< block memory */
564  SCIP_SET* set, /**< global SCIP settings */
565  SCIP_STAT* stat, /**< problem statistics */
566  SCIP_LP* lp, /**< LP data */
567  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
568  SCIP_EVENTQUEUE* eventqueue /**< event queue */
569  )
570 {
571  SCIP_VAR* var;
572  int v;
573 
574  assert(pricestore != NULL);
575  assert(set != NULL);
576  assert(lp != NULL);
577  assert(pricestore->nvars == 0);
578  assert(pricestore->naddedbdviolvars == pricestore->nbdviolvars);
579 
580  /* reset variables' bounds, release them, and clear the boundviolation storage;
581  * the inference information is unimportant in these removals of temporary bound changes
582  */
583  for( v = 0; v < pricestore->nbdviolvars; ++v )
584  {
585  var = pricestore->bdviolvars[v];
586  assert(var != NULL);
587 
588  SCIPsetDebugMsg(set, "resetting bounds of <%s> from [%g,%g] to [%g,%g]\n", var->name,
589  SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), pricestore->bdviolvarslb[v], pricestore->bdviolvarsub[v]);
590  SCIP_CALL( SCIPvarChgLbLocal(var, blkmem, set, stat, lp, branchcand, eventqueue, pricestore->bdviolvarslb[v]) );
591  SCIP_CALL( SCIPvarChgUbLocal(var, blkmem, set, stat, lp, branchcand, eventqueue, pricestore->bdviolvarsub[v]) );
592  SCIP_CALL( SCIPvarRelease(&pricestore->bdviolvars[v], blkmem, set, eventqueue, lp) );
593  }
594  pricestore->naddedbdviolvars = 0;
595  pricestore->nbdviolvars = 0;
596 
597  return SCIP_OKAY;
598 }
599 
600 /** gets number of variables in pricing storage */
602  SCIP_PRICESTORE* pricestore /**< pricing storage */
603  )
604 {
605  assert(pricestore != NULL);
606  assert(pricestore->nbdviolvars >= pricestore->naddedbdviolvars);
607 
608  return pricestore->nvars + pricestore->nbdviolvars - pricestore->naddedbdviolvars;
609 }
610 
611 /** gets number of variables in pricing storage whose bounds must be reset */
613  SCIP_PRICESTORE* pricestore /**< pricing storage */
614  )
615 {
616  assert(pricestore != NULL);
617  assert(pricestore->nbdviolvars >= pricestore->naddedbdviolvars);
618 
619  return pricestore->nbdviolvars - pricestore->naddedbdviolvars;
620 }
621 
622 /** gets time needed to price existing problem variables */
624  SCIP_PRICESTORE* pricestore /**< pricing storage */
625  )
626 {
627  assert(pricestore != NULL);
628 
629  return SCIPclockGetTime(pricestore->probpricingtime);
630 }
631 
632 /** gets total number of calls to problem variable pricing */
634  SCIP_PRICESTORE* pricestore /**< pricing storage */
635  )
636 {
637  assert(pricestore != NULL);
638 
639  return pricestore->nprobpricings;
640 }
641 
642 /** gets total number of times, a problem variable was priced in */
644  SCIP_PRICESTORE* pricestore /**< pricing storage */
645  )
646 {
647  assert(pricestore != NULL);
648 
649  return pricestore->nprobvarsfound;
650 }
651 
652 /** get total number of variables found so far in pricing */
654  SCIP_PRICESTORE* pricestore /**< pricing storage */
655  )
656 {
657  assert(pricestore != NULL);
658 
659  return pricestore->nvarsfound;
660 }
661 
662 /** get total number of variables priced into the LP so far */
664  SCIP_PRICESTORE* pricestore /**< pricing storage */
665  )
666 {
667  assert(pricestore != NULL);
668 
669  return pricestore->nvarsapplied;
670 }
671 
void SCIPpricestoreEndInitialLP(SCIP_PRICESTORE *pricestore)
Definition: pricestore.c:158
data structures for storing priced variables
#define BMSfreeMemoryArrayNull(ptr)
Definition: memory.h:107
internal methods for branch and bound tree
char * name
Definition: struct_var.h:228
int SCIPpricestoreGetNVars(SCIP_PRICESTORE *pricestore)
Definition: pricestore.c:601
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:643
SCIP_Real SCIPpricestoreGetProbPricingTime(SCIP_PRICESTORE *pricestore)
Definition: pricestore.c:623
internal methods for clocks and timing issues
SCIP_Bool SCIPsetIsPositive(SCIP_SET *set, SCIP_Real val)
Definition: set.c:5640
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17225
SCIP_Real SCIPvarGetBestBoundLocal(SCIP_VAR *var)
Definition: var.c:17255
void SCIPclockStop(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:350
#define FALSE
Definition: def.h:64
int lppos
Definition: struct_lp.h:163
SCIP_Bool solved
Definition: struct_lp.h:345
void SCIPclockStart(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:280
SCIP_Bool SCIPsetIsZero(SCIP_SET *set, SCIP_Real val)
Definition: set.c:5629
#define TRUE
Definition: def.h:63
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
int SCIPtreeGetCurrentDepth(SCIP_TREE *tree)
Definition: tree.c:8132
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:16862
SCIP_RETCODE SCIPpricestoreCreate(SCIP_PRICESTORE **pricestore)
Definition: pricestore.c:96
int SCIPsetCalcMemGrowSize(SCIP_SET *set, int num)
Definition: set.c:5091
SCIP_Bool SCIPsetIsNegative(SCIP_SET *set, SCIP_Real val)
Definition: set.c:5651
#define BMSfreeMemory(ptr)
Definition: memory.h:104
SCIP_LPSOLSTAT SCIPlpGetSolstat(SCIP_LP *lp)
Definition: lp.c:12527
internal methods for LP management
SCIP_Bool SCIPtreeIsFocusNodeLPConstructed(SCIP_TREE *tree)
Definition: tree.c:8095
void SCIPpricestoreStartInitialLP(SCIP_PRICESTORE *pricestore)
Definition: pricestore.c:146
int SCIPpricestoreGetNBoundResets(SCIP_PRICESTORE *pricestore)
Definition: pricestore.c:612
int SCIPlpGetNCols(SCIP_LP *lp)
Definition: lp.c:16654
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:7501
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:298
int SCIPpricestoreGetNVarsApplied(SCIP_PRICESTORE *pricestore)
Definition: pricestore.c:663
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:9148
SCIP_RETCODE SCIPvarRelease(SCIP_VAR **var, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
Definition: var.c:2765
SCIP_CLOCK * probpricingtime
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16555
SCIP_Real SCIPclockGetTime(SCIP_CLOCK *clck)
Definition: clock.c:428
#define NULL
Definition: lpi_spx1.cpp:137
internal methods for global SCIP settings
#define SCIP_CALL(x)
Definition: def.h:316
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:7627
SCIP_RETCODE SCIPpricestoreFree(SCIP_PRICESTORE **pricestore)
Definition: pricestore.c:125
SCIP_RETCODE SCIPclockCreate(SCIP_CLOCK **clck, SCIP_CLOCKTYPE clocktype)
Definition: clock.c:160
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:472
#define SCIP_Bool
Definition: def.h:61
void SCIPvarCapture(SCIP_VAR *var)
Definition: var.c:2753
SCIP_Real * scores
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:343
#define SCIPsetDebugMsg
Definition: set.h:1870
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17017
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:257
SCIP_Bool SCIPtreeHasCurrentNodeLP(SCIP_TREE *tree)
Definition: tree.c:8149
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:16883
int ncolvars
Definition: struct_prob.h:66
SCIP * scip
Definition: struct_var.h:200
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:561
int SCIPcolGetNNonz(SCIP_COL *col)
Definition: lp.c:16235
int SCIPpricestoreGetNVarsFound(SCIP_PRICESTORE *pricestore)
Definition: pricestore.c:653
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:3402
public methods for message output
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16674
static SCIP_RETCODE pricestoreEnsureBdviolvarsMem(SCIP_PRICESTORE *pricestore, SCIP_SET *set, int num)
Definition: pricestore.c:70
#define SCIP_Real
Definition: def.h:145
SCIP_VAR ** vars
Definition: struct_prob.h:55
SCIP_Real SCIPcolGetFarkasValue(SCIP_COL *col, SCIP_STAT *stat, SCIP_LP *lp)
Definition: lp.c:4030
#define BMSallocMemory(ptr)
Definition: memory.h:78
#define BMSreallocMemoryArray(ptr, num)
Definition: memory.h:86
SCIP_Real * bdviolvarsub
SCIP_VAR * var
Definition: struct_lp.h:151
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17235
SCIP_Real SCIPcolGetFeasibility(SCIP_COL *col, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp)
Definition: lp.c:3845
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:396
#define SCIP_ALLOC(x)
Definition: def.h:327
SCIP_Bool SCIPcolIsInLP(SCIP_COL *col)
Definition: lp.c:16224
int SCIPsetGetPriceMaxvars(SCIP_SET *set, SCIP_Bool root)
Definition: set.c:5233
int SCIPpricestoreGetNProbPricings(SCIP_PRICESTORE *pricestore)
Definition: pricestore.c:633