knapsack_solver.h

Go to the documentation of this file.

// Copyright 2010-2025 Google LLC
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
 
#ifndef ORTOOLS_ALGORITHMS_KNAPSACK_SOLVER_H_
#define ORTOOLS_ALGORITHMS_KNAPSACK_SOLVER_H_
 
#include <cstdint>
#include <memory>
#include <string>
#include <vector>
 
#include "absl/strings/string_view.h"
#include "ortools/util/time_limit.h"
 
namespace operations_research {
 
class BaseKnapsackSolver;

class KnapsackSolver {
 public:
  enum SolverType {
    KNAPSACK_BRUTE_FORCE_SOLVER = 0,

    KNAPSACK_64ITEMS_SOLVER = 1,

    KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER = 2,

    KNAPSACK_MULTIDIMENSION_CBC_MIP_SOLVER = 3,

    KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER = 5,

    KNAPSACK_MULTIDIMENSION_SCIP_MIP_SOLVER = 6,

    KNAPSACK_MULTIDIMENSION_XPRESS_MIP_SOLVER = 7,

    KNAPSACK_MULTIDIMENSION_CPLEX_MIP_SOLVER = 8,

    KNAPSACK_DIVIDE_AND_CONQUER_SOLVER = 9,

    KNAPSACK_MULTIDIMENSION_CP_SAT_SOLVER = 10,
  };
 
  explicit KnapsackSolver(const std::string& solver_name);
  KnapsackSolver(SolverType solver_type, const std::string& solver_name);
 
#ifndef SWIG
  // This type is neither copyable nor movable.
  KnapsackSolver(const KnapsackSolver&) = delete;
  KnapsackSolver& operator=(const KnapsackSolver&) = delete;
#endif
 
  virtual ~KnapsackSolver();

  void Init(const std::vector<int64_t>& profits,
            const std::vector<std::vector<int64_t> >& weights,
            const std::vector<int64_t>& capacities);

  int64_t Solve();

  bool BestSolutionContains(int item_id) const;
  bool IsSolutionOptimal() const { return is_solution_optimal_; }
  std::string GetName() const;
 
  bool use_reduction() const { return use_reduction_; }
  void set_use_reduction(bool use_reduction) { use_reduction_ = use_reduction; }

  void set_time_limit(double time_limit_seconds) {
    time_limit_seconds_ = time_limit_seconds;
    time_limit_ = std::make_unique<TimeLimit>(time_limit_seconds_);
  }
 
 private:
  int ReduceCapacities(int num_items,
                       const std::vector<std::vector<int64_t> >& weights,
                       const std::vector<int64_t>& capacities,
                       std::vector<std::vector<int64_t> >* reduced_weights,
                       std::vector<int64_t>* reduced_capacities);
  int ReduceProblem(int num_items);
  void ComputeAdditionalProfit(const std::vector<int64_t>& profits);
  void InitReducedProblem(const std::vector<int64_t>& profits,
                          const std::vector<std::vector<int64_t> >& weights,
                          const std::vector<int64_t>& capacities);
 
  std::unique_ptr<BaseKnapsackSolver> solver_;
  std::vector<bool> known_value_;
  std::vector<bool> best_solution_;
  bool is_solution_optimal_ = false;
  std::vector<int> mapping_reduced_item_id_;
  bool is_problem_solved_;
  int64_t additional_profit_;
  bool use_reduction_;
  double time_limit_seconds_;
  std::unique_ptr<TimeLimit> time_limit_;
};
 
#if !defined(SWIG)
// The following code defines needed classes for the KnapsackGenericSolver
// class which is the entry point to extend knapsack with new constraints such
// as conflicts between items.
//
// Constraints are enforced using KnapsackPropagator objects, in the current
// code there is one propagator per dimension (KnapsackCapacityPropagator).
// One of those propagators, named primary propagator, is used to guide the
// search, i.e. decides which item should be assigned next.
// Roughly speaking the search algorithm is:
//  - While not optimal
//    - Select next search node to expand
//    - Select next item_i to assign (using primary propagator)
//    - Generate a new search node where item_i is in the knapsack
//      - Check validity of this new partial solution (using propagators)
//      - If valid, add this new search node to the search
//    - Generate a new search node where item_i is not in the knapsack
//      - Check validity of this new partial solution (using propagators)
//      - If valid, add this new search node to the search
//
// TODO(user): Add a new propagator class for conflict constraint.
// TODO(user): Add a new propagator class used as a guide when the problem has
// several dimensions.
 
// ----- KnapsackAssignment -----
struct KnapsackAssignment {
  KnapsackAssignment(int _item_id, bool _is_in)
      : item_id(_item_id), is_in(_is_in) {}
  int item_id;
  bool is_in;
};
 
// ----- KnapsackItem -----
struct KnapsackItem {
  KnapsackItem(int _id, int64_t _weight, int64_t _profit)
      : id(_id), weight(_weight), profit(_profit) {}
  double GetEfficiency(int64_t profit_max) const {
    return (weight > 0)
               ? static_cast<double>(profit) / static_cast<double>(weight)
               : static_cast<double>(profit_max);
  }

