OR-Tools  8.2
knapsack_solver.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#ifndef OR_TOOLS_ALGORITHMS_KNAPSACK_SOLVER_H_
15#define OR_TOOLS_ALGORITHMS_KNAPSACK_SOLVER_H_
16
17#include <math.h>
18
19#include <memory>
20#include <string>
21#include <vector>
22
23#include "absl/memory/memory.h"
27#include "ortools/base/macros.h"
29
30namespace operations_research {
31
32class BaseKnapsackSolver;
33
118 public:
132
140
148
149#if defined(USE_CBC)
156#endif // USE_CBC
157
164
165#if defined(USE_SCIP)
172#endif // USE_SCIP
173
174#if defined(USE_XPRESS)
180 KNAPSACK_MULTIDIMENSION_XPRESS_MIP_SOLVER = 7,
181#endif
182
183#if defined(USE_CPLEX)
189 KNAPSACK_MULTIDIMENSION_CPLEX_MIP_SOLVER = 8,
190#endif
191 };
192
193 explicit KnapsackSolver(const std::string& solver_name);
194 KnapsackSolver(SolverType solver_type, const std::string& solver_name);
195 virtual ~KnapsackSolver();
196
200 void Init(const std::vector<int64>& profits,
201 const std::vector<std::vector<int64> >& weights,
202 const std::vector<int64>& capacities);
203
207 int64 Solve();
208
212 bool BestSolutionContains(int item_id) const;
216 bool IsSolutionOptimal() const { return is_solution_optimal_; }
217 std::string GetName() const;
218
219 bool use_reduction() const { return use_reduction_; }
220 void set_use_reduction(bool use_reduction) { use_reduction_ = use_reduction; }
221
227 void set_time_limit(double time_limit_seconds) {
228 time_limit_seconds_ = time_limit_seconds;
229 time_limit_ = absl::make_unique<TimeLimit>(time_limit_seconds_);
230 }
231
232 private:
233 // Trivial reduction of capacity constraints when the capacity is higher than
234 // the sum of the weights of the items. Returns the number of reduced items.
235 int ReduceCapacities(int num_items,
236 const std::vector<std::vector<int64> >& weights,
237 const std::vector<int64>& capacities,
238 std::vector<std::vector<int64> >* reduced_weights,
239 std::vector<int64>* reduced_capacities);
240 int ReduceProblem(int num_items);
241 void ComputeAdditionalProfit(const std::vector<int64>& profits);
242 void InitReducedProblem(const std::vector<int64>& profits,
243 const std::vector<std::vector<int64> >& weights,
244 const std::vector<int64>& capacities);
245
246 std::unique_ptr<BaseKnapsackSolver> solver_;
247 std::vector<bool> known_value_;
248 std::vector<bool> best_solution_;
249 bool is_solution_optimal_ = false;
250 std::vector<int> mapping_reduced_item_id_;
251 bool is_problem_solved_;
252 int64 additional_profit_;
253 bool use_reduction_;
254 double time_limit_seconds_;
255 std::unique_ptr<TimeLimit> time_limit_;
256
257 DISALLOW_COPY_AND_ASSIGN(KnapsackSolver);
258};
259
260#if !defined(SWIG)
261// The following code defines needed classes for the KnapsackGenericSolver
262// class which is the entry point to extend knapsack with new constraints such
263// as conflicts between items.
264//
265// Constraints are enforced using KnapsackPropagator objects, in the current
266// code there is one propagator per dimension (KnapsackCapacityPropagator).
267// One of those propagators, named master propagator, is used to guide the
268// search, i.e. decides which item should be assigned next.
269// Roughly speaking the search algorithm is:
270// - While not optimal
271// - Select next search node to expand
272// - Select next item_i to assign (using master propagator)
273// - Generate a new search node where item_i is in the knapsack
274// - Check validity of this new partial solution (using propagators)
275// - If valid, add this new search node to the search
276// - Generate a new search node where item_i is not in the knapsack
277// - Check validity of this new partial solution (using propagators)
278// - If valid, add this new search node to the search
279//
280// TODO(user): Add a new propagator class for conflict constraint.
281// TODO(user): Add a new propagator class used as a guide when the problem has
282// several dimensions.
283
284// ----- KnapsackAssignement -----
285// KnapsackAssignement is a small struct used to pair an item with its
286// assignment. It is mainly used for search nodes and updates.
288 KnapsackAssignment(int _item_id, bool _is_in)
289 : item_id(_item_id), is_in(_is_in) {}
291 bool is_in;
292};
293
294// ----- KnapsackItem -----
295// KnapsackItem is a small struct to pair an item weight with its
296// corresponding profit.
297// The aim of the knapsack problem is to pack as many valuable items as
298// possible. A straight forward heuristic is to take those with the greatest
299// profit-per-unit-weight. This ratio is called efficiency in this
300// implementation. So items will be grouped in vectors, and sorted by
301// decreasing efficiency.
302// Note that profits are duplicated for each dimension. This is done to
303// simplify the code, especially the GetEfficiency method and vector sorting.
304// As there usually are only few dimensions, the overhead should not be an
305// issue.
307 KnapsackItem(int _id, int64 _weight, int64 _profit)
308 : id(_id), weight(_weight), profit(_profit) {}
310 return (weight > 0)
311 ? static_cast<double>(profit) / static_cast<double>(weight)
312 : static_cast<double>(profit_max);
313 }
314
315 // The 'id' field is used to retrieve the initial item in order to
316 // communicate with other propagators and state.
317 const int id;
320};
322
323// ----- KnapsackSearchNode -----
324// KnapsackSearchNode is a class used to describe a decision in the decision
325// search tree.
326// The node is defined by a pointer to the parent search node and an
327// assignment (see KnapsackAssignement).
328// As the current state is not explicitly stored in a search node, one should
329// go through the search tree to incrementally build a partial solution from
330// a previous search node.
332 public:
335 int depth() const { return depth_; }
336 const KnapsackSearchNode* const parent() const { return parent_; }
337 const KnapsackAssignment& assignment() const { return assignment_; }
338
339 int64 current_profit() const { return current_profit_; }
340 void set_current_profit(int64 profit) { current_profit_ = profit; }
341
342 int64 profit_upper_bound() const { return profit_upper_bound_; }
343 void set_profit_upper_bound(int64 profit) { profit_upper_bound_ = profit; }
344
345 int next_item_id() const { return next_item_id_; }
346 void set_next_item_id(int id) { next_item_id_ = id; }
347
348 private:
349 // 'depth' field is used to navigate efficiently through the search tree
350 // (see KnapsackSearchPath).
351 int depth_;
352 const KnapsackSearchNode* const parent_;
353 KnapsackAssignment assignment_;
354
355 // 'current_profit' and 'profit_upper_bound' fields are used to sort search
356 // nodes using a priority queue. That allows to pop the node with the best
357 // upper bound, and more importantly to stop the search when optimality is
358 // proved.
359 int64 current_profit_;
360 int64 profit_upper_bound_;
361
362 // 'next_item_id' field allows to avoid an O(number_of_items) scan to find
363 // next item to select. This is done for free by the upper bound computation.
364 int next_item_id_;
365
366 DISALLOW_COPY_AND_ASSIGN(KnapsackSearchNode);
367};
368
369// ----- KnapsackSearchPath -----
370// KnapsackSearchPath is a small class used to represent the path between a
371// node to another node in the search tree.
372// As the solution state is not stored for each search node, the state should
373// be rebuilt at each node. One simple solution is to apply all decisions
374// between the node 'to' and the root. This can be computed in
375// O(number_of_items).
376//
377// However, it is possible to achieve better average complexity. Two
378// consecutively explored nodes are usually close enough (i.e., much less than
379// number_of_items) to benefit from an incremental update from the node
380// 'from' to the node 'to'.
381//
382// The 'via' field is the common parent of 'from' field and 'to' field.
383// So the state can be built by reverting all decisions from 'from' to 'via'
384// and then applying all decisions from 'via' to 'to'.
386 public:
388 const KnapsackSearchNode& to);
389 void Init();
390 const KnapsackSearchNode& from() const { return from_; }
391 const KnapsackSearchNode& via() const { return *via_; }
392 const KnapsackSearchNode& to() const { return to_; }
394 int depth) const;
395
396 private:
397 const KnapsackSearchNode& from_;
398 const KnapsackSearchNode* via_; // Computed in 'Init'.
399 const KnapsackSearchNode& to_;
400
401 DISALLOW_COPY_AND_ASSIGN(KnapsackSearchPath);
402};
403
404// ----- KnapsackState -----
405// KnapsackState represents a partial solution to the knapsack problem.
407 public:
409
410 // Initializes vectors with number_of_items set to false (i.e. not bound yet).
411 void Init(int number_of_items);
412 // Updates the state by applying or reverting a decision.
413 // Returns false if fails, i.e. trying to apply an inconsistent decision
414 // to an already assigned item.
415 bool UpdateState(bool revert, const KnapsackAssignment& assignment);
416
417 int GetNumberOfItems() const { return is_bound_.size(); }
418 bool is_bound(int id) const { return is_bound_.at(id); }
419 bool is_in(int id) const { return is_in_.at(id); }
420
421 private:
422 // Vectors 'is_bound_' and 'is_in_' contain a boolean value for each item.
423 // 'is_bound_(item_i)' is false when there is no decision for item_i yet.
424 // When item_i is bound, 'is_in_(item_i)' represents the presence (true) or
425 // the absence (false) of item_i in the current solution.
426 std::vector<bool> is_bound_;
427 std::vector<bool> is_in_;
428
429 DISALLOW_COPY_AND_ASSIGN(KnapsackState);
430};
431
432// ----- KnapsackPropagator -----
433// KnapsackPropagator is the base class for modeling and propagating a
434// constraint given an assignment.
435//
436// When some work has to be done both by the base and the derived class,
437// a protected pure virtual method ending by 'Propagator' is defined.
438// For instance, 'Init' creates a vector of items, and then calls
439// 'InitPropagator' to let the derived class perform its own initialization.
441 public:
442 explicit KnapsackPropagator(const KnapsackState& state);
443 virtual ~KnapsackPropagator();
444
445 // Initializes data structure and then calls InitPropagator.
446 void Init(const std::vector<int64>& profits,
447 const std::vector<int64>& weights);
448
449 // Updates data structure and then calls UpdatePropagator.
450 // Returns false when failure.
451 bool Update(bool revert, const KnapsackAssignment& assignment);
452 // ComputeProfitBounds should set 'profit_lower_bound_' and
453 // 'profit_upper_bound_' which are constraint specific.
454 virtual void ComputeProfitBounds() = 0;
455 // Returns the id of next item to assign.
456 // Returns kNoSelection when all items are bound.
457 virtual int GetNextItemId() const = 0;
458
459 int64 current_profit() const { return current_profit_; }
460 int64 profit_lower_bound() const { return profit_lower_bound_; }
461 int64 profit_upper_bound() const { return profit_upper_bound_; }
462
463 // Copies the current state into 'solution'.
464 // All unbound items are set to false (i.e. not in the knapsack).
465 // When 'has_one_propagator' is true, CopyCurrentSolutionPropagator is called
466 // to have a better solution. When there is only one propagator
467 // there is no need to check the solution with other propagators, so the
468 // partial solution can be smartly completed.
469 void CopyCurrentStateToSolution(bool has_one_propagator,
470 std::vector<bool>* solution) const;
471
472 protected:
473 // Initializes data structure. This method is called after initialization
474 // of KnapsackPropagator data structure.
475 virtual void InitPropagator() = 0;
476
477 // Updates internal data structure incrementally. This method is called
478 // after update of KnapsackPropagator data structure.
479 virtual bool UpdatePropagator(bool revert,
480 const KnapsackAssignment& assignment) = 0;
481
482 // Copies the current state into 'solution'.
483 // Only unbound items have to be copied as CopyCurrentSolution was already
484 // called with current state.
485 // This method is useful when a propagator is able to find a better solution
486 // than the blind instantiation to false of unbound items.
488 std::vector<bool>* solution) const = 0;
489
490 const KnapsackState& state() const { return state_; }
491 const std::vector<KnapsackItemPtr>& items() const { return items_; }
492
493 void set_profit_lower_bound(int64 profit) { profit_lower_bound_ = profit; }
494 void set_profit_upper_bound(int64 profit) { profit_upper_bound_ = profit; }
495
496 private:
497 std::vector<KnapsackItemPtr> items_;
498 int64 current_profit_;
499 int64 profit_lower_bound_;
500 int64 profit_upper_bound_;
501 const KnapsackState& state_;
502
503 DISALLOW_COPY_AND_ASSIGN(KnapsackPropagator);
504};
505
506// ----- KnapsackCapacityPropagator -----
507// KnapsackCapacityPropagator is a KnapsackPropagator used to enforce
508// a capacity constraint.
509// As a KnapsackPropagator is supposed to compute profit lower and upper
510// bounds, and get the next item to select, it can be seen as a 0-1 Knapsack
511// solver. The most efficient way to compute the upper bound is to iterate on
512// items in profit-per-unit-weight decreasing order. The break item is
513// commonly defined as the first item for which there is not enough remaining
514// capacity. Selecting this break item as the next-item-to-assign usually
515// gives the best results (see Greenberg & Hegerich).
516//
517// This is exactly what is implemented in this class.
518//
519// When there is only one propagator, it is possible to compute a better
520// profit lower bound almost for free. During the scan to find the
521// break element all unbound items are added just as if they were part of
522// the current solution. This is used in both ComputeProfitBounds and
523// CopyCurrentSolutionPropagator.
524// For incrementality reasons, the ith item should be accessible in O(1). That's
525// the reason why the item vector has to be duplicated 'sorted_items_'.
527 public:
530 void ComputeProfitBounds() override;
531 int GetNextItemId() const override { return break_item_id_; }
532
533 protected:
534 // Initializes KnapsackCapacityPropagator (e.g., sort items in decreasing
535 // order).
536 void InitPropagator() override;
537 // Updates internal data structure incrementally (i.e., 'consumed_capacity_')
538 // to avoid a O(number_of_items) scan.
539 bool UpdatePropagator(bool revert,
540 const KnapsackAssignment& assignment) override;
542 std::vector<bool>* solution) const override;
543
544 private:
545 // An obvious additional profit upper bound corresponds to the linear
546 // relaxation: remaining_capacity * efficiency of the break item.
547 // It is possible to do better in O(1), using Martello-Toth bound U2.
548 // The main idea is to enforce integrality constraint on the break item,
549 // ie. either the break item is part of the solution, either it is not.
550 // So basically the linear relaxation is done on the item before the break
551 // item, or the one after the break item.
552 // This is what GetAdditionalProfit method implements.
553 int64 GetAdditionalProfit(int64 remaining_capacity, int break_item_id) const;
554
555 const int64 capacity_;
556 int64 consumed_capacity_;
557 int break_item_id_;
558 std::vector<KnapsackItemPtr> sorted_items_;
559 int64 profit_max_;
560
561 DISALLOW_COPY_AND_ASSIGN(KnapsackCapacityPropagator);
562};
563
564// ----- BaseKnapsackSolver -----
565// This is the base class for knapsack solvers.
567 public:
568 explicit BaseKnapsackSolver(const std::string& solver_name)
569 : solver_name_(solver_name) {}
571
572 // Initializes the solver and enters the problem to be solved.
573 virtual void Init(const std::vector<int64>& profits,
574 const std::vector<std::vector<int64> >& weights,
575 const std::vector<int64>& capacities) = 0;
576
577 // Gets the lower and upper bound when the item is in or out of the knapsack.
578 // To ensure objects are correctly initialized, this method should not be
579 // called before ::Init.
580 virtual void GetLowerAndUpperBoundWhenItem(int item_id, bool is_item_in,
581 int64* lower_bound,
582 int64* upper_bound);
583
584 // Solves the problem and returns the profit of the optimal solution.
585 virtual int64 Solve(TimeLimit* time_limit, bool* is_solution_optimal) = 0;
586
587 // Returns true if the item 'item_id' is packed in the optimal knapsack.
588 virtual bool best_solution(int item_id) const = 0;
589
590 virtual std::string GetName() const { return solver_name_; }
591
592 private:
593 const std::string solver_name_;
594};
595
596// ----- KnapsackGenericSolver -----
597// KnapsackGenericSolver is the multi-dimensional knapsack solver class.
598// In the current implementation, the next item to assign is given by the
599// master propagator. Using SetMasterPropagator allows changing the default
600// (propagator of the first dimension), and selecting another dimension when
601// more constrained.
602// TODO(user): In the case of a multi-dimensional knapsack problem, implement
603// an aggregated propagator to combine all dimensions and give a better guide
604// to select the next item (see, for instance, Dobson's aggregated efficiency).
606 public:
607 explicit KnapsackGenericSolver(const std::string& solver_name);
608 ~KnapsackGenericSolver() override;
609
610 // Initializes the solver and enters the problem to be solved.
611 void Init(const std::vector<int64>& profits,
612 const std::vector<std::vector<int64> >& weights,
613 const std::vector<int64>& capacities) override;
614 int GetNumberOfItems() const { return state_.GetNumberOfItems(); }
615 void GetLowerAndUpperBoundWhenItem(int item_id, bool is_item_in,
616 int64* lower_bound,
617 int64* upper_bound) override;
618
619 // Sets which propagator should be used to guide the search.
620 // 'master_propagator_id' should be in 0..p-1 with p the number of
621 // propagators.
622 void set_master_propagator_id(int master_propagator_id) {
623 master_propagator_id_ = master_propagator_id;
624 }
625
626 // Solves the problem and returns the profit of the optimal solution.
627 int64 Solve(TimeLimit* time_limit, bool* is_solution_optimal) override;
628 // Returns true if the item 'item_id' is packed in the optimal knapsack.
629 bool best_solution(int item_id) const override {
630 return best_solution_.at(item_id);
631 }
632
633 private:
634 // Clears internal data structure.
635 void Clear();
636
637 // Updates all propagators reverting/applying all decision on the path.
638 // Returns true if fails. Note that, even if fails, all propagators should
639 // be updated to be in a stable state in order to stay incremental.
640 bool UpdatePropagators(const KnapsackSearchPath& path);
641 // Updates all propagators reverting/applying one decision.
642 // Return true if fails. Note that, even if fails, all propagators should
643 // be updated to be in a stable state in order to stay incremental.
644 bool IncrementalUpdate(bool revert, const KnapsackAssignment& assignment);
645 // Updates the best solution if the current solution has a better profit.
646 void UpdateBestSolution();
647
648 // Returns true if new relevant search node was added to the nodes array, that
649 // means this node should be added to the search queue too.
650 bool MakeNewNode(const KnapsackSearchNode& node, bool is_in);
651
652 // Gets the aggregated (min) profit upper bound among all propagators.
653 int64 GetAggregatedProfitUpperBound() const;
654 bool HasOnePropagator() const { return propagators_.size() == 1; }
655 int64 GetCurrentProfit() const {
656 return propagators_.at(master_propagator_id_)->current_profit();
657 }
658 int64 GetNextItemId() const {
659 return propagators_.at(master_propagator_id_)->GetNextItemId();
660 }
661
662 std::vector<KnapsackPropagator*> propagators_;
663 int master_propagator_id_;
664 std::vector<KnapsackSearchNode*> search_nodes_;
665 KnapsackState state_;
666 int64 best_solution_profit_;
667 std::vector<bool> best_solution_;
668
669 DISALLOW_COPY_AND_ASSIGN(KnapsackGenericSolver);
670};
671#endif // SWIG
672} // namespace operations_research
673
674#endif // OR_TOOLS_ALGORITHMS_KNAPSACK_SOLVER_H_
virtual int64 Solve(TimeLimit *time_limit, bool *is_solution_optimal)=0
virtual void GetLowerAndUpperBoundWhenItem(int item_id, bool is_item_in, int64 *lower_bound, int64 *upper_bound)
BaseKnapsackSolver(const std::string &solver_name)
virtual void Init(const std::vector< int64 > &profits, const std::vector< std::vector< int64 > > &weights, const std::vector< int64 > &capacities)=0
virtual std::string GetName() const
virtual bool best_solution(int item_id) const =0
KnapsackCapacityPropagator(const KnapsackState &state, int64 capacity)
bool UpdatePropagator(bool revert, const KnapsackAssignment &assignment) override
void CopyCurrentStateToSolutionPropagator(std::vector< bool > *solution) const override
KnapsackGenericSolver(const std::string &solver_name)
void GetLowerAndUpperBoundWhenItem(int item_id, bool is_item_in, int64 *lower_bound, int64 *upper_bound) override
void set_master_propagator_id(int master_propagator_id)
void Init(const std::vector< int64 > &profits, const std::vector< std::vector< int64 > > &weights, const std::vector< int64 > &capacities) override
bool best_solution(int item_id) const override
int64 Solve(TimeLimit *time_limit, bool *is_solution_optimal) override
void CopyCurrentStateToSolution(bool has_one_propagator, std::vector< bool > *solution) const
virtual bool UpdatePropagator(bool revert, const KnapsackAssignment &assignment)=0
const std::vector< KnapsackItemPtr > & items() const
virtual int GetNextItemId() const =0
void Init(const std::vector< int64 > &profits, const std::vector< int64 > &weights)
virtual void CopyCurrentStateToSolutionPropagator(std::vector< bool > *solution) const =0
KnapsackPropagator(const KnapsackState &state)
bool Update(bool revert, const KnapsackAssignment &assignment)
const KnapsackState & state() const
const KnapsackSearchNode *const parent() const
KnapsackSearchNode(const KnapsackSearchNode *const parent, const KnapsackAssignment &assignment)
const KnapsackAssignment & assignment() const
const KnapsackSearchNode * MoveUpToDepth(const KnapsackSearchNode &node, int depth) const
KnapsackSearchPath(const KnapsackSearchNode &from, const KnapsackSearchNode &to)
const KnapsackSearchNode & from() const
const KnapsackSearchNode & via() const
const KnapsackSearchNode & to() const
This library solves knapsack problems.
bool BestSolutionContains(int item_id) const
Returns true if the item 'item_id' is packed in the optimal knapsack.
int64 Solve()
Solves the problem and returns the profit of the optimal solution.
KnapsackSolver(const std::string &solver_name)
void set_time_limit(double time_limit_seconds)
Time limit in seconds.
void Init(const std::vector< int64 > &profits, const std::vector< std::vector< int64 > > &weights, const std::vector< int64 > &capacities)
Initializes the solver and enters the problem to be solved.
SolverType
Enum controlling which underlying algorithm is used.
@ KNAPSACK_MULTIDIMENSION_SCIP_MIP_SOLVER
SCIP based solver.
@ KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER
Generic Solver.
@ KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER
Dynamic Programming approach for single dimension problems.
@ KNAPSACK_64ITEMS_SOLVER
Optimized method for single dimension small problems.
@ KNAPSACK_BRUTE_FORCE_SOLVER
Brute force method.
@ KNAPSACK_MULTIDIMENSION_CBC_MIP_SOLVER
CBC Based Solver.
bool IsSolutionOptimal() const
Returns true if the solution was proven optimal.
void set_use_reduction(bool use_reduction)
void Init(int number_of_items)
bool UpdateState(bool revert, const KnapsackAssignment &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 int64 profit_max
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
KnapsackItem * KnapsackItemPtr
int64 capacity
KnapsackAssignment(int _item_id, bool _is_in)
double GetEfficiency(int64 profit_max) const
KnapsackItem(int _id, int64 _weight, int64 _profit)