All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Macros Pages
lp_base.hpp
Go to the documentation of this file.
1 //=======================================================================
2 // Copyright (c) 2013 Piotr Wygocki, Piotr Godlewski
3 //
4 // Distributed under the Boost Software License, Version 1.0. (See
5 // accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7 //=======================================================================
15 #ifndef PAAL_LP_BASE_HPP
16 #define PAAL_LP_BASE_HPP
17 
18 #include "paal/lp/constraints.hpp"
19 #include "paal/lp/ids.hpp"
20 #include "paal/lp/problem_type.hpp"
21 
22 #include <boost/range/iterator_range.hpp>
23 
24 #include <cassert>
25 #include <string>
26 #include <unordered_map>
27 #include <unordered_set>
28 
29 namespace paal {
30 namespace lp {
31 
34  MINIMIZE,
35  MAXIMIZE
36 };
37 
40  PRIMAL,
41  DUAL
42 };
43 
44 namespace detail {
45 
55 template <typename LP> class lp_base : public LP {
56  using RowSet = std::unordered_set<row_id>;
57  using ColSet = std::unordered_set<col_id>;
58  using RowNames = std::unordered_map<row_id, std::string>;
59  using ColNames = std::unordered_map<col_id, std::string>;
60 
61  public:
62 
63  using RowIter = RowSet::const_iterator;
64  using ColIter = ColSet::const_iterator;
65 
69  lp_base(const std::string problem_name = "",
70  optimization_type opt_type = MINIMIZE)
71  : LP(), m_problem_name(problem_name) {
72  LP::set_optimization_type(opt_type);
73  }
74 
78  void set_lp_name(const std::string problem_name) {
79  m_problem_name = problem_name;
80  }
81 
92  col_id add_column(double cost_coef = 0, double lb = 0.,
93  double ub = lp_traits::PLUS_INF,
94  const std::string &name = "") {
95  col_id colId = LP::add_column(cost_coef, lb, ub);
96  m_col_ids.insert(colId);
97  m_col_names.insert(std::make_pair(colId, name));
98  return colId;
99  }
100 
111  const std::string &name = "") {
112  row_id rowId = LP::add_row(constraint);
113  m_row_ids.insert(rowId);
114  m_row_names.insert(std::make_pair(rowId, name));
115  return rowId;
116  }
117 
121  int columns_number() const { return m_col_ids.size(); }
122 
126  int rows_number() const { return m_row_ids.size(); }
127 
131  std::string get_col_name(col_id col) const {
132  auto it = m_col_names.find(col);
133  assert(it != m_col_names.end());
134  return it->second;
135  }
136 
140  std::string get_row_name(row_id row) const {
141  auto it = m_row_names.find(row);
142  assert(it != m_row_names.end());
143  return it->second;
144  }
145 
153  ColIter delete_col(ColIter col) {
154  LP::delete_col(*col);
155  m_col_names.erase(*col);
156  return m_col_ids.erase(col);
157  }
158 
164  void delete_col(col_id col) {
165  LP::delete_col(col);
166  m_col_names.erase(col);
167  std::size_t nr = m_col_ids.erase(col);
168  assert(nr == 1);
169  }
170 
178  RowIter delete_row(RowIter row) {
179  LP::delete_row(*row);
180  m_row_names.erase(*row);
181  return m_row_ids.erase(row);
182  }
183 
189  void delete_row(row_id row) {
190  LP::delete_row(row);
191  m_row_names.erase(row);
192  std::size_t nr = m_row_ids.erase(row);
193  assert(nr == 1);
194  }
195 
199  void clear() {
200  for (auto &&row : m_row_ids) {
201  LP::delete_row(row);
202  }
203  m_row_names.clear();
204  m_row_ids.clear();
205 
206  for (auto &&col : m_col_ids) {
207  LP::delete_col(col);
208  }
209  m_col_names.clear();
210  m_col_ids.clear();
211  }
212 
216  const ColSet &get_columns() const { return m_col_ids; }
217 
221  const RowSet &get_rows() const { return m_row_ids; }
222 
228  double get_col_value(col_id col) const {
229  return std::min(
230  std::max(LP::get_col_value(col),
231  LP::get_col_lower_bound(col)),
232  LP::get_col_upper_bound(col));
233  }
234 
239  int get_col_degree(col_id col) const {
240  return boost::distance(LP::get_rows_in_column(col));
241  }
242 
246  int get_row_degree(row_id row) const {
247  return LP::get_row_expression(row).non_zeros();
248  }
249 
255  double get_row_sum(row_id row) const {
256  auto expr = LP::get_row_expression(row);
257  auto ids = expr.get_elements();
258  return get_row_sum_for_ids(ids.begin(), ids.end());
259  }
260 
264  template <typename ostream>
265  friend ostream &operator<<(ostream &o, const lp_base<LP> &lp) {
266  o << "Problem name: " << lp.m_problem_name << std::endl;
267  auto get_name = [&](col_id col) {
268  auto name = " " + lp.get_col_name(col);
269  if (name == " ") {
270  name = detail::col_id_to_string(col);
271  }
272  return name;
273  };
274 
275  o << std::endl << "Objective function:" << std::endl;
277  o, lp.get_columns() | boost::adaptors::transformed([&](col_id col) {
278  return pretty_to_string(lp.get_col_coef(col)) + get_name(col);
279  }),
280  " + ");
281 
282  o << std::endl << std::endl << "Columns:" << std::endl;
283  for (auto col : lp.get_columns()) {
284  o << lp.get_col_lower_bound(col) << " <= " << get_name(col)
285  << " <= " << lp.get_col_upper_bound(col) << std::endl;
286  }
287  o << std::endl << "Rows:" << std::endl;
288 
289  for (auto row : lp.get_rows()) {
290  auto cols = lp.get_row_expression(row);
291  if (cols.non_zeros() == 0) {
292  continue;
293  }
294  o << "Row " << lp.get_row_name(row) << std::endl;
295  print_double_bounded_expression(
296  o, double_bounded_expression(std::move(cols),
297  lp.get_row_lower_bound(row),
298  lp.get_row_upper_bound(row)),
299  get_name);
300  o << std::endl << std::endl;
301  }
302  o << std::endl << "Current solution: " << std::endl;
304  o, lp.get_columns() | boost::adaptors::transformed([&](col_id col) {
305  return get_name(col) + " = " +
306  pretty_to_string(lp.get_col_value(col));
307  }),
308  ", ");
309  o << std::endl;
310 
311  return o;
312  }
313 
314  private:
315  lp_base(lp_base &&) {}
316  lp_base(const lp_base &) {}
317 
318  template <typename Iter>
319  double get_row_sum_for_ids(Iter begin, Iter end) const {
320  return std::accumulate(
321  begin, end, 0., [ = ](double sum, std::pair<col_id, double> col) {
322  return sum + LP::get_col_value(col.first) * col.second;
323  });
324  }
325 
326 
327  std::string m_problem_name;
328 
329  ColSet m_col_ids;
330  RowSet m_row_ids;
331 
332  ColNames m_col_names;
333  RowNames m_row_names;
334 };
335 
336 } // detail
337 } // lp
338 } // paal
339 
340 #endif // PAAL_LP_BASE_HPP
The common LP solvers base class. Responsible for:
Definition: lp_base.hpp:55
col_id add_column(double cost_coef=0, double lb=0., double ub=lp_traits::PLUS_INF, const std::string &name="")
Definition: lp_base.hpp:92
double get_row_sum(row_id row) const
Definition: lp_base.hpp:255
std::string pretty_to_string(double x, double epsilon=1e-9)
pretty_to_string prints double which is close to int as int
void print_collection(Stream &o, Range &&r, const std::string &del)
prints collection with delimiters without trailing delimiter
int get_col_degree(col_id col) const
Definition: lp_base.hpp:239
void set_lp_name(const std::string problem_name)
Definition: lp_base.hpp:78
std::string get_row_name(row_id row) const
Definition: lp_base.hpp:140
RowIter delete_row(RowIter row)
Definition: lp_base.hpp:178
simplex_type
simplex method type
Definition: lp_base.hpp:39
lp_base(const std::string problem_name="", optimization_type opt_type=MINIMIZE)
Definition: lp_base.hpp:69
int get_row_degree(row_id row) const
Definition: lp_base.hpp:246
optimization_type
optimization type
Definition: lp_base.hpp:33
void delete_col(col_id col)
Definition: lp_base.hpp:164
int columns_number() const
Definition: lp_base.hpp:121
std::string get_col_name(col_id col) const
Definition: lp_base.hpp:131
ColIter delete_col(ColIter col)
Definition: lp_base.hpp:153
const ColSet & get_columns() const
Definition: lp_base.hpp:216
double get_col_value(col_id col) const
Definition: lp_base.hpp:228
row_id add_row(const double_bounded_expression &constraint=double_bounded_expression{}, const std::string &name="")
Definition: lp_base.hpp:109
const RowSet & get_rows() const
Definition: lp_base.hpp:221
int rows_number() const
Definition: lp_base.hpp:126
void delete_row(row_id row)
Definition: lp_base.hpp:189