  const int id;
  const int64_t weight;
  const int64_t profit;
};
typedef KnapsackItem* KnapsackItemPtr;
 
// ----- KnapsackSearchNode -----
class KnapsackSearchNode {
 public:
  KnapsackSearchNode(const KnapsackSearchNode* parent,
                     const KnapsackAssignment& assignment);
 
#ifndef SWIG
  // This type is neither copyable nor movable.
  KnapsackSearchNode(const KnapsackSearchNode&) = delete;
  KnapsackSearchNode& operator=(const KnapsackSearchNode&) = delete;
#endif
 
  int depth() const { return depth_; }
  const KnapsackSearchNode* parent() const { return parent_; }
  const KnapsackAssignment& assignment() const { return assignment_; }
 
  int64_t current_profit() const { return current_profit_; }
  void set_current_profit(int64_t profit) { current_profit_ = profit; }
 
  int64_t profit_upper_bound() const { return profit_upper_bound_; }
  void set_profit_upper_bound(int64_t profit) { profit_upper_bound_ = profit; }
 
  int next_item_id() const { return next_item_id_; }
  void set_next_item_id(int id) { next_item_id_ = id; }
 
 private:
  int depth_;
  const KnapsackSearchNode* const parent_;
  KnapsackAssignment assignment_;

  int64_t current_profit_;
  int64_t profit_upper_bound_;

  int next_item_id_;
};
 
// ----- KnapsackSearchPath -----
class KnapsackSearchPath {
 public:
  KnapsackSearchPath(const KnapsackSearchNode& from,
                     const KnapsackSearchNode& to);
 
#ifndef SWIG
  // This type is neither copyable nor movable.
  KnapsackSearchPath(const KnapsackSearchPath&) = delete;
  KnapsackSearchPath& operator=(const KnapsackSearchPath&) = delete;
#endif
 
  void Init();
  const KnapsackSearchNode& from() const { return from_; }
  const KnapsackSearchNode& via() const { return *via_; }
  const KnapsackSearchNode& to() const { return to_; }
  const KnapsackSearchNode* MoveUpToDepth(const KnapsackSearchNode& node,
                                          int depth) const;
 
 private:
  const KnapsackSearchNode& from_;
  const KnapsackSearchNode* via_;  // Computed in 'Init'.
  const KnapsackSearchNode& to_;
};
 
// ----- KnapsackState -----

class KnapsackState {
 public:
  KnapsackState();
 
#ifndef SWIG
  // This type is neither copyable nor movable.
  KnapsackState(const KnapsackState&) = delete;
  KnapsackState& operator=(const KnapsackState&) = delete;
#endif

  void Init(int number_of_items);
  bool UpdateState(bool revert, const KnapsackAssignment& assignment);
 
  int GetNumberOfItems() const { return is_bound_.size(); }
  bool is_bound(int id) const { return is_bound_.at(id); }
  bool is_in(int id) const { return is_in_.at(id); }
 
 private:
  std::vector<bool> is_bound_;
  std::vector<bool> is_in_;
};
 
// ----- KnapsackPropagator -----

class KnapsackPropagator {
 public:
  explicit KnapsackPropagator(const KnapsackState& state);
 
#ifndef SWIG
  // This type is neither copyable nor movable.
  KnapsackPropagator(const KnapsackPropagator&) = delete;
  KnapsackPropagator& operator=(const KnapsackPropagator&) = delete;
#endif
 
  virtual ~KnapsackPropagator();

  void Init(const std::vector<int64_t>& profits,
            const std::vector<int64_t>& weights);

  bool Update(bool revert, const KnapsackAssignment& assignment);
  virtual void ComputeProfitBounds() = 0;
  virtual int GetNextItemId() const = 0;
 
  int64_t current_profit() const { return current_profit_; }
  int64_t profit_lower_bound() const { return profit_lower_bound_; }
  int64_t profit_upper_bound() const { return profit_upper_bound_; }

  void CopyCurrentStateToSolution(bool has_one_propagator,
                                  std::vector<bool>* solution) const;
 
 protected:
  virtual void InitPropagator() = 0;

  virtual bool UpdatePropagator(bool revert,
                                const KnapsackAssignment& assignment) = 0;

  virtual void CopyCurrentStateToSolutionPropagator(
      std::vector<bool>* solution) const = 0;
 
  const KnapsackState& state() const { return state_; }
  const std::vector<KnapsackItemPtr>& items() const { return items_; }
 
  void set_profit_lower_bound(int64_t profit) { profit_lower_bound_ = profit; }
  void set_profit_upper_bound(int64_t profit) { profit_upper_bound_ = profit; }
 
