C++ Reference: knapsack_solver_for_cuts

Note: This documentation is automatically generated.

This library solves 0-1 one-dimensional knapsack problems with fractional profits and weights using the branch and bound algorithm. Note that algorithms/knapsack_solver uses 'int64_t' for the profits and the weights. TODO(user): Merge this code with algorithms/knapsack_solver.

Given n items, each with a profit and a weight and a knapsack of capacity c, the goal is to find a subset of the items which fits inside c and maximizes the total profit. Without loss of generality, profits and weights are assumed to be positive.

From a mathematical point of view, the one-dimensional knapsack problem can be modeled by linear constraint: Sum(i:1..n)(weight_i * item_i) <= c, where item_i is a 0-1 integer variable. The goal is to maximize: Sum(i:1..n)(profit_i * item_i).

Example Usage: std::vector<double> profits = {0, 0.5, 0.4, 1, 1, 1.1}; std::vector<double> weights = {9, 6, 2, 1.5, 1.5, 1.5}; KnapsackSolverForCuts solver("solver"); solver.Init(profits, weights, capacity); bool is_solution_optimal = false; std::unique_ptr<TimeLimit> time_limit = absl::make_unique<TimeLimit>(time_limit_seconds); // Set the time limit. const double profit = solver.Solve(time_limit.get(), &is_solution_optimal); const int number_of_items(profits.size()); for (int item_id(0); item_id < number_of_items; ++item_id) { solver.best_solution(item_id); // Access the solution. }

Classes
KnapsackPropagatorForCuts
KnapsackSearchNodeForCuts
KnapsackSearchPathForCuts
KnapsackSolverForCuts
KnapsackStateForCuts