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
21
22namespace operations_research {
23namespace {
24
25const int kNoSelection(-1);
26const int kDefaultMasterPropagatorId(0);
27const double kInfinity = std::numeric_limits<double>::infinity();
28
29// Comparator used to sort item in decreasing efficiency order
30// (see KnapsackCapacityPropagator).
31struct 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.
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();
53 }
54 return profit_upper_bound_1 < profit_upper_bound_2;
55 }
56};
57
58using 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 -----
104
105void 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
137void 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;
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;
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
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()) {
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
286void 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.
387bool 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
406double 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
412bool 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
450bool 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
459void 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
KnapsackPropagatorForCuts(const KnapsackStateForCuts *state)
bool Update(bool revert, const KnapsackAssignmentForCuts &assignment)
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)
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)
STL namespace.
int64 weight
Definition: pack.cc:509
int64 capacity