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