OR-Tools  8.2
knapsack_solver.cc
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
15 
16 #include <algorithm>
17 #include <queue>
18 #include <string>
19 #include <vector>
20 
21 #include "absl/memory/memory.h"
22 #include "ortools/base/stl_util.h"
24 #include "ortools/util/bitset.h"
26 
27 namespace operations_research {
28 
29 namespace {
30 const int kNoSelection = -1;
31 const int kMasterPropagatorId = 0;
32 const int kMaxNumberOfBruteForceItems = 30;
33 const int kMaxNumberOf64Items = 64;
34 
35 // Comparator used to sort item in decreasing efficiency order
36 // (see KnapsackCapacityPropagator).
37 struct CompareKnapsackItemsInDecreasingEfficiencyOrder {
38  explicit CompareKnapsackItemsInDecreasingEfficiencyOrder(int64 _profit_max)
39  : profit_max(_profit_max) {}
40  bool operator()(const KnapsackItemPtr& item1,
41  const KnapsackItemPtr& item2) const {
42  return item1->GetEfficiency(profit_max) > item2->GetEfficiency(profit_max);
43  }
45 };
46 
47 // Comparator used to sort search nodes in the priority queue in order
48 // to pop first the node with the highest profit upper bound
49 // (see KnapsackSearchNode). When two nodes have the same upper bound, we
50 // prefer the one with the highest current profit, ie. usually the one closer
51 // to a leaf. In practice, the main advantage is to have smaller path.
52 struct CompareKnapsackSearchNodePtrInDecreasingUpperBoundOrder {
53  bool operator()(const KnapsackSearchNode* node_1,
54  const KnapsackSearchNode* node_2) const {
55  const int64 profit_upper_bound_1 = node_1->profit_upper_bound();
56  const int64 profit_upper_bound_2 = node_2->profit_upper_bound();
57  if (profit_upper_bound_1 == profit_upper_bound_2) {
58  return node_1->current_profit() < node_2->current_profit();
59  }
60  return profit_upper_bound_1 < profit_upper_bound_2;
61  }
62 };
63 
64 typedef std::priority_queue<
65  KnapsackSearchNode*, std::vector<KnapsackSearchNode*>,
66  CompareKnapsackSearchNodePtrInDecreasingUpperBoundOrder>
67  SearchQueue;
68 
69 // Returns true when value_1 * value_2 may overflow int64.
70 inline bool WillProductOverflow(int64 value_1, int64 value_2) {
71  const int MostSignificantBitPosition1 = MostSignificantBitPosition64(value_1);
72  const int MostSignificantBitPosition2 = MostSignificantBitPosition64(value_2);
73  // The sum should be less than 61 to be safe as we are only considering the
74  // most significant bit and dealing with int64 instead of uint64.
75  const int kOverflow = 61;
76  return MostSignificantBitPosition1 + MostSignificantBitPosition2 > kOverflow;
77 }
78 
79 // Returns an upper bound of (numerator_1 * numerator_2) / denominator
80 int64 UpperBoundOfRatio(int64 numerator_1, int64 numerator_2,
81  int64 denominator) {
82  DCHECK_GT(denominator, int64{0});
83  if (!WillProductOverflow(numerator_1, numerator_2)) {
84  const int64 numerator = numerator_1 * numerator_2;
85  // Round to zero.
86  const int64 result = numerator / denominator;
87  return result;
88  } else {
89  const double ratio =
90  (static_cast<double>(numerator_1) * static_cast<double>(numerator_2)) /
91  static_cast<double>(denominator);
92  // Round near.
93  const int64 result = static_cast<int64>(floor(ratio + 0.5));
94  return result;
95  }
96 }
97 
98 } // namespace
99 
100 // ----- KnapsackSearchNode -----
102  const KnapsackAssignment& assignment)
103  : depth_((parent == nullptr) ? 0 : parent->depth() + 1),
104  parent_(parent),
105  assignment_(assignment),
106  current_profit_(0),
107  profit_upper_bound_(kint64max),
108  next_item_id_(kNoSelection) {}
109 
110 // ----- KnapsackSearchPath -----
112  const KnapsackSearchNode& to)
113  : from_(from), via_(nullptr), to_(to) {}
114 
116  const KnapsackSearchNode* node_from = MoveUpToDepth(from_, to_.depth());
117  const KnapsackSearchNode* node_to = MoveUpToDepth(to_, from_.depth());
118  CHECK_EQ(node_from->depth(), node_to->depth());
119 
120  // Find common parent.
121  while (node_from != node_to) {
122  node_from = node_from->parent();
123  node_to = node_to->parent();
124  }
125  via_ = node_from;
126 }
127 
129  const KnapsackSearchNode& node, int depth) const {
130  const KnapsackSearchNode* current_node = &node;
131  while (current_node->depth() > depth) {
132  current_node = current_node->parent();
133  }
134  return current_node;
135 }
136 
137 // ----- KnapsackState -----
138 KnapsackState::KnapsackState() : is_bound_(), is_in_() {}
139 
140 void KnapsackState::Init(int number_of_items) {
141  is_bound_.assign(number_of_items, false);
142  is_in_.assign(number_of_items, false);
143 }
144 
145 // Returns false when the state is invalid.
146 bool KnapsackState::UpdateState(bool revert,
147  const KnapsackAssignment& assignment) {
148  if (revert) {
149  is_bound_[assignment.item_id] = false;
150  } else {
151  if (is_bound_[assignment.item_id] &&
152  is_in_[assignment.item_id] != assignment.is_in) {
153  return false;
154  }
155  is_bound_[assignment.item_id] = true;
156  is_in_[assignment.item_id] = assignment.is_in;
157  }
158  return true;
159 }
160 
161 // ----- KnapsackPropagator -----
163  : items_(),
164  current_profit_(0),
165  profit_lower_bound_(0),
166  profit_upper_bound_(kint64max),
167  state_(state) {}
168 
170 
171 void KnapsackPropagator::Init(const std::vector<int64>& profits,
172  const std::vector<int64>& weights) {
173  const int number_of_items = profits.size();
174  items_.assign(number_of_items, static_cast<KnapsackItemPtr>(nullptr));
175  for (int i = 0; i < number_of_items; ++i) {
176  items_[i] = new KnapsackItem(i, weights[i], profits[i]);
177  }
178  current_profit_ = 0;
179  profit_lower_bound_ = kint64min;
180  profit_upper_bound_ = kint64max;
181  InitPropagator();
182 }
183 
184 bool KnapsackPropagator::Update(bool revert,
185  const KnapsackAssignment& assignment) {
186  if (assignment.is_in) {
187  if (revert) {
188  current_profit_ -= items_[assignment.item_id]->profit;
189  } else {
190  current_profit_ += items_[assignment.item_id]->profit;
191  }
192  }
193  return UpdatePropagator(revert, assignment);
194 }
195 
197  bool has_one_propagator, std::vector<bool>* solution) const {
198  CHECK(solution != nullptr);
199  for (const KnapsackItem* const item : items_) {
200  const int item_id = item->id;
201  (*solution)[item_id] = state_.is_bound(item_id) && state_.is_in(item_id);
202  }
203  if (has_one_propagator) {
205  }
206 }
207 
208 // ----- KnapsackCapacityPropagator -----
210  const KnapsackState& state, int64 capacity)
211  : KnapsackPropagator(state),
212  capacity_(capacity),
213  consumed_capacity_(0),
214  break_item_id_(kNoSelection),
215  sorted_items_(),
216  profit_max_(0) {}
217 
219 
220 // TODO(user): Make it more incremental, by saving the break item in a
221 // search node for instance.
224  break_item_id_ = kNoSelection;
225 
226  int64 remaining_capacity = capacity_ - consumed_capacity_;
227  int break_sorted_item_id = kNoSelection;
228  const int number_of_sorted_items = sorted_items_.size();
229  for (int sorted_id = 0; sorted_id < number_of_sorted_items; ++sorted_id) {
230  const KnapsackItem* const item = sorted_items_[sorted_id];
231  if (!state().is_bound(item->id)) {
232  break_item_id_ = item->id;
233 
234  if (remaining_capacity >= item->weight) {
235  remaining_capacity -= item->weight;
237  } else {
238  break_sorted_item_id = sorted_id;
239  break;
240  }
241  }
242  }
243 
245 
246  if (break_sorted_item_id != kNoSelection) {
247  const int64 additional_profit =
248  GetAdditionalProfit(remaining_capacity, break_sorted_item_id);
249  set_profit_upper_bound(profit_upper_bound() + additional_profit);
250  }
251 }
252 
254  consumed_capacity_ = 0;
255  break_item_id_ = kNoSelection;
256  sorted_items_ = items();
257  profit_max_ = 0;
258  for (const KnapsackItem* const item : sorted_items_) {
259  profit_max_ = std::max(profit_max_, item->profit);
260  }
261  ++profit_max_;
262  CompareKnapsackItemsInDecreasingEfficiencyOrder compare_object(profit_max_);
263  std::sort(sorted_items_.begin(), sorted_items_.end(), compare_object);
264 }
265 
266 // Returns false when the propagator fails.
268  bool revert, const KnapsackAssignment& assignment) {
269  if (assignment.is_in) {
270  if (revert) {
271  consumed_capacity_ -= items()[assignment.item_id]->weight;
272  } else {
273  consumed_capacity_ += items()[assignment.item_id]->weight;
274  if (consumed_capacity_ > capacity_) {
275  return false;
276  }
277  }
278  }
279  return true;
280 }
281 
283  std::vector<bool>* solution) const {
284  CHECK(solution != nullptr);
285  int64 remaining_capacity = capacity_ - consumed_capacity_;
286  for (const KnapsackItem* const item : sorted_items_) {
287  if (!state().is_bound(item->id)) {
288  if (remaining_capacity >= item->weight) {
289  remaining_capacity -= item->weight;
290  (*solution)[item->id] = true;
291  } else {
292  return;
293  }
294  }
295  }
296 }
297 
298 int64 KnapsackCapacityPropagator::GetAdditionalProfit(int64 remaining_capacity,
299  int break_item_id) const {
300  const int after_break_item_id = break_item_id + 1;
301  int64 additional_profit_when_no_break_item = 0;
302  if (after_break_item_id < sorted_items_.size()) {
303  // As items are sorted by decreasing profit / weight ratio, and the current
304  // weight is non-zero, the next_weight is non-zero too.
305  const int64 next_weight = sorted_items_[after_break_item_id]->weight;
306  const int64 next_profit = sorted_items_[after_break_item_id]->profit;
307  additional_profit_when_no_break_item =
308  UpperBoundOfRatio(remaining_capacity, next_profit, next_weight);
309  }
310 
311  const int before_break_item_id = break_item_id - 1;
312  int64 additional_profit_when_break_item = 0;
313  if (before_break_item_id >= 0) {
314  const int64 previous_weight = sorted_items_[before_break_item_id]->weight;
315  // Having previous_weight == 0 means the total capacity is smaller than
316  // the weight of the current item. In such a case the item cannot be part
317  // of a solution of the local one dimension problem.
318  if (previous_weight != 0) {
319  const int64 previous_profit = sorted_items_[before_break_item_id]->profit;
320  const int64 overused_capacity =
321  sorted_items_[break_item_id]->weight - remaining_capacity;
322  const int64 ratio = UpperBoundOfRatio(overused_capacity, previous_profit,
323  previous_weight);
324  additional_profit_when_break_item =
325  sorted_items_[break_item_id]->profit - ratio;
326  }
327  }
328 
329  const int64 additional_profit = std::max(additional_profit_when_no_break_item,
330  additional_profit_when_break_item);
331  CHECK_GE(additional_profit, 0);
332  return additional_profit;
333 }
334 
335 // ----- KnapsackGenericSolver -----
336 KnapsackGenericSolver::KnapsackGenericSolver(const std::string& solver_name)
337  : BaseKnapsackSolver(solver_name),
338  propagators_(),
339  master_propagator_id_(kMasterPropagatorId),
340  search_nodes_(),
341  state_(),
342  best_solution_profit_(0),
343  best_solution_() {}
344 
346 
347 void KnapsackGenericSolver::Init(const std::vector<int64>& profits,
348  const std::vector<std::vector<int64>>& weights,
349  const std::vector<int64>& capacities) {
350  CHECK_EQ(capacities.size(), weights.size());
351 
352  Clear();
353  const int number_of_items = profits.size();
354  const int number_of_dimensions = weights.size();
355  state_.Init(number_of_items);
356  best_solution_.assign(number_of_items, false);
357  for (int i = 0; i < number_of_dimensions; ++i) {
358  CHECK_EQ(number_of_items, weights[i].size());
359 
360  KnapsackCapacityPropagator* propagator =
361  new KnapsackCapacityPropagator(state_, capacities[i]);
362  propagator->Init(profits, weights[i]);
363  propagators_.push_back(propagator);
364  }
365  master_propagator_id_ = kMasterPropagatorId;
366 }
367 
369  bool is_item_in,
370  int64* lower_bound,
371  int64* upper_bound) {
372  CHECK(lower_bound != nullptr);
373  CHECK(upper_bound != nullptr);
374  KnapsackAssignment assignment(item_id, is_item_in);
375  const bool fail = !IncrementalUpdate(false, assignment);
376  if (fail) {
377  *lower_bound = 0LL;
378  *upper_bound = 0LL;
379  } else {
380  *lower_bound =
381  (HasOnePropagator())
382  ? propagators_[master_propagator_id_]->profit_lower_bound()
383  : 0LL;
384  *upper_bound = GetAggregatedProfitUpperBound();
385  }
386 
387  const bool fail_revert = !IncrementalUpdate(true, assignment);
388  if (fail_revert) {
389  *lower_bound = 0LL;
390  *upper_bound = 0LL;
391  }
392 }
393 
395  bool* is_solution_optimal) {
396  DCHECK(time_limit != nullptr);
397  DCHECK(is_solution_optimal != nullptr);
398  best_solution_profit_ = 0LL;
399  *is_solution_optimal = true;
400 
401  SearchQueue search_queue;
402  const KnapsackAssignment assignment(kNoSelection, true);
403  KnapsackSearchNode* root_node = new KnapsackSearchNode(nullptr, assignment);
404  root_node->set_current_profit(GetCurrentProfit());
405  root_node->set_profit_upper_bound(GetAggregatedProfitUpperBound());
406  root_node->set_next_item_id(GetNextItemId());
407  search_nodes_.push_back(root_node);
408 
409  if (MakeNewNode(*root_node, false)) {
410  search_queue.push(search_nodes_.back());
411  }
412  if (MakeNewNode(*root_node, true)) {
413  search_queue.push(search_nodes_.back());
414  }
415 
416  KnapsackSearchNode* current_node = root_node;
417  while (!search_queue.empty() &&
418  search_queue.top()->profit_upper_bound() > best_solution_profit_) {
419  if (time_limit->LimitReached()) {
420  *is_solution_optimal = false;
421  break;
422  }
423  KnapsackSearchNode* const node = search_queue.top();
424  search_queue.pop();
425 
426  if (node != current_node) {
427  KnapsackSearchPath path(*current_node, *node);
428  path.Init();
429  const bool no_fail = UpdatePropagators(path);
430  current_node = node;
431  CHECK_EQ(no_fail, true);
432  }
433 
434  if (MakeNewNode(*node, false)) {
435  search_queue.push(search_nodes_.back());
436  }
437  if (MakeNewNode(*node, true)) {
438  search_queue.push(search_nodes_.back());
439  }
440  }
441  return best_solution_profit_;
442 }
443 
444 void KnapsackGenericSolver::Clear() {
445  gtl::STLDeleteElements(&propagators_);
446  gtl::STLDeleteElements(&search_nodes_);
447 }
448 
449 // Returns false when at least one propagator fails.
450 bool KnapsackGenericSolver::UpdatePropagators(const KnapsackSearchPath& path) {
451  bool no_fail = true;
452  // Revert previous changes.
453  const KnapsackSearchNode* node = &path.from();
454  const KnapsackSearchNode* via = &path.via();
455  while (node != via) {
456  no_fail = IncrementalUpdate(true, node->assignment()) && no_fail;
457  node = node->parent();
458  }
459  // Apply current changes.
460  node = &path.to();
461  while (node != via) {
462  no_fail = IncrementalUpdate(false, node->assignment()) && no_fail;
463  node = node->parent();
464  }
465  return no_fail;
466 }
467 
468 int64 KnapsackGenericSolver::GetAggregatedProfitUpperBound() const {
469  int64 upper_bound = kint64max;
470  for (KnapsackPropagator* const prop : propagators_) {
471  prop->ComputeProfitBounds();
472  const int64 propagator_upper_bound = prop->profit_upper_bound();
473  upper_bound = std::min(upper_bound, propagator_upper_bound);
474  }
475  return upper_bound;
476 }
477 
478 bool KnapsackGenericSolver::MakeNewNode(const KnapsackSearchNode& node,
479  bool is_in) {
480  if (node.next_item_id() == kNoSelection) {
481  return false;
482  }
483  KnapsackAssignment assignment(node.next_item_id(), is_in);
484  KnapsackSearchNode new_node(&node, assignment);
485 
486  KnapsackSearchPath path(node, new_node);
487  path.Init();
488  const bool no_fail = UpdatePropagators(path);
489  if (no_fail) {
490  new_node.set_current_profit(GetCurrentProfit());
491  new_node.set_profit_upper_bound(GetAggregatedProfitUpperBound());
492  new_node.set_next_item_id(GetNextItemId());
493  UpdateBestSolution();
494  }
495 
496  // Revert to be able to create another node from parent.
497  KnapsackSearchPath revert_path(new_node, node);
498  revert_path.Init();
499  UpdatePropagators(revert_path);
500 
501  if (!no_fail || new_node.profit_upper_bound() < best_solution_profit_) {
502  return false;
503  }
504 
505  // The node is relevant.
506  KnapsackSearchNode* relevant_node = new KnapsackSearchNode(&node, assignment);
507  relevant_node->set_current_profit(new_node.current_profit());
508  relevant_node->set_profit_upper_bound(new_node.profit_upper_bound());
509  relevant_node->set_next_item_id(new_node.next_item_id());
510  search_nodes_.push_back(relevant_node);
511 
512  return true;
513 }
514 
515 bool KnapsackGenericSolver::IncrementalUpdate(
516  bool revert, const KnapsackAssignment& assignment) {
517  // Do not stop on a failure: To be able to be incremental on the update,
518  // partial solution (state) and propagators must all be in the same state.
519  bool no_fail = state_.UpdateState(revert, assignment);
520  for (KnapsackPropagator* const prop : propagators_) {
521  no_fail = prop->Update(revert, assignment) && no_fail;
522  }
523  return no_fail;
524 }
525 
526 void KnapsackGenericSolver::UpdateBestSolution() {
527  const int64 profit_lower_bound =
528  (HasOnePropagator())
529  ? propagators_[master_propagator_id_]->profit_lower_bound()
530  : propagators_[master_propagator_id_]->current_profit();
531 
532  if (best_solution_profit_ < profit_lower_bound) {
533  best_solution_profit_ = profit_lower_bound;
534  propagators_[master_propagator_id_]->CopyCurrentStateToSolution(
535  HasOnePropagator(), &best_solution_);
536  }
537 }
538 
539 // ----- KnapsackBruteForceSolver -----
540 // KnapsackBruteForceSolver solves the 0-1 knapsack problem when the number of
541 // items is less or equal to 30 with brute force, ie. explores all states.
542 // Experiments show better results than KnapsackGenericSolver when the
543 // number of items is less than 15.
545  public:
546  explicit KnapsackBruteForceSolver(const std::string& solver_name);
547 
548  // Initializes the solver and enters the problem to be solved.
549  void Init(const std::vector<int64>& profits,
550  const std::vector<std::vector<int64>>& weights,
551  const std::vector<int64>& capacities) override;
552 
553  // Solves the problem and returns the profit of the optimal solution.
554  int64 Solve(TimeLimit* time_limit, bool* is_solution_optimal) override;
555 
556  // Returns true if the item 'item_id' is packed in the optimal knapsack.
557  bool best_solution(int item_id) const override {
558  return (best_solution_ & OneBit32(item_id)) != 0U;
559  }
560 
561  private:
562  int num_items_;
563  int64 profits_weights_[kMaxNumberOfBruteForceItems * 2];
564  int64 capacity_;
565  int64 best_solution_profit_;
566  uint32 best_solution_;
567 
568  DISALLOW_COPY_AND_ASSIGN(KnapsackBruteForceSolver);
569 };
570 
572  const std::string& solver_name)
573  : BaseKnapsackSolver(solver_name),
574  num_items_(0),
575  capacity_(0LL),
576  best_solution_profit_(0LL),
577  best_solution_(0U) {}
578 
580  const std::vector<int64>& profits,
581  const std::vector<std::vector<int64>>& weights,
582  const std::vector<int64>& capacities) {
583  // TODO(user): Implement multi-dimensional brute force solver.
584  CHECK_EQ(weights.size(), 1)
585  << "Brute force solver only works with one dimension.";
586  CHECK_EQ(capacities.size(), weights.size());
587 
588  num_items_ = profits.size();
589  CHECK_EQ(num_items_, weights.at(0).size());
590  CHECK_LE(num_items_, kMaxNumberOfBruteForceItems)
591  << "To use KnapsackBruteForceSolver the number of items should be "
592  << "less than " << kMaxNumberOfBruteForceItems
593  << ". Current value: " << num_items_ << ".";
594 
595  for (int i = 0; i < num_items_; ++i) {
596  profits_weights_[i * 2] = profits.at(i);
597  profits_weights_[i * 2 + 1] = weights.at(0).at(i);
598  }
599  capacity_ = capacities.at(0);
600 }
601 
603  bool* is_solution_optimal) {
604  DCHECK(is_solution_optimal != nullptr);
605  *is_solution_optimal = true;
606  best_solution_profit_ = 0LL;
607  best_solution_ = 0U;
608 
609  const uint32 num_states = OneBit32(num_items_);
610  uint32 prev_state = 0U;
611  uint64 sum_profit = 0ULL;
612  uint64 sum_weight = 0ULL;
613  uint32 diff_state = 0U;
614  uint32 local_state = 0U;
615  int item_id = 0;
616  // This loop starts at 1, because state = 0 was already considered previously,
617  // ie. when no items are in, sum_profit = 0.
618  for (uint32 state = 1U; state < num_states; ++state, ++prev_state) {
619  diff_state = state ^ prev_state;
620  local_state = state;
621  item_id = 0;
622  while (diff_state) {
623  if (diff_state & 1U) { // There is a diff.
624  if (local_state & 1U) { // This item is now in the knapsack.
625  sum_profit += profits_weights_[item_id];
626  sum_weight += profits_weights_[item_id + 1];
627  CHECK_LT(item_id + 1, 2 * num_items_);
628  } else { // This item has been removed of the knapsack.
629  sum_profit -= profits_weights_[item_id];
630  sum_weight -= profits_weights_[item_id + 1];
631  CHECK_LT(item_id + 1, 2 * num_items_);
632  }
633  }
634  item_id += 2;
635  local_state = local_state >> 1;
636  diff_state = diff_state >> 1;
637  }
638 
639  if (sum_weight <= capacity_ && best_solution_profit_ < sum_profit) {
640  best_solution_profit_ = sum_profit;
641  best_solution_ = state;
642  }
643  }
644 
645  return best_solution_profit_;
646 }
647 
648 // ----- KnapsackItemWithEfficiency -----
649 // KnapsackItem is a small struct to pair an item weight with its
650 // corresponding profit.
651 // This struct is used by Knapsack64ItemsSolver. As this solver deals only
652 // with one dimension, that's more efficient to store 'efficiency' than
653 // computing it on the fly.
655  KnapsackItemWithEfficiency(int _id, int64 _profit, int64 _weight,
656  int64 _profit_max)
657  : id(_id),
658  profit(_profit),
659  weight(_weight),
660  efficiency((weight > 0) ? static_cast<double>(_profit) /
661  static_cast<double>(_weight)
662  : static_cast<double>(_profit_max)) {}
663 
664  int id;
667  double efficiency;
668 };
669 
670 // ----- Knapsack64ItemsSolver -----
671 // Knapsack64ItemsSolver solves the 0-1 knapsack problem when the number of
672 // items is less or equal to 64. This implementation is about 4 times faster
673 // than KnapsackGenericSolver.
675  public:
676  explicit Knapsack64ItemsSolver(const std::string& solver_name);
677 
678  // Initializes the solver and enters the problem to be solved.
679  void Init(const std::vector<int64>& profits,
680  const std::vector<std::vector<int64>>& weights,
681  const std::vector<int64>& capacities) override;
682 
683  // Solves the problem and returns the profit of the optimal solution.
684  int64 Solve(TimeLimit* time_limit, bool* is_solution_optimal) override;
685 
686  // Returns true if the item 'item_id' is packed in the optimal knapsack.
687  bool best_solution(int item_id) const override {
688  return (best_solution_ & OneBit64(item_id)) != 0ULL;
689  }
690 
691  private:
692  int GetBreakItemId(int64 capacity) const;
693  void GetLowerAndUpperBound(int64* lower_bound, int64* upper_bound) const;
694  void GoToNextState(bool has_failed);
695  void BuildBestSolution();
696 
697  std::vector<KnapsackItemWithEfficiency> sorted_items_;
698  std::vector<int64> sum_profits_;
699  std::vector<int64> sum_weights_;
700  int64 capacity_;
701  uint64 state_;
702  int state_depth_;
703 
704  int64 best_solution_profit_;
705  uint64 best_solution_;
706  int best_solution_depth_;
707 
708  // Sum of weights of included item in state.
709  int64 state_weight_;
710  // Sum of profits of non included items in state.
711  int64 rejected_items_profit_;
712  // Sum of weights of non included items in state.
713  int64 rejected_items_weight_;
714 };
715 
716 // Comparator used to sort item in decreasing efficiency order
718  const KnapsackItemWithEfficiency& item1,
719  const KnapsackItemWithEfficiency& item2) {
720  return item1.efficiency > item2.efficiency;
721 }
722 
723 // ----- Knapsack64ItemsSolver -----
724 Knapsack64ItemsSolver::Knapsack64ItemsSolver(const std::string& solver_name)
725  : BaseKnapsackSolver(solver_name),
726  sorted_items_(),
727  sum_profits_(),
728  sum_weights_(),
729  capacity_(0LL),
730  state_(0ULL),
731  state_depth_(0),
732  best_solution_profit_(0LL),
733  best_solution_(0ULL),
734  best_solution_depth_(0),
735  state_weight_(0LL),
736  rejected_items_profit_(0LL),
737  rejected_items_weight_(0LL) {}
738 
739 void Knapsack64ItemsSolver::Init(const std::vector<int64>& profits,
740  const std::vector<std::vector<int64>>& weights,
741  const std::vector<int64>& capacities) {
742  CHECK_EQ(weights.size(), 1)
743  << "Brute force solver only works with one dimension.";
744  CHECK_EQ(capacities.size(), weights.size());
745 
746  sorted_items_.clear();
747  sum_profits_.clear();
748  sum_weights_.clear();
749 
750  capacity_ = capacities[0];
751  const int num_items = profits.size();
752  CHECK_LE(num_items, kMaxNumberOf64Items)
753  << "To use Knapsack64ItemsSolver the number of items should be "
754  << "less than " << kMaxNumberOf64Items << ". Current value: " << num_items
755  << ".";
756  int64 profit_max = *std::max_element(profits.begin(), profits.end());
757 
758  for (int i = 0; i < num_items; ++i) {
759  sorted_items_.push_back(
760  KnapsackItemWithEfficiency(i, profits[i], weights[0][i], profit_max));
761  }
762 
763  std::sort(sorted_items_.begin(), sorted_items_.end(),
765 
766  int64 sum_profit = 0;
767  int64 sum_weight = 0;
768  sum_profits_.push_back(sum_profit);
769  sum_weights_.push_back(sum_weight);
770  for (int i = 0; i < num_items; ++i) {
771  sum_profit += sorted_items_[i].profit;
772  sum_weight += sorted_items_[i].weight;
773 
774  sum_profits_.push_back(sum_profit);
775  sum_weights_.push_back(sum_weight);
776  }
777 }
778 
780  bool* is_solution_optimal) {
781  DCHECK(is_solution_optimal != nullptr);
782  *is_solution_optimal = true;
783  const int num_items = sorted_items_.size();
784  state_ = 1ULL;
785  state_depth_ = 0;
786  state_weight_ = sorted_items_[0].weight;
787  rejected_items_profit_ = 0LL;
788  rejected_items_weight_ = 0LL;
789  best_solution_profit_ = 0LL;
790  best_solution_ = 0ULL;
791  best_solution_depth_ = 0;
792 
793  int64 lower_bound = 0LL;
794  int64 upper_bound = 0LL;
795  bool fail = false;
796  while (state_depth_ >= 0) {
797  fail = false;
798  if (state_weight_ > capacity_ || state_depth_ >= num_items) {
799  fail = true;
800  } else {
801  GetLowerAndUpperBound(&lower_bound, &upper_bound);
802  if (best_solution_profit_ < lower_bound) {
803  best_solution_profit_ = lower_bound;
804  best_solution_ = state_;
805  best_solution_depth_ = state_depth_;
806  }
807  }
808  fail = fail || best_solution_profit_ >= upper_bound;
809  GoToNextState(fail);
810  }
811 
812  BuildBestSolution();
813  return best_solution_profit_;
814 }
815 
816 int Knapsack64ItemsSolver::GetBreakItemId(int64 capacity) const {
817  std::vector<int64>::const_iterator binary_search_iterator =
818  std::upper_bound(sum_weights_.begin(), sum_weights_.end(), capacity);
819  return static_cast<int>(binary_search_iterator - sum_weights_.begin()) - 1;
820 }
821 
822 // This method is called for each possible state.
823 // Lower and upper bounds can be equal from one state to another.
824 // For instance state 1010???? and state 101011?? have exactly the same
825 // bounds. So it sounds like a good idea to cache those bounds.
826 // Unfortunately, experiments show equivalent results with or without this
827 // code optimization (only 1/7 of calls can be reused).
828 // In order to simplify the code, this optimization is not implemented.
829 void Knapsack64ItemsSolver::GetLowerAndUpperBound(int64* lower_bound,
830  int64* upper_bound) const {
831  const int64 available_capacity = capacity_ + rejected_items_weight_;
832  const int break_item_id = GetBreakItemId(available_capacity);
833  const int num_items = sorted_items_.size();
834  if (break_item_id >= num_items) {
835  *lower_bound = sum_profits_[num_items] - rejected_items_profit_;
836  *upper_bound = *lower_bound;
837  return;
838  }
839 
840  *lower_bound = sum_profits_[break_item_id] - rejected_items_profit_;
841  *upper_bound = *lower_bound;
842  const int64 consumed_capacity = sum_weights_[break_item_id];
843  const int64 remaining_capacity = available_capacity - consumed_capacity;
844  const double efficiency = sorted_items_[break_item_id].efficiency;
845  const int64 additional_profit =
846  static_cast<int64>(remaining_capacity * efficiency);
847  *upper_bound += additional_profit;
848 }
849 
850 // As state_depth_ is the position of the most significant bit on state_
851 // it is possible to remove the loop and so be in O(1) instead of O(depth).
852 // In such a case rejected_items_profit_ is computed using sum_profits_ array.
853 // Unfortunately experiments show smaller computation time using the 'while'
854 // (10% speed-up). That's the reason why the loop version is implemented.
855 void Knapsack64ItemsSolver::GoToNextState(bool has_failed) {
856  uint64 mask = OneBit64(state_depth_);
857  if (!has_failed) { // Go to next item.
858  ++state_depth_;
859  state_ = state_ | (mask << 1);
860  state_weight_ += sorted_items_[state_depth_].weight;
861  } else {
862  // Backtrack to last item in.
863  while ((state_ & mask) == 0ULL && state_depth_ >= 0) {
864  const KnapsackItemWithEfficiency& item = sorted_items_[state_depth_];
865  rejected_items_profit_ -= item.profit;
866  rejected_items_weight_ -= item.weight;
867  --state_depth_;
868  mask = mask >> 1ULL;
869  }
870 
871  if (state_ & mask) { // Item was in, remove it.
872  state_ = state_ & ~mask;
873  const KnapsackItemWithEfficiency& item = sorted_items_[state_depth_];
874  rejected_items_profit_ += item.profit;
875  rejected_items_weight_ += item.weight;
876  state_weight_ -= item.weight;
877  }
878  }
879 }
880 
881 void Knapsack64ItemsSolver::BuildBestSolution() {
882  int64 remaining_capacity = capacity_;
883  int64 check_profit = 0LL;
884 
885  // Compute remaining capacity at best_solution_depth_ to be able to redo
886  // the GetLowerAndUpperBound computation.
887  for (int i = 0; i <= best_solution_depth_; ++i) {
888  if (best_solution_ & OneBit64(i)) {
889  remaining_capacity -= sorted_items_[i].weight;
890  check_profit += sorted_items_[i].profit;
891  }
892  }
893 
894  // Add all items till the break item.
895  const int num_items = sorted_items_.size();
896  for (int i = best_solution_depth_ + 1; i < num_items; ++i) {
897  int64 weight = sorted_items_[i].weight;
898  if (remaining_capacity >= weight) {
899  remaining_capacity -= weight;
900  check_profit += sorted_items_[i].profit;
901  best_solution_ = best_solution_ | OneBit64(i);
902  } else {
903  best_solution_ = best_solution_ & ~OneBit64(i);
904  }
905  }
906  CHECK_EQ(best_solution_profit_, check_profit);
907 
908  // Items were sorted by efficiency, solution should be unsorted to be
909  // in user order.
910  // Note that best_solution_ will not be in the same order than other data
911  // structures anymore.
912  uint64 tmp_solution = 0ULL;
913  for (int i = 0; i < num_items; ++i) {
914  if (best_solution_ & OneBit64(i)) {
915  const int original_id = sorted_items_[i].id;
916  tmp_solution = tmp_solution | OneBit64(original_id);
917  }
918  }
919 
920  best_solution_ = tmp_solution;
921 }
922 
923 // ----- KnapsackDynamicProgrammingSolver -----
924 // KnapsackDynamicProgrammingSolver solves the 0-1 knapsack problem
925 // using dynamic programming. This algorithm is pseudo-polynomial because it
926 // depends on capacity, ie. the time and space complexity is
927 // O(capacity * number_of_items).
928 // The implemented algorithm is 'DP-3' in "Knapsack problems", Hans Kellerer,
929 // Ulrich Pferschy and David Pisinger, Springer book (ISBN 978-3540402862).
931  public:
932  explicit KnapsackDynamicProgrammingSolver(const std::string& solver_name);
933 
934  // Initializes the solver and enters the problem to be solved.
935  void Init(const std::vector<int64>& profits,
936  const std::vector<std::vector<int64>>& weights,
937  const std::vector<int64>& capacities) override;
938 
939  // Solves the problem and returns the profit of the optimal solution.
940  int64 Solve(TimeLimit* time_limit, bool* is_solution_optimal) override;
941 
942  // Returns true if the item 'item_id' is packed in the optimal knapsack.
943  bool best_solution(int item_id) const override {
944  return best_solution_.at(item_id);
945  }
946 
947  private:
948  int64 SolveSubProblem(int64 capacity, int num_items);
949 
950  std::vector<int64> profits_;
951  std::vector<int64> weights_;
952  int64 capacity_;
953  std::vector<int64> computed_profits_;
954  std::vector<int> selected_item_ids_;
955  std::vector<bool> best_solution_;
956 };
957 
958 // ----- KnapsackDynamicProgrammingSolver -----
960  const std::string& solver_name)
961  : BaseKnapsackSolver(solver_name),
962  profits_(),
963  weights_(),
964  capacity_(0),
965  computed_profits_(),
966  selected_item_ids_(),
967  best_solution_() {}
968 
970  const std::vector<int64>& profits,
971  const std::vector<std::vector<int64>>& weights,
972  const std::vector<int64>& capacities) {
973  CHECK_EQ(weights.size(), 1)
974  << "Current implementation of the dynamic programming solver only deals"
975  << " with one dimension.";
976  CHECK_EQ(capacities.size(), weights.size());
977 
978  profits_ = profits;
979  weights_ = weights[0];
980  capacity_ = capacities[0];
981 }
982 
983 int64 KnapsackDynamicProgrammingSolver::SolveSubProblem(int64 capacity,
984  int num_items) {
985  const int64 capacity_plus_1 = capacity + 1;
986  std::fill_n(selected_item_ids_.begin(), capacity_plus_1, 0);
987  std::fill_n(computed_profits_.begin(), capacity_plus_1, int64{0});
988  for (int item_id = 0; item_id < num_items; ++item_id) {
989  const int64 item_weight = weights_[item_id];
990  const int64 item_profit = profits_[item_id];
991  for (int64 used_capacity = capacity; used_capacity >= item_weight;
992  --used_capacity) {
993  if (computed_profits_[used_capacity - item_weight] + item_profit >
994  computed_profits_[used_capacity]) {
995  computed_profits_[used_capacity] =
996  computed_profits_[used_capacity - item_weight] + item_profit;
997  selected_item_ids_[used_capacity] = item_id;
998  }
999  }
1000  }
1001  return selected_item_ids_.at(capacity);
1002 }
1003 
1005  bool* is_solution_optimal) {
1006  DCHECK(is_solution_optimal != nullptr);
1007  *is_solution_optimal = true;
1008  const int64 capacity_plus_1 = capacity_ + 1;
1009  selected_item_ids_.assign(capacity_plus_1, 0);
1010  computed_profits_.assign(capacity_plus_1, 0LL);
1011 
1012  int64 remaining_capacity = capacity_;
1013  int num_items = profits_.size();
1014  best_solution_.assign(num_items, false);
1015 
1016  while (remaining_capacity > 0 && num_items > 0) {
1017  const int selected_item_id = SolveSubProblem(remaining_capacity, num_items);
1018  remaining_capacity -= weights_[selected_item_id];
1019  num_items = selected_item_id;
1020  if (remaining_capacity >= 0) {
1021  best_solution_[selected_item_id] = true;
1022  }
1023  }
1024 
1025  return computed_profits_[capacity_];
1026 }
1027 
1028 // ----- KnapsackMIPSolver -----
1030  public:
1032  const std::string& solver_name);
1033 
1034  // Initializes the solver and enters the problem to be solved.
1035  void Init(const std::vector<int64>& profits,
1036  const std::vector<std::vector<int64>>& weights,
1037  const std::vector<int64>& capacities) override;
1038 
1039  // Solves the problem and returns the profit of the optimal solution.
1040  int64 Solve(TimeLimit* time_limit, bool* is_solution_optimal) override;
1041 
1042  // Returns true if the item 'item_id' is packed in the optimal knapsack.
1043  bool best_solution(int item_id) const override {
1044  return best_solution_.at(item_id);
1045  }
1046 
1047  private:
1048  MPSolver::OptimizationProblemType problem_type_;
1049  std::vector<int64> profits_;
1050  std::vector<std::vector<int64>> weights_;
1051  std::vector<int64> capacities_;
1052  std::vector<bool> best_solution_;
1053 };
1054 
1057  const std::string& solver_name)
1058  : BaseKnapsackSolver(solver_name),
1059  problem_type_(problem_type),
1060  profits_(),
1061  weights_(),
1062  capacities_(),
1063  best_solution_() {}
1064 
1065 void KnapsackMIPSolver::Init(const std::vector<int64>& profits,
1066  const std::vector<std::vector<int64>>& weights,
1067  const std::vector<int64>& capacities) {
1068  profits_ = profits;
1069  weights_ = weights;
1070  capacities_ = capacities;
1071 }
1072 
1074  bool* is_solution_optimal) {
1075  DCHECK(is_solution_optimal != nullptr);
1076  *is_solution_optimal = true;
1077  MPSolver solver(GetName(), problem_type_);
1078 
1079  const int num_items = profits_.size();
1080  std::vector<MPVariable*> variables;
1081  solver.MakeBoolVarArray(num_items, "x", &variables);
1082 
1083  // Add constraints.
1084  const int num_dimensions = capacities_.size();
1085  CHECK(weights_.size() == num_dimensions)
1086  << "Weights should be vector of num_dimensions (" << num_dimensions
1087  << ") vectors of size num_items (" << num_items << ").";
1088  for (int i = 0; i < num_dimensions; ++i) {
1089  MPConstraint* const ct = solver.MakeRowConstraint(0LL, capacities_.at(i));
1090  for (int j = 0; j < num_items; ++j) {
1091  ct->SetCoefficient(variables.at(j), weights_.at(i).at(j));
1092  }
1093  }
1094 
1095  // Define objective to minimize. Minimization is used instead of maximization
1096  // because of an issue with CBC solver which does not always find the optimal
1097  // solution on maximization problems.
1098  MPObjective* const objective = solver.MutableObjective();
1099  for (int j = 0; j < num_items; ++j) {
1100  objective->SetCoefficient(variables.at(j), -profits_.at(j));
1101  }
1102  objective->SetMinimization();
1103 
1104  solver.SuppressOutput();
1105  solver.Solve();
1106 
1107  // Store best solution.
1108  const float kRoundNear = 0.5;
1109  best_solution_.assign(num_items, false);
1110  for (int j = 0; j < num_items; ++j) {
1111  const double value = variables.at(j)->solution_value();
1112  best_solution_.at(j) = value >= kRoundNear;
1113  }
1114 
1115  return -objective->Value() + kRoundNear;
1116 }
1117 
1118 // ----- KnapsackSolver -----
1119 KnapsackSolver::KnapsackSolver(const std::string& solver_name)
1120  : KnapsackSolver(KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
1121  solver_name) {}
1122 
1124  const std::string& solver_name)
1125  : solver_(),
1126  known_value_(),
1127  best_solution_(),
1128  mapping_reduced_item_id_(),
1129  is_problem_solved_(false),
1130  additional_profit_(0LL),
1131  use_reduction_(true),
1132  time_limit_seconds_(std::numeric_limits<double>::infinity()) {
1133  switch (solver_type) {
1135  solver_ = absl::make_unique<KnapsackBruteForceSolver>(solver_name);
1136  break;
1138  solver_ = absl::make_unique<Knapsack64ItemsSolver>(solver_name);
1139  break;
1141  solver_ =
1142  absl::make_unique<KnapsackDynamicProgrammingSolver>(solver_name);
1143  break;
1145  solver_ = absl::make_unique<KnapsackGenericSolver>(solver_name);
1146  break;
1147 #if defined(USE_CBC)
1149  solver_ = absl::make_unique<KnapsackMIPSolver>(
1151  break;
1152 #endif // USE_CBC
1153 #if defined(USE_SCIP)
1155  solver_ = absl::make_unique<KnapsackMIPSolver>(
1157  break;
1158 #endif // USE_SCIP
1159 #if defined(USE_XPRESS)
1160  case KNAPSACK_MULTIDIMENSION_XPRESS_MIP_SOLVER:
1161  solver_ = absl::make_unique<KnapsackMIPSolver>(
1163  break;
1164 #endif
1165 #if defined(USE_CPLEX)
1166  case KNAPSACK_MULTIDIMENSION_CPLEX_MIP_SOLVER:
1167  solver_ = absl::make_unique<KnapsackMIPSolver>(
1169  break;
1170 #endif
1171  default:
1172  LOG(FATAL) << "Unknown knapsack solver type.";
1173  }
1174 }
1175 
1177 
1178 void KnapsackSolver::Init(const std::vector<int64>& profits,
1179  const std::vector<std::vector<int64>>& weights,
1180  const std::vector<int64>& capacities) {
1181  time_limit_ = absl::make_unique<TimeLimit>(time_limit_seconds_);
1182  is_solution_optimal_ = false;
1183  additional_profit_ = 0LL;
1184  is_problem_solved_ = false;
1185 
1186  const int num_items = profits.size();
1187  std::vector<std::vector<int64>> reduced_weights;
1188  std::vector<int64> reduced_capacities;
1189  if (use_reduction_) {
1190  const int num_reduced_items = ReduceCapacities(
1191  num_items, weights, capacities, &reduced_weights, &reduced_capacities);
1192  if (num_reduced_items > 0) {
1193  ComputeAdditionalProfit(profits);
1194  }
1195  } else {
1196  reduced_weights = weights;
1197  reduced_capacities = capacities;
1198  }
1199  if (!is_problem_solved_) {
1200  solver_->Init(profits, reduced_weights, reduced_capacities);
1201  if (use_reduction_) {
1202  const int num_reduced_items = ReduceProblem(num_items);
1203 
1204  if (num_reduced_items > 0) {
1205  ComputeAdditionalProfit(profits);
1206  }
1207 
1208  if (num_reduced_items > 0 && num_reduced_items < num_items) {
1209  InitReducedProblem(profits, reduced_weights, reduced_capacities);
1210  }
1211  }
1212  }
1213  if (is_problem_solved_) {
1214  is_solution_optimal_ = true;
1215  }
1216 }
1217 
1218 int KnapsackSolver::ReduceCapacities(
1219  int num_items, const std::vector<std::vector<int64>>& weights,
1220  const std::vector<int64>& capacities,
1221  std::vector<std::vector<int64>>* reduced_weights,
1222  std::vector<int64>* reduced_capacities) {
1223  known_value_.assign(num_items, false);
1224  best_solution_.assign(num_items, false);
1225  mapping_reduced_item_id_.assign(num_items, 0);
1226  std::vector<bool> active_capacities(weights.size(), true);
1227  int number_of_active_capacities = 0;
1228  for (int i = 0; i < weights.size(); ++i) {
1229  int64 max_weight = 0;
1230  for (int64 weight : weights[i]) {
1231  max_weight += weight;
1232  }
1233  if (max_weight <= capacities[i]) {
1234  active_capacities[i] = false;
1235  } else {
1236  ++number_of_active_capacities;
1237  }
1238  }
1239  reduced_weights->reserve(number_of_active_capacities);
1240  reduced_capacities->reserve(number_of_active_capacities);
1241  for (int i = 0; i < weights.size(); ++i) {
1242  if (active_capacities[i]) {
1243  reduced_weights->push_back(weights[i]);
1244  reduced_capacities->push_back(capacities[i]);
1245  }
1246  }
1247  if (reduced_capacities->empty()) {
1248  // There are no capacity constraints in the problem so we can reduce all
1249  // items and just add them to the best solution.
1250  for (int item_id = 0; item_id < num_items; ++item_id) {
1251  known_value_[item_id] = true;
1252  best_solution_[item_id] = true;
1253  }
1254  is_problem_solved_ = true;
1255  // All items are reduced.
1256  return num_items;
1257  }
1258  // There are still capacity constraints so no item reduction is done.
1259  return 0;
1260 }
1261 
1262 int KnapsackSolver::ReduceProblem(int num_items) {
1263  known_value_.assign(num_items, false);
1264  best_solution_.assign(num_items, false);
1265  mapping_reduced_item_id_.assign(num_items, 0);
1266  additional_profit_ = 0LL;
1267 
1268  for (int item_id = 0; item_id < num_items; ++item_id) {
1269  mapping_reduced_item_id_[item_id] = item_id;
1270  }
1271 
1272  int64 best_lower_bound = 0LL;
1273  std::vector<int64> J0_upper_bounds(num_items, kint64max);
1274  std::vector<int64> J1_upper_bounds(num_items, kint64max);
1275  for (int item_id = 0; item_id < num_items; ++item_id) {
1276  if (time_limit_->LimitReached()) {
1277  break;
1278  }
1279  int64 lower_bound = 0LL;
1280  int64 upper_bound = kint64max;
1281  solver_->GetLowerAndUpperBoundWhenItem(item_id, false, &lower_bound,
1282  &upper_bound);
1283  J1_upper_bounds.at(item_id) = upper_bound;
1284  best_lower_bound = std::max(best_lower_bound, lower_bound);
1285 
1286  solver_->GetLowerAndUpperBoundWhenItem(item_id, true, &lower_bound,
1287  &upper_bound);
1288  J0_upper_bounds.at(item_id) = upper_bound;
1289  best_lower_bound = std::max(best_lower_bound, lower_bound);
1290  }
1291 
1292  int num_reduced_items = 0;
1293  for (int item_id = 0; item_id < num_items; ++item_id) {
1294  if (best_lower_bound > J0_upper_bounds[item_id]) {
1295  known_value_[item_id] = true;
1296  best_solution_[item_id] = false;
1297  ++num_reduced_items;
1298  } else if (best_lower_bound > J1_upper_bounds[item_id]) {
1299  known_value_[item_id] = true;
1300  best_solution_[item_id] = true;
1301  ++num_reduced_items;
1302  }
1303  }
1304 
1305  is_problem_solved_ = num_reduced_items == num_items;
1306  return num_reduced_items;
1307 }
1308 
1309 void KnapsackSolver::ComputeAdditionalProfit(
1310  const std::vector<int64>& profits) {
1311  const int num_items = profits.size();
1312  additional_profit_ = 0LL;
1313  for (int item_id = 0; item_id < num_items; ++item_id) {
1314  if (known_value_[item_id] && best_solution_[item_id]) {
1315  additional_profit_ += profits[item_id];
1316  }
1317  }
1318 }
1319 
1320 void KnapsackSolver::InitReducedProblem(
1321  const std::vector<int64>& profits,
1322  const std::vector<std::vector<int64>>& weights,
1323  const std::vector<int64>& capacities) {
1324  const int num_items = profits.size();
1325  const int num_dimensions = capacities.size();
1326 
1327  std::vector<int64> reduced_profits;
1328  for (int item_id = 0; item_id < num_items; ++item_id) {
1329  if (!known_value_[item_id]) {
1330  mapping_reduced_item_id_[item_id] = reduced_profits.size();
1331  reduced_profits.push_back(profits[item_id]);
1332  }
1333  }
1334 
1335  std::vector<std::vector<int64>> reduced_weights;
1336  std::vector<int64> reduced_capacities = capacities;
1337  for (int dim = 0; dim < num_dimensions; ++dim) {
1338  const std::vector<int64>& one_dimension_weights = weights[dim];
1339  std::vector<int64> one_dimension_reduced_weights;
1340  for (int item_id = 0; item_id < num_items; ++item_id) {
1341  if (known_value_[item_id]) {
1342  if (best_solution_[item_id]) {
1343  reduced_capacities[dim] -= one_dimension_weights[item_id];
1344  }
1345  } else {
1346  one_dimension_reduced_weights.push_back(one_dimension_weights[item_id]);
1347  }
1348  }
1349  reduced_weights.push_back(one_dimension_reduced_weights);
1350  }
1351  solver_->Init(reduced_profits, reduced_weights, reduced_capacities);
1352 }
1353 
1355  return additional_profit_ +
1356  ((is_problem_solved_)
1357  ? 0
1358  : solver_->Solve(time_limit_.get(), &is_solution_optimal_));
1359 }
1360 
1361 bool KnapsackSolver::BestSolutionContains(int item_id) const {
1362  const int mapped_item_id =
1363  (use_reduction_) ? mapping_reduced_item_id_[item_id] : item_id;
1364  return (use_reduction_ && known_value_[item_id])
1365  ? best_solution_[item_id]
1366  : solver_->best_solution(mapped_item_id);
1367 }
1368 
1369 std::string KnapsackSolver::GetName() const { return solver_->GetName(); }
1370 
1371 // ----- BaseKnapsackSolver -----
1373  bool is_item_in,
1374  int64* lower_bound,
1375  int64* upper_bound) {
1376  CHECK(lower_bound != nullptr);
1377  CHECK(upper_bound != nullptr);
1378  *lower_bound = 0LL;
1379  *upper_bound = kint64max;
1380 }
1381 
1382 } // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define CHECK(condition)
Definition: base/logging.h:495
#define CHECK_LT(val1, val2)
Definition: base/logging.h:700
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
#define DCHECK_GT(val1, val2)
Definition: base/logging.h:890
#define LOG(severity)
Definition: base/logging.h:420
#define DCHECK(condition)
Definition: base/logging.h:884
#define CHECK_LE(val1, val2)
Definition: base/logging.h:699
virtual void GetLowerAndUpperBoundWhenItem(int item_id, bool is_item_in, int64 *lower_bound, int64 *upper_bound)
virtual std::string GetName() const
Knapsack64ItemsSolver(const std::string &solver_name)
void Init(const std::vector< int64 > &profits, const std::vector< std::vector< int64 >> &weights, const std::vector< int64 > &capacities) override
bool best_solution(int item_id) const override
int64 Solve(TimeLimit *time_limit, bool *is_solution_optimal) override
KnapsackBruteForceSolver(const std::string &solver_name)
void Init(const std::vector< int64 > &profits, const std::vector< std::vector< int64 >> &weights, const std::vector< int64 > &capacities) override
bool best_solution(int item_id) const override
int64 Solve(TimeLimit *time_limit, bool *is_solution_optimal) override
KnapsackCapacityPropagator(const KnapsackState &state, int64 capacity)
bool UpdatePropagator(bool revert, const KnapsackAssignment &assignment) override
void CopyCurrentStateToSolutionPropagator(std::vector< bool > *solution) const override
void Init(const std::vector< int64 > &profits, const std::vector< std::vector< int64 >> &weights, const std::vector< int64 > &capacities) override
KnapsackDynamicProgrammingSolver(const std::string &solver_name)
int64 Solve(TimeLimit *time_limit, bool *is_solution_optimal) override
KnapsackGenericSolver(const std::string &solver_name)
void GetLowerAndUpperBoundWhenItem(int item_id, bool is_item_in, int64 *lower_bound, int64 *upper_bound) override
void Init(const std::vector< int64 > &profits, const std::vector< std::vector< int64 > > &weights, const std::vector< int64 > &capacities) override
int64 Solve(TimeLimit *time_limit, bool *is_solution_optimal) override
KnapsackMIPSolver(MPSolver::OptimizationProblemType problem_type, const std::string &solver_name)
void Init(const std::vector< int64 > &profits, const std::vector< std::vector< int64 >> &weights, const std::vector< int64 > &capacities) override
bool best_solution(int item_id) const override
int64 Solve(TimeLimit *time_limit, bool *is_solution_optimal) override
void CopyCurrentStateToSolution(bool has_one_propagator, std::vector< bool > *solution) const
virtual bool UpdatePropagator(bool revert, const KnapsackAssignment &assignment)=0
const KnapsackState & state() const
void Init(const std::vector< int64 > &profits, const std::vector< int64 > &weights)
const std::vector< KnapsackItemPtr > & items() const
virtual void CopyCurrentStateToSolutionPropagator(std::vector< bool > *solution) const =0
KnapsackPropagator(const KnapsackState &state)
bool Update(bool revert, const KnapsackAssignment &assignment)
KnapsackSearchNode(const KnapsackSearchNode *const parent, const KnapsackAssignment &assignment)
const KnapsackSearchNode *const parent() const
const KnapsackSearchNode * MoveUpToDepth(const KnapsackSearchNode &node, int depth) const
KnapsackSearchPath(const KnapsackSearchNode &from, const KnapsackSearchNode &to)
This library solves knapsack problems.
bool BestSolutionContains(int item_id) const
Returns true if the item 'item_id' is packed in the optimal knapsack.
int64 Solve()
Solves the problem and returns the profit of the optimal solution.
KnapsackSolver(const std::string &solver_name)
void Init(const std::vector< int64 > &profits, const std::vector< std::vector< int64 > > &weights, const std::vector< int64 > &capacities)
Initializes the solver and enters the problem to be solved.
SolverType
Enum controlling which underlying algorithm is used.
@ KNAPSACK_MULTIDIMENSION_SCIP_MIP_SOLVER
SCIP based solver.
@ KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER
Generic Solver.
@ KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER
Dynamic Programming approach for single dimension problems.
@ KNAPSACK_64ITEMS_SOLVER
Optimized method for single dimension small problems.
@ KNAPSACK_BRUTE_FORCE_SOLVER
Brute force method.
@ KNAPSACK_MULTIDIMENSION_CBC_MIP_SOLVER
CBC Based Solver.
void Init(int number_of_items)
bool UpdateState(bool revert, const KnapsackAssignment &assignment)
The class for constraints of a Mathematical Programming (MP) model.
A class to express a linear objective.
void SetCoefficient(const MPVariable *const var, double coeff)
Sets the coefficient of the variable in the objective.
double Value() const
Returns the objective value of the best solution found so far.
void SetMinimization()
Sets the optimization direction to minimize.
This mathematical programming (MP) solver class is the main class though which users build and solve ...
void MakeBoolVarArray(int nb, const std::string &name, std::vector< MPVariable * > *vars)
Creates an array of boolean variables.
MPObjective * MutableObjective()
Returns the mutable objective object.
MPConstraint * MakeRowConstraint(double lb, double ub)
Creates a linear constraint with given bounds.
OptimizationProblemType
The type of problems (LP or MIP) that will be solved and the underlying solver (GLOP,...
ResultStatus Solve()
Solves the problem using the default parameter values.
void SuppressOutput()
Suppresses solver logging.
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
Definition: time_limit.h:105
SharedTimeLimit * time_limit
const Constraint * ct
int64 value
unsigned int uint32
static const int64 kint64max
int64_t int64
uint64_t uint64
static const int64 kint64min
const int64 profit_max
MPSolver::OptimizationProblemType problem_type
A C++ wrapper that provides a simple and unified interface to several linear programming and mixed in...
const int FATAL
Definition: log_severity.h:32
void STLDeleteElements(T *container)
Definition: stl_util.h:372
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int MostSignificantBitPosition64(uint64 n)
Definition: bitset.h:231
bool CompareKnapsackItemWithEfficiencyInDecreasingEfficiencyOrder(const KnapsackItemWithEfficiency &item1, const KnapsackItemWithEfficiency &item2)
uint32 OneBit32(int pos)
Definition: bitset.h:39
KnapsackItem * KnapsackItemPtr
uint64 OneBit64(int pos)
Definition: bitset.h:38
int64 weight
Definition: pack.cc:509
Fractional ratio
int64 capacity
KnapsackItemWithEfficiency(int _id, int64 _profit, int64 _weight, int64 _profit_max)