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"
24#include "ortools/util/bitset.h"
26
27namespace operations_research {
28
29namespace {
30const int kNoSelection = -1;
31const int kMasterPropagatorId = 0;
32const int kMaxNumberOfBruteForceItems = 30;
33const int kMaxNumberOf64Items = 64;
34
35// Comparator used to sort item in decreasing efficiency order
36// (see KnapsackCapacityPropagator).
37struct 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.
52struct 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
64typedef std::priority_queue<
65 KnapsackSearchNode*, std::vector<KnapsackSearchNode*>,
66 CompareKnapsackSearchNodePtrInDecreasingUpperBoundOrder>
67 SearchQueue;
68
69// Returns true when value_1 * value_2 may overflow int64.
70inline 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
80int64 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 -----
138KnapsackState::KnapsackState() : is_bound_(), is_in_() {}
139
140void 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.
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
171void 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;
182}
183
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
298int64 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 -----
336KnapsackGenericSolver::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
347void 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
444void KnapsackGenericSolver::Clear() {
445 gtl::STLDeleteElements(&propagators_);
446 gtl::STLDeleteElements(&search_nodes_);
447}
448
449// Returns false when at least one propagator fails.
450bool 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
468int64 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
478bool 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
515bool 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
526void 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;
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 -----
724Knapsack64ItemsSolver::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
739void 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
816int 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.
829void 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.
855void 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
881void 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
983int64 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:
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
1065void 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 -----
1119KnapsackSolver::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
1178void 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
1218int 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
1262int 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
1309void 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
1320void 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
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
1369std::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
void Init(const std::vector< int64 > &profits, const std::vector< std::vector< int64 > > &weights, const std::vector< int64 > &capacities) override
Knapsack64ItemsSolver(const std::string &solver_name)
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
void Init(const std::vector< int64 > &profits, const std::vector< std::vector< int64 > > &weights, const std::vector< int64 > &capacities) override
KnapsackMIPSolver(MPSolver::OptimizationProblemType problem_type, const std::string &solver_name)
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 std::vector< KnapsackItemPtr > & items() const
void Init(const std::vector< int64 > &profits, const std::vector< int64 > &weights)
virtual void CopyCurrentStateToSolutionPropagator(std::vector< bool > *solution) const =0
KnapsackPropagator(const KnapsackState &state)
bool Update(bool revert, const KnapsackAssignment &assignment)
const KnapsackState & state() const
const KnapsackSearchNode *const parent() const
KnapsackSearchNode(const KnapsackSearchNode *const parent, const KnapsackAssignment &assignment)
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.
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.
MPObjective * MutableObjective()
Returns the mutable objective object.
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
uint64 OneBit64(int pos)
Definition: bitset.h:38
KnapsackItem * KnapsackItemPtr
STL namespace.
int64 weight
Definition: pack.cc:509
Fractional ratio
int64 capacity
KnapsackItemWithEfficiency(int _id, int64 _profit, int64 _weight, int64 _profit_max)