Scippy

GCG

Branch-and-Price & Column Generation for Everyone

class_stabilization.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 class_stabilization.h
29  * @brief class with functions for dual variable smoothing
30  * @author Martin Bergner
31  * @author Jonas Witt
32  */
33 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 #ifndef CLASS_STABILIZATION_H_
37 #define CLASS_STABILIZATION_H_
38 
39 #include "objscip/objscip.h"
40 #include "class_pricingtype.h"
41 
42 namespace gcg {
43 
45 {
46 private:
47  SCIP* scip_;
48  SCIP_Real* stabcenterconsvals;
49  int stabcenterconsvalssize;
50  int nstabcenterconsvals;
51  SCIP_Real* stabcentercutvals;
52  int stabcentercutvalssize;
53  int nstabcentercutvals;
54  SCIP_Real* stabcenterlinkingconsvals;
55  int nstabcenterlinkingconsvals;
56  int stabcenterlinkingconsvalssize;
57  SCIP_Real* stabcenterconv;
58  int nstabcenterconv;
59  SCIP_Real dualdiffnorm; /**< norm of difference between stabcenter and current duals */
60  SCIP_Real* subgradientconsvals;
61  int subgradientconsvalssize;
62  int nsubgradientconsvals;
63  SCIP_Real* subgradientcutvals;
64  int subgradientcutvalssize;
65  int nsubgradientcutvals;
66  SCIP_Real* subgradientlinkingconsvals;
67  int subgradientlinkingconsvalssize;
68  SCIP_Real subgradientnorm;
69  SCIP_Real hybridfactor;
70  PricingType* pricingtype;
71  SCIP_Real alpha;
72  SCIP_Real alphabar; /**< alpha that is used and updated in a mispricing schedule */
73  SCIP_Bool hybridascent; /**< hybridize smoothing with an ascent method? */
74  SCIP_Real beta;
75  SCIP_Longint nodenr;
76  int k; /**< counter for the number of stabilized pricing rounds in B&B node, excluding the mispricing schedule iterations */
77  int t; /**< counter for the number of pricing rounds during a mispricing schedule, restarted after a mispricing schedule is finished */
78  SCIP_Bool hasstabilitycenter;
79  SCIP_Real stabcenterbound;
80  SCIP_Bool inmispricingschedule; /**< currently in mispricing schedule */
81  SCIP_Real subgradientproduct;
82 
83 public:
84  /** constructor */
86  SCIP* scip, /**< SCIP data structure */
87  PricingType* pricingtype, /**< the pricing type when the stabilization should run */
88  SCIP_Bool hybridascent /**< enable hybridization of smoothing with an ascent method? */
89  );
90  /** constructor */
91  Stabilization();
92 
93  /** destructor */
94  virtual ~Stabilization();
95 
96  /** gets the stabilized dual solution of constraint at position i */
97  SCIP_RETCODE consGetDual(
98  int i, /**< index of the constraint */
99  SCIP_Real* dual /**< return pointer for dual value */
100  );
101 
102  /** gets the stabilized dual solution of cut at position i */
103  SCIP_RETCODE rowGetDual(
104  int i, /**< index of the row */
105  SCIP_Real* dual /**< return pointer for dual value */
106  );
107 
108  /** gets the stabilized dual of the convexity constraint at position i */
109  SCIP_Real convGetDual(
110  int i
111  );
112 
113  /** updates the stability center if the bound has increased */
114  SCIP_RETCODE updateStabilityCenter(
115  SCIP_Real lowerbound, /**< lower bound due to lagrange function corresponding to current (stabilized) dual vars */
116  SCIP_Real* dualsolconv, /**< corresponding feasible dual solution for convexity constraints */
117  GCG_COL** pricingcols /**< columns of the pricing problems */
118  );
119 
120  /** updates the alpha after unsuccessful pricing */
121  void updateAlphaMisprice();
122 
123  /** updates the alpha after successful pricing */
124  void updateAlpha();
125 
126  /** returns whether the stabilization is active */
127  SCIP_Bool isStabilized();
128 
129  /** enabling mispricing schedule */
131  );
132 
133  /** disabling mispricing schedule */
135  );
136 
137  /** is mispricing schedule enabled */
138  SCIP_Bool isInMispricingSchedule(
139  ) const;
140 
141  /** sets the variable linking constraints in the master */
142  SCIP_RETCODE setLinkingConss(
143  SCIP_CONS** linkingconss, /**< array of linking master constraints */
144  int* linkingconsblock, /**< block of the linking constraints */
145  int nlinkingconss /**< size of the array */
146  );
147 
148  /** increases the number of new variable linking constraints */
149  SCIP_RETCODE setNLinkingconsvals(
150  int nlinkingconssnew /**< number of new linking constraints */
151  );
152 
153  /** increases the number of new convexity constraints */
154  SCIP_RETCODE setNConvconsvals(
155  int nconvconssnew
156  );
157 
158  /** gets the dual of variable linking constraints at index i */
159  SCIP_Real linkingconsGetDual(
160  int i
161  );
162 
163  /**< update node */
164  void updateNode();
165 
166  /**< update information for hybrid stablization with dual ascent */
167  SCIP_RETCODE updateHybrid();
168 
169  /** update subgradient product */
170  SCIP_RETCODE updateSubgradientProduct(
171  GCG_COL** pricingcols /**< solutions of the pricing problems */
172  );
173 
174 private:
175  /** updates the number of iterations */
176  void updateIterationCount();
177 
178  /** updates the number of iterations in the current mispricing schedule */
179  void updateIterationCountMispricing();
180 
181  /** updates the constraints in the stability center (and allocates more memory) */
182  SCIP_RETCODE updateStabcenterconsvals();
183 
184  /** updates the cuts in the stability center (and allocates more memory) */
185  SCIP_RETCODE updateStabcentercutvals();
186 
187  /** updates the constraints in the subgradient (and allocates more memory) */
188  SCIP_RETCODE updateSubgradientconsvals();
189 
190  /** updates the cuts in the subgradient (and allocates more memory) */
191  SCIP_RETCODE updateSubgradientcutvals();
192 
193  /** increase the alpha value */
194  void increaseAlpha();
195 
196  /** decrease the alpha value */
197  void decreaseAlpha();
198 
199  /** calculates the product of subgradient (with linking variables)
200  * with the difference of current duals and the stability center */
201  SCIP_Real calculateSubgradientProduct(
202  GCG_COL** pricingcols /**< columns of the pricing problems */
203  );
204 
205  /** calculates the normalized subgradient (with linking variables) multiplied
206  * with the norm of the difference of current duals and the stability center */
207  void calculateSubgradient(
208  GCG_COL** pricingcols /**< columns of the pricing problems */
209  );
210 
211  /**< calculate norm of difference between stabcenter and current duals */
212  void calculateDualdiffnorm();
213 
214  /**< calculate beta */
215  void calculateBeta();
216 
217  /**< calculate factor that is needed in hybrid stabilization */
218  void calculateHybridFactor();
219 
220  /** computes the new dual value based on the current and the stability center values */
221  SCIP_Real computeDual(
222  SCIP_Real center, /**< value of stabilility center */
223  SCIP_Real current, /**< current dual value */
224  SCIP_Real subgradient, /**< subgradient (or 0.0 if not needed) */
225  SCIP_Real lhs, /**< lhs (or 0.0 if not needed) */
226  SCIP_Real rhs /**< rhs (or 0.0 if not needed) */
227  ) const;
228 };
229 
230 } /* namespace gcg */
231 #endif /* CLASS_STABILIZATION_H_ */
SCIP_RETCODE setNConvconsvals(int nconvconssnew)
SCIP_RETCODE setLinkingConss(SCIP_CONS **linkingconss, int *linkingconsblock, int nlinkingconss)
SCIP_RETCODE setNLinkingconsvals(int nlinkingconssnew)
SCIP_Real linkingconsGetDual(int i)
SCIP_Real convGetDual(int i)
SCIP_RETCODE rowGetDual(int i, SCIP_Real *dual)
abstraction for SCIP pricing types
SCIP_RETCODE updateSubgradientProduct(GCG_COL **pricingcols)
SCIP_Bool isInMispricingSchedule() const
SCIP_RETCODE updateStabilityCenter(SCIP_Real lowerbound, SCIP_Real *dualsolconv, GCG_COL **pricingcols)
SCIP_RETCODE consGetDual(int i, SCIP_Real *dual)