14#ifndef OR_TOOLS_ALGORITHMS_KNAPSACK_SOLVER_H_
15#define OR_TOOLS_ALGORITHMS_KNAPSACK_SOLVER_H_
23#include "absl/memory/memory.h"
32class BaseKnapsackSolver;
174#if defined(USE_XPRESS)
180 KNAPSACK_MULTIDIMENSION_XPRESS_MIP_SOLVER = 7,
183#if defined(USE_CPLEX)
189 KNAPSACK_MULTIDIMENSION_CPLEX_MIP_SOLVER = 8,
200 void Init(
const std::vector<int64>& profits,
201 const std::vector<std::vector<int64> >& weights,
202 const std::vector<int64>& capacities);
228 time_limit_seconds_ = time_limit_seconds;
229 time_limit_ = absl::make_unique<TimeLimit>(time_limit_seconds_);
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);
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_;
254 double time_limit_seconds_;
255 std::unique_ptr<TimeLimit> time_limit_;
311 ?
static_cast<double>(
profit) /
static_cast<double>(
weight)
335 int depth()
const {
return depth_; }
359 int64 current_profit_;
360 int64 profit_upper_bound_;
411 void Init(
int number_of_items);
418 bool is_bound(
int id)
const {
return is_bound_.at(
id); }
419 bool is_in(
int id)
const {
return is_in_.at(
id); }
426 std::vector<bool> is_bound_;
427 std::vector<bool> is_in_;
446 void Init(
const std::vector<int64>& profits,
447 const std::vector<int64>& weights);
470 std::vector<bool>* solution)
const;
488 std::vector<bool>* solution)
const = 0;
491 const std::vector<KnapsackItemPtr>&
items()
const {
return items_; }
497 std::vector<KnapsackItemPtr> items_;
498 int64 current_profit_;
499 int64 profit_lower_bound_;
500 int64 profit_upper_bound_;
542 std::vector<bool>* solution)
const override;
553 int64 GetAdditionalProfit(
int64 remaining_capacity,
int break_item_id)
const;
555 const int64 capacity_;
556 int64 consumed_capacity_;
558 std::vector<KnapsackItemPtr> sorted_items_;
569 : solver_name_(solver_name) {}
573 virtual void Init(
const std::vector<int64>& profits,
574 const std::vector<std::vector<int64> >& weights,
575 const std::vector<int64>& capacities) = 0;
590 virtual std::string
GetName()
const {
return solver_name_; }
593 const std::string solver_name_;
611 void Init(
const std::vector<int64>& profits,
612 const std::vector<std::vector<int64> >& weights,
613 const std::vector<int64>& capacities)
override;
617 int64* upper_bound)
override;
623 master_propagator_id_ = master_propagator_id;
630 return best_solution_.at(item_id);
646 void UpdateBestSolution();
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();
658 int64 GetNextItemId()
const {
659 return propagators_.at(master_propagator_id_)->GetNextItemId();
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_;
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)
virtual ~BaseKnapsackSolver()
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
void ComputeProfitBounds() override
~KnapsackCapacityPropagator() override
void InitPropagator() override
int GetNextItemId() const override
~KnapsackGenericSolver() 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
int GetNumberOfItems() const
bool best_solution(int item_id) const override
int64 Solve(TimeLimit *time_limit, bool *is_solution_optimal) override
int64 profit_lower_bound() const
void CopyCurrentStateToSolution(bool has_one_propagator, std::vector< bool > *solution) const
virtual bool UpdatePropagator(bool revert, const KnapsackAssignment &assignment)=0
void set_profit_lower_bound(int64 profit)
const std::vector< KnapsackItemPtr > & items() const
virtual void InitPropagator()=0
virtual void ComputeProfitBounds()=0
virtual int GetNextItemId() const =0
void Init(const std::vector< int64 > &profits, const std::vector< int64 > &weights)
void set_profit_upper_bound(int64 profit)
virtual void CopyCurrentStateToSolutionPropagator(std::vector< bool > *solution) const =0
int64 profit_upper_bound() const
virtual ~KnapsackPropagator()
KnapsackPropagator(const KnapsackState &state)
int64 current_profit() const
bool Update(bool revert, const KnapsackAssignment &assignment)
const KnapsackState & state() const
void set_current_profit(int64 profit)
const KnapsackSearchNode *const parent() const
void set_next_item_id(int id)
void set_profit_upper_bound(int64 profit)
KnapsackSearchNode(const KnapsackSearchNode *const parent, const KnapsackAssignment &assignment)
int64 profit_upper_bound() const
int64 current_profit() const
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.
std::string GetName() const
void set_use_reduction(bool use_reduction)
virtual ~KnapsackSolver()
bool use_reduction() const
int GetNumberOfItems() const
void Init(int number_of_items)
bool is_bound(int id) const
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...
SharedTimeLimit * time_limit
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
KnapsackItem * KnapsackItemPtr
KnapsackAssignment(int _item_id, bool _is_in)
double GetEfficiency(int64 profit_max) const
KnapsackItem(int _id, int64 _weight, int64 _profit)