Python Reference: Algorithms

Module pywrapknapsack_solver

Expand source code

# This file was automatically generated by SWIG (http://www.swig.org).
# Version 4.0.1
#
# Do not make changes to this file unless you know what you are doing--modify
# the SWIG interface file instead.

from sys import version_info as _swig_python_version_info
if _swig_python_version_info < (2, 7, 0):
    raise RuntimeError("Python 2.7 or later required")

# Import the low-level C/C++ module
if __package__ or "." in __name__:
    from . import _pywrapknapsack_solver
else:
    import _pywrapknapsack_solver

try:
    import builtins as __builtin__
except ImportError:
    import __builtin__

def _swig_repr(self):
    try:
        strthis = "proxy of " + self.this.__repr__()
    except __builtin__.Exception:
        strthis = ""
    return "<%s.%s; %s >" % (self.__class__.__module__, self.__class__.__name__, strthis,)


def _swig_setattr_nondynamic_instance_variable(set):
    def set_instance_attr(self, name, value):
        if name == "thisown":
            self.this.own(value)
        elif name == "this":
            set(self, name, value)
        elif hasattr(self, name) and isinstance(getattr(type(self), name), property):
            set(self, name, value)
        else:
            raise AttributeError("You cannot add instance attributes to %s" % self)
    return set_instance_attr


def _swig_setattr_nondynamic_class_variable(set):
    def set_class_attr(cls, name, value):
        if hasattr(cls, name) and not isinstance(getattr(cls, name), property):
            set(cls, name, value)
        else:
            raise AttributeError("You cannot add class attributes to %s" % cls)
    return set_class_attr


def _swig_add_metaclass(metaclass):
    """Class decorator for adding a metaclass to a SWIG wrapped class - a slimmed down version of six.add_metaclass"""
    def wrapper(cls):
        return metaclass(cls.__name__, cls.__bases__, cls.__dict__.copy())
    return wrapper


class _SwigNonDynamicMeta(type):
    """Meta class to enforce nondynamic attributes (no new attributes) for a class"""
    __setattr__ = _swig_setattr_nondynamic_class_variable(type.__setattr__)


class KnapsackSolver(object):
    r"""
     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**:

      .. code-block:: c++

              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++**:

      .. code-block:: 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 solver(
                 KnapsackSolver::KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
                 "Multi-dimensional solver");
             solver.Init(profits, weights, capacities);
             const int64 profit = solver.Solve();

      **Java**:

      .. code-block:: c++

            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();
    """

    thisown = property(lambda x: x.this.own(), lambda x, v: x.this.own(v), doc="The membership flag")
    __repr__ = _swig_repr
    KNAPSACK_BRUTE_FORCE_SOLVER = _pywrapknapsack_solver.KnapsackSolver_KNAPSACK_BRUTE_FORCE_SOLVER
    r"""
     Brute force method.

    Limited to 30 items and one dimension, this
    solver uses a brute force algorithm, ie. explores all possible states.
    Experiments show competitive performance for instances with less than
    15 items.
    """
    KNAPSACK_64ITEMS_SOLVER = _pywrapknapsack_solver.KnapsackSolver_KNAPSACK_64ITEMS_SOLVER
    r"""
     Optimized method for single dimension small problems

    Limited to 64 items and one dimension, this
    solver uses a branch & bound algorithm. This solver is about 4 times
    faster than KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER.
    """
    KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER = _pywrapknapsack_solver.KnapsackSolver_KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER
    r"""
     Dynamic Programming approach for single dimension problems

    Limited to one dimension, this solver is based on a dynamic programming
    algorithm. The time and space complexity is O(capacity *
    number_of_items).
    """
    KNAPSACK_MULTIDIMENSION_CBC_MIP_SOLVER = _pywrapknapsack_solver.KnapsackSolver_KNAPSACK_MULTIDIMENSION_CBC_MIP_SOLVER
    r"""
     CBC Based Solver

     This solver can deal with both large number of items and several
    dimensions. This solver is based on Integer Programming solver CBC.
    """
    KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER = _pywrapknapsack_solver.KnapsackSolver_KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER
    r"""
     Generic Solver.

    This solver can deal with both large number of items and several
    dimensions. This solver is based on branch and bound.
    """

    def __init__(self, *args):
        _pywrapknapsack_solver.KnapsackSolver_swiginit(self, _pywrapknapsack_solver.new_KnapsackSolver(*args))
    __swig_destroy__ = _pywrapknapsack_solver.delete_KnapsackSolver

    def Init(self, profits: "std::vector< int64 > const &", weights: "std::vector< std::vector< int64 > > const &", capacities: "std::vector< int64 > const &") -> "void":
        r"""Initializes the solver and enters the problem to be solved."""
        return _pywrapknapsack_solver.KnapsackSolver_Init(self, profits, weights, capacities)

    def Solve(self) -> "int64":
        r"""Solves the problem and returns the profit of the optimal solution."""
        return _pywrapknapsack_solver.KnapsackSolver_Solve(self)

    def BestSolutionContains(self, item_id: "int") -> "bool":
        r"""Returns true if the item 'item_id' is packed in the optimal knapsack."""
        return _pywrapknapsack_solver.KnapsackSolver_BestSolutionContains(self, item_id)

    def set_use_reduction(self, use_reduction: "bool") -> "void":
        return _pywrapknapsack_solver.KnapsackSolver_set_use_reduction(self, use_reduction)

    def set_time_limit(self, time_limit_seconds: "double") -> "void":
        r"""
         Time limit in seconds.

        When a finite time limit is set the solution obtained might not be optimal
        if the limit is reached.
        """
        return _pywrapknapsack_solver.KnapsackSolver_set_time_limit(self, time_limit_seconds)

