1 /* Copyright 2017-2021 PaGMO development team 2 3 This file is part of the PaGMO library. 4 5 The PaGMO library is free software; you can redistribute it and/or modify 6 it under the terms of either: 7 8 * the GNU Lesser General Public License as published by the Free 9 Software Foundation; either version 3 of the License, or (at your 10 option) any later version. 11 12 or 13 14 * the GNU General Public License as published by the Free Software 15 Foundation; either version 3 of the License, or (at your option) any 16 later version. 17 18 or both in parallel, as here. 19 20 The PaGMO library is distributed in the hope that it will be useful, but 21 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 22 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 23 for more details. 24 25 You should have received copies of the GNU General Public License and the 26 GNU Lesser General Public License along with the PaGMO library. If not, 27 see https://www.gnu.org/licenses/. */ 28 29 #ifndef PAGMO_PROBLEMS_GOLOMB_RULER_HPP 30 #define PAGMO_PROBLEMS_GOLOMB_RULER_HPP 31 32 #include <string> 33 #include <utility> 34 35 #include <pagmo/detail/visibility.hpp> 36 #include <pagmo/problem.hpp> 37 #include <pagmo/s11n.hpp> 38 #include <pagmo/types.hpp> 39 40 namespace pagmo 41 { 42 43 /// The Golomb Ruler Problem 44 /** 45 * 46 * \image html golomb_ruler.png "The optimal Golomb Ruler of order 4" width=3cm 47 * 48 * In mathematics, a Golomb ruler is a set of marks at integer positions along an imaginary ruler such that no two pairs 49 * of marks are the same distance apart. The number of marks on the ruler is its order, and the largest distance between 50 * two of its marks is its length. Translation and reflection of a Golomb ruler are considered trivial, so the smallest 51 * mark is customarily put at 0 and the next mark at the smaller of its two possible values. There is no requirement 52 * that a Golomb ruler be able to measure all distances up to its length, but if it does, it is called a perfect Golomb 53 * ruler. 54 * 55 * A Golomb ruler is optimal if no shorter Golomb ruler of the same order exists. Creating Golomb rulers is easy, 56 * but finding the optimal Golomb ruler (or rulers) for a specified order is computationally very challenging. 57 * 58 * This UDP represents the problem of finding an optimal Golomb ruler of a given order \f$ n\f$. A maximal distance \f$ 59 * l_{max}\f$ between consecutive marks is also specified to make the problem representation possible. The resulting 60 * optimization problem is an integer programming problem with one equality constraint. 61 * 62 * In this UDP, the decision vector is \f$ x=[d_1, d_2, d_{n-1}]\f$, where the distances between consecutive ticks are 63 * indicated with \f$ d_i\f$. The ticks on the ruler can then be reconstructed as \f$ a_0 = 0\f$, \f$ a_i = sum_{j=1}^i 64 * d_i, i=1 .. n-1\f$ 65 * 66 * Its formulation can thus be written as: 67 * 68 * \f[ 69 * \begin{array}{rl} 70 * \mbox{find:} & 1 \le d_i \le l_{max}, \forall i=1..n-1 \\ 71 * \mbox{to minimize: } & \sum_i d_i \\ 72 * \mbox{subject to:} & |a_i-a_j| \neq |a_l - a_m|, \forall (\mbox{distinct}) i,j,l,m \in [0, n] 73 * \end{array} 74 * \f] 75 * 76 * We transcribe the constraints as one single equality constraint: \f$ c = 0 \f$ where \f$ c\f$ is the count of 77 * repeated distances. 78 * 79 * See: https://en.wikipedia.org/wiki/Golomb_ruler 80 * 81 */ 82 class PAGMO_DLL_PUBLIC golomb_ruler 83 { 84 public: 85 /// Constructor from ruler order and maximal consecutive ticks distance 86 /** 87 * Constructs a Golomb Ruler problem. 88 * 89 * @param order ruler order. 90 * @param upper_bound maximum distance between consecutive ticks. 91 * 92 * @throw std::invalid_argument if \p order is < 2 or \p upper_bound is < 1. 93 * @throw std::overflow_error if \p upper_bound is too large. 94 */ 95 golomb_ruler(unsigned order = 3u, unsigned upper_bound = 10); 96 // Fitness computation 97 vector_double fitness(const vector_double &) const; 98 // Box-bounds 99 std::pair<vector_double, vector_double> get_bounds() const; 100 /// Equality constraint dimension 101 /** 102 * Returns the number of equality constraints 103 * 104 * @return the number of equality constraints 105 */ get_nec() const106 vector_double::size_type get_nec() const 107 { 108 return 1u; 109 } 110 /// Integer dimension 111 /** 112 * Returns the integer dimension of the problem. 113 * 114 * @return the integer dimension of the problem. 115 */ get_nix() const116 vector_double::size_type get_nix() const 117 { 118 return m_order - 1u; 119 } 120 // Problem name 121 std::string get_name() const; 122 123 private: 124 // Object serialization 125 friend class boost::serialization::access; 126 template <typename Archive> 127 void serialize(Archive &, unsigned); 128 129 /// Ruler Order. 130 unsigned m_order; 131 /// Maximum distance between consecutive ticks. 132 unsigned m_upper_bound; 133 }; 134 135 } // namespace pagmo 136 137 PAGMO_S11N_PROBLEM_EXPORT_KEY(pagmo::golomb_ruler) 138 139 #endif 140