Scippy

GCG

Branch-and-Price & Column Generation for Everyone

objpricer_gcg.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program */
4 /* GCG --- Generic Column Generation */
5 /* a Dantzig-Wolfe decomposition based extension */
6 /* of the branch-cut-and-price framework */
7 /* SCIP --- Solving Constraint Integer Programs */
8 /* */
9 /* Copyright (C) 2010-2021 Operations Research, RWTH Aachen University */
10 /* Zuse Institute Berlin (ZIB) */
11 /* */
12 /* This program is free software; you can redistribute it and/or */
13 /* modify it under the terms of the GNU Lesser General Public License */
14 /* as published by the Free Software Foundation; either version 3 */
15 /* of the License, or (at your option) any later version. */
16 /* */
17 /* This program is distributed in the hope that it will be useful, */
18 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
19 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
20 /* GNU Lesser General Public License for more details. */
21 /* */
22 /* You should have received a copy of the GNU Lesser General Public License */
23 /* along with this program; if not, write to the Free Software */
24 /* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
25 /* */
26 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
27 
28 /**@file objpricer_gcg.h
29  * @brief GCG variable pricer
30  * @author Martin Bergner
31  * @ingroup PRICERS
32  */
33 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 #ifndef GCG_OBJPRICER_GCG_H_
37 #define GCG_OBJPRICER_GCG_H_
38 
39 #include "objscip/objscip.h"
40 #include "class_pricingtype.h"
42 #include "class_stabilization.h"
43 #include "pub_gcgcol.h"
44 #include "pub_colpool.h"
45 #include "pricestore_gcg.h"
46 
47 /**@defgroup GCGPRICEROBJ GCG Variable Pricer Object
48  * @ingroup PRICING_PUB
49  * @{
50  */
51 
53 using gcg::Stabilization;
54 
55 class ObjPricerGcg : public scip::ObjPricer
56 {
57 public:
58  /*lint --e{1540}*/
59 
60  SCIP* origprob; /**< the original program */
61  SCIP_PRICERDATA* pricerdata; /**< pricerdata data structure */
62  GCG_COLPOOL* colpool; /**< column pool */
63  GCG_PRICESTORE* pricestore; /**< price storage */
64  static int threads;
65 
66  /** default constructor */
68  SCIP* scip, /**< SCIP data structure */
69  SCIP* origscip, /**< SCIP data structure of original problem */
70  const char* name, /**< name of variable pricer */
71  const char* desc, /**< description of variable pricer */
72  int priority, /**< priority of the variable pricer */
73  unsigned int delay, /**< should the pricer be delayed until no other pricers or already existing*/
74  SCIP_PRICERDATA *pricerdata /**< pricerdata data structure */
75  );
76  /** destructor */
77  virtual ~ObjPricerGcg()
78  {}
79 
80  /** destructor of variable pricer to free user data (called when SCIP is exiting) */
81  virtual SCIP_DECL_PRICERFREE(scip_free);
82  /** initialization method of variable pricer (called after problem was transformed) */
83  virtual SCIP_DECL_PRICERINIT(scip_init);
84  /** deinitialization method of variable pricer (called before transformed problem is freed) */
85  virtual SCIP_DECL_PRICEREXIT(scip_exit);
86  /** solving process initialization method of variable pricer (called when branch and bound process is about to begin) */
87  virtual SCIP_DECL_PRICERINITSOL(scip_initsol);
88  /** solving process deinitialization method of variable pricer (called before branch and bound process data is freed) */
89  virtual SCIP_DECL_PRICEREXITSOL(scip_exitsol);
90  /** reduced cost pricing method of variable pricer for feasible LPs */
91  virtual SCIP_DECL_PRICERREDCOST(scip_redcost);
92  /** farkas pricing method of variable pricer for infeasible LPs */
93  virtual SCIP_DECL_PRICERFARKAS(scip_farkas);
94  inline SCIP_PRICERDATA *getPricerdata()
95  {
96  return pricerdata;
97  }
98 
99  /** for a pricing problem, get the dual solution value or Farkas value of the convexity constraint */
100  SCIP_Real getConvconsDualsol(
101  PricingType* pricetype, /**< Farkas or Reduced cost pricing */
102  int probnr /**< index of corresponding pricing problem */
103  );
104 
105  /** computes the pricing problem objectives */
106  SCIP_RETCODE setPricingObjs(
107  PricingType* pricetype, /**< Farkas or Reduced cost pricing */
108  SCIP_Bool stabilize /**< do we use stabilization ? */
109  );
110 
111  /** update reduced cost of columns in column pool */
113  PricingType* pricetype /**< type of pricing: reduced cost or Farkas */
114  );
115  /** method to price new columns from Column Pool */
116  SCIP_RETCODE priceColumnPoolOld(
117  PricingType* pricetype, /**< type of pricing: reduced cost or Farkas */
118  int* pnfoundvars /**< pointer to store number of priced variables */
119  );
120 
121  /** performs the pricing routine, gets the type of pricing that should be done: farkas or redcost pricing */
122  SCIP_RETCODE priceNewVariables(
123  PricingType* pricetype, /**< type of the pricing */
124  SCIP_RESULT* result, /**< result pointer */
125  double* lowerbound /**< lower bound of pricingproblems */
126  );
127 
128  /** creates a new master variable corresponding to the given solution and problem */
129  SCIP_RETCODE createNewMasterVar(
130  SCIP* scip, /**< SCIP data structure */
131  PricingType* pricetype, /**< type of the pricing */
132  SCIP_SOL* sol, /**< solution to compute reduced cost for */
133  SCIP_VAR** solvars, /**< array of variables with non-zero value in the solution of the pricing problem */
134  double* solvals, /**< array of values in the solution of the pricing problem for variables in array solvars*/
135  int nsolvars, /**< number of variables in array solvars */
136  unsigned int solisray, /**< is the solution a ray? */
137  int prob, /**< number of the pricing problem the solution belongs to */
138  unsigned int force, /**< should the given variable be added also if it has non-negative reduced cost? */
139  unsigned int* added, /**< pointer to store whether the variable was successfully added */
140  SCIP_VAR** addedvar /**< pointer to store the created variable */
141  );
142 
143  /** creates a new master variable corresponding to the given gcg column */
144  SCIP_RETCODE createNewMasterVarFromGcgCol(
145  SCIP* scip, /**< SCIP data structure */
146  PricingType* pricetype, /**< type of pricing */
147  GCG_COL* gcgcol, /**< GCG column data structure */
148  SCIP_Bool force, /**< should the given variable be added also if it has non-negative reduced cost? */
149  SCIP_Bool* added, /**< pointer to store whether the variable was successfully added */
150  SCIP_VAR** addedvar, /**< pointer to store the created variable */
151  SCIP_Real score /**< score of column (or -1.0 if not specified) */
152  );
153 
154  /* Compute difference of two dual solutions */
155  SCIP_RETCODE computeDualDiff(
156  SCIP_Real** dualvals1, /**< array of dual values for each pricing problem */
157  SCIP_Real* dualconv1, /**< array of dual solutions for the convexity constraints */
158  SCIP_Real** dualvals2, /**< array of dual values for each pricing problem */
159  SCIP_Real* dualconv2, /**< array of dual solutions for the convexity constraints */
160  SCIP_Real* dualdiff /**< pointer to store difference of duals solutions */
161  );
162 
163  /** the pricing loop: solve the pricing problems */
164  SCIP_RETCODE pricingLoop(
165  PricingType* pricetype, /**< type of pricing */
166  SCIP_RESULT* result, /**< result pointer */
167  int* nfoundvars, /**< pointer to store number of found variables */
168  SCIP_Real* lowerbound, /**< pointer to store lowerbound obtained due to lagrange bound */
169  SCIP_Bool* bestredcostvalid /**< pointer to store if bestredcost are valid (pp solvedoptimal) */
170  );
171 
173  {
174  return farkaspricing;
175  }
176 
178  {
179  return farkaspricing;
180  }
181 
183  {
184  return reducedcostpricing;
185  }
186 
188  {
189  return reducedcostpricing;
190  }
191 
192  SCIP* getOrigprob()
193  {
194  return origprob;
195  }
196 
197  /** get the number of columns to be added to the master LP in the current pricing round */
198  int getMaxColsRound() const;
199 
200  /** get the number of columns per pricing problem to be added to the master LP in the current pricing round */
201  int getMaxColsProb() const;
202 
203  /** add artificial vars */
204  SCIP_RETCODE addArtificialVars();
205 
206  /** add trivial sols */
207  SCIP_RETCODE addTrivialsols();
208 
209  /** create the pointers for the pricing types */
210  SCIP_RETCODE createPricingTypes();
211 
212  /** create the pricing controller */
213  SCIP_RETCODE createPricingcontroller();
214 
215  /** create the pointers for the stabilization */
216  void createStabilization();
217 
218  /** create the pointers for the colpool */
219  SCIP_RETCODE createColpool();
220 
221  /** create the pointers for the pricestore */
222  SCIP_RETCODE createPricestore();
223 
224  /** for given columns, (re-)compute and update their reduced costs */
225  void updateRedcosts(
226  PricingType* pricetype, /**< type of pricing */
227  GCG_COL** cols, /**< columns to compute reduced costs for */
228  int ncols, /**< number of columns */
229  int* nimpcols /**< pointer to store number of improving columns */
230  );
231 
232  /** add a new column to the pricing storage */
233  SCIP_RETCODE addColToPricestore(
234  GCG_COL* col /**< priced col */
235  );
236 
237  /** for each pricing problem, get the best found column from the pricing storage */
238  void getBestCols(
239  GCG_COL** pricingprobcols /**< array to be filled with best column per pricing problem */
240  );
241 
242  /** get the sum over the dual values of convexity constraints */
243  SCIP_Real getDualconvsum(
244  GCG_COL** bestcols /**< best columns found per pricing problem */
245  );
246 
247  /* computes the objective value of the current (stabilized) dual variables) in the dual program */
248  SCIP_RETCODE getStabilizedDualObjectiveValue(
249  PricingType* pricetype, /**< type of pricing */
250  SCIP_Real* stabdualval, /**< pointer to store stabilized dual objective value */
251  SCIP_Bool stabilize /**< stabilize? */
252  );
253 
254  SCIP_Real computeRedCostGcgCol(
255  PricingType* pricetype, /**< type of pricing */
256  GCG_Col* gcgcol, /**< gcg column to compute reduced cost for */
257  SCIP_Real* objvalptr /**< pointer to store the computed objective value */
258  ) const;
259 
260  /** compute master coefficients of column */
261  SCIP_RETCODE computeColMastercoefs(
262  GCG_COL* gcgcol /**< GCG column data structure */
263  );
264 
265  /** compute master cut coefficients of column */
266  SCIP_RETCODE computeColMastercuts(
267  GCG_COL* gcgcol /**< GCG column data structure */
268  );
269 
270 private:
271  ReducedCostPricing* reducedcostpricing;
272  FarkasPricing* farkaspricing;
273  PricingType* pricingtype; /**< current pricing type, or NULL if we are not in pricing */
274  Pricingcontroller* pricingcontroller;
275  Stabilization* stabilization;
276 
277  /** free pricing problems */
278  SCIP_RETCODE freePricingProblems();
279 
280  SCIP_Real computeRedCost(
281  PricingType* pricetype, /**< type of pricing */
282  SCIP_SOL* sol, /**< solution to compute reduced cost for */
283  SCIP_Bool solisray, /**< is the solution a ray? */
284  int prob, /**< number of the pricing problem the solution belongs to */
285  SCIP_Real* objvalptr /**< pointer to store the computed objective value */
286  ) const;
287 
288  /** for given columns, (re-)compute and update their reduced costs */
289  void updateRedcosts(
290  PricingType* pricetype, /**< type of pricing */
291  GCG_COL** cols, /**< columns to compute reduced costs for */
292  int ncols /**< number of columns */
293  ) const;
294 
295  /** return TRUE or FALSE whether the master LP is solved to optimality */
296  SCIP_Bool isMasterLPOptimal() const;
297 
298  /** ensures size of pricedvars array */
299  SCIP_RETCODE ensureSizePricedvars(
300  int size /**< needed size */
301  );
302 
303  /** adds new variable to the end of the priced variables array */
304  SCIP_RETCODE addVariableToPricedvars(
305  SCIP_VAR* newvar /**< variable to add */
306  );
307 
308  /** ensures size of root bounds arrays */
309  SCIP_RETCODE ensureSizeRootBounds(
310  int size /**< needed size */
311  );
312 
313  /** adds new bounds to the bound arrays as well as some additional information on dual variables and root lp solution */
314  SCIP_RETCODE addRootBounds(
315  SCIP_Real primalbound, /**< new primal bound for the root master LP */
316  SCIP_Real dualbound /**< new dual bound for the root master LP */
317  );
318 
319  /** add master variable to all constraints */
320  SCIP_RETCODE addVariableToMasterconstraints(
321  SCIP_VAR* newvar, /**< The new variable to add */
322  int prob, /**< number of the pricing problem the solution belongs to */
323  SCIP_VAR** solvars, /**< array of variables with non-zero value in the solution of the pricing problem */
324  SCIP_Real* solvals, /**< array of values in the solution of the pricing problem for variables in array solvars*/
325  int nsolvars /**< number of variables in array solvars */
326  );
327 
328  /** add master variable to all constraints */
329  SCIP_RETCODE addVariableToMasterconstraintsFromGCGCol(
330  SCIP_VAR* newvar, /**< The new variable to add */
331  GCG_COL* gcgcol /**< GCG column data structure */
332  );
333 
334  /** add variable with computed coefficients to the master cuts */
335  SCIP_RETCODE addVariableToMastercuts(
336  SCIP_VAR* newvar, /**< The new variable to add */
337  int prob, /**< number of the pricing problem the solution belongs to */
338  SCIP_VAR** solvars, /**< array of variables with non-zero value in the solution of the pricing problem */
339  SCIP_Real* solvals, /**< array of values in the solution of the pricing problem for variables in array solvars*/
340  int nsolvars /**< number of variables in array solvars */
341  );
342 
343  /** add variable with computed coefficients to the master cuts */
344  SCIP_RETCODE addVariableToMastercutsFromGCGCol(
345  SCIP_VAR* newvar, /**< The new variable to add */
346  GCG_COL* gcgcol /**< GCG column data structure */
347  );
348 
349  /**
350  * check whether pricing can be aborted:
351  * if objective value is always integral and the current node's current
352  * lowerbound rounded up equals the current lp objective value rounded
353  * up we don't need to continue pricing since the best possible feasible
354  * solution must have at least this value
355  */
356  SCIP_Bool canPricingBeAborted() const;
357 
358  /** sorts pricing problems according to their score */
359  void sortPricingProblemsByScore() const;
360 
361  /** returns the gegeneracy of the masterproblem */
362  SCIP_RETCODE computeCurrentDegeneracy(
363  double* degeneracy /**< pointer to store degeneracy */
364  );
365 
366  /** set subproblem memory limit */
367  SCIP_RETCODE setPricingProblemMemorylimit(
368  SCIP* pricingscip /**< SCIP of the pricingproblem */
369  );
370 
371 #ifdef SCIP_DISABLED_CODE
372  /** generic method to generate feasible columns from the pricing problem
373  * @note This method has to be threadsafe!
374  */
375  SCIP_RETCODE generateColumnsFromPricingProblem(
376  GCG_PRICINGJOB* pricingjob, /**< pricing job to be performed */
377  PricingType* pricetype, /**< type of pricing: reduced cost or Farkas */
378  int maxcols /**< size of the cols array to indicate maximum columns */
379  );
380 
381  /** solves a specific pricing problem
382  * @todo simplify
383  * @note This method has to be threadsafe!
384  */
385  SCIP_RETCODE solvePricingProblem(
386  GCG_PRICINGJOB* pricingjob, /**< pricing job to be performed */
387  PricingType* pricetype, /**< type of pricing: reduced cost or Farkas */
388  int maxcols /**< size of the cols array to indicate maximum columns */
389  );
390 #endif
391 
392  /** perform a pricing job, i.e. apply the corresponding solver to the pricing problem
393  * @note This method has to be threadsafe!
394  */
395  SCIP_RETCODE performPricingjob(
396  GCG_PRICINGJOB* pricingjob, /**< pricing job */
397  PricingType* pricetype, /**< type of pricing: reduced cost or Farkas */
398  GCG_PRICINGSTATUS* status, /**< pointer to store pricing status */
399  SCIP_Real* lowerbound /**< pointer to store the obtained lower bound */
400  );
401 
402  /** frees all solvers */
403  SCIP_RETCODE solversFree();
404 
405  /** calls the init method on all solvers */
406  SCIP_RETCODE solversInit();
407 
408  /** calls the exit method on all solvers */
409  SCIP_RETCODE solversExit();
410 
411  /** calls the initsol method on all solvers */
412  SCIP_RETCODE solversInitsol();
413 
414  /** calls the exitsol method of all solvers */
415  SCIP_RETCODE solversExitsol();
416 
417  /** computes the stack of masterbranch constraints up to the last generic branching node
418  * @note This method has to be threadsafe!
419  */
420  SCIP_RETCODE computeGenericBranchingconssStack(
421  PricingType* pricetype, /**< type of pricing: reduced cost or Farkas */
422  int prob, /**< index of pricing problem */
423  SCIP_CONS*** consstack, /**< stack of branching constraints */
424  int* nconsstack, /**< size of the stack */
425  SCIP_Real** consduals /**< dual values of the masterbranch solutions, or NULL */
426  ) const;
427 
428  /** add bounds change from constraint from the pricing problem at this node
429  * @note This method has to be threadsafe!
430  */
431  SCIP_RETCODE addBranchingBoundChangesToPricing(
432  int prob, /**< index of pricing problem */
433  SCIP_CONS* branchcons /**< branching constraints from which bound should applied */
434  ) const;
435 
436  SCIP_RETCODE checkBranchingBoundChanges(
437  int prob, /**< index of pricing problem */
438  SCIP_SOL* sol, /**< solution to check */
439  SCIP_CONS* branchcons, /**< branching constraints from which bound should applied */
440  SCIP_Bool* feasible /**< check whether the solution is feasible */
441  ) const;
442 
443  /** check bounds change from constraint from the pricing problem at this node
444  * @note This method has to be threadsafe!
445  */
446  SCIP_RETCODE checkBranchingBoundChangesGcgCol(
447  GCG_COL* gcgcol, /**< gcg column to check */
448  SCIP_CONS* branchcons, /**< branching constraints from which bound should applied */
449  SCIP_Bool* feasible /**< check whether the solution is feasible */
450  ) const;
451 
452  SCIP_RETCODE ensureSizeArtificialvars(
453  int size /**< needed size */
454  );
455 
456 };
457 /** @} */
458 #endif
SCIP_RETCODE priceNewVariables(PricingType *pricetype, SCIP_RESULT *result, double *lowerbound)
int getMaxColsProb() const
Definition: pricer_gcg.cpp:375
class with functions for dual variable smoothing
virtual SCIP_DECL_PRICERFREE(scip_free)
SCIP_RETCODE pricingLoop(PricingType *pricetype, SCIP_RESULT *result, int *nfoundvars, SCIP_Real *lowerbound, SCIP_Bool *bestredcostvalid)
SCIP_RETCODE computeDualDiff(SCIP_Real **dualvals1, SCIP_Real *dualconv1, SCIP_Real **dualvals2, SCIP_Real *dualconv2, SCIP_Real *dualdiff)
SCIP_RETCODE priceColumnPoolOld(PricingType *pricetype, int *pnfoundvars)
SCIP_Real getConvconsDualsol(PricingType *pricetype, int probnr)
Definition: pricer_gcg.cpp:690
SCIP_RETCODE createNewMasterVar(SCIP *scip, PricingType *pricetype, SCIP_SOL *sol, SCIP_VAR **solvars, double *solvals, int nsolvars, unsigned int solisray, int prob, unsigned int force, unsigned int *added, SCIP_VAR **addedvar)
virtual ~ObjPricerGcg()
Definition: objpricer_gcg.h:77
virtual SCIP_DECL_PRICERINIT(scip_init)
SCIP_PRICERDATA * getPricerdata()
Definition: objpricer_gcg.h:94
SCIP_RETCODE createPricingcontroller()
SCIP_RETCODE addArtificialVars()
virtual SCIP_DECL_PRICERINITSOL(scip_initsol)
virtual SCIP_DECL_PRICEREXIT(scip_exit)
SCIP_PRICERDATA * pricerdata
Definition: objpricer_gcg.h:61
SCIP_RETCODE createNewMasterVarFromGcgCol(SCIP *scip, PricingType *pricetype, GCG_COL *gcgcol, SCIP_Bool force, SCIP_Bool *added, SCIP_VAR **addedvar, SCIP_Real score)
public methods for working with gcg columns
FarkasPricing * getFarkasPricingNonConst()
void updateRedcosts(PricingType *pricetype, GCG_COL **cols, int ncols, int *nimpcols)
virtual SCIP_DECL_PRICEREXITSOL(scip_exitsol)
SCIP_RETCODE addTrivialsols()
enum GCG_PricingStatus GCG_PRICINGSTATUS
ReducedCostPricing * getReducedCostPricingNonConst()
SCIP_Real computeRedCostGcgCol(PricingType *pricetype, GCG_Col *gcgcol, SCIP_Real *objvalptr) const
GCG_COLPOOL * colpool
Definition: objpricer_gcg.h:62
SCIP_RETCODE computeColMastercuts(GCG_COL *gcgcol)
SCIP_RETCODE computeColMastercoefs(GCG_COL *gcgcol)
static int threads
Definition: objpricer_gcg.h:64
GCG_PRICESTORE * pricestore
Definition: objpricer_gcg.h:63
ObjPricerGcg(SCIP *scip, SCIP *origscip, const char *name, const char *desc, int priority, unsigned int delay, SCIP_PRICERDATA *pricerdata)
SCIP_RETCODE createPricestore()
void updateRedcostColumnPool(PricingType *pricetype)
public methods for storing cols in a col pool
pricing controller managing the pricing strategy
SCIP_RETCODE getStabilizedDualObjectiveValue(PricingType *pricetype, SCIP_Real *stabdualval, SCIP_Bool stabilize)
virtual SCIP_DECL_PRICERFARKAS(scip_farkas)
SCIP * getOrigprob()
SCIP_RETCODE addColToPricestore(GCG_COL *col)
SCIP * origprob
Definition: objpricer_gcg.h:60
const ReducedCostPricing * getReducedCostPricing() const
abstraction for SCIP pricing types
void getBestCols(GCG_COL **pricingprobcols)
const FarkasPricing * getFarkasPricing() const
methods for storing priced cols (based on SCIP's separation storage)
int getMaxColsRound() const
Definition: pricer_gcg.cpp:367
virtual SCIP_DECL_PRICERREDCOST(scip_redcost)
SCIP_RETCODE createPricingTypes()
void createStabilization()
SCIP_RETCODE setPricingObjs(PricingType *pricetype, SCIP_Bool stabilize)
Definition: pricer_gcg.cpp:704
SCIP_RETCODE createColpool()
SCIP_Real getDualconvsum(GCG_COL **bestcols)