idol
A C++ Framework for Optimization
Loading...
Searching...
No Matches
IntegerMaster.h
1//
2// Created by henri on 30/03/23.
3//
4
5#ifndef IDOL_INTEGERMASTER_H
6#define IDOL_INTEGERMASTER_H
7
8#include "idol/mixed-integer/optimizers/branch-and-bound/nodes/DefaultNodeInfo.h"
9#include "idol/mixed-integer/optimizers/branch-and-bound/callbacks/BranchAndBoundCallbackFactory.h"
10#include "idol/mixed-integer/optimizers/branch-and-bound/callbacks/BranchAndBoundCallback.h"
11#include "idol/mixed-integer/optimizers/dantzig-wolfe/Optimizers_DantzigWolfeDecomposition.h"
12
13namespace idol::Heuristics {
14 template<class NodeInfoT> class IntegerMaster;
15}
16
17template<class NodeInfoT = idol::DefaultNodeInfo>
19 std::unique_ptr<OptimizerFactory> m_optimizer_factory;
20
21 std::optional<bool> m_integer_columns;
22
23 std::optional<double> m_time_limit;
24 std::optional<unsigned int> m_iteration_limit;
25 std::optional<unsigned int> m_max_depth;
26 std::optional<unsigned int> m_frequency;
27
28 IntegerMaster(const IntegerMaster& t_src);
29public:
30 IntegerMaster() = default;
31
32 IntegerMaster(IntegerMaster&&) noexcept = default;
33
34 IntegerMaster& operator=(const IntegerMaster&) = delete;
35 IntegerMaster& operator=(IntegerMaster&&) noexcept = default;
36
37 class Strategy : public BranchAndBoundCallback<NodeInfoT> {
38 std::unique_ptr<OptimizerFactory> m_optimizer_factory;
39 bool m_integer_columns = true;
40 double m_time_limit = std::numeric_limits<double>::max();
41 unsigned int m_iteration_limit = std::numeric_limits<unsigned int>::max();
42 unsigned int m_max_depth = 1000;
43 unsigned int m_frequency = 1;
44 unsigned int m_n_relevant_calls = 0; // Counts the number of calls to the callback which can trigger the heuristic, except for frequency reasons
45 protected:
46 void operator()(CallbackEvent t_event) override;
47 public:
48 explicit Strategy(const OptimizerFactory& t_optimizer);
49
50 [[nodiscard]] bool with_integer_columns() const { return m_integer_columns; }
51
52 void set_integer_columns(bool t_value) { m_integer_columns = t_value; }
53
54 void set_time_limit(double t_time_limit) { m_time_limit = std::max(0., t_time_limit); }
55
56 void set_iteration_limit(unsigned int t_iteration_limit) { m_iteration_limit = t_iteration_limit; }
57
58 void set_max_depth(unsigned int t_max_depth) { m_max_depth = t_max_depth; }
59
60 void set_frequency(unsigned int t_frequency) { m_frequency = t_frequency; }
61 };
62
63 BranchAndBoundCallback<NodeInfoT> *operator()() override;
64
65 [[nodiscard]] BranchAndBoundCallbackFactory<NodeInfoT> *clone() const override;
66
67 IntegerMaster& with_optimizer(const OptimizerFactory& t_optimizer);
68
69 IntegerMaster& with_integer_columns(bool t_value);
70
71 IntegerMaster& with_time_limit(double t_time_limit);
72
73 IntegerMaster& with_iteration_limit(unsigned int t_iteration_limit);
74
75 IntegerMaster& with_max_depth(unsigned int t_max_depth);
76
77 IntegerMaster& with_frequency(unsigned int t_frequency);
78};
79
80template<class NodeInfoT>
82 : m_optimizer_factory(t_src.m_optimizer_factory ? t_src.m_optimizer_factory->clone() : nullptr),
83 m_integer_columns(t_src.m_integer_columns),
84 m_time_limit(t_src.m_time_limit),
85 m_iteration_limit(t_src.m_time_limit),
86 m_max_depth(t_src.m_max_depth),
87 m_frequency(t_src.m_frequency)
88{}
89
90template<class NodeInfoT>
92
93 if (!m_optimizer_factory) {
94 throw Exception("No solver was given to solve the integer master problem, please call IntegerMaster.rst::with_osi_interface to configure.");
95 }
96
97 auto* result = new Strategy(*m_optimizer_factory);
98
99 if (m_integer_columns.has_value()) {
100 result->set_integer_columns(m_integer_columns.value());
101 }
102
103 if (m_time_limit.has_value()) {
104 result->set_time_limit(m_time_limit.value());
105 }
106
107 if (m_iteration_limit.has_value()) {
108 result->set_iteration_limit(m_iteration_limit.value());
109 }
110
111 if (m_max_depth.has_value()){
112 result->set_max_depth(m_max_depth.value());
113 }
114
115 if (m_frequency.has_value()) {
116 result->set_frequency(m_frequency.value());
117 }
118
119 return result;
120}
121
122template<class NodeInfoT>
124
125 if (m_optimizer_factory) {
126 throw Exception("A solver has already been given.");
127 }
128
129 m_optimizer_factory.reset(t_optimizer.clone());
130
131 return *this;
132}
133
134template<class NodeInfoT>
136 return new IntegerMaster(*this);
137}
138
139template<class NodeInfoT>
141 m_integer_columns = t_value;
142 return *this;
143}
144
145template<class NodeInfoT>
147 m_time_limit = t_time_limit;
148 return *this;
149}
150
151template<class NodeInfoT>
153 m_iteration_limit = t_iteration_limit;
154 return *this;
155}
156
157template<class NodeInfoT>
159 m_max_depth = t_max_depth;
160 return *this;
161}
162
163template<class NodeInfoT>
165 m_frequency = t_frequency;
166 return *this;
167}
168
169template<class NodeInfoT>
171 : m_optimizer_factory(t_optimizer.clone()) {
172
173}
174
175template<class NodeInfoT>
177
178 if (t_event != InvalidSolution) {
179 return;
180 }
181
182 if (m_max_depth < this->node().level()) {
183 return;
184 }
185
186 unsigned int n_relevant_calls = m_n_relevant_calls++;
187
188 if ( n_relevant_calls % m_frequency != 0) {
189 return;
190 }
191
192 const auto& relaxation = this->relaxation();
193 const auto& dantzig_wolfe_optimizer = relaxation.optimizer().template as<Optimizers::DantzigWolfeDecomposition>();
194 const auto& original_model = this->original_model();
195 const auto& formulation = dantzig_wolfe_optimizer.formulation();
196
197 const unsigned int n_sub_problems = formulation.n_sub_problems();
198
199 std::unique_ptr<Model> integer_master(formulation.master().clone());
200
201 integer_master->unuse();
202
203 for (const auto& var : original_model.vars()) {
204 const VarType type = original_model.get_var_type(var);
205 if (integer_master->has(var)) {
206 integer_master->set_var_type(var, type);
207 }
208 }
209
210 if (m_integer_columns) {
211 for (unsigned int i = 0 ; i < n_sub_problems ; ++i) {
212 for (const auto &[alpha, generator]: formulation.present_generators(i)) {
213 integer_master->set_var_type(alpha, Binary);
214 }
215 }
216 }
217
218 integer_master->use(*m_optimizer_factory);
219
220 integer_master->optimizer().set_param_time_limit(std::min(m_time_limit, relaxation.optimizer().get_remaining_time()));
221 // TODO set bound stop
222 integer_master->optimizer().set_param_iteration_limit(m_iteration_limit);
223
224 integer_master->optimize();
225
226 const int status = integer_master->get_status();
227
228 if (status != Optimal && status != Feasible) {
229 return;
230 }
231
232 auto solution = save_primal(*integer_master);
233
234 // search for alpha = 1, add generator to solution
235 for (unsigned int i = 0 ; i < n_sub_problems ; ++i) {
236 for (const auto &[alpha, generator]: formulation.present_generators(i)) {
237 if (solution.get(alpha) > .5) {
238 solution.merge_without_conflict(generator);
239 solution.set(alpha, 0.);
240 }
241 }
242 }
243
244 auto* info = new NodeInfoT();
245 info->set_primal_solution(std::move(solution));
246
247 this->submit_heuristic_solution(info);
248
249}
250
251#endif //IDOL_INTEGERMASTER_H
void operator()(CallbackEvent t_event) override