21#include "absl/memory/memory.h"
30const int kNoSelection = -1;
31const int kMasterPropagatorId = 0;
32const int kMaxNumberOfBruteForceItems = 30;
33const int kMaxNumberOf64Items = 64;
37struct CompareKnapsackItemsInDecreasingEfficiencyOrder {
38 explicit CompareKnapsackItemsInDecreasingEfficiencyOrder(
int64 _profit_max)
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();
60 return profit_upper_bound_1 < profit_upper_bound_2;
64typedef std::priority_queue<
65 KnapsackSearchNode*, std::vector<KnapsackSearchNode*>,
66 CompareKnapsackSearchNodePtrInDecreasingUpperBoundOrder>
70inline bool WillProductOverflow(
int64 value_1,
int64 value_2) {
75 const int kOverflow = 61;
76 return MostSignificantBitPosition1 + MostSignificantBitPosition2 > kOverflow;
83 if (!WillProductOverflow(numerator_1, numerator_2)) {
84 const int64 numerator = numerator_1 * numerator_2;
86 const int64 result = numerator / denominator;
90 (
static_cast<double>(numerator_1) *
static_cast<double>(numerator_2)) /
91 static_cast<double>(denominator);
103 : depth_((parent == nullptr) ? 0 : parent->depth() + 1),
105 assignment_(assignment),
108 next_item_id_(kNoSelection) {}
113 : from_(from), via_(nullptr), to_(to) {}
121 while (node_from != node_to) {
122 node_from = node_from->
parent();
123 node_to = node_to->
parent();
131 while (current_node->
depth() > depth) {
132 current_node = current_node->
parent();
141 is_bound_.assign(number_of_items,
false);
142 is_in_.assign(number_of_items,
false);
149 is_bound_[assignment.
item_id] =
false;
151 if (is_bound_[assignment.
item_id] &&
155 is_bound_[assignment.
item_id] =
true;
165 profit_lower_bound_(0),
172 const std::vector<int64>& weights) {
173 const int number_of_items = profits.size();
175 for (
int i = 0; i < number_of_items; ++i) {
176 items_[i] =
new KnapsackItem(i, weights[i], profits[i]);
186 if (assignment.
is_in) {
188 current_profit_ -= items_[assignment.
item_id]->profit;
190 current_profit_ += items_[assignment.
item_id]->profit;
197 bool has_one_propagator, std::vector<bool>* solution)
const {
198 CHECK(solution !=
nullptr);
200 const int item_id = item->id;
201 (*solution)[item_id] = state_.
is_bound(item_id) && state_.
is_in(item_id);
203 if (has_one_propagator) {
213 consumed_capacity_(0),
214 break_item_id_(kNoSelection),
224 break_item_id_ = kNoSelection;
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;
234 if (remaining_capacity >= item->
weight) {
235 remaining_capacity -= item->
weight;
238 break_sorted_item_id = sorted_id;
246 if (break_sorted_item_id != kNoSelection) {
247 const int64 additional_profit =
248 GetAdditionalProfit(remaining_capacity, break_sorted_item_id);
254 consumed_capacity_ = 0;
255 break_item_id_ = kNoSelection;
256 sorted_items_ =
items();
259 profit_max_ =
std::max(profit_max_, item->profit);
262 CompareKnapsackItemsInDecreasingEfficiencyOrder compare_object(profit_max_);
263 std::sort(sorted_items_.begin(), sorted_items_.end(), compare_object);
269 if (assignment.
is_in) {
271 consumed_capacity_ -=
items()[assignment.
item_id]->weight;
273 consumed_capacity_ +=
items()[assignment.
item_id]->weight;
274 if (consumed_capacity_ > capacity_) {
283 std::vector<bool>* solution)
const {
284 CHECK(solution !=
nullptr);
285 int64 remaining_capacity = capacity_ - consumed_capacity_;
287 if (!
state().is_bound(item->id)) {
288 if (remaining_capacity >= item->weight) {
289 remaining_capacity -= item->weight;
290 (*solution)[item->id] =
true;
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()) {
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);
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;
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,
324 additional_profit_when_break_item =
325 sorted_items_[break_item_id]->profit -
ratio;
329 const int64 additional_profit =
std::max(additional_profit_when_no_break_item,
330 additional_profit_when_break_item);
332 return additional_profit;
339 master_propagator_id_(kMasterPropagatorId),
342 best_solution_profit_(0),
348 const std::vector<std::vector<int64>>& weights,
349 const std::vector<int64>& capacities) {
350 CHECK_EQ(capacities.size(), weights.size());
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());
362 propagator->
Init(profits, weights[i]);
363 propagators_.push_back(propagator);
365 master_propagator_id_ = kMasterPropagatorId;
371 int64* upper_bound) {
372 CHECK(lower_bound !=
nullptr);
373 CHECK(upper_bound !=
nullptr);
375 const bool fail = !IncrementalUpdate(
false, assignment);
382 ? propagators_[master_propagator_id_]->profit_lower_bound()
384 *upper_bound = GetAggregatedProfitUpperBound();
387 const bool fail_revert = !IncrementalUpdate(
true, assignment);
395 bool* is_solution_optimal) {
397 DCHECK(is_solution_optimal !=
nullptr);
398 best_solution_profit_ = 0LL;
399 *is_solution_optimal =
true;
401 SearchQueue search_queue;
407 search_nodes_.push_back(root_node);
409 if (MakeNewNode(*root_node,
false)) {
410 search_queue.push(search_nodes_.back());
412 if (MakeNewNode(*root_node,
true)) {
413 search_queue.push(search_nodes_.back());
417 while (!search_queue.empty() &&
418 search_queue.top()->profit_upper_bound() > best_solution_profit_) {
420 *is_solution_optimal =
false;
426 if (node != current_node) {
429 const bool no_fail = UpdatePropagators(path);
434 if (MakeNewNode(*node,
false)) {
435 search_queue.push(search_nodes_.back());
437 if (MakeNewNode(*node,
true)) {
438 search_queue.push(search_nodes_.back());
441 return best_solution_profit_;
444void KnapsackGenericSolver::Clear() {
450bool KnapsackGenericSolver::UpdatePropagators(
const KnapsackSearchPath& path) {
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();
461 while (node != via) {
462 no_fail = IncrementalUpdate(
false, node->assignment()) && no_fail;
463 node = node->parent();
468int64 KnapsackGenericSolver::GetAggregatedProfitUpperBound()
const {
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);
478bool KnapsackGenericSolver::MakeNewNode(
const KnapsackSearchNode& node,
480 if (node.next_item_id() == kNoSelection) {
483 KnapsackAssignment assignment(node.next_item_id(), is_in);
484 KnapsackSearchNode new_node(&node, assignment);
486 KnapsackSearchPath path(node, new_node);
488 const bool no_fail = UpdatePropagators(path);
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();
497 KnapsackSearchPath revert_path(new_node, node);
499 UpdatePropagators(revert_path);
501 if (!no_fail || new_node.profit_upper_bound() < best_solution_profit_) {
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);
515bool KnapsackGenericSolver::IncrementalUpdate(
516 bool revert,
const KnapsackAssignment& assignment) {
519 bool no_fail = state_.
UpdateState(revert, assignment);
520 for (KnapsackPropagator*
const prop : propagators_) {
521 no_fail = prop->Update(revert, assignment) && no_fail;
526void KnapsackGenericSolver::UpdateBestSolution() {
527 const int64 profit_lower_bound =
529 ? propagators_[master_propagator_id_]->profit_lower_bound()
530 : propagators_[master_propagator_id_]->current_profit();
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_);
549 void Init(
const std::vector<int64>& profits,
550 const std::vector<std::vector<int64>>& weights,
551 const std::vector<int64>& capacities)
override;
558 return (best_solution_ &
OneBit32(item_id)) != 0U;
563 int64 profits_weights_[kMaxNumberOfBruteForceItems * 2];
565 int64 best_solution_profit_;
572 const std::string& solver_name)
576 best_solution_profit_(0LL),
577 best_solution_(0U) {}
580 const std::vector<int64>& profits,
581 const std::vector<std::vector<int64>>& weights,
582 const std::vector<int64>& capacities) {
585 <<
"Brute force solver only works with one dimension.";
586 CHECK_EQ(capacities.size(), weights.size());
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_ <<
".";
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);
599 capacity_ = capacities.at(0);
603 bool* is_solution_optimal) {
604 DCHECK(is_solution_optimal !=
nullptr);
605 *is_solution_optimal =
true;
606 best_solution_profit_ = 0LL;
618 for (
uint32 state = 1U; state < num_states; ++state, ++prev_state) {
619 diff_state = state ^ prev_state;
623 if (diff_state & 1U) {
624 if (local_state & 1U) {
625 sum_profit += profits_weights_[item_id];
626 sum_weight += profits_weights_[item_id + 1];
627 CHECK_LT(item_id + 1, 2 * num_items_);
629 sum_profit -= profits_weights_[item_id];
630 sum_weight -= profits_weights_[item_id + 1];
631 CHECK_LT(item_id + 1, 2 * num_items_);
635 local_state = local_state >> 1;
636 diff_state = diff_state >> 1;
639 if (sum_weight <= capacity_ && best_solution_profit_ < sum_profit) {
640 best_solution_profit_ = sum_profit;
641 best_solution_ = state;
645 return best_solution_profit_;
661 static_cast<double>(_weight)
662 : static_cast<double>(_profit_max)) {}
679 void Init(
const std::vector<int64>& profits,
680 const std::vector<std::vector<int64>>& weights,
681 const std::vector<int64>& capacities)
override;
688 return (best_solution_ &
OneBit64(item_id)) != 0ULL;
693 void GetLowerAndUpperBound(
int64* lower_bound,
int64* upper_bound)
const;
694 void GoToNextState(
bool has_failed);
695 void BuildBestSolution();
697 std::vector<KnapsackItemWithEfficiency> sorted_items_;
698 std::vector<int64> sum_profits_;
699 std::vector<int64> sum_weights_;
704 int64 best_solution_profit_;
706 int best_solution_depth_;
711 int64 rejected_items_profit_;
713 int64 rejected_items_weight_;
732 best_solution_profit_(0LL),
733 best_solution_(0ULL),
734 best_solution_depth_(0),
736 rejected_items_profit_(0LL),
737 rejected_items_weight_(0LL) {}
740 const std::vector<std::vector<int64>>& weights,
741 const std::vector<int64>& capacities) {
743 <<
"Brute force solver only works with one dimension.";
744 CHECK_EQ(capacities.size(), weights.size());
746 sorted_items_.clear();
747 sum_profits_.clear();
748 sum_weights_.clear();
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
758 for (
int i = 0; i < num_items; ++i) {
759 sorted_items_.push_back(
763 std::sort(sorted_items_.begin(), sorted_items_.end(),
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;
774 sum_profits_.push_back(sum_profit);
775 sum_weights_.push_back(sum_weight);
780 bool* is_solution_optimal) {
781 DCHECK(is_solution_optimal !=
nullptr);
782 *is_solution_optimal =
true;
783 const int num_items = sorted_items_.size();
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;
793 int64 lower_bound = 0LL;
794 int64 upper_bound = 0LL;
796 while (state_depth_ >= 0) {
798 if (state_weight_ > capacity_ || state_depth_ >= num_items) {
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_;
808 fail = fail || best_solution_profit_ >= upper_bound;
813 return best_solution_profit_;
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;
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;
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;
855void Knapsack64ItemsSolver::GoToNextState(
bool has_failed) {
859 state_ = state_ | (mask << 1);
860 state_weight_ += sorted_items_[state_depth_].weight;
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;
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;
881void Knapsack64ItemsSolver::BuildBestSolution() {
882 int64 remaining_capacity = capacity_;
883 int64 check_profit = 0LL;
887 for (
int i = 0; i <= best_solution_depth_; ++i) {
889 remaining_capacity -= sorted_items_[i].weight;
890 check_profit += sorted_items_[i].profit;
895 const int num_items = sorted_items_.size();
896 for (
int i = best_solution_depth_ + 1; i < num_items; ++i) {
898 if (remaining_capacity >=
weight) {
899 remaining_capacity -=
weight;
900 check_profit += sorted_items_[i].profit;
901 best_solution_ = best_solution_ |
OneBit64(i);
903 best_solution_ = best_solution_ & ~OneBit64(i);
906 CHECK_EQ(best_solution_profit_, check_profit);
912 uint64 tmp_solution = 0ULL;
913 for (
int i = 0; i < num_items; ++i) {
915 const int original_id = sorted_items_[i].id;
916 tmp_solution = tmp_solution |
OneBit64(original_id);
920 best_solution_ = tmp_solution;
935 void Init(
const std::vector<int64>& profits,
936 const std::vector<std::vector<int64>>& weights,
937 const std::vector<int64>& capacities)
override;
944 return best_solution_.at(item_id);
950 std::vector<int64> profits_;
951 std::vector<int64> weights_;
953 std::vector<int64> computed_profits_;
954 std::vector<int> selected_item_ids_;
955 std::vector<bool> best_solution_;
960 const std::string& solver_name)
966 selected_item_ids_(),
970 const std::vector<int64>& profits,
971 const std::vector<std::vector<int64>>& weights,
972 const std::vector<int64>& capacities) {
974 <<
"Current implementation of the dynamic programming solver only deals"
975 <<
" with one dimension.";
976 CHECK_EQ(capacities.size(), weights.size());
979 weights_ = weights[0];
980 capacity_ = capacities[0];
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;
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;
1001 return selected_item_ids_.at(
capacity);
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);
1012 int64 remaining_capacity = capacity_;
1013 int num_items = profits_.size();
1014 best_solution_.assign(num_items,
false);
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;
1025 return computed_profits_[capacity_];
1032 const std::string& solver_name);
1035 void Init(
const std::vector<int64>& profits,
1036 const std::vector<std::vector<int64>>& weights,
1037 const std::vector<int64>& capacities)
override;
1044 return best_solution_.at(item_id);
1049 std::vector<int64> profits_;
1050 std::vector<std::vector<int64>> weights_;
1051 std::vector<int64> capacities_;
1052 std::vector<bool> best_solution_;
1057 const std::string& solver_name)
1066 const std::vector<std::vector<int64>>& weights,
1067 const std::vector<int64>& capacities) {
1070 capacities_ = capacities;
1074 bool* is_solution_optimal) {
1075 DCHECK(is_solution_optimal !=
nullptr);
1076 *is_solution_optimal =
true;
1079 const int num_items = profits_.size();
1080 std::vector<MPVariable*> variables;
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) {
1090 for (
int j = 0; j < num_items; ++j) {
1091 ct->SetCoefficient(variables.at(j), weights_.at(i).at(j));
1099 for (
int j = 0; j < num_items; ++j) {
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;
1115 return -objective->
Value() + kRoundNear;
1120 :
KnapsackSolver(KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
1124 const std::string& solver_name)
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);
1138 solver_ = absl::make_unique<Knapsack64ItemsSolver>(solver_name);
1142 absl::make_unique<KnapsackDynamicProgrammingSolver>(solver_name);
1145 solver_ = absl::make_unique<KnapsackGenericSolver>(solver_name);
1149 solver_ = absl::make_unique<KnapsackMIPSolver>(
1153#if defined(USE_SCIP)
1155 solver_ = absl::make_unique<KnapsackMIPSolver>(
1159#if defined(USE_XPRESS)
1160 case KNAPSACK_MULTIDIMENSION_XPRESS_MIP_SOLVER:
1161 solver_ = absl::make_unique<KnapsackMIPSolver>(
1165#if defined(USE_CPLEX)
1166 case KNAPSACK_MULTIDIMENSION_CPLEX_MIP_SOLVER:
1167 solver_ = absl::make_unique<KnapsackMIPSolver>(
1172 LOG(
FATAL) <<
"Unknown knapsack solver type.";
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;
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);
1196 reduced_weights = weights;
1197 reduced_capacities = capacities;
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);
1204 if (num_reduced_items > 0) {
1205 ComputeAdditionalProfit(profits);
1208 if (num_reduced_items > 0 && num_reduced_items < num_items) {
1209 InitReducedProblem(profits, reduced_weights, reduced_capacities);
1213 if (is_problem_solved_) {
1214 is_solution_optimal_ =
true;
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;
1233 if (max_weight <= capacities[i]) {
1234 active_capacities[i] =
false;
1236 ++number_of_active_capacities;
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]);
1247 if (reduced_capacities->empty()) {
1250 for (
int item_id = 0; item_id < num_items; ++item_id) {
1251 known_value_[item_id] =
true;
1252 best_solution_[item_id] =
true;
1254 is_problem_solved_ =
true;
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;
1268 for (
int item_id = 0; item_id < num_items; ++item_id) {
1269 mapping_reduced_item_id_[item_id] = item_id;
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()) {
1279 int64 lower_bound = 0LL;
1281 solver_->GetLowerAndUpperBoundWhenItem(item_id,
false, &lower_bound,
1283 J1_upper_bounds.at(item_id) = upper_bound;
1284 best_lower_bound =
std::max(best_lower_bound, lower_bound);
1286 solver_->GetLowerAndUpperBoundWhenItem(item_id,
true, &lower_bound,
1288 J0_upper_bounds.at(item_id) = upper_bound;
1289 best_lower_bound =
std::max(best_lower_bound, lower_bound);
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;
1305 is_problem_solved_ = num_reduced_items == num_items;
1306 return num_reduced_items;
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];
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();
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]);
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];
1346 one_dimension_reduced_weights.push_back(one_dimension_weights[item_id]);
1349 reduced_weights.push_back(one_dimension_reduced_weights);
1351 solver_->Init(reduced_profits, reduced_weights, reduced_capacities);
1355 return additional_profit_ +
1356 ((is_problem_solved_)
1358 : solver_->Solve(time_limit_.get(), &is_solution_optimal_));
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);
1375 int64* upper_bound) {
1376 CHECK(lower_bound !=
nullptr);
1377 CHECK(upper_bound !=
nullptr);
#define CHECK_LT(val1, val2)
#define CHECK_EQ(val1, val2)
#define CHECK_GE(val1, val2)
#define DCHECK_GT(val1, val2)
#define DCHECK(condition)
#define CHECK_LE(val1, val2)
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 ComputeProfitBounds() override
~KnapsackCapacityPropagator() override
void InitPropagator() override
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
KnapsackDynamicProgrammingSolver(const std::string &solver_name)
int64 Solve(TimeLimit *time_limit, bool *is_solution_optimal) override
~KnapsackGenericSolver() 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
int64 profit_lower_bound() const
void CopyCurrentStateToSolution(bool has_one_propagator, std::vector< bool > *solution) const
virtual bool UpdatePropagator(bool revert, const KnapsackAssignment &assignment)=0
void set_profit_lower_bound(int64 profit)
const std::vector< KnapsackItemPtr > & items() const
virtual void InitPropagator()=0
void Init(const std::vector< int64 > &profits, const std::vector< int64 > &weights)
void set_profit_upper_bound(int64 profit)
virtual void CopyCurrentStateToSolutionPropagator(std::vector< bool > *solution) const =0
int64 profit_upper_bound() const
virtual ~KnapsackPropagator()
KnapsackPropagator(const KnapsackState &state)
int64 current_profit() const
bool Update(bool revert, const KnapsackAssignment &assignment)
const KnapsackState & state() const
void set_current_profit(int64 profit)
const KnapsackSearchNode *const parent() const
void set_next_item_id(int id)
void set_profit_upper_bound(int64 profit)
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.
std::string GetName() const
virtual ~KnapsackSolver()
void Init(int number_of_items)
bool is_bound(int id) const
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,...
@ CPLEX_MIXED_INTEGER_PROGRAMMING
@ XPRESS_MIXED_INTEGER_PROGRAMMING
@ SCIP_MIXED_INTEGER_PROGRAMMING
@ CBC_MIXED_INTEGER_PROGRAMMING
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...
SharedTimeLimit * time_limit
static const int64 kint64max
static const int64 kint64min
MPSolver::OptimizationProblemType problem_type
A C++ wrapper that provides a simple and unified interface to several linear programming and mixed in...
void STLDeleteElements(T *container)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int MostSignificantBitPosition64(uint64 n)
bool CompareKnapsackItemWithEfficiencyInDecreasingEfficiencyOrder(const KnapsackItemWithEfficiency &item1, const KnapsackItemWithEfficiency &item2)
KnapsackItem * KnapsackItemPtr
KnapsackItemWithEfficiency(int _id, int64 _profit, int64 _weight, int64 _profit_max)