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
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/* */
/* 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_pricingcontroller.h
* @brief pricing controller managing the pricing strategy
* @author Christian Puchert
*/
/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
#ifndef CLASS_PRICINGCONTROLLER_H_
#define CLASS_PRICINGCONTROLLER_H_
#include "colpool.h"
#include "pricestore_gcg.h"
#include "class_pricingtype.h"
#include "type_gcgpqueue.h"
#include "type_pricingjob.h"
#include "type_pricingprob.h"
#include "objscip/objscip.h"
namespace gcg {
class Pricingcontroller
{
private:
SCIP* scip_; /**< SCIP instance (master problem) */
GCG_PRICINGPROB** pricingprobs; /**< pricing problems */
int npricingprobs; /**< number of pricing problems */
int maxpricingprobs; /**< capacity of pricingprobs */
GCG_PRICINGJOB** pricingjobs; /**< pricing jobs */
int npricingjobs; /**< number of pricing jobs */
int maxpricingjobs; /**< capacity of pricingjobs */
/* parameters */
int heurpricingiters; /**< maximum number of heuristic pricing iterations per pricing call and problem */
int maxheurdepth; /**< maximum depth at which heuristic pricing should be performed (-1 for infinity) */
char sorting; /**< order by which the pricing problems should be sorted */
int nroundscol; /**< number of previous pricing rounds for which the number of improving columns should be counted */
int chunksize; /**< maximal number of pricing problems to be solved during one pricing loop */
int eagerfreq; /**< frequency at which all pricing problems should be solved */
/* strategy */
GCG_PQUEUE* pqueue; /**< priority queue containing the pricing jobs */
SCIP_Real* score; /**< scores of the pricing problems */
int maxniters; /**< maximal possible number of pricing iterations */
int nchunks; /**< number of pricing problem 'chunks' */
int curchunk; /**< index of current chunk of pricing problems */
int startchunk; /**< first chunk considered in a pricing call */
PricingType* pricingtype_; /**< current pricing type */
/* statistics */
int eagerage; /**< iterations since last eager iteration */
int nsolvedprobs; /**< number of completely solved pricing problems during the current pricing loop */
public:
/** default constructor */
Pricingcontroller();
/** constructor */
Pricingcontroller(SCIP* scip);
/** destructor */
virtual ~Pricingcontroller();
SCIP_RETCODE addParameters();
SCIP_RETCODE initSol();
SCIP_RETCODE exitSol();
/** pricing initialization, called right at the beginning of pricing */
SCIP_RETCODE initPricing(
PricingType* pricingtype /**< type of pricing */
);
/** pricing deinitialization, called when pricing is finished */
void exitPricing();
/** setup the priority queue (done once per stabilization round): add all pricing jobs to be performed */
SCIP_RETCODE setupPriorityQueue(
SCIP_Real* dualsolconv /**< dual solution values / Farkas coefficients of convexity constraints */
);
/** get the next pricing job to be performed */
GCG_PRICINGJOB* getNextPricingjob();
/** add the information that the next branching constraint must be added,
* and for the pricing job, reset heuristic pricing counter and flag
*/
SCIP_RETCODE pricingprobNextBranchcons(
GCG_PRICINGPROB* pricingprob /**< pricing problem structure */
);
/** set an individual time limit for a pricing job */
SCIP_RETCODE setPricingjobTimelimit(
GCG_PRICINGJOB* pricingjob /**< pricing job */
);
/** update solution information of a pricing problem */
void updatePricingprob(
GCG_PRICINGPROB* pricingprob, /**< pricing problem structure */
GCG_PRICINGSTATUS status, /**< new pricing status */
SCIP_Real lowerbound, /**< new lower bound */
int nimpcols /**< number of new improving columns */
);
/** update solution statistics of a pricing job */
void updatePricingjobSolvingStats(
GCG_PRICINGJOB* pricingjob /**< pricing job */
);
/** decide whether a pricing job must be treated again */
void evaluatePricingjob(
GCG_PRICINGJOB* pricingjob, /**< pricing job */
GCG_PRICINGSTATUS status /**< status of pricing job */
);
/** collect solution results from all pricing problems */
void collectResults(
GCG_COL** bestcols, /**< best found columns per pricing problem */
SCIP_Bool* infeasible, /**< pointer to store whether pricing is infeasible */
SCIP_Bool* optimal, /**< pointer to store whether all pricing problems were solved to optimality */
SCIP_Real* bestobjvals, /**< array to store best lower bounds */
SCIP_Real* beststabobj, /**< pointer to store total lower bound */
SCIP_Real* bestredcost, /**< pointer to store best total reduced cost */
SCIP_Bool* bestredcostvalid /**< pointer to store whether best reduced cost is valid */
);
/** check if the next chunk of pricing problems is to be used */
SCIP_Bool checkNextChunk();
/** decide whether the pricing loop can be aborted */
SCIP_Bool canPricingloopBeAborted(
PricingType* pricingtype, /**< type of pricing (reduced cost or Farkas) */
int nfoundcols, /**< number of negative reduced cost columns found so far */
int nsuccessfulprobs /**< number of pricing problems solved successfully so far */
) const;
void resetEagerage();
void increaseEagerage();
/** for a given problem index, get the corresponding pricing problem (or NULL, if it does not exist) */
GCG_PRICINGPROB* getPricingprob(
int probnr /**< index of the pricing problem */
);
/** get maximal possible number of pricing iterations */
int getMaxNIters() const;
private:
/** comparison operator for pricing jobs w.r.t. their solution priority */
static
SCIP_DECL_SORTPTRCOMP(comparePricingjobs);
/** for each pricing problem, get its corresponding generic branching constraints */
SCIP_RETCODE getGenericBranchconss();
/** check if a pricing job is done */
SCIP_Bool pricingprobIsDone(
GCG_PRICINGPROB* pricingprob /**< pricing problem structure */
) const;
/** check whether the next generic branching constraint of a pricing problem must be considered */
SCIP_Bool pricingprobNeedsNextBranchingcons(
GCG_PRICINGPROB* pricingprob /**< pricing problem structure */
) const;
};
} /* namespace gcg */
#endif /* CLASS_PRICINGCONTROLLER_H_ */