 private:
  std::vector<KnapsackItemPtr> items_;
  int64_t current_profit_;
  int64_t profit_lower_bound_;
  int64_t profit_upper_bound_;
  const KnapsackState& state_;
};
 
// ----- KnapsackCapacityPropagator -----

class KnapsackCapacityPropagator : public KnapsackPropagator {
 public:
  KnapsackCapacityPropagator(const KnapsackState& state, int64_t capacity);
 
#ifndef SWIG
  // This type is neither copyable nor movable.
  KnapsackCapacityPropagator(const KnapsackCapacityPropagator&) = delete;
  KnapsackCapacityPropagator& operator=(const KnapsackCapacityPropagator&) =
      delete;
#endif
 
  ~KnapsackCapacityPropagator() override;
  void ComputeProfitBounds() override;
  int GetNextItemId() const override { return break_item_id_; }
 
 protected:
  void InitPropagator() override;
  bool UpdatePropagator(bool revert,
                        const KnapsackAssignment& assignment) override;
  void CopyCurrentStateToSolutionPropagator(
      std::vector<bool>* solution) const override;
 
 private:
  int64_t GetAdditionalProfit(int64_t remaining_capacity,
                              int break_item_id) const;
 
  const int64_t capacity_;
  int64_t consumed_capacity_;
  int break_item_id_;
  std::vector<KnapsackItemPtr> sorted_items_;
  int64_t profit_max_;
};
 
// ----- BaseKnapsackSolver -----

class BaseKnapsackSolver {
 public:
  explicit BaseKnapsackSolver(absl::string_view solver_name)
      : solver_name_(solver_name) {}
  virtual ~BaseKnapsackSolver() = default;


  virtual void Init(const std::vector<int64_t>& profits,
                    const std::vector<std::vector<int64_t> >& weights,
                    const std::vector<int64_t>& capacities) = 0;
 
  // Gets the lower and upper bound when the item is in or out of the knapsack.
  // To ensure objects are correctly initialized, this method should not be
  // called before ::Init.
  virtual void GetLowerAndUpperBoundWhenItem(int item_id, bool is_item_in,
                                             int64_t* lower_bound,
                                             int64_t* upper_bound);

  virtual int64_t Solve(TimeLimit* time_limit, double time_limit_in_seconds,
                        bool* is_solution_optimal) = 0;

  virtual bool best_solution(int item_id) const = 0;
 
  virtual std::string GetName() const { return solver_name_; }
 
 private:
  const std::string solver_name_;
};
 
// ----- KnapsackGenericSolver -----

class KnapsackGenericSolver : public BaseKnapsackSolver {
 public:
  explicit KnapsackGenericSolver(const std::string& solver_name);
 
#ifndef SWIG
  // This type is neither copyable nor movable.
  KnapsackGenericSolver(const KnapsackGenericSolver&) = delete;
  KnapsackGenericSolver& operator=(const KnapsackGenericSolver&) = delete;
#endif
 
  ~KnapsackGenericSolver() override;

  void Init(const std::vector<int64_t>& profits,
            const std::vector<std::vector<int64_t> >& weights,
            const std::vector<int64_t>& capacities) override;
  int GetNumberOfItems() const { return state_.GetNumberOfItems(); }
  void GetLowerAndUpperBoundWhenItem(int item_id, bool is_item_in,
                                     int64_t* lower_bound,
                                     int64_t* upper_bound) override;

  void set_primary_propagator_id(int primary_propagator_id) {
    primary_propagator_id_ = primary_propagator_id;
  }

  int64_t Solve(TimeLimit* time_limit, double time_limit_in_seconds,
                bool* is_solution_optimal) override;
  bool best_solution(int item_id) const override {
    return best_solution_.at(item_id);
  }
 
 private:

  void Clear();

  bool UpdatePropagators(const KnapsackSearchPath& path);
  bool IncrementalUpdate(bool revert, const KnapsackAssignment& assignment);
  void UpdateBestSolution();

  bool MakeNewNode(const KnapsackSearchNode& node, bool is_in);

  int64_t GetAggregatedProfitUpperBound() const;
  bool HasOnePropagator() const { return propagators_.size() == 1; }
  int64_t GetCurrentProfit() const {
    return propagators_.at(primary_propagator_id_)->current_profit();
  }
  int64_t GetNextItemId() const {
    return propagators_.at(primary_propagator_id_)->GetNextItemId();
  }
 
  std::vector<KnapsackPropagator*> propagators_;
  int primary_propagator_id_;
  std::vector<KnapsackSearchNode*> search_nodes_;
  KnapsackState state_;
  int64_t best_solution_profit_;
  std::vector<bool> best_solution_;
};
#endif  // SWIG
}  // namespace operations_research
 
#endif  // ORTOOLS_ALGORITHMS_KNAPSACK_SOLVER_H_