44 #ifndef OR_TOOLS_ALGORITHMS_KNAPSACK_SOLVER_FOR_CUTS_H_
45 #define OR_TOOLS_ALGORITHMS_KNAPSACK_SOLVER_FOR_CUTS_H_
51 #include "absl/memory/memory.h"
110 int depth()
const {
return depth_; }
133 double current_profit_;
134 double profit_upper_bound_;
180 const KnapsackSearchNodeForCuts* node,
int depth);
192 void Init(
int number_of_items);
200 bool is_bound(
int id)
const {
return is_bound_.at(
id); }
201 bool is_in(
int id)
const {
return is_in_.at(
id); }
208 std::vector<bool> is_bound_;
209 std::vector<bool> is_in_;
240 void Init(
const std::vector<double>& profits,
241 const std::vector<double>& weights,
double capacity);
265 const std::vector<KnapsackItemForCutsPtr>&
items()
const {
return items_; }
279 double GetAdditionalProfitUpperBound(
double remaining_capacity,
280 int break_item_id)
const;
283 double consumed_capacity_;
285 std::vector<KnapsackItemForCutsPtr> sorted_items_;
287 std::vector<KnapsackItemForCutsPtr> items_;
288 double current_profit_;
289 double profit_lower_bound_;
290 double profit_upper_bound_;
307 void Init(
const std::vector<double>& profits,
308 const std::vector<double>& weights,
const double capacity);
315 double* lower_bound,
double* upper_bound);
323 const double solution_lower_bound_threshold) {
324 solution_lower_bound_threshold_ = solution_lower_bound_threshold;
330 const double solution_upper_bound_threshold) {
331 solution_upper_bound_threshold_ = solution_upper_bound_threshold;
341 DCHECK(item_id < best_solution_.size());
342 return best_solution_[item_id];
345 const std::string&
GetName()
const {
return solver_name_; }
355 bool IncrementalUpdate(
bool revert,
358 void UpdateBestSolution();
365 double GetAggregatedProfitUpperBound();
366 double GetCurrentProfit()
const {
return propagator_.
current_profit(); }
367 int GetNextItemId()
const {
return propagator_.
GetNextItemId(); }
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();
#define DCHECK(condition)
void Init(const std::vector< double > &profits, const std::vector< double > &weights, double capacity)
int GetNextItemId() const
void CopyCurrentStateToSolution(std::vector< bool > *solution) const
double profit_upper_bound() const
~KnapsackPropagatorForCuts()
const KnapsackStateForCuts & state() const
const std::vector< KnapsackItemForCutsPtr > & items() const
void set_profit_lower_bound(double profit)
double profit_lower_bound() const
KnapsackPropagatorForCuts(const KnapsackPropagatorForCuts &)=delete
double current_profit() const
KnapsackPropagatorForCuts(const KnapsackStateForCuts *state)
void set_profit_upper_bound(double profit)
bool Update(bool revert, const KnapsackAssignmentForCuts &assignment)
void ComputeProfitBounds()
KnapsackPropagatorForCuts & operator=(const KnapsackPropagatorForCuts &)=delete
const KnapsackSearchNodeForCuts *const parent() const
void set_current_profit(double profit)
double profit_upper_bound() const
KnapsackSearchNodeForCuts(const KnapsackSearchNodeForCuts &)=delete
void set_next_item_id(int id)
KnapsackSearchNodeForCuts & operator=(const KnapsackSearchNodeForCuts &)=delete
const KnapsackAssignmentForCuts & assignment() const
KnapsackSearchNodeForCuts(const KnapsackSearchNodeForCuts *parent, const KnapsackAssignmentForCuts &assignment)
double current_profit() const
void set_profit_upper_bound(double profit)
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(std::string solver_name)
bool best_solution(int item_id) const
void set_node_limit(const int64 node_limit)
const std::string & GetName() const
int GetNumberOfItems() const
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
int GetNumberOfItems() const
void Init(int number_of_items)
bool UpdateState(bool revert, const KnapsackAssignmentForCuts &assignment)
KnapsackStateForCuts & operator=(const KnapsackStateForCuts &)=delete
bool is_bound(int id) const
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
SharedTimeLimit * time_limit
static const int64 kint64max
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)
KnapsackAssignmentForCuts(int item_id, bool is_in)
KnapsackItemForCuts(int id, double weight, double profit)
double GetEfficiency(double profit_max) const