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"
52 #include "ortools/base/int_type.h"
53 #include "ortools/base/logging.h"
55 
56 namespace 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.
63  : item_id(item_id), is_in(is_in) {}
64 
65  int item_id;
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 };
91 using 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.
179 const 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
const std::vector< KnapsackItemForCutsPtr > & items() const
KnapsackPropagatorForCuts(const KnapsackPropagatorForCuts &)=delete
KnapsackPropagatorForCuts(const KnapsackStateForCuts *state)
bool Update(bool revert, const KnapsackAssignmentForCuts &assignment)
KnapsackPropagatorForCuts & operator=(const KnapsackPropagatorForCuts &)=delete
const KnapsackSearchNodeForCuts *const parent() const
KnapsackSearchNodeForCuts(const KnapsackSearchNodeForCuts &)=delete
KnapsackSearchNodeForCuts & operator=(const KnapsackSearchNodeForCuts &)=delete
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)
KnapsackSearchPathForCuts & operator=(const KnapsackSearchPathForCuts &)=delete
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
bool UpdateState(bool revert, const KnapsackAssignmentForCuts &assignment)
KnapsackStateForCuts & operator=(const KnapsackStateForCuts &)=delete
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