# Register KnapsackSolver in _pywrapknapsack_solver:
_pywrapknapsack_solver.KnapsackSolver_swigregister(KnapsackSolver)

Classes

KnapsackSolver

class KnapsackSolver (*args)

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:

.. code-block:: c++

      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++:

.. code-block:: 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 solver(
         KnapsackSolver::KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
         "Multi-dimensional solver");
     solver.Init(profits, weights, capacities);
     const int64 profit = solver.Solve();

Java:

.. code-block:: c++

    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();

Expand source code

class KnapsackSolver(object):
    r"""
     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**:

      .. code-block:: c++

              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++**:

      .. code-block:: 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 solver(
                 KnapsackSolver::KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
                 "Multi-dimensional solver");
             solver.Init(profits, weights, capacities);
             const int64 profit = solver.Solve();

      **Java**:

      .. code-block:: c++

            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();
    """

    thisown = property(lambda x: x.this.own(), lambda x, v: x.this.own(v), doc="The membership flag")
    __repr__ = _swig_repr
    KNAPSACK_BRUTE_FORCE_SOLVER = _pywrapknapsack_solver.KnapsackSolver_KNAPSACK_BRUTE_FORCE_SOLVER
    r"""
     Brute force method.

    Limited to 30 items and one dimension, this
    solver uses a brute force algorithm, ie. explores all possible states.
    Experiments show competitive performance for instances with less than
    15 items.
    """
    KNAPSACK_64ITEMS_SOLVER = _pywrapknapsack_solver.KnapsackSolver_KNAPSACK_64ITEMS_SOLVER
    r"""
     Optimized method for single dimension small problems

    Limited to 64 items and one dimension, this
    solver uses a branch & bound algorithm. This solver is about 4 times
    faster than KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER.
    """
    KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER = _pywrapknapsack_solver.KnapsackSolver_KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER
    r"""
     Dynamic Programming approach for single dimension problems

    Limited to one dimension, this solver is based on a dynamic programming
    algorithm. The time and space complexity is O(capacity *
    number_of_items).
    """
    KNAPSACK_MULTIDIMENSION_CBC_MIP_SOLVER = _pywrapknapsack_solver.KnapsackSolver_KNAPSACK_MULTIDIMENSION_CBC_MIP_SOLVER
    r"""
     CBC Based Solver

     This solver can deal with both large number of items and several
    dimensions. This solver is based on Integer Programming solver CBC.
    """
    KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER = _pywrapknapsack_solver.KnapsackSolver_KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER
    r"""
     Generic Solver.

    This solver can deal with both large number of items and several
    dimensions. This solver is based on branch and bound.
    """

    def __init__(self, *args):
        _pywrapknapsack_solver.KnapsackSolver_swiginit(self, _pywrapknapsack_solver.new_KnapsackSolver(*args))
    __swig_destroy__ = _pywrapknapsack_solver.delete_KnapsackSolver

    def Init(self, profits: "std::vector< int64 > const &", weights: "std::vector< std::vector< int64 > > const &", capacities: "std::vector< int64 > const &") -> "void":
        r"""Initializes the solver and enters the problem to be solved."""
        return _pywrapknapsack_solver.KnapsackSolver_Init(self, profits, weights, capacities)

    def Solve(self) -> "int64":
        r"""Solves the problem and returns the profit of the optimal solution."""
        return _pywrapknapsack_solver.KnapsackSolver_Solve(self)

    def BestSolutionContains(self, item_id: "int") -> "bool":
        r"""Returns true if the item 'item_id' is packed in the optimal knapsack."""
        return _pywrapknapsack_solver.KnapsackSolver_BestSolutionContains(self, item_id)

    def set_use_reduction(self, use_reduction: "bool") -> "void":
        return _pywrapknapsack_solver.KnapsackSolver_set_use_reduction(self, use_reduction)

    def set_time_limit(self, time_limit_seconds: "double") -> "void":
        r"""
         Time limit in seconds.

        When a finite time limit is set the solution obtained might not be optimal
        if the limit is reached.
        """
        return _pywrapknapsack_solver.KnapsackSolver_set_time_limit(self, time_limit_seconds)

