OR-Tools  8.2
knapsack_solver_for_cuts.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 <utility>
19 
20 #include "ortools/base/logging.h"
21 
22 namespace operations_research {
23 namespace {
24 
25 const int kNoSelection(-1);
26 const int kDefaultMasterPropagatorId(0);
27 const double kInfinity = std::numeric_limits<double>::infinity();
28 
29 // Comparator used to sort item in decreasing efficiency order
30 // (see KnapsackCapacityPropagator).
31 struct CompareKnapsackItemsInDecreasingEfficiencyOrder {
32  explicit CompareKnapsackItemsInDecreasingEfficiencyOrder(double _profit_max)
33  : profit_max(_profit_max) {}
34  bool operator()(const KnapsackItemForCutsPtr& item1,
35  const KnapsackItemForCutsPtr& item2) const {
36  return item1->GetEfficiency(profit_max) > item2->GetEfficiency(profit_max);
37  }
38  const double profit_max;
39 };
40 
41 // Comparator used to sort search nodes in the priority queue in order
42 // to pop first the node with the highest profit upper bound
43 // (see KnapsackSearchNodeForCuts). When two nodes have the same upper bound, we
44 // prefer the one with the highest current profit. This is usually the one
45 // closer to a leaf. In practice, the main advantage is to have smaller path.
46 struct 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();
53  }
54  return profit_upper_bound_1 < profit_upper_bound_2;
55  }
56 };
57 
58 using SearchQueue = std::priority_queue<
59  KnapsackSearchNodeForCuts*, std::vector<KnapsackSearchNodeForCuts*>,
60  CompareKnapsackSearchNodePtrInDecreasingUpperBoundOrder>;
61 
62 } // namespace
63 
64 // ----- KnapsackSearchNodeForCuts -----
66  const KnapsackSearchNodeForCuts* const parent,
67  const KnapsackAssignmentForCuts& assignment)
68  : depth_(parent == nullptr ? 0 : parent->depth() + 1),
69  parent_(parent),
70  assignment_(assignment),
71  current_profit_(0),
72  profit_upper_bound_(kInfinity),
73  next_item_id_(kNoSelection) {}
74 
75 // ----- KnapsackSearchPathForCuts -----
78  : from_(from), via_(nullptr), to_(to) {}
79 
81  const KnapsackSearchNodeForCuts* node_from =
82  MoveUpToDepth(from_, to_->depth());
83  const KnapsackSearchNodeForCuts* node_to = MoveUpToDepth(to_, from_->depth());
84  DCHECK_EQ(node_from->depth(), node_to->depth());
85 
86  // Find common parent.
87  while (node_from != node_to) {
88  node_from = node_from->parent();
89  node_to = node_to->parent();
90  }
91  via_ = node_from;
92 }
93 
95  const KnapsackSearchNodeForCuts* node, int depth) {
96  while (node->depth() > depth) {
97  node = node->parent();
98  }
99  return node;
100 }
101 
102 // ----- KnapsackStateForCuts -----
103 KnapsackStateForCuts::KnapsackStateForCuts() : is_bound_(), is_in_() {}
104 
105 void KnapsackStateForCuts::Init(int number_of_items) {
106  is_bound_.assign(number_of_items, false);
107  is_in_.assign(number_of_items, false);
108 }
109 
110 // Returns false when the state is invalid.
112  bool revert, const KnapsackAssignmentForCuts& assignment) {
113  if (revert) {
114  is_bound_[assignment.item_id] = false;
115  } else {
116  if (is_bound_[assignment.item_id] &&
117  is_in_[assignment.item_id] != assignment.is_in) {
118  return false;
119  }
120  is_bound_[assignment.item_id] = true;
121  is_in_[assignment.item_id] = assignment.is_in;
122  }
123  return true;
124 }
125 
126 // ----- KnapsackPropagatorForCuts -----
128  const KnapsackStateForCuts* state)
129  : items_(),
130  current_profit_(0),
131  profit_lower_bound_(0),
132  profit_upper_bound_(kInfinity),
133  state_(state) {}
134 
136 
137 void KnapsackPropagatorForCuts::Init(const std::vector<double>& profits,
138  const std::vector<double>& weights,
139  const double capacity) {
140  const int number_of_items = profits.size();
141  items_.clear();
142 
143  for (int i = 0; i < number_of_items; ++i) {
144  items_.emplace_back(
145  absl::make_unique<KnapsackItemForCuts>(i, weights[i], profits[i]));
146  }
147  capacity_ = capacity;
148  current_profit_ = 0;
149  profit_lower_bound_ = -kInfinity;
150  profit_upper_bound_ = kInfinity;
151  InitPropagator();
152 }
153 
155  bool revert, const KnapsackAssignmentForCuts& assignment) {
156  if (assignment.is_in) {
157  if (revert) {
158  current_profit_ -= items_[assignment.item_id]->profit;
159  consumed_capacity_ -= items()[assignment.item_id]->weight;
160  } else {
161  current_profit_ += items_[assignment.item_id]->profit;
162  consumed_capacity_ += items()[assignment.item_id]->weight;
163  if (consumed_capacity_ > capacity_) {
164  return false;
165  }
166  }
167  }
168  return true;
169 }
170 
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);
177  }
178  double remaining_capacity = capacity_ - consumed_capacity_;
179  for (const KnapsackItemForCutsPtr& item : sorted_items_) {
180  if (!state().is_bound(item->id)) {
181  if (remaining_capacity >= item->weight) {
182  remaining_capacity -= item->weight;
183  (*solution)[item->id] = true;
184  } else {
185  return;
186  }
187  }
188  }
189 }
190 
193  break_item_id_ = kNoSelection;
194 
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)) {
199  const KnapsackItemForCutsPtr& item = sorted_items_[sorted_id];
200  break_item_id_ = item->id;
201  if (remaining_capacity >= item->weight) {
202  remaining_capacity -= item->weight;
203  set_profit_lower_bound(profit_lower_bound() + item->profit);
204  } else {
205  break_sorted_item_id = sorted_id;
206  break;
207  }
208  }
209  }
210 
212  // If break_sorted_item_id == kNoSelection, then all remaining items fit into
213  // the knapsack, and thus the lower bound on the profit equals the upper
214  // bound. Otherwise, we compute a tight upper bound by filling the remaining
215  // capacity of the knapsack with "fractional" items, in the decreasing order
216  // of their efficiency.
217  if (break_sorted_item_id != kNoSelection) {
218  const double additional_profit =
219  GetAdditionalProfitUpperBound(remaining_capacity, break_sorted_item_id);
220  set_profit_upper_bound(profit_upper_bound() + additional_profit);
221  }
222 }
223 
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>(
231  i, items()[i]->weight, items()[i]->profit));
232  }
233  profit_max_ = 0;
234  for (const KnapsackItemForCutsPtr& item : sorted_items_) {
235  profit_max_ = std::max(profit_max_, item->profit);
236  }
237  profit_max_ += 1.0;
238  CompareKnapsackItemsInDecreasingEfficiencyOrder compare_object(profit_max_);
239  std::sort(sorted_items_.begin(), sorted_items_.end(), compare_object);
240 }
241 
242 double 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()) {
247  // As items are sorted by decreasing profit / weight ratio, and the current
248  // weight is non-zero, the next_weight is non-zero too.
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);
253  }
254 
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;
259  // Having previous_weight == 0 means the total capacity is smaller than
260  // the weight of the current item. In such a case the item cannot be part
261  // of a solution of the local one dimension problem.
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,
271  0.0);
272  }
273  }
274 
275  const double additional_profit = std::max(
276  additional_profit_when_no_break_item, additional_profit_when_break_item);
277  return additional_profit;
278 }
279 
280 // ----- KnapsackSolverForCuts -----
282  : propagator_(&state_),
283  best_solution_profit_(0),
284  solver_name_(std::move(solver_name)) {}
285 
286 void KnapsackSolverForCuts::Init(const std::vector<double>& profits,
287  const std::vector<double>& weights,
288  const double capacity) {
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());
293 
294  propagator_.Init(profits, weights, capacity);
295 }
296 
298  bool is_item_in,
299  double* lower_bound,
300  double* upper_bound) {
301  DCHECK(lower_bound != nullptr);
302  DCHECK(upper_bound != nullptr);
303  KnapsackAssignmentForCuts assignment(item_id, is_item_in);
304  const bool fail = !IncrementalUpdate(false, assignment);
305  if (fail) {
306  *lower_bound = 0;
307  *upper_bound = 0;
308  } else {
309  *lower_bound = propagator_.profit_lower_bound();
310  *upper_bound = GetAggregatedProfitUpperBound();
311  }
312 
313  const bool fail_revert = !IncrementalUpdate(true, assignment);
314  if (fail_revert) {
315  *lower_bound = 0;
316  *upper_bound = 0;
317  }
318 }
319 
321  bool* is_solution_optimal) {
322  DCHECK(time_limit != nullptr);
323  DCHECK(is_solution_optimal != nullptr);
324  best_solution_profit_ = 0;
325  *is_solution_optimal = true;
326 
327  SearchQueue search_queue;
328  const KnapsackAssignmentForCuts assignment(kNoSelection, true);
329  auto root_node =
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));
335  const KnapsackSearchNodeForCuts* current_node =
336  search_nodes_.back().get(); // Start with the root node.
337 
338  if (MakeNewNode(*current_node, false)) {
339  search_queue.push(search_nodes_.back().get());
340  }
341  if (MakeNewNode(*current_node, true)) {
342  search_queue.push(search_nodes_.back().get());
343  }
344 
345  int64 number_of_nodes_visited = 0;
346  while (!search_queue.empty() &&
347  search_queue.top()->profit_upper_bound() > best_solution_profit_) {
348  if (time_limit->LimitReached()) {
349  *is_solution_optimal = false;
350  break;
351  }
352  if (solution_upper_bound_threshold_ > -kInfinity &&
353  GetAggregatedProfitUpperBound() < solution_upper_bound_threshold_) {
354  *is_solution_optimal = false;
355  break;
356  }
357  if (best_solution_profit_ > solution_lower_bound_threshold_) {
358  *is_solution_optimal = false;
359  break;
360  }
361  if (number_of_nodes_visited >= node_limit_) {
362  *is_solution_optimal = false;
363  break;
364  }
365  KnapsackSearchNodeForCuts* const node = search_queue.top();
366  search_queue.pop();
367 
368  if (node != current_node) {
369  KnapsackSearchPathForCuts path(current_node, node);
370  path.Init();
371  CHECK_EQ(UpdatePropagators(path), true);
372  current_node = node;
373  }
374  number_of_nodes_visited++;
375 
376  if (MakeNewNode(*node, false)) {
377  search_queue.push(search_nodes_.back().get());
378  }
379  if (MakeNewNode(*node, true)) {
380  search_queue.push(search_nodes_.back().get());
381  }
382  }
383  return best_solution_profit_;
384 }
385 
386 // Returns false when at least one propagator fails.
387 bool KnapsackSolverForCuts::UpdatePropagators(
388  const KnapsackSearchPathForCuts& path) {
389  bool no_fail = true;
390  // Revert previous changes.
391  const KnapsackSearchNodeForCuts* node = &path.from();
392  const KnapsackSearchNodeForCuts* const via = &path.via();
393  while (node != via) {
394  no_fail = IncrementalUpdate(true, node->assignment()) && no_fail;
395  node = node->parent();
396  }
397  // Apply current changes.
398  node = &path.to();
399  while (node != via) {
400  no_fail = IncrementalUpdate(false, node->assignment()) && no_fail;
401  node = node->parent();
402  }
403  return no_fail;
404 }
405 
406 double KnapsackSolverForCuts::GetAggregatedProfitUpperBound() {
407  propagator_.ComputeProfitBounds();
408  const double propagator_upper_bound = propagator_.profit_upper_bound();
409  return std::min(kInfinity, propagator_upper_bound);
410 }
411 
412 bool KnapsackSolverForCuts::MakeNewNode(const KnapsackSearchNodeForCuts& node,
413  bool is_in) {
414  if (node.next_item_id() == kNoSelection) {
415  return false;
416  }
417  KnapsackAssignmentForCuts assignment(node.next_item_id(), is_in);
418  KnapsackSearchNodeForCuts new_node(&node, assignment);
419 
420  KnapsackSearchPathForCuts path(&node, &new_node);
421  path.Init();
422  const bool no_fail = UpdatePropagators(path);
423  if (no_fail) {
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();
428  }
429 
430  // Revert to be able to create another node from parent.
431  KnapsackSearchPathForCuts revert_path(&new_node, &node);
432  revert_path.Init();
433  UpdatePropagators(revert_path);
434 
435  if (!no_fail || new_node.profit_upper_bound() < best_solution_profit_) {
436  return false;
437  }
438 
439  // The node is relevant.
440  auto relevant_node =
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));
446 
447  return true;
448 }
449 
450 bool KnapsackSolverForCuts::IncrementalUpdate(
451  bool revert, const KnapsackAssignmentForCuts& assignment) {
452  // Do not stop on a failure: To be able to be incremental on the update,
453  // partial solution (state) and propagators must all be in the same state.
454  bool no_fail = state_.UpdateState(revert, assignment);
455  no_fail = propagator_.Update(revert, assignment) && no_fail;
456  return no_fail;
457 }
458 
459 void KnapsackSolverForCuts::UpdateBestSolution() {
460  const double profit_lower_bound = propagator_.profit_lower_bound();
461 
462  if (best_solution_profit_ < profit_lower_bound) {
463  best_solution_profit_ = profit_lower_bound;
464  propagator_.CopyCurrentStateToSolution(&best_solution_);
465  }
466 }
467 
468 } // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define DCHECK(condition)
Definition: base/logging.h:884
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
void Init(const std::vector< double > &profits, const std::vector< double > &weights, double capacity)
void CopyCurrentStateToSolution(std::vector< bool > *solution) const
const std::vector< KnapsackItemForCutsPtr > & items() const
KnapsackPropagatorForCuts(const KnapsackStateForCuts *state)
bool Update(bool revert, const KnapsackAssignmentForCuts &assignment)
const KnapsackSearchNodeForCuts *const parent() const
const KnapsackAssignmentForCuts & assignment() const
KnapsackSearchNodeForCuts(const KnapsackSearchNodeForCuts *parent, const KnapsackAssignmentForCuts &assignment)
const KnapsackSearchNodeForCuts & from() const
const KnapsackSearchNodeForCuts & via() const
const KnapsackSearchNodeForCuts & to() const
KnapsackSearchPathForCuts(const KnapsackSearchNodeForCuts *from, const KnapsackSearchNodeForCuts *to)
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)
bool UpdateState(bool revert, const KnapsackAssignmentForCuts &assignment)
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
int64_t int64
const double profit_max
const double kInfinity
Definition: lp_types.h:83
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)
int64 weight
Definition: pack.cc:509
int64 capacity