OR-Tools  8.2
knapsack_solver_for_cuts.h
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
14// This library solves 0-1 one-dimensional knapsack problems with fractional
15// profits and weights using the branch and bound algorithm. Note that
16// algorithms/knapsack_solver uses 'int64' for the profits and the weights.
17// TODO(user): Merge this code with algorithms/knapsack_solver.
18//
19// Given n items, each with a profit and a weight and a knapsack of
20// capacity c, the goal is to find a subset of the items which fits inside c
21// and maximizes the total profit.
22// Without loss of generality, profits and weights are assumed to be positive.
23//
24// From a mathematical point of view, the one-dimensional knapsack problem
25// can be modeled by linear constraint:
26// Sum(i:1..n)(weight_i * item_i) <= c,
27// where item_i is a 0-1 integer variable.
28// The goal is to maximize: Sum(i:1..n)(profit_i * item_i).
29//
30// Example Usage:
31// std::vector<double> profits = {0, 0.5, 0.4, 1, 1, 1.1};
32// std::vector<double> weights = {9, 6, 2, 1.5, 1.5, 1.5};
33// KnapsackSolverForCuts solver("solver");
34// solver.Init(profits, weights, capacity);
35// bool is_solution_optimal = false;
36// std::unique_ptr<TimeLimit> time_limit =
37// absl::make_unique<TimeLimit>(time_limit_seconds); // Set the time limit.
38// const double profit = solver.Solve(time_limit.get(), &is_solution_optimal);
39// const int number_of_items(profits.size());
40// for (int item_id(0); item_id < number_of_items; ++item_id) {
41// solver.best_solution(item_id); // Access the solution.
42// }
43
44#ifndef OR_TOOLS_ALGORITHMS_KNAPSACK_SOLVER_FOR_CUTS_H_
45#define OR_TOOLS_ALGORITHMS_KNAPSACK_SOLVER_FOR_CUTS_H_
46
47#include <memory>
48#include <string>
49#include <vector>
50
51#include "absl/memory/memory.h"
55
56namespace operations_research {
57
58// ----- KnapsackAssignementForCuts -----
59// KnapsackAssignementForCuts is a small struct used to pair an item with
60// its assignment. It is mainly used for search nodes and updates.
64
66 bool is_in;
67};
68
69// ----- KnapsackItemForCuts -----
70// KnapsackItemForCuts is a small struct to pair an item weight with its
71// corresponding profit.
72// The aim of the knapsack problem is to pack as many valuable items as
73// possible. A straight forward heuristic is to take those with the greatest
74// profit-per-unit-weight. This ratio is called efficiency in this
75// implementation. So items will be grouped in vectors, and sorted by
76// decreasing efficiency.
78 KnapsackItemForCuts(int id, double weight, double profit)
79 : id(id), weight(weight), profit(profit) {}
80
81 double GetEfficiency(double profit_max) const {
82 return (weight > 0) ? profit / weight : profit_max;
83 }
84
85 // The 'id' field is used to retrieve the initial item in order to
86 // communicate with other propagators and state.
87 const int id;
88 const double weight;
89 const double profit;
90};
91using KnapsackItemForCutsPtr = std::unique_ptr<KnapsackItemForCuts>;
92
93// ----- KnapsackSearchNodeForCuts -----
94// KnapsackSearchNodeForCuts is a class used to describe a decision in the
95// decision search tree.
96// The node is defined by a pointer to the parent search node and an
97// assignment (see KnapsackAssignementForCuts).
98// As the current state is not explicitly stored in a search node, one should
99// go through the search tree to incrementally build a partial solution from
100// a previous search node.
102 public:
105
108 delete;
109
110 int depth() const { return depth_; }
111 const KnapsackSearchNodeForCuts* const parent() const { return parent_; }
112 const KnapsackAssignmentForCuts& assignment() const { return assignment_; }
113
114 double current_profit() const { return current_profit_; }
115 void set_current_profit(double profit) { current_profit_ = profit; }
116
117 double profit_upper_bound() const { return profit_upper_bound_; }
118 void set_profit_upper_bound(double profit) { profit_upper_bound_ = profit; }
119
120 int next_item_id() const { return next_item_id_; }
121 void set_next_item_id(int id) { next_item_id_ = id; }
122
123 private:
124 // 'depth_' is used to navigate efficiently through the search tree.
125 int depth_;
126 const KnapsackSearchNodeForCuts* const parent_;
127 KnapsackAssignmentForCuts assignment_;
128
129 // 'current_profit_' and 'profit_upper_bound_' fields are used to sort search
130 // nodes using a priority queue. That allows to pop the node with the best
131 // upper bound, and more importantly to stop the search when optimality is
132 // proved.
133 double current_profit_;
134 double profit_upper_bound_;
135
136 // 'next_item_id_' field allows to avoid an O(number_of_items) scan to find
137 // next item to select. This is done for free by the upper bound computation.
138 int next_item_id_;
139};
140
141// ----- KnapsackSearchPathForCuts -----
142// KnapsackSearchPathForCuts is a small class used to represent the path between
143// a node to another node in the search tree.
144// As the solution state is not stored for each search node, the state should
145// be rebuilt at each node. One simple solution is to apply all decisions
146// between the node 'to' and the root. This can be computed in
147// O(number_of_items).
148//
149// However, it is possible to achieve better average complexity. Two
150// consecutively explored nodes are usually close enough (i.e., much less than
151// number_of_items) to benefit from an incremental update from the node
152// 'from' to the node 'to'.
153//
154// The 'via' field is the common parent of 'from' field and 'to' field.
155// So the state can be built by reverting all decisions from 'from' to 'via'
156// and then applying all decisions from 'via' to 'to'.
158 public:
161
164 delete;
165
166 void Init();
167 const KnapsackSearchNodeForCuts& from() const { return *from_; }
168 const KnapsackSearchNodeForCuts& via() const { return *via_; }
169 const KnapsackSearchNodeForCuts& to() const { return *to_; }
170
171 private:
172 const KnapsackSearchNodeForCuts* from_;
173 const KnapsackSearchNodeForCuts* via_; // Computed in 'Init'.
174 const KnapsackSearchNodeForCuts* to_;
175};
176
177// From the given node, this method moves up the tree and returns the node at
178// given depth.
179const KnapsackSearchNodeForCuts* MoveUpToDepth(
180 const KnapsackSearchNodeForCuts* node, int depth);
181
182// ----- KnapsackStateForCuts -----
183// KnapsackStateForCuts represents a partial solution to the knapsack problem.
185 public:
187
190
191 // Initializes vectors with number_of_items set to false (i.e. not bound yet).
192 void Init(int number_of_items);
193
194 // Updates the state by applying or reverting a decision.
195 // Returns false if fails, i.e. trying to apply an inconsistent decision
196 // to an already assigned item.
197 bool UpdateState(bool revert, const KnapsackAssignmentForCuts& assignment);
198
199 int GetNumberOfItems() const { return is_bound_.size(); }
200 bool is_bound(int id) const { return is_bound_.at(id); }
201 bool is_in(int id) const { return is_in_.at(id); }
202
203 private:
204 // Vectors 'is_bound_' and 'is_in_' contain a boolean value for each item.
205 // 'is_bound_(item_i)' is false when there is no decision for item_i yet.
206 // When item_i is bound, 'is_in_(item_i)' represents the presence (true) or
207 // the absence (false) of item_i in the current solution.
208 std::vector<bool> is_bound_;
209 std::vector<bool> is_in_;
210};
211
212// ----- KnapsackPropagatorForCuts -----
213// KnapsackPropagatorForCuts is used to enforce a capacity constraint.
214// It is supposed to compute profit lower and upper bounds, and get the next
215// item to select, it can be seen as a 0-1 Knapsack solver. The most efficient
216// way to compute the upper bound is to iterate on items in
217// profit-per-unit-weight decreasing order. The break item is commonly defined
218// as the first item for which there is not enough remaining capacity. Selecting
219// this break item as the next-item-to-assign usually gives the best results
220// (see Greenberg & Hegerich).
221//
222// This is exactly what is implemented in this class.
223//
224// It is possible to compute a better profit lower bound almost for free. During
225// the scan to find the break element all unbound items are added just as if
226// they were part of the current solution. This is used in both
227// ComputeProfitBounds() and CopyCurrentSolution(). For incrementality reasons,
228// the ith item should be accessible in O(1). That's the reason why the item
229// vector has to be duplicated 'sorted_items_'.
231 public:
234
237 delete;
238
239 // Initializes the data structure and then calls InitPropagator.
240 void Init(const std::vector<double>& profits,
241 const std::vector<double>& weights, double capacity);
242
243 // Updates data structure. Returns false on failure.
244 bool Update(bool revert, const KnapsackAssignmentForCuts& assignment);
245 // ComputeProfitBounds should set 'profit_lower_bound_' and
246 // 'profit_upper_bound_' which are constraint specific.
247 void ComputeProfitBounds();
248 // Returns the id of next item to assign.
249 // Returns kNoSelection when all items are bound.
250 int GetNextItemId() const { return break_item_id_; }
251
252 double current_profit() const { return current_profit_; }
253 double profit_lower_bound() const { return profit_lower_bound_; }
254 double profit_upper_bound() const { return profit_upper_bound_; }
255
256 // Copies the current state into 'solution'.
257 // All unbound items are set to false (i.e. not in the knapsack).
258 void CopyCurrentStateToSolution(std::vector<bool>* solution) const;
259
260 // Initializes the propagator. This method is called by Init() after filling
261 // the fields defined in this class.
262 void InitPropagator();
263
264 const KnapsackStateForCuts& state() const { return *state_; }
265 const std::vector<KnapsackItemForCutsPtr>& items() const { return items_; }
266
267 void set_profit_lower_bound(double profit) { profit_lower_bound_ = profit; }
268 void set_profit_upper_bound(double profit) { profit_upper_bound_ = profit; }
269
270 private:
271 // An obvious additional profit upper bound corresponds to the linear
272 // relaxation: remaining_capacity * efficiency of the break item.
273 // It is possible to do better in O(1), using Martello-Toth bound U2.
274 // The main idea is to enforce integrality constraint on the break item,
275 // i.e. either the break item is part of the solution, or it is not.
276 // So basically the linear relaxation is done on the item before the break
277 // item, or the one after the break item. This is what GetAdditionalProfit
278 // method implements.
279 double GetAdditionalProfitUpperBound(double remaining_capacity,
280 int break_item_id) const;
281
282 double capacity_;
283 double consumed_capacity_;
284 int break_item_id_;
285 std::vector<KnapsackItemForCutsPtr> sorted_items_;
286 double profit_max_;
287 std::vector<KnapsackItemForCutsPtr> items_;
288 double current_profit_;
289 double profit_lower_bound_;
290 double profit_upper_bound_;
291 const KnapsackStateForCuts* const state_;
292};
293
294// ----- KnapsackSolverForCuts -----
295// KnapsackSolverForCuts is the one-dimensional knapsack solver class.
296// In the current implementation, the next item to assign is given by the
297// master propagator. Using SetMasterPropagator allows changing the default
298// (propagator of the first dimension).
300 public:
301 explicit KnapsackSolverForCuts(std::string solver_name);
302
305
306 // Initializes the solver and enters the problem to be solved.
307 void Init(const std::vector<double>& profits,
308 const std::vector<double>& weights, const double capacity);
309 int GetNumberOfItems() const { return state_.GetNumberOfItems(); }
310
311 // Gets the lower and the upper bound when the item is in or out of the
312 // knapsack. To ensure objects are correctly initialized, this method should
313 // not be called before Init().
314 void GetLowerAndUpperBoundWhenItem(int item_id, bool is_item_in,
315 double* lower_bound, double* upper_bound);
316
317 // Get the best upper bound found so far.
318 double GetUpperBound() { return GetAggregatedProfitUpperBound(); }
319
320 // The solver stops if a solution with profit better than
321 // 'solution_lower_bound_threshold' is found.
323 const double solution_lower_bound_threshold) {
324 solution_lower_bound_threshold_ = solution_lower_bound_threshold;
325 }
326
327 // The solver stops if the upper bound on profit drops below
328 // 'solution_upper_bound_threshold'.
330 const double solution_upper_bound_threshold) {
331 solution_upper_bound_threshold_ = solution_upper_bound_threshold;
332 }
333
334 // Stops the knapsack solver after processing 'node_limit' nodes.
335 void set_node_limit(const int64 node_limit) { node_limit_ = node_limit; }
336
337 // Solves the problem and returns the profit of the best solution found.
338 double Solve(TimeLimit* time_limit, bool* is_solution_optimal);
339 // Returns true if the item 'item_id' is packed in the optimal knapsack.
340 bool best_solution(int item_id) const {
341 DCHECK(item_id < best_solution_.size());
342 return best_solution_[item_id];
343 }
344
345 const std::string& GetName() const { return solver_name_; }
346
347 private:
348 // Updates propagator reverting/applying all decision on the path. Returns
349 // true if the propagation fails. Note that even if it fails, propagator
350 // should be updated to be in a stable state in order to stay incremental.
351 bool UpdatePropagators(const KnapsackSearchPathForCuts& path);
352 // Updates propagator reverting/applying one decision. Returns true if
353 // the propagation fails. Note that even if it fails, propagator should
354 // be updated to be in a stable state in order to stay incremental.
355 bool IncrementalUpdate(bool revert,
356 const KnapsackAssignmentForCuts& assignment);
357 // Updates the best solution if the current solution has a better profit.
358 void UpdateBestSolution();
359
360 // Returns true if new relevant search node was added to the nodes array. That
361 // means this node should be added to the search queue too.
362 bool MakeNewNode(const KnapsackSearchNodeForCuts& node, bool is_in);
363
364 // Gets the aggregated (min) profit upper bound among all propagators.
365 double GetAggregatedProfitUpperBound();
366 double GetCurrentProfit() const { return propagator_.current_profit(); }
367 int GetNextItemId() const { return propagator_.GetNextItemId(); }
368
369 KnapsackPropagatorForCuts propagator_;
370 std::vector<std::unique_ptr<KnapsackSearchNodeForCuts>> search_nodes_;
371 KnapsackStateForCuts state_;
372 double best_solution_profit_;
373 std::vector<bool> best_solution_;
374 const std::string solver_name_;
375 double solution_lower_bound_threshold_ =
376 std::numeric_limits<double>::infinity();
377 double solution_upper_bound_threshold_ =
378 -std::numeric_limits<double>::infinity();
379 int64 node_limit_ = kint64max;
380};
381// TODO(user) : Add reduction algorithm.
382
383} // namespace operations_research
384
385#endif // OR_TOOLS_ALGORITHMS_KNAPSACK_SOLVER_FOR_CUTS_H_
#define DCHECK(condition)
Definition: base/logging.h:884
void Init(const std::vector< double > &profits, const std::vector< double > &weights, double capacity)
void CopyCurrentStateToSolution(std::vector< bool > *solution) const
KnapsackPropagatorForCuts(const KnapsackPropagatorForCuts &)=delete
KnapsackPropagatorForCuts(const KnapsackStateForCuts *state)
KnapsackPropagatorForCuts & operator=(const KnapsackPropagatorForCuts &)=delete
bool Update(bool revert, const KnapsackAssignmentForCuts &assignment)
const std::vector< KnapsackItemForCutsPtr > & items() const
KnapsackSearchNodeForCuts & operator=(const KnapsackSearchNodeForCuts &)=delete
KnapsackSearchNodeForCuts(const KnapsackSearchNodeForCuts &)=delete
const KnapsackAssignmentForCuts & assignment() const
KnapsackSearchNodeForCuts(const KnapsackSearchNodeForCuts *parent, const KnapsackAssignmentForCuts &assignment)
const KnapsackSearchNodeForCuts *const parent() const
KnapsackSearchPathForCuts & operator=(const KnapsackSearchPathForCuts &)=delete
const KnapsackSearchNodeForCuts & to() const
const KnapsackSearchNodeForCuts & via() const
const KnapsackSearchNodeForCuts & from() const
KnapsackSearchPathForCuts(const KnapsackSearchNodeForCuts *from, const KnapsackSearchNodeForCuts *to)
KnapsackSearchPathForCuts(const KnapsackSearchPathForCuts &)=delete
KnapsackSolverForCuts & operator=(const KnapsackSolverForCuts &)=delete
KnapsackSolverForCuts(const KnapsackSolverForCuts &)=delete
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 set_solution_lower_bound_threshold(const double solution_lower_bound_threshold)
void set_solution_upper_bound_threshold(const double solution_upper_bound_threshold)
KnapsackStateForCuts(const KnapsackStateForCuts &)=delete
KnapsackStateForCuts & operator=(const KnapsackStateForCuts &)=delete
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
static const int64 kint64max
int64_t int64
const int64 profit_max
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 capacity
KnapsackItemForCuts(int id, double weight, double profit)
double GetEfficiency(double profit_max) const