1 #ifndef OPTIMIZER_HPP
2 #define OPTIMIZER_HPP
3
4 #include <tuple>
5 #include <functional>
6 #include <limits>
7
8 #include <libnest2d/common.hpp>
9
10 namespace libnest2d { namespace opt {
11
12 using std::forward;
13 using std::tuple;
14 using std::make_tuple;
15
16 /// A Type trait for upper and lower limit of a numeric type.
17 template<class T, class B = void >
18 struct limits {
minlibnest2d::opt::limits19 inline static T min() { return std::numeric_limits<T>::min(); }
maxlibnest2d::opt::limits20 inline static T max() { return std::numeric_limits<T>::max(); }
21 };
22
23 template<class T>
24 struct limits<T, enable_if_t<std::numeric_limits<T>::has_infinity, void>> {
minlibnest2d::opt::limits25 inline static T min() { return -std::numeric_limits<T>::infinity(); }
maxlibnest2d::opt::limits26 inline static T max() { return std::numeric_limits<T>::infinity(); }
27 };
28
29 /// An interval of possible input values for optimization
30 template<class T>
31 class Bound {
32 T min_;
33 T max_;
34 public:
Bound(const T & min=limits<T>::min (),const T & max=limits<T>::max ())35 Bound(const T& min = limits<T>::min(),
36 const T& max = limits<T>::max()): min_(min), max_(max) {}
min() const37 inline const T min() const BP2D_NOEXCEPT { return min_; }
max() const38 inline const T max() const BP2D_NOEXCEPT { return max_; }
39 };
40
41 /**
42 * Helper function to make a Bound object with its type deduced automatically.
43 */
44 template<class T>
bound(const T & min,const T & max)45 inline Bound<T> bound(const T& min, const T& max) { return Bound<T>(min, max); }
46
47 /**
48 * This is the type of an input tuple for the object function. It holds the
49 * values and their type in each dimension.
50 */
51 template<class...Args> using Input = tuple<Args...>;
52
53 template<class...Args>
initvals(Args...args)54 inline tuple<Args...> initvals(Args...args) { return make_tuple(args...); }
55
56 /**
57 * @brief Specific optimization methods for which a default optimizer
58 * implementation can be instantiated.
59 */
60 enum class Method {
61 L_SIMPLEX,
62 L_SUBPLEX,
63 G_GENETIC,
64 G_PARTICLE_SWARM
65 //...
66 };
67
68 /**
69 * @brief Info about result of an optimization. These codes are exactly the same
70 * as the nlopt codes for convinience.
71 */
72 enum ResultCodes {
73 FAILURE = -1, /* generic failure code */
74 INVALID_ARGS = -2,
75 OUT_OF_MEMORY = -3,
76 ROUNDOFF_LIMITED = -4,
77 FORCED_STOP = -5,
78 SUCCESS = 1, /* generic success code */
79 STOPVAL_REACHED = 2,
80 FTOL_REACHED = 3,
81 XTOL_REACHED = 4,
82 MAXEVAL_REACHED = 5,
83 MAXTIME_REACHED = 6
84 };
85
86 /**
87 * \brief A type to hold the complete result of the optimization.
88 */
89 template<class...Args>
90 struct Result {
91 ResultCodes resultcode;
92 tuple<Args...> optimum;
93 double score;
94 };
95
96 /**
97 * @brief A type for specifying the stop criteria.
98 */
99 struct StopCriteria {
100
101 /// If the absolute value difference between two scores.
102 double absolute_score_difference = std::nan("");
103
104 /// If the relative value difference between two scores.
105 double relative_score_difference = std::nan("");
106
107 /// Stop if this value or better is found.
108 double stop_score = std::nan("");
109
110 /// A predicate that if evaluates to true, the optimization should terminate
111 /// and the best result found prior to termination should be returned.
__anon339361cd0102libnest2d::opt::StopCriteria112 std::function<bool()> stop_condition = [] { return false; };
113
114 /// The max allowed number of iterations.
115 unsigned max_iterations = 0;
116 };
117
118 /**
119 * \brief The Optimizer base class with CRTP pattern.
120 */
121 template<class Subclass>
122 class Optimizer {
123 protected:
124 enum class OptDir{
125 MIN,
126 MAX
127 } dir_;
128
129 StopCriteria stopcr_;
130
131 public:
132
Optimizer(const StopCriteria & scr={})133 inline explicit Optimizer(const StopCriteria& scr = {}): stopcr_(scr) {}
134
135 /**
136 * \brief Optimize for minimum value of the provided objectfunction.
137 * \param objectfunction The function that will be searched for the minimum
138 * return value.
139 * \param initvals A tuple with the initial values for the search
140 * \param bounds A parameter pack with the bounds for each dimension.
141 * \return Returns a Result<Args...> structure.
142 * An example call would be:
143 * auto result = opt.optimize_min(
144 * [](tuple<double> x) // object function
145 * {
146 * return std::pow(std::get<0>(x), 2);
147 * },
148 * make_tuple(-0.5), // initial value
149 * {-1.0, 1.0} // search space bounds
150 * );
151 */
152 template<class Func, class...Args>
optimize_min(Func && objectfunction,Input<Args...> initvals,Bound<Args>...bounds)153 inline Result<Args...> optimize_min(Func&& objectfunction,
154 Input<Args...> initvals,
155 Bound<Args>... bounds)
156 {
157 dir_ = OptDir::MIN;
158 return static_cast<Subclass*>(this)->template optimize<Func, Args...>(
159 forward<Func>(objectfunction), initvals, bounds... );
160 }
161
162 template<class Func, class...Args>
optimize_min(Func && objectfunction,Input<Args...> initvals)163 inline Result<Args...> optimize_min(Func&& objectfunction,
164 Input<Args...> initvals)
165 {
166 dir_ = OptDir::MIN;
167 return static_cast<Subclass*>(this)->template optimize<Func, Args...>(
168 forward<Func>(objectfunction), initvals, Bound<Args>()... );
169 }
170
171 template<class...Args, class Func>
optimize_min(Func && objectfunction)172 inline Result<Args...> optimize_min(Func&& objectfunction)
173 {
174 dir_ = OptDir::MIN;
175 return static_cast<Subclass*>(this)->template optimize<Func, Args...>(
176 forward<Func>(objectfunction),
177 Input<Args...>(),
178 Bound<Args>()... );
179 }
180
181 /// Same as optimize_min but optimizes for maximum function value.
182 template<class Func, class...Args>
optimize_max(Func && objectfunction,Input<Args...> initvals,Bound<Args>...bounds)183 inline Result<Args...> optimize_max(Func&& objectfunction,
184 Input<Args...> initvals,
185 Bound<Args>... bounds)
186 {
187 dir_ = OptDir::MAX;
188 return static_cast<Subclass*>(this)->template optimize<Func, Args...>(
189 forward<Func>(objectfunction), initvals, bounds... );
190 }
191
192 template<class Func, class...Args>
optimize_max(Func && objectfunction,Input<Args...> initvals)193 inline Result<Args...> optimize_max(Func&& objectfunction,
194 Input<Args...> initvals)
195 {
196 dir_ = OptDir::MAX;
197 return static_cast<Subclass*>(this)->template optimize<Func, Args...>(
198 forward<Func>(objectfunction), initvals, Bound<Args>()... );
199 }
200
201 template<class...Args, class Func>
optimize_max(Func && objectfunction)202 inline Result<Args...> optimize_max(Func&& objectfunction)
203 {
204 dir_ = OptDir::MAX;
205 return static_cast<Subclass*>(this)->template optimize<Func, Args...>(
206 forward<Func>(objectfunction),
207 Input<Args...>(),
208 Bound<Args>()... );
209 }
210
211 };
212
213 // Just to be able to instantiate an unimplemented method and generate compile
214 // error.
215 template<class T = void>
216 class DummyOptimizer : public Optimizer<DummyOptimizer<T>> {
217 friend class Optimizer<DummyOptimizer<T>>;
218
219 public:
DummyOptimizer()220 DummyOptimizer() {
221 static_assert(always_false<T>::value, "Optimizer unimplemented!");
222 }
223
DummyOptimizer(const StopCriteria &)224 DummyOptimizer(const StopCriteria&) {
225 static_assert(always_false<T>::value, "Optimizer unimplemented!");
226 }
227
228 template<class Func, class...Args>
optimize(Func &&,tuple<Args...>,Bound<Args>...)229 Result<Args...> optimize(Func&& /*func*/,
230 tuple<Args...> /*initvals*/,
231 Bound<Args>... /*args*/)
232 {
233 return Result<Args...>();
234 }
235 };
236
237 // Specializing this struct will tell what kind of optimizer to generate for
238 // a given method
239 template<Method m> struct OptimizerSubclass { using Type = DummyOptimizer<>; };
240
241 /// Optimizer type based on the method provided in parameter m.
242 template<Method m> using TOptimizer = typename OptimizerSubclass<m>::Type;
243
244 /// Global optimizer with an explicitly specified local method.
245 template<Method m>
GlobalOptimizer(Method,const StopCriteria & scr={})246 inline TOptimizer<m> GlobalOptimizer(Method, const StopCriteria& scr = {})
247 { // Need to be specialized in order to do anything useful.
248 return TOptimizer<m>(scr);
249 }
250
251 }
252 }
253
254 #endif // OPTIMIZER_HPP
255