knapsack_solver.h File Reference

Detailed Description

This library solves knapsack problems. Problems the library solves include:

• 0-1 knapsack problems,
• Multi-dimensional knapsack problems,

Given n items, each with a profit and a weight, given a knapsack of capacity c, the goal is to find a subset of items which fits inside c and maximizes the total profit.
The knapsack problem can easily be extended from 1 to d dimensions. As an example, this can be useful to constrain the maximum number of items inside the knapsack.
Without loss of generality, profits and weights are assumed to be positive. From a mathematical point of view, the multi-dimensional knapsack problem can be modeled by d linear constraints:

ForEach(j:1..d)(Sum(i:1..n)(weight_ij * item_i) <= c_j
    where item_i is a 0-1 integer variable.

Then the goal is to maximize:

Sum(i:1..n)(profit_i * item_i).

There are several ways to solve knapsack problems. One of the most efficient is based on dynamic programming (mainly when weights, profits and dimensions are small, and the algorithm runs in pseudo polynomial time). Unfortunately, when adding conflict constraints the problem becomes strongly NP-hard, i.e. there is no pseudo-polynomial algorithm to solve it.
That's the reason why the most of the following code is based on branch and bound search.
For instance to solve a 2-dimensional knapsack problem with 9 items, one just has to feed a profit vector with the 9 profits, a vector of 2 vectors for weights, and a vector of capacities.
E.g.:
Python:

profits = [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
weights = [ [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ],
            [ 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
          ]
capacities = [ 34, 4 ]
solver = knapsack_solver.KnapsackSolver(
    knapsack_solver.SolverType
        .KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
    'Multi-dimensional solver')
solver.init(profits, weights, capacities)
profit = solver.solve()

C++:

const std::vector<int64_t> profits = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
const std::vector<std::vector<int64_t>> weights =
    { { 1, 2, 3, 4, 5, 6, 7, 8, 9 },
      { 1, 1, 1, 1, 1, 1, 1, 1, 1 } };
const std::vector<int64_t> capacities = { 34, 4 };
KnapsackSolver solver(
    KnapsackSolver::KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
    "Multi-dimensional solver");
solver.Init(profits, weights, capacities);
const int64_t profit = solver.Solve();

Java:

final long[] profits = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
final long[][] weights = { { 1, 2, 3, 4, 5, 6, 7, 8, 9 },
                           { 1, 1, 1, 1, 1, 1, 1, 1, 1 } };
final long[] capacities = { 34, 4 };
KnapsackSolver solver = new KnapsackSolver(
    KnapsackSolver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
    "Multi-dimensional solver");
solver.init(profits, weights, capacities);
final long profit = solver.solve();

Definition in file knapsack_solver.h.

#include <cstdint>
#include <memory>
#include <string>
#include <vector>
#include "absl/strings/string_view.h"
#include "ortools/util/time_limit.h"

Go to the source code of this file.

Classes
class	operations_research::KnapsackSolver
struct	operations_research::KnapsackAssignment
struct	operations_research::KnapsackItem
class	operations_research::KnapsackSearchNode
class	operations_research::KnapsackSearchPath
class	operations_research::KnapsackState
	KnapsackState represents a partial solution to the knapsack problem. More...
class	operations_research::KnapsackPropagator
	KnapsackPropagator is the base class for modeling and propagating a constraint given an assignment. More...
class	operations_research::KnapsackCapacityPropagator
	KnapsackCapacityPropagator is a KnapsackPropagator used to enforce a capacity constraint. More...
class	operations_research::BaseKnapsackSolver
	This is the base class for knapsack solvers. More...
class	operations_research::KnapsackGenericSolver
	KnapsackGenericSolver is the multi-dimensional knapsack solver class. More...

Namespaces
namespace	operations_research
	OR-Tools root namespace.

Typedefs
typedef KnapsackItem *	operations_research::KnapsackItemPtr

Functions
Select next search node to expand Select next item_i to	operations_research::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
Select next search node to expand Select next item_i to 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	operations_research::solution (using propagators) - If valid