lp_row_generation.hpp
Go to the documentation of this file.
1 //=======================================================================
3 //
5 // accompanying file LICENSE_1_0.txt or copy at
7 //=======================================================================
15 #ifndef PAAL_LP_ROW_GENERATION_HPP
16 #define PAAL_LP_ROW_GENERATION_HPP
17
18 #include "paal/lp/lp_base.hpp"
19 #include "paal/lp/problem_type.hpp"
20 #include "paal/utils/rotate.hpp"
21
22 #include <boost/range/counting_range.hpp>
23
24 namespace paal {
25 namespace lp {
26
35 template <class TryAddViolated, class SolveLp>
37  {
38  problem_type res;
39  do res = solve_lp(); while (res == OPTIMAL && try_add_violated());
40  return res;
41  }
42
51 template<
52  class GetCandidates,
53  class HowViolated,
55  class CompareHow
56 >
58  GetCandidates m_get_candidates;
59  HowViolated m_how_violated;
61  CompareHow m_cmp;
62
63  public:
67  : m_get_candidates(get_candidates), m_how_violated(how_violated),
69
71  bool operator()() {
72  auto&& cands = m_get_candidates();
73  using how_violated_t = puretype(m_how_violated(*std::begin(cands)));
74  using cand_it_t = puretype(std::begin(cands));
75  boost::optional<std::pair<how_violated_t, cand_it_t>> most;
76  for (auto cand : boost::counting_range(cands)) {
77  auto const how = m_how_violated(*cand);
78  if (!how) continue;
79  if (!most || m_cmp(most->first, how))
80  most = std::make_pair(std::move(how), cand);
81  }
82  if (!most) return false;
84  return true;
85  }
86 };
87
90  template <
91  class GetCandidates,
92  class HowViolated,
94  class CompareHow = utils::less
95  >
97  auto operator()(
98  GetCandidates get_candidates,
99  HowViolated is_violated,
101  CompareHow compare_how = CompareHow{}
102  ) const {
105  }
106 };
107
109 template <class GetCandidates,
110  class HowViolated,
112  class ReorderCandidates>
114  GetCandidates m_get_candidates;
115  HowViolated m_how_violated;
117  ReorderCandidates m_reorder_candidates;
118
119  public:
122  GetCandidates get_candidates,
123  HowViolated how_violated,
125  ReorderCandidates reorder_candidates
126  ) : m_get_candidates(get_candidates),
127  m_how_violated(how_violated),
129  m_reorder_candidates(std::move(reorder_candidates)) {}
130
132  bool operator()() {
133  auto&& cands = m_get_candidates();
134  auto reordered =
135  m_reorder_candidates(std::forward<decltype(cands)>(cands));
136  for (auto c : boost::counting_range(reordered)) {
137  if (m_how_violated(*c)) {
139  return true;
140  }
141  }
142  return false;
143  }
144 };
145
148  template <
149  class GetCandidates,
150  class HowViolated,
152  class ReorderCandidates = utils::identity_functor
153  >
156  GetCandidates get_candidates,
157  HowViolated how_violated,
159  ReorderCandidates reorder_candidates = ReorderCandidates{}
160  ) const {
163  reorder_candidates);
164  }
165 };
166
167 namespace detail {
168 template <class URNG>
170  URNG m_g;
171  public:
172  random_rotate(URNG&& g)
173  : m_g(std::forward<URNG>(g)) {}
174  template <class ForwardRange>
175  auto operator()(const ForwardRange& rng)
176  {
177  auto const len = boost::distance(rng);
178  std::uniform_int_distribution<decltype(len)> d(0, len);
179  return utils::rotate(rng, d(m_g));
180  }
181 };
182
183 template <class URNG = std::default_random_engine>
184 auto make_random_rotate(URNG&& g = URNG{})
185 {
186  return random_rotate<URNG>(std::forward<URNG>(g));
187 }
188 }
189
194  template <
195  class GetCandidates,
196  class HowViolated,
198  class URNG = std::default_random_engine
199  >
202  GetCandidates get_candidates,
203  HowViolated how_violated,
205  URNG&& g = URNG{}
206  ) const {
207  return first_violated_separation_oracle{}(get_candidates,
209  }
210 };
211
212
213 } // lp
214 } // paal
215
216 #endif // PAAL_LP_ROW_GENERATION_HPP
operator()
operator()
less functor
Definition: functors.hpp:497
functor for adding maximum violated constraint
problem_type
LP problem type.