Class variables

KNAPSACK_64ITEMS_SOLVER

var KNAPSACK_64ITEMS_SOLVER

Optimized method for single dimension small problems

Limited to 64 items and one dimension, this solver uses a branch & bound algorithm. This solver is about 4 times faster than KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER.

KNAPSACK_BRUTE_FORCE_SOLVER

var KNAPSACK_BRUTE_FORCE_SOLVER

Brute force method.

Limited to 30 items and one dimension, this solver uses a brute force algorithm, ie. explores all possible states. Experiments show competitive performance for instances with less than 15 items.

KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER

var KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER

Dynamic Programming approach for single dimension problems

Limited to one dimension, this solver is based on a dynamic programming algorithm. The time and space complexity is O(capacity * number_of_items).

KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER

var KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER

Generic Solver.

This solver can deal with both large number of items and several dimensions. This solver is based on branch and bound.

KNAPSACK_MULTIDIMENSION_CBC_MIP_SOLVER

var KNAPSACK_MULTIDIMENSION_CBC_MIP_SOLVER

CBC Based Solver

This solver can deal with both large number of items and several dimensions. This solver is based on Integer Programming solver CBC.

Instance variables

thisown

var thisown

The membership flag

Expand source code

thisown = property(lambda x: x.this.own(), lambda x, v: x.this.own(v), doc="The membership flag")

Methods

BestSolutionContains

def BestSolutionContains(self, item_id: int) -> bool

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

Expand source code

def BestSolutionContains(self, item_id: "int") -> "bool":
    r"""Returns true if the item 'item_id' is packed in the optimal knapsack."""
    return _pywrapknapsack_solver.KnapsackSolver_BestSolutionContains(self, item_id)

Init

def Init(self, profits: std::vector< int64 > const &, weights: std::vector< std::vector< int64 > > const &, capacities: std::vector< int64 > const &) -> 'void'

Initializes the solver and enters the problem to be solved.

Expand source code

def Init(self, profits: "std::vector< int64 > const &", weights: "std::vector< std::vector< int64 > > const &", capacities: "std::vector< int64 > const &") -> "void":
    r"""Initializes the solver and enters the problem to be solved."""
    return _pywrapknapsack_solver.KnapsackSolver_Init(self, profits, weights, capacities)

Solve

def Solve(self) -> 'int64'

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

Expand source code

def Solve(self) -> "int64":
    r"""Solves the problem and returns the profit of the optimal solution."""
    return _pywrapknapsack_solver.KnapsackSolver_Solve(self)

set_time_limit

def set_time_limit(self, time_limit_seconds: double) -> 'void'

Time limit in seconds.

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

Expand source code

def set_time_limit(self, time_limit_seconds: "double") -> "void":
    r"""
     Time limit in seconds.

    When a finite time limit is set the solution obtained might not be optimal
    if the limit is reached.
    """
    return _pywrapknapsack_solver.KnapsackSolver_set_time_limit(self, time_limit_seconds)

set_use_reduction

def set_use_reduction(self, use_reduction: bool) -> 'void'

Expand source code

def set_use_reduction(self, use_reduction: "bool") -> "void":
    return _pywrapknapsack_solver.KnapsackSolver_set_use_reduction(self, use_reduction)