All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Macros Pages
generalised_assignment.hpp
Go to the documentation of this file.
1 //=======================================================================
2 // Copyright (c) 2013 Piotr Wygocki
3 // 2014 Piotr Godlewski
4 //
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //=======================================================================
16 #ifndef PAAL_GENERALISED_ASSIGNMENT_HPP
17 #define PAAL_GENERALISED_ASSIGNMENT_HPP
18 
19 
22 
23 #include <boost/range/adaptor/indexed.hpp>
24 
25 namespace paal {
26 namespace ir {
27 
36  template <typename Problem, typename LP>
37  bool operator()(Problem &problem, const LP &lp, lp::row_id row) {
38  auto &&machine_rows = problem.get_machine_rows();
39  if (machine_rows.find(row) == machine_rows.end()) {
40  return false;
41  }
42  auto row_deg = lp.get_row_degree(row);
43  return row_deg <= 1 || (row_deg == 2 && problem.get_compare().ge(
44  lp.get_row_sum(row), 1));
45  }
46 };
47 
55  template <typename Problem, typename GetSolution>
56  void operator()(Problem &problem, const GetSolution &solution) {
57  auto jbegin = std::begin(problem.get_jobs());
58  auto mbegin = std::begin(problem.get_machines());
59  auto &col_idx = problem.get_col_idx();
60  auto job_to_machine = problem.get_job_to_machines();
61 
62  for (auto idx : irange(col_idx.size())) {
63  if (problem.get_compare().e(solution(col_idx[idx]), 1)) {
64  *job_to_machine =
65  std::make_pair(*(jbegin + problem.get_j_idx(idx)),
66  *(mbegin + problem.get_m_idx(idx)));
67  ++job_to_machine;
68  }
69  }
70  }
71 };
72 
76 class ga_init {
77  public:
82  template <typename Problem, typename LP>
83  void operator()(Problem &problem, LP &lp) {
84  lp.set_lp_name("generalized assignment problem");
85  lp.set_optimization_type(lp::MINIMIZE);
86 
87  add_variables(problem, lp);
88  add_constraints_for_jobs(problem, lp);
89  add_constraints_for_machines(problem, lp);
90  }
91 
92  private:
98  template <typename Problem, typename LP>
99  void add_variables(Problem &problem, LP &lp) {
100  auto &col_idx = problem.get_col_idx();
101  col_idx.reserve(problem.get_machines_cnt() * problem.get_jobs_cnt());
102  for (auto &&j : problem.get_jobs()) {
103  for (auto &&m : problem.get_machines()) {
104  if (problem.get_proceeding_time()(j, m) <=
105  problem.get_machine_available_time()(m)) {
106  col_idx.push_back(lp.add_column(problem.get_cost()(j, m)));
107  } else {
108  col_idx.push_back(
109  lp.add_column(problem.get_cost()(j, m), 0, 0));
110  }
111  }
112  }
113  }
114 
115  // constraints for job
116  template <typename Problem, typename LP>
117  void add_constraints_for_jobs(Problem &problem, LP &lp) {
118  auto &col_idx = problem.get_col_idx();
119  for (auto j_idx : irange(problem.get_jobs_cnt())) {
120  lp::linear_expression expr;
121  for (auto m_idx : irange(problem.get_machines_cnt())) {
122  expr += col_idx[problem.idx(j_idx, m_idx)];
123  }
124  lp.add_row(std::move(expr) == 1.0);
125  }
126  }
127 
128  // constraints for machines
129  template <typename Problem, typename LP>
130  void add_constraints_for_machines(Problem &problem, LP &lp) {
131  auto &col_idx = problem.get_col_idx();
132  for (auto m : problem.get_machines() | boost::adaptors::indexed()) {
133  auto T = problem.get_machine_available_time()(m.value());
134  lp::linear_expression expr;
135 
136  for (auto j : problem.get_jobs() | boost::adaptors::indexed()) {
137  auto t = problem.get_proceeding_time()(j.value(), m.value());
138  auto x = col_idx[problem.idx(j.index(), m.index())];
139  expr += x * t;
140  }
141  auto row = lp.add_row(std::move(expr) <= T);
142  problem.get_machine_rows().insert(row);
143  }
144  }
145 };
146 
147 template <typename Init = ga_init,
148  typename RoundCondition = default_round_condition,
149  typename RelaxContition = ga_relax_condition,
150  typename SetSolution = ga_set_solution>
151 using ga_ir_components =
152  IRcomponents<Init, RoundCondition, RelaxContition, SetSolution>;
153 
154 
167 template <typename MachineIter, typename JobIter, typename Cost,
168  typename ProceedingTime, typename MachineAvailableTime,
169  typename JobsToMachinesOutputIterator>
171  public:
172  using Job = typename std::iterator_traits<JobIter>::value_type;
173  using Machine = typename std::iterator_traits<MachineIter>::value_type;
174 
176  using MachineRows = std::unordered_set<lp::row_id>;
177  using ColIdx = std::vector<lp::col_id>;
178 
179  using ErrorMessage = boost::optional<std::string>;
180 
184  generalised_assignment(MachineIter mbegin, MachineIter mend, JobIter jbegin,
185  JobIter jend, const Cost &c, const ProceedingTime &t,
186  const MachineAvailableTime &T,
187  JobsToMachinesOutputIterator job_to_machines)
188  : m_m_cnt(std::distance(mbegin, mend)),
189  m_j_cnt(std::distance(jbegin, jend)), m_jbegin(jbegin), m_jend(jend),
190  m_mbegin(mbegin), m_mend(mend), m_c(c), m_t(t), m_T(T),
191  m_job_to_machine(job_to_machines) {}
192 
196  ErrorMessage check_input_validity() {
197  return ErrorMessage{};
198  }
199 
203  std::size_t idx(std::size_t j_idx, std::size_t m_idx) { return j_idx * m_m_cnt + m_idx; }
204 
209  std::size_t get_j_idx(std::size_t idx) { return idx / m_m_cnt; }
210 
215  std::size_t get_m_idx(std::size_t idx) { return idx % m_m_cnt; }
216 
220  MachineRows &get_machine_rows() { return m_machine_rows; }
221 
225  Compare get_compare() { return m_compare; }
226 
230  std::size_t get_machines_cnt() const { return m_m_cnt; }
231 
235  std::size_t get_jobs_cnt() const { return m_j_cnt; }
236 
240  boost::iterator_range<MachineIter> get_machines() {
241  return boost::make_iterator_range(m_mbegin, m_mend);
242  }
243 
247  boost::iterator_range<JobIter> get_jobs() {
248  return boost::make_iterator_range(m_jbegin, m_jend);
249  }
250 
254  ColIdx &get_col_idx() { return m_col_idx; }
255 
259  JobsToMachinesOutputIterator get_job_to_machines() {
260  return m_job_to_machine;
261  }
262 
267  const ProceedingTime &get_proceeding_time() { return m_t; }
268 
273  const MachineAvailableTime &get_machine_available_time() { return m_T; }
274 
279  const Cost &get_cost() const { return m_c; }
280 
281  private:
282 
283  const std::size_t m_m_cnt;
284  const std::size_t m_j_cnt;
285  JobIter m_jbegin;
286  JobIter m_jend;
287  MachineIter m_mbegin;
288  MachineIter m_mend;
289  const Cost &m_c;
290  const ProceedingTime &m_t;
291  const MachineAvailableTime &m_T;
292  JobsToMachinesOutputIterator m_job_to_machine;
293  const Compare m_compare;
294  ColIdx m_col_idx;
295  MachineRows m_machine_rows;
296 };
297 
318 template <typename MachineIter, typename JobIter, typename Cost,
319  typename ProceedingTime, typename MachineAvailableTime,
320  typename JobsToMachinesOutputIterator>
321 generalised_assignment<MachineIter, JobIter, Cost, ProceedingTime,
322  MachineAvailableTime, JobsToMachinesOutputIterator>
323 make_generalised_assignment(MachineIter mbegin, MachineIter mend,
324  JobIter jbegin, JobIter jend, const Cost &c,
325  const ProceedingTime &t,
326  const MachineAvailableTime &T,
327  JobsToMachinesOutputIterator jobs_to_machines) {
328  return generalised_assignment<
329  MachineIter, JobIter, Cost, ProceedingTime, MachineAvailableTime,
330  JobsToMachinesOutputIterator>(mbegin, mend, jbegin, jend, c, t, T,
331  jobs_to_machines);
332 }
333 
358 template <typename MachineIter, typename JobIter, typename Cost,
359  typename ProceedingTime, typename MachineAvailableTime,
360  typename JobsToMachinesOutputIterator,
361  typename Components = ga_ir_components<>,
362  typename Visitor = trivial_visitor>
364  MachineIter mbegin, MachineIter mend, JobIter jbegin, JobIter jend,
365  const Cost &c, const ProceedingTime &t, const MachineAvailableTime &T,
366  JobsToMachinesOutputIterator jobs_to_machines,
367  Components components = Components(), Visitor visitor = Visitor()) {
368  auto ga_solution = make_generalised_assignment(mbegin, mend, jbegin, jend,
369  c, t, T, jobs_to_machines);
370  return solve_iterative_rounding(ga_solution, std::move(components),
371  std::move(visitor));
372 }
373 
374 
375 } // ir
376 } // paal
377 #endif // PAAL_GENERALISED_ASSIGNMENT_HPP
std::size_t idx(std::size_t j_idx, std::size_t m_idx)
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
std::size_t get_j_idx(std::size_t idx)
double get_row_sum(row_id row) const
Definition: lp_base.hpp:255
The class for solving the Generalised Assignment problem using Iterative Rounding.
std::size_t get_m_idx(std::size_t idx)
IRResult generalised_assignment_iterative_rounding(MachineIter mbegin, MachineIter mend, JobIter jbegin, JobIter jend, const Cost &c, const ProceedingTime &t, const MachineAvailableTime &T, JobsToMachinesOutputIterator jobs_to_machines, Components components=Components(), Visitor visitor=Visitor())
Solves the Generalised Assignment problem using Iterative Rounding.
void set_lp_name(const std::string problem_name)
Definition: lp_base.hpp:78
bool operator()(Problem &problem, const LP &lp, lp::row_id row)
boost::iterator_range< JobIter > get_jobs()
auto irange(T begin, T end)
irange
Definition: irange.hpp:22
generalised_assignment(MachineIter mbegin, MachineIter mend, JobIter jbegin, JobIter jend, const Cost &c, const ProceedingTime &t, const MachineAvailableTime &T, JobsToMachinesOutputIterator job_to_machines)
boost::iterator_range< MachineIter > get_machines()
JobsToMachinesOutputIterator get_job_to_machines()
int get_row_degree(row_id row) const
Definition: lp_base.hpp:246
void operator()(Problem &problem, const GetSolution &solution)
void operator()(Problem &problem, LP &lp)
const ProceedingTime & get_proceeding_time()
row_id add_row(const double_bounded_expression &constraint=double_bounded_expression{}, const std::string &name="")
Definition: lp_base.hpp:109
const MachineAvailableTime & get_machine_available_time()
std::pair< lp::problem_type, IRSolutionCost > IRResult
IRResult solve_iterative_rounding(Problem &problem, IRcomponents components, Visitor visitor=Visitor())
Solves an Iterative Rounding problem.
generalised_assignment< MachineIter, JobIter, Cost, ProceedingTime, MachineAvailableTime, JobsToMachinesOutputIterator > make_generalised_assignment(MachineIter mbegin, MachineIter mend, JobIter jbegin, JobIter jend, const Cost &c, const ProceedingTime &t, const MachineAvailableTime &T, JobsToMachinesOutputIterator jobs_to_machines)
Creates a generalised_assignment object.