Java Reference

Java Reference

KnapsackSolver

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 = pywrapknapsack_solver.KnapsackSolver(
    pywrapknapsack_solver.KnapsackSolver
    .KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
    'Multi-dimensional solver')
    solver.Init(profits, weights, capacities)
    profit = solver.Solve()


    C++:

    const std::vectorint64 profits = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    const std::vectorstd::vector<int64 weights =
    { { 1, 2, 3, 4, 5, 6, 7, 8, 9 },
    { 1, 1, 1, 1, 1, 1, 1, 1, 1 } };
    const std::vectorint64 capacities = { 34, 4 };
    KnapsackSolver::KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
    "Multi-dimensional solver");
    solver.Init(profits, weights, capacities);
    const int64 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.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
    "Multi-dimensional solver");
    solver.init(profits, weights, capacities);
    final long profit = solver.solve();

Definition at line 97 of file KnapsackSolver.java.

Classes

enum  SolverType
 Enum controlling which underlying algorithm is used. More...
 

Public Member Functions

synchronized void delete ()
 
 KnapsackSolver (String solver_name)
 
 KnapsackSolver (KnapsackSolver.SolverType solver_type, String solver_name)
 
void init (long[] profits, long[][] weights, long[] capacities)
 Initializes the solver and enters the problem to be solved. More...
 
long solve ()
 Solves the problem and returns the profit of the optimal solution. More...
 
boolean bestSolutionContains (int item_id)
 Returns true if the item 'item_id' is packed in the optimal knapsack. More...
 
boolean isSolutionOptimal ()
 Returns true if the solution was proven optimal. More...
 
String getName ()
 
boolean useReduction ()
 
void setUseReduction (boolean use_reduction)
 
void setTimeLimit (double time_limit_seconds)
 Time limit in seconds. More...
 

Protected Member Functions

 KnapsackSolver (long cPtr, boolean cMemoryOwn)
 

Constructor & Destructor Documentation

◆ KnapsackSolver() [1/3]

KnapsackSolver ( long  cPtr,
boolean  cMemoryOwn 
)
inlineprotected

Definition at line 101 of file KnapsackSolver.java.

◆ KnapsackSolver() [2/3]

KnapsackSolver ( String  solver_name)
inline

Definition at line 125 of file KnapsackSolver.java.

◆ KnapsackSolver() [3/3]

KnapsackSolver ( KnapsackSolver.SolverType  solver_type,
String  solver_name 
)
inline

Definition at line 129 of file KnapsackSolver.java.

Member Function Documentation

◆ bestSolutionContains()

boolean bestSolutionContains ( int  item_id)
inline

Returns true if the item 'item_id' is packed in the optimal knapsack.

Definition at line 150 of file KnapsackSolver.java.

◆ delete()

synchronized void delete ( )
inline

Definition at line 115 of file KnapsackSolver.java.

◆ getName()

String getName ( )
inline

Definition at line 161 of file KnapsackSolver.java.

◆ init()

void init ( long[]  profits,
long  weights[][],
long[]  capacities 
)
inline

Initializes the solver and enters the problem to be solved.

Definition at line 136 of file KnapsackSolver.java.

◆ isSolutionOptimal()

boolean isSolutionOptimal ( )
inline

Returns true if the solution was proven optimal.

Definition at line 157 of file KnapsackSolver.java.

◆ setTimeLimit()

void setTimeLimit ( double  time_limit_seconds)
inline

Time limit in seconds.



When a finite time limit is set the solution obtained might not be optimal
if the limit is reached.

Definition at line 179 of file KnapsackSolver.java.

◆ setUseReduction()

void setUseReduction ( boolean  use_reduction)
inline

Definition at line 169 of file KnapsackSolver.java.

◆ solve()

long solve ( )
inline

Solves the problem and returns the profit of the optimal solution.

Definition at line 143 of file KnapsackSolver.java.

◆ useReduction()

boolean useReduction ( )
inline

Definition at line 165 of file KnapsackSolver.java.


The documentation for this class was generated from the following file:
KnapsackSolver(long cPtr, boolean cMemoryOwn)