1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/* */
/* This file is part of the program */
/* GCG --- Generic Column Generation */
/* a Dantzig-Wolfe decomposition based extension */
/* of the branch-cut-and-price framework */
/* SCIP --- Solving Constraint Integer Programs */
/* */
/* Copyright (C) 2010-2022 Operations Research, RWTH Aachen University */
/* Zuse Institute Berlin (ZIB) */
/* */
/* This program is free software; you can redistribute it and/or */
/* modify it under the terms of the GNU Lesser General Public License */
/* as published by the Free Software Foundation; either version 3 */
/* of the License, or (at your option) any later version. */
/* */
/* This program is distributed in the hope that it will be useful, */
/* but WITHOUT ANY WARRANTY; without even the implied warranty of */
/* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
/* GNU Lesser General Public License for more details. */
/* */
/* You should have received a copy of the GNU Lesser General Public License */
/* along with this program; if not, write to the Free Software */
/* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
/* */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/**@file class_stabilization.h
* @brief class with functions for dual variable smoothing
* @author Martin Bergner
* @author Jonas Witt
*/
/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
#ifndef CLASS_STABILIZATION_H_
#define CLASS_STABILIZATION_H_
#include "objscip/objscip.h"
#include "class_pricingtype.h"
namespace gcg {
class Stabilization
{
private:
SCIP* scip_;
SCIP_Real* stabcenterconsvals;
int stabcenterconsvalssize;
int nstabcenterconsvals;
SCIP_Real* stabcentercutvals;
int stabcentercutvalssize;
int nstabcentercutvals;
SCIP_Real* stabcenterlinkingconsvals;
int nstabcenterlinkingconsvals;
int stabcenterlinkingconsvalssize;
SCIP_Real* stabcenterconv;
int nstabcenterconv;
SCIP_Real dualdiffnorm; /**< norm of difference between stabcenter and current duals */
SCIP_Real* subgradientconsvals;
int subgradientconsvalssize;
int nsubgradientconsvals;
SCIP_Real* subgradientcutvals;
int subgradientcutvalssize;
int nsubgradientcutvals;
SCIP_Real* subgradientlinkingconsvals;
int subgradientlinkingconsvalssize;
SCIP_Real subgradientnorm;
SCIP_Real hybridfactor;
PricingType* pricingtype;
SCIP_Real alpha;
SCIP_Real alphabar; /**< alpha that is used and updated in a mispricing schedule */
SCIP_Bool hybridascent; /**< hybridize smoothing with an ascent method? */
SCIP_Real beta;
SCIP_Longint nodenr;
int k; /**< counter for the number of stabilized pricing rounds in B&B node, excluding the mispricing schedule iterations */
int t; /**< counter for the number of pricing rounds during a mispricing schedule, restarted after a mispricing schedule is finished */
SCIP_Bool hasstabilitycenter;
SCIP_Real stabcenterbound;
SCIP_Bool inmispricingschedule; /**< currently in mispricing schedule */
SCIP_Real subgradientproduct;
public:
/** constructor */
Stabilization(
SCIP* scip, /**< SCIP data structure */
PricingType* pricingtype, /**< the pricing type when the stabilization should run */
SCIP_Bool hybridascent /**< enable hybridization of smoothing with an ascent method? */
);
/** constructor */
Stabilization();
/** destructor */
virtual ~Stabilization();
/** gets the stabilized dual solution of constraint at position i */
SCIP_RETCODE consGetDual(
int i, /**< index of the constraint */
SCIP_Real* dual /**< return pointer for dual value */
);
/** gets the stabilized dual solution of cut at position i */
SCIP_RETCODE rowGetDual(
int i, /**< index of the row */
SCIP_Real* dual /**< return pointer for dual value */
);
/** gets the stabilized dual of the convexity constraint at position i */
SCIP_Real convGetDual(
int i
);
/** updates the stability center if the bound has increased */
SCIP_RETCODE updateStabilityCenter(
SCIP_Real lowerbound, /**< lower bound due to lagrange function corresponding to current (stabilized) dual vars */
SCIP_Real* dualsolconv, /**< corresponding feasible dual solution for convexity constraints */
GCG_COL** pricingcols /**< columns of the pricing problems */
);
/** updates the alpha after unsuccessful pricing */
void updateAlphaMisprice();
/** updates the alpha after successful pricing */
void updateAlpha();
/** returns whether the stabilization is active */
SCIP_Bool isStabilized();
/** enabling mispricing schedule */
void activateMispricingSchedule(
);
/** disabling mispricing schedule */
void disablingMispricingSchedule(
);
/** is mispricing schedule enabled */
SCIP_Bool isInMispricingSchedule(
) const;
/** sets the variable linking constraints in the master */
SCIP_RETCODE setLinkingConss(
SCIP_CONS** linkingconss, /**< array of linking master constraints */
int* linkingconsblock, /**< block of the linking constraints */
int nlinkingconss /**< size of the array */
);
/** increases the number of new variable linking constraints */
SCIP_RETCODE setNLinkingconsvals(
int nlinkingconssnew /**< number of new linking constraints */
);
/** increases the number of new convexity constraints */
SCIP_RETCODE setNConvconsvals(
int nconvconssnew
);
/** gets the dual of variable linking constraints at index i */
SCIP_Real linkingconsGetDual(
int i
);
/**< update node */
void updateNode();
/**< update information for hybrid stablization with dual ascent */
SCIP_RETCODE updateHybrid();
/** update subgradient product */
SCIP_RETCODE updateSubgradientProduct(
GCG_COL** pricingcols /**< solutions of the pricing problems */
);
private:
/** updates the number of iterations */
void updateIterationCount();
/** updates the number of iterations in the current mispricing schedule */
void updateIterationCountMispricing();
/** updates the constraints in the stability center (and allocates more memory) */
SCIP_RETCODE updateStabcenterconsvals();
/** updates the cuts in the stability center (and allocates more memory) */
SCIP_RETCODE updateStabcentercutvals();
/** updates the constraints in the subgradient (and allocates more memory) */
SCIP_RETCODE updateSubgradientconsvals();
/** updates the cuts in the subgradient (and allocates more memory) */
SCIP_RETCODE updateSubgradientcutvals();
/** increase the alpha value */
void increaseAlpha();
/** decrease the alpha value */
void decreaseAlpha();
/** calculates the product of subgradient (with linking variables)
* with the difference of current duals and the stability center */
SCIP_Real calculateSubgradientProduct(
GCG_COL** pricingcols /**< columns of the pricing problems */
);
/** calculates the normalized subgradient (with linking variables) multiplied
* with the norm of the difference of current duals and the stability center */
void calculateSubgradient(
GCG_COL** pricingcols /**< columns of the pricing problems */
);
/**< calculate norm of difference between stabcenter and current duals */
void calculateDualdiffnorm();
/**< calculate beta */
void calculateBeta();
/**< calculate factor that is needed in hybrid stabilization */
void calculateHybridFactor();
/** computes the new dual value based on the current and the stability center values */
SCIP_Real computeDual(
SCIP_Real center, /**< value of stabilility center */
SCIP_Real current, /**< current dual value */
SCIP_Real subgradient, /**< subgradient (or 0.0 if not needed) */
SCIP_Real lhs, /**< lhs (or 0.0 if not needed) */
SCIP_Real rhs /**< rhs (or 0.0 if not needed) */
) const;
};
} /* namespace gcg */
#endif /* CLASS_STABILIZATION_H_ */