25const int kNoSelection(-1);
26const int kDefaultMasterPropagatorId(0);
27const double kInfinity = std::numeric_limits<double>::infinity();
31struct CompareKnapsackItemsInDecreasingEfficiencyOrder {
32 explicit CompareKnapsackItemsInDecreasingEfficiencyOrder(
double _profit_max)
46struct CompareKnapsackSearchNodePtrInDecreasingUpperBoundOrder {
47 bool operator()(
const KnapsackSearchNodeForCuts* node_1,
48 const KnapsackSearchNodeForCuts* node_2)
const {
49 const double profit_upper_bound_1 = node_1->profit_upper_bound();
50 const double profit_upper_bound_2 = node_2->profit_upper_bound();
51 if (profit_upper_bound_1 == profit_upper_bound_2) {
52 return node_1->current_profit() < node_2->current_profit();
54 return profit_upper_bound_1 < profit_upper_bound_2;
58using SearchQueue = std::priority_queue<
59 KnapsackSearchNodeForCuts*, std::vector<KnapsackSearchNodeForCuts*>,
60 CompareKnapsackSearchNodePtrInDecreasingUpperBoundOrder>;
68 : depth_(parent == nullptr ? 0 : parent->depth() + 1),
70 assignment_(assignment),
73 next_item_id_(kNoSelection) {}
78 : from_(from), via_(nullptr), to_(to) {}
87 while (node_from != node_to) {
88 node_from = node_from->
parent();
89 node_to = node_to->
parent();
96 while (node->
depth() > depth) {
106 is_bound_.assign(number_of_items,
false);
107 is_in_.assign(number_of_items,
false);
114 is_bound_[assignment.
item_id] =
false;
116 if (is_bound_[assignment.
item_id] &&
120 is_bound_[assignment.
item_id] =
true;
131 profit_lower_bound_(0),
138 const std::vector<double>& weights,
140 const int number_of_items = profits.size();
143 for (
int i = 0; i < number_of_items; ++i) {
145 absl::make_unique<KnapsackItemForCuts>(i, weights[i], profits[i]));
156 if (assignment.
is_in) {
158 current_profit_ -= items_[assignment.
item_id]->profit;
159 consumed_capacity_ -=
items()[assignment.
item_id]->weight;
161 current_profit_ += items_[assignment.
item_id]->profit;
162 consumed_capacity_ +=
items()[assignment.
item_id]->weight;
163 if (consumed_capacity_ > capacity_) {
172 std::vector<bool>* solution)
const {
173 DCHECK(solution !=
nullptr);
174 for (
int i(0); i < items_.size(); ++i) {
175 const int item_id = items_[i]->id;
176 (*solution)[item_id] = state_->
is_bound(item_id) && state_->
is_in(item_id);
178 double remaining_capacity = capacity_ - consumed_capacity_;
180 if (!
state().is_bound(item->id)) {
181 if (remaining_capacity >= item->weight) {
182 remaining_capacity -= item->weight;
183 (*solution)[item->id] =
true;
193 break_item_id_ = kNoSelection;
195 double remaining_capacity = capacity_ - consumed_capacity_;
196 int break_sorted_item_id = kNoSelection;
197 for (
int sorted_id(0); sorted_id < sorted_items_.size(); ++sorted_id) {
198 if (!
state().is_bound(sorted_items_[sorted_id]->
id)) {
200 break_item_id_ = item->id;
201 if (remaining_capacity >= item->weight) {
202 remaining_capacity -= item->weight;
205 break_sorted_item_id = sorted_id;
217 if (break_sorted_item_id != kNoSelection) {
218 const double additional_profit =
219 GetAdditionalProfitUpperBound(remaining_capacity, break_sorted_item_id);
225 consumed_capacity_ = 0;
226 break_item_id_ = kNoSelection;
227 sorted_items_.clear();
228 sorted_items_.reserve(
items().size());
229 for (
int i(0); i <
items().size(); ++i) {
230 sorted_items_.emplace_back(absl::make_unique<KnapsackItemForCuts>(
235 profit_max_ =
std::max(profit_max_, item->profit);
238 CompareKnapsackItemsInDecreasingEfficiencyOrder compare_object(profit_max_);
239 std::sort(sorted_items_.begin(), sorted_items_.end(), compare_object);
242double KnapsackPropagatorForCuts::GetAdditionalProfitUpperBound(
243 double remaining_capacity,
int break_item_id)
const {
244 const int after_break_item_id = break_item_id + 1;
245 double additional_profit_when_no_break_item = 0;
246 if (after_break_item_id < sorted_items_.size()) {
249 const double next_weight = sorted_items_[after_break_item_id]->weight;
250 const double next_profit = sorted_items_[after_break_item_id]->profit;
251 additional_profit_when_no_break_item =
252 std::max((remaining_capacity * next_profit) / next_weight, 0.0);
255 const int before_break_item_id = break_item_id - 1;
256 double additional_profit_when_break_item = 0;
257 if (before_break_item_id >= 0) {
258 const double previous_weight = sorted_items_[before_break_item_id]->weight;
262 if (previous_weight != 0) {
263 const double previous_profit =
264 sorted_items_[before_break_item_id]->profit;
265 const double overused_capacity =
266 sorted_items_[break_item_id]->weight - remaining_capacity;
267 const double lost_profit_from_previous_item =
268 (overused_capacity * previous_profit) / previous_weight;
269 additional_profit_when_break_item =
std::max(
270 sorted_items_[break_item_id]->profit - lost_profit_from_previous_item,
275 const double additional_profit =
std::max(
276 additional_profit_when_no_break_item, additional_profit_when_break_item);
277 return additional_profit;
282 : propagator_(&state_),
283 best_solution_profit_(0),
284 solver_name_(
std::move(solver_name)) {}
287 const std::vector<double>& weights,
289 const int number_of_items(profits.size());
290 state_.
Init(number_of_items);
291 best_solution_.assign(number_of_items,
false);
292 CHECK_EQ(number_of_items, weights.size());
300 double* upper_bound) {
301 DCHECK(lower_bound !=
nullptr);
302 DCHECK(upper_bound !=
nullptr);
304 const bool fail = !IncrementalUpdate(
false, assignment);
310 *upper_bound = GetAggregatedProfitUpperBound();
313 const bool fail_revert = !IncrementalUpdate(
true, assignment);
321 bool* is_solution_optimal) {
323 DCHECK(is_solution_optimal !=
nullptr);
324 best_solution_profit_ = 0;
325 *is_solution_optimal =
true;
327 SearchQueue search_queue;
330 absl::make_unique<KnapsackSearchNodeForCuts>(
nullptr, assignment);
331 root_node->set_current_profit(GetCurrentProfit());
332 root_node->set_profit_upper_bound(GetAggregatedProfitUpperBound());
333 root_node->set_next_item_id(GetNextItemId());
334 search_nodes_.push_back(std::move(root_node));
336 search_nodes_.back().get();
338 if (MakeNewNode(*current_node,
false)) {
339 search_queue.push(search_nodes_.back().get());
341 if (MakeNewNode(*current_node,
true)) {
342 search_queue.push(search_nodes_.back().get());
345 int64 number_of_nodes_visited = 0;
346 while (!search_queue.empty() &&
347 search_queue.top()->profit_upper_bound() > best_solution_profit_) {
349 *is_solution_optimal =
false;
352 if (solution_upper_bound_threshold_ > -
kInfinity &&
353 GetAggregatedProfitUpperBound() < solution_upper_bound_threshold_) {
354 *is_solution_optimal =
false;
357 if (best_solution_profit_ > solution_lower_bound_threshold_) {
358 *is_solution_optimal =
false;
361 if (number_of_nodes_visited >= node_limit_) {
362 *is_solution_optimal =
false;
368 if (node != current_node) {
371 CHECK_EQ(UpdatePropagators(path),
true);
374 number_of_nodes_visited++;
376 if (MakeNewNode(*node,
false)) {
377 search_queue.push(search_nodes_.back().get());
379 if (MakeNewNode(*node,
true)) {
380 search_queue.push(search_nodes_.back().get());
383 return best_solution_profit_;
387bool KnapsackSolverForCuts::UpdatePropagators(
393 while (node != via) {
394 no_fail = IncrementalUpdate(
true, node->
assignment()) && no_fail;
399 while (node != via) {
400 no_fail = IncrementalUpdate(
false, node->
assignment()) && no_fail;
406double KnapsackSolverForCuts::GetAggregatedProfitUpperBound() {
412bool KnapsackSolverForCuts::MakeNewNode(
const KnapsackSearchNodeForCuts& node,
414 if (node.next_item_id() == kNoSelection) {
417 KnapsackAssignmentForCuts assignment(node.next_item_id(), is_in);
418 KnapsackSearchNodeForCuts new_node(&node, assignment);
420 KnapsackSearchPathForCuts path(&node, &new_node);
422 const bool no_fail = UpdatePropagators(path);
424 new_node.set_current_profit(GetCurrentProfit());
425 new_node.set_profit_upper_bound(GetAggregatedProfitUpperBound());
426 new_node.set_next_item_id(GetNextItemId());
427 UpdateBestSolution();
431 KnapsackSearchPathForCuts revert_path(&new_node, &node);
433 UpdatePropagators(revert_path);
435 if (!no_fail || new_node.profit_upper_bound() < best_solution_profit_) {
441 absl::make_unique<KnapsackSearchNodeForCuts>(&node, assignment);
442 relevant_node->set_current_profit(new_node.current_profit());
443 relevant_node->set_profit_upper_bound(new_node.profit_upper_bound());
444 relevant_node->set_next_item_id(new_node.next_item_id());
445 search_nodes_.push_back(std::move(relevant_node));
450bool KnapsackSolverForCuts::IncrementalUpdate(
451 bool revert,
const KnapsackAssignmentForCuts& assignment) {
454 bool no_fail = state_.
UpdateState(revert, assignment);
455 no_fail = propagator_.
Update(revert, assignment) && no_fail;
459void KnapsackSolverForCuts::UpdateBestSolution() {
462 if (best_solution_profit_ < profit_lower_bound) {
463 best_solution_profit_ = profit_lower_bound;
#define CHECK_EQ(val1, val2)
#define DCHECK(condition)
#define DCHECK_EQ(val1, val2)
void Init(const std::vector< double > &profits, const std::vector< double > &weights, double capacity)
void CopyCurrentStateToSolution(std::vector< bool > *solution) const
double profit_upper_bound() const
const KnapsackStateForCuts & state() const
~KnapsackPropagatorForCuts()
void set_profit_lower_bound(double profit)
double profit_lower_bound() const
double current_profit() const
KnapsackPropagatorForCuts(const KnapsackStateForCuts *state)
void set_profit_upper_bound(double profit)
bool Update(bool revert, const KnapsackAssignmentForCuts &assignment)
void ComputeProfitBounds()
const std::vector< KnapsackItemForCutsPtr > & items() const
const KnapsackAssignmentForCuts & assignment() const
KnapsackSearchNodeForCuts(const KnapsackSearchNodeForCuts *parent, const KnapsackAssignmentForCuts &assignment)
const KnapsackSearchNodeForCuts *const parent() const
const KnapsackSearchNodeForCuts & to() const
const KnapsackSearchNodeForCuts & via() const
const KnapsackSearchNodeForCuts & from() const
KnapsackSearchPathForCuts(const KnapsackSearchNodeForCuts *from, const KnapsackSearchNodeForCuts *to)
KnapsackSolverForCuts(std::string solver_name)
void Init(const std::vector< double > &profits, const std::vector< double > &weights, const double capacity)
double Solve(TimeLimit *time_limit, bool *is_solution_optimal)
void GetLowerAndUpperBoundWhenItem(int item_id, bool is_item_in, double *lower_bound, double *upper_bound)
void Init(int number_of_items)
bool UpdateState(bool revert, const KnapsackAssignmentForCuts &assignment)
bool is_bound(int id) const
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
SharedTimeLimit * time_limit
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
std::unique_ptr< KnapsackItemForCuts > KnapsackItemForCutsPtr
const KnapsackSearchNodeForCuts * MoveUpToDepth(const KnapsackSearchNodeForCuts *node, int depth)