iterative_rounding.hpp
Go to the documentation of this file.
1 //=======================================================================
2 // Copyright (c) 2013 Piotr Wygocki
3 // 2014 Piotr Godlewski
5 // accompanying file LICENSE_1_0.txt or copy at
7 //=======================================================================
15 #ifndef PAAL_ITERATIVE_ROUNDING_HPP
16 #define PAAL_ITERATIVE_ROUNDING_HPP
17
18
20 #include "paal/lp/glp.hpp"
21 #include "paal/utils/floating.hpp"
23 #include "paal/utils/irange.hpp"
24
25 #include <boost/optional.hpp>
26
27 #include <cstdlib>
28 #include <unordered_map>
29
30 namespace paal {
31 namespace ir {
32
40  template <typename Problem, typename LP>
41  void solve_lp(Problem &problem, LP &lp) {}
42
46  template <typename Problem, typename LP>
47  void round_col(Problem &problem, LP &lp, lp::col_id col, double val) {}
48
52  template <typename Problem, typename LP>
53  void relax_row(Problem &problem, LP &lp, lp::row_id row) {}
54 };
55
58 template <typename Problem, typename LP>
60  bool m_first;
61  LP & m_lp;
62 public:
64  default_solve_lp_in_row_generation(Problem &, LP & lp) : m_first(true), m_lp(lp) {}
65
68  {
69  if (m_first) {
70  m_first = false;
71  return m_lp.solve_simplex(lp::PRIMAL);
72  }
73  return m_lp.resolve_simplex(lp::DUAL);
74  }
75 };
76
79 template <template <class, class> class SolveLP = default_solve_lp_in_row_generation>
82 template <class Problem, class LP>
83  auto operator()(Problem & problem, LP & lp) {
84  return row_generation(problem.get_find_violation(lp), SolveLP<Problem, LP>(problem, lp));
85  }
86 };
87
88
89
90 namespace detail {
91
100 template <typename Problem, typename IRcomponents, typename Visitor = trivial_visitor, typename LP = lp::glp>
102  using RoundedCols = std::unordered_map<lp::col_id, std::pair<double, double>>;
103
107  double get_val(lp::col_id col) const {
108  auto i = m_rounded.find(col);
109  if (i == m_rounded.end()) {
110  return m_lp.get_col_value(col);
111  } else {
112  return i->second.first;
113  }
114  }
115
116  public:
120  iterative_rounding(Problem &problem, IRcomponents e,
121  Visitor vis = Visitor())
122  : m_ir_components(std::move(e)), m_visitor(std::move(vis)),
123  m_problem(problem) {
124  call<Init>(m_problem, m_lp);
125  }
126
133  auto prob_type = call<SolveLP>(m_problem, m_lp);
134  assert(prob_type != lp::UNDEFINED);
135  m_visitor.solve_lp(m_problem, m_lp);
136  return prob_type;
137  }
138
145  auto prob_type = call<ResolveLP>(m_problem, m_lp);
146  assert(prob_type != lp::UNDEFINED);
147  m_visitor.solve_lp(m_problem, m_lp);
148  return prob_type;
149  }
150
154  double get_solution_cost() {
155  double sol_cost(0);
156  for (auto col : m_lp.get_columns()) {
157  sol_cost += m_lp.get_col_value(col) * m_lp.get_col_coef(col);
158  }
159  for (auto rounded_col : m_rounded) {
160  sol_cost += rounded_col.second.first * rounded_col.second.second;
161  }
162  return sol_cost;
163  }
164
171  bool round() {
172  int deleted(0);
173  auto &&cols = m_lp.get_columns();
174  auto cbegin = std::begin(cols);
175  auto cend = std::end(cols);
176
177  while (cbegin != cend) {
178  lp::col_id col = *cbegin;
179  auto do_round = call<RoundCondition>(m_problem, m_lp, col);
180  if (do_round) {
181  ++deleted;
182  m_rounded.insert(std::make_pair(col,
183  std::make_pair(*do_round, m_lp.get_col_coef(col))));
184  m_visitor.round_col(m_problem, m_lp, col, *do_round);
185  cbegin = delete_column(cbegin, *do_round);
186  }
187  else {
188  ++cbegin;
189  }
190  }
191
192  return deleted > 0;
193  }
194
200  bool relax() {
201  int deleted(0);
202  auto &&rows = m_lp.get_rows();
203  auto rbegin = std::begin(rows);
204  auto rend = std::end(rows);
205
206  while (rbegin != rend) {
207  lp::row_id row = *rbegin;
208  if (call<RelaxCondition>(m_problem, m_lp, row)) {
209  ++deleted;
210  m_visitor.relax_row(m_problem, m_lp, row);
211  rbegin = m_lp.delete_row(rbegin);
212  if (call<RelaxationsLimit>(deleted)) {
213  break;
214  }
215  } else {
216  ++rbegin;
217  }
218  }
219
220  return deleted > 0;
221  }
222
226  LP &get_lp() { return m_lp; }
227
231  IRcomponents &get_ir_components() { return m_ir_components; }
232
236  void set_solution() {
237  call<SetSolution>(m_problem, boost::bind(&iterative_rounding::get_val,
238  this, _1));
239  }
240
244  void dependent_round() { call<RoundCondition>(m_problem, m_lp); }
245
252  bool stop_condition() { return call<StopCondition>(m_problem, m_lp); }
253
254  private:
255  template <typename Action, typename... Args>
256  auto call(Args &&... args)
257  ->decltype(std::declval<IRcomponents>().template call<Action>(
258  std::forward<Args>(args)...)) {
259  return m_ir_components.template call<Action>(
260  std::forward<Args>(args)...);
261  }
262
264  typename LP::ColIter
265  delete_column(typename LP::ColIter col_iter, double value) {
266  auto column = m_lp.get_rows_in_column(*col_iter);
267  lp::row_id row;
268  double coef;
269  for (auto const &c : column) {
270  boost::tie(row, coef) = c;
271  double ub = m_lp.get_row_upper_bound(row);
272  double lb = m_lp.get_row_lower_bound(row);
273  double diff = coef * value;
274  m_lp.set_row_upper_bound(row, ub - diff);
275  m_lp.set_row_lower_bound(row, lb - diff);
276  }
277  return m_lp.delete_col(col_iter);
278  };
279
280  LP m_lp;
281  IRcomponents m_ir_components;
282  Visitor m_visitor;
283  utils::compare<double> m_compare;
284  RoundedCols m_rounded;
285  Problem &m_problem;
286 };
287
288 } //detail
289
291 using IRSolutionCost = boost::optional<double>;
294 using IRResult = std::pair<lp::problem_type, IRSolutionCost>;
295
307 template <typename Problem, typename IRcomponents, typename Visitor = trivial_visitor, typename LP = lp::glp>
308 IRResult solve_iterative_rounding(Problem & problem, IRcomponents components, Visitor visitor = Visitor()) {
309  detail::iterative_rounding<Problem, IRcomponents, Visitor, LP> ir(problem, std::move(components), std::move(visitor));
310
311  auto prob_type = ir.solve_lp();
312  if (prob_type != lp::OPTIMAL) {
313  return IRResult(prob_type, IRSolutionCost{});
314  }
315
316  while (!ir.stop_condition()) {
317  bool rounded{ ir.round() };
318  bool relaxed{ ir.relax() };
319  assert(rounded || relaxed);
320
321  prob_type = ir.resolve_lp();
322  if (prob_type != lp::OPTIMAL) {
323  return IRResult(prob_type, IRSolutionCost{});
324  }
325  }
326  ir.set_solution();
327  return IRResult(lp::OPTIMAL, IRSolutionCost(ir.get_solution_cost()));
328 }
329
341 template <typename Problem, typename IRcomponents, typename Visitor = trivial_visitor, typename LP = lp::glp>
342 IRResult solve_dependent_iterative_rounding(Problem & problem, IRcomponents components, Visitor visitor = Visitor()) {
343  detail::iterative_rounding<Problem, IRcomponents, Visitor, LP> ir(problem, std::move(components), std::move(visitor));
344
345  auto prob_type = ir.solve_lp();
346  if (prob_type != lp::OPTIMAL) {
347  return IRResult(prob_type, IRSolutionCost{});
348  }
349
350  while (!ir.stop_condition()) {
351  ir.dependent_round();
352  ir.relax();
353
354  prob_type = ir.resolve_lp();
355  if (prob_type != lp::OPTIMAL) {
356  return IRResult(prob_type, IRSolutionCost{});
357  }
358  }
359  ir.set_solution();
360  return IRResult(lp::OPTIMAL, IRSolutionCost(ir.get_solution_cost()));
361 }
362
363 } // ir
364 } // paal
365
366 #endif // PAAL_ITERATIVE_ROUNDING_HPP
iterative_rounding(Problem &problem, IRcomponents e, Visitor vis=Visitor())
Constructor.
The common LP solvers base class. Responsible for:
Definition: lp_base.hpp:55
default_solve_lp_in_row_generation(Problem &, LP &lp)
constructor
auto operator()(Problem &problem, LP &lp)
operator()
problem_type
LP problem type.
void solve_lp(Problem &problem, LP &lp)
Method called after (re)solving the LP.
bool relax()
Relaxes the LP rows using the RelaxCondition component.
bool stop_condition()
Checks if the IR problem has been solved, using the StopCondition component.
void dependent_round()
Rounds the LP using the RoundCondition component.
LP & get_lp()
Returns the LP object used to solve the IR.
double get_solution_cost()
Returns the solution cost based on the LP values.
IRcomponents & get_ir_components()
Returns the IR components.
void relax_row(Problem &problem, LP &lp, lp::row_id row)
Method called after relaxing a row of the LP.
This class solves an iterative rounding problem.
void round_col(Problem &problem, LP &lp, lp::col_id col, double val)
Method called after rounding a column of the LP.
RowIter delete_row(RowIter row)
Definition: lp_base.hpp:178
Default Iterative Rounding visitor.
void set_solution()
Sets the solution to the problem using SetSolution component.
ColIter delete_col(ColIter col)
Definition: lp_base.hpp:153
typename components::type< Args...> IRcomponents
Iterative rounding components.
const ColSet & get_columns() const
Definition: lp_base.hpp:216
double get_col_value(col_id col) const
Definition: lp_base.hpp:228
lp::problem_type resolve_lp()
Finds solution to the LP.
bool round()
Rounds the LP columns (independently) using the RoundCondition component.
std::pair< lp::problem_type, IRSolutionCost > IRResult
IRResult solve_iterative_rounding(Problem &problem, IRcomponents components, Visitor visitor=Visitor())
Solves an Iterative Rounding problem.
boost::optional< double > IRSolutionCost
Iterative Rounding solution cost type. Solution cost only makes sense if the LP has been solved to op...
lp::problem_type solve_lp()
Finds solution to the LP.
const RowSet & get_rows() const
Definition: lp_base.hpp:221
IRResult solve_dependent_iterative_rounding(Problem &problem, IRcomponents components, Visitor visitor=Visitor())
Solves an Iterative Rounding problem with dependent rounding.