mknapsack package

Solving knapsack problems with Python.

exception mknapsack.FortranInputCheckError(method=None, z=None)

Bases: Exception

Error in Fortran source code input validation.

exception mknapsack.NoSolutionError

Bases: Exception

Error when no solution to a problem exists.

exception mknapsack.ProblemSizeError

Bases: Exception

Error when problem size is too large to be solved.

mknapsack.solve_bin_packing(weights: List[int], capacity: int, method: str = 'mtp', method_kwargs: Optional[dict] = None, verbose: bool = False) → ndarray

Solves the bin packing problem.

Given a set of items with weights, assign each item exactly to one bin while minimizing the number of bins required.

Parameters

  • weights – Weight of each item.

  • capacity – Capacity of the bins.

  • method –

    Algorithm to use for solving, should be one of

    • ’mtp’ - provides a fast heuristical solution or an exact solution if required

    Defaults to ‘mtp’.

  • method_kwargs –

    Keyword arguments to pass to a given method.

    • ’mtp’

      • require_exact (int, optional) - Whether to require an exact solution or not (0=no, 1=yes). Defaults to 0.

      • max_backtracks (int, optional) - The maximum number of backtracks to perform when require_exact=0. Defaults to 100000.

      • check_inputs (int, optional) - Whether to check inputs or not (0=no, 1=yes). Defaults to 1.

    Defaults to None.

  • verbose – Log details of the solution. Defaults to False.

Returns

Assigned bin for each item.

Return type

np.ndarray

Raises

  • FortranInputCheckError – Something is wrong with the inputs when validated in the original Fortran source code side.

  • ValueError – Something is wrong with the given inputs.

Example

from mknapsack import solve_bin_packing

res = solve_bin_packing(
    weights=[4, 1, 8, 1, 4, 2],
    capacity=10
)

References

mknapsack.solve_bounded_change_making(weights: List[int], n_items: List[int], capacity: int, method: str = 'mtcb', method_kwargs: Optional[dict] = None, verbose: bool = False) → ndarray

Solves the bounded change-making problem.

Given a number of items for item types with weights, and a knapsack with capacity, find the minimum number of items that add up to the capacity.

Parameters

  • weights – Weight of each item type.

  • n_items – Number of items available for each item type.

  • capacity – Capacity of knapsack.

  • method –

    Algorithm to use for solving, should be one of

    • ’mtcb’ - provides a fast heuristical solution that might not be the global optimum, but is suitable for larger problems, or an exact solution if required

    Defaults to ‘mtcb’.

  • method_kwargs –

    Keyword arguments to pass to a given method.

    • ’mtcb’

      • require_exact (int, optional) - Whether to require an exact solution or not (0=no, 1=yes). Defaults to 0.

      • max_backtracks (int, optional) - The maximum number of backtracks to perform when require_exact=0. Defaults to 100000.

      • check_inputs (int, optional) - Whether to check inputs or not (0=no, 1=yes). Defaults to 1.

    Defaults to None.

  • verbose – Log details of the solution. Defaults to False.

Returns

Number of items for each item type.

Return type

np.ndarray

Raises

  • NoSolutionError – No feasible solution found.

  • FortranInputCheckError – Something is wrong with the inputs when validated in the original Fortran source code side.

  • ValueError – Something is wrong with the given inputs.

Example

from mknapsack import solve_bounded_change_making

res = solve_bounded_change_making(
    weights=[18, 9, 23, 20, 59, 61, 70, 75, 76, 30],
    n_items=[1, 2, 3, 2, 1, 1, 1, 2, 3, 2],
    capacity=190
)

References

mknapsack.solve_bounded_knapsack(profits: List[float], weights: List[float], n_items: List[float], capacity: float, method: str = 'mtb2', method_kwargs: Optional[dict] = None, verbose: bool = False) → ndarray

Solves the bounded knapsack problem.

Given a certain number of item types with profits and weights, and a knapsack with given capacity, how many of each item type should be picked to maximize profits?

Parameters

  • profits – Profit of each item type.

  • weights – Weight of each item type.

  • n_items – Number of items available for each item type.

  • capacity – Capacity of knapsack.

  • method – Algorithm to use for solving, currently only ‘mtb2’ is supported. Defaults to ‘mtb2’.

  • method_kwargs –

    Keyword arguments to pass to ‘mtb2’ algorithm:

    • require_exact (int, optional) - Whether to require an exact solution or not (0=no, 1=yes). Defaults to 0.

    • check_inputs (int, optional) - Whether to check inputs or not (0=no, 1=yes). Defaults to 1.

    Defaults to None.

  • verbose – Log details of the solution. Defaults to False.

Returns

Number of items assigned to the knapsack for each item type.

Return type

np.ndarray

Raises

  • FortranInputCheckError – Something is wrong with the inputs when validated in the original Fortran source code side.

  • ValueError – Something is wrong with the given inputs.

Example

from mknapsack import solve_bounded_knapsack

res = solve_bounded_knapsack(
    profits=[78, 35, 89, 36, 94, 75, 74, 100, 80, 16],
    weights=[18, 9, 23, 20, 59, 61, 70, 75, 76, 30],
    n_items=[1, 2, 3, 2, 2, 1, 2, 2, 1, 4],
    capacity=190
)

References

mknapsack.solve_change_making(weights: List[int], capacity: int, method: str = 'mtc2', method_kwargs: Optional[dict] = None, verbose: bool = False) → ndarray

Solves the change-making problem.

Given a set of item types with weights and a knapsack with capacity, find the minimum number of items that add up to the capacity.

Parameters

  • weights – Weight of each item type.

  • capacity – Capacity of knapsack.

  • method –

    Algorithm to use for solving, should be one of

    • ’mtc2’ - provides a fast heuristical solution that might not be the global optimum, but is suitable for larger problems, or an exact solution if required

    Defaults to ‘mtc2’.

  • method_kwargs –

    Keyword arguments to pass to a given method.

    • ’mtc2’

      • require_exact (int, optional) - Whether to require an exact solution or not (0=no, 1=yes). Defaults to 0.

      • max_backtracks (int, optional) - The maximum number of backtracks to perform when require_exact=0. Defaults to 100000.

      • check_inputs (int, optional) - Whether to check inputs or not (0=no, 1=yes). Defaults to 1.

    Defaults to None.

  • verbose – Log details of the solution. Defaults to False.

Returns

Number of items for each item type.

Return type

np.ndarray

Raises

  • NoSolutionError – No feasible solution found.

  • FortranInputCheckError – Something is wrong with the inputs when validated in the original Fortran source code side.

  • ValueError – Something is wrong with the given inputs.

Example

from mknapsack import solve_change_making

res = solve_change_making(
    weights=[18, 9, 23, 20, 59, 61, 70, 75, 76, 30],
    capacity=190
)

References

mknapsack.solve_generalized_assignment(profits: List[List[int]], weights: List[List[int]], capacities: List[int], maximize: bool = True, method: str = 'mthg', method_kwargs: Optional[dict] = None, verbose: bool = False) → ndarray

Solves the generalized assignment problem.

Given a set of items with knapsack-dependent weights and profits, assign items exactly to one knapsack while maximizing or minimizing profit.

Parameters

  • profits – Profit of item when assigned to a knapsack, where knapsacks are in the rows and items in the columns.

  • weights – Weight of each item when assigned to a knapsack, where knapsacks are in the rows and items in the columns.

  • capacities – Capacity of each knapsack, which should match the number of rows in profits and weights.

  • maximize – Whether to maximize or minimize profits. Defaults to True.

  • method –

    Algorithm to use for solving, should be one of

    • ’mtg’ - provides a fast heuristical solution or an exact solution if required, but is not the most suitable for larger problems

      The problem size is limited as follows:

      • Number of knapsacks <= 10

      • Number of items <= 100

    • ’mthg’ - provides a fast heuristical solution that might not be the global optimum, but is suitable for larger problems

      The problem size is limited as follows:

      • Number of knapsacks <= 50

      • Number of items <= 500

    Defaults to ‘mthg’.

  • method_kwargs –

    Keyword arguments to pass to a given method.

    • ’mtg’

      • require_exact (int, optional) - Whether to require an exact solution or not (0=no, 1=yes). Defaults to 0.

      • max_backtracks (int, optional) - The maximum number of backtracks to perform when require_exact=0. Defaults to 100000.

      • check_inputs (int, optional) - Whether to check inputs or not (0=no, 1=yes). Defaults to 1.

    • ’mthg’

      • check_inputs (int, optional) - Whether to check inputs or not (0=no, 1=yes). Defaults to 1.

    Defaults to None.

  • verbose – Log details of the solution. Defaults to False.

Returns

Assigned knapsack for each item.

Return type

np.ndarray

Raises

  • NoSolutionError – No feasible solution found.

  • ProblemSizeError – When problem is too large to be solved with the given method.

  • FortranInputCheckError – Something is wrong with the inputs when validated in the original Fortran source code side.

  • ValueError – Something is wrong with the given inputs.

Example

from mknapsack import solve_generalized_assignment

res = solve_generalized_assignment(
    profits=[[6, 9, 4, 2, 10, 3, 6],
             [4, 8, 9, 1, 7, 5, 4]],
    weights=[[4, 1, 2, 1, 4, 3, 8],
             [9, 9, 8, 1, 3, 8, 7]],
    capacities=[11, 22],
    maximize=True
)

References

mknapsack.solve_multiple_knapsack(profits: List[int], weights: List[int], capacities: List[int], method: str = 'mthm', method_kwargs: Optional[dict] = None, verbose: bool = False) → ndarray

Solves the multiple 0-1 knapsack problem.

Given a set of items with profits and weights and knapsacks with given capacities, how should assign the items into knapsacks in order to maximize profits?

Parameters

  • profits – Profit of each item.

  • weights – Weight of each item.

  • capacities – Capacity of each knapsack.

  • method –

    Algorithm to use for solving, should be one of

    • ’mtm’ - provides a global optimum, but may take a long time to solve for larger problem sizes

    • ’mthm’ - provides a fast heuristical solution that might not be the global optimum, but is suitable for larger problems

    Defaults to ‘mthm’.

  • method_kwargs –

    Keyword arguments to pass to a given method.

    • ’mtm’

      • max_backtracks (int, optional) - Maximum number of backtracks to perform. Setting -1 corresponds to exact solution. Defaults to -1.

      • check_inputs (int, optional) - Whether to check inputs or not (0=no, 1=yes). Defaults to 1.

    • ’mthm’

      • call_stack (int, optional) - Operations to perform on top of the initial solution. Should be one of

        • 0 = output initial feasible solution

        • 1 = try to improve solution once

        • 2 = try to improve solution twice

        Defaults to 2.

      • check_inputs (int, optional) - Whether to check inputs or not (0=no, 1=yes). Defaults to 1.

    Defaults to None.

  • verbose – Log details of the solution. Defaults to False.

Returns

The corresponding knapsack for each item, where 0 means that the item was not assigned to a knapsack.

Return type

np.ndarray

Raises

  • FortranInputCheckError – Something is wrong with the inputs when validated in the original Fortran source code side.

  • ValueError – Something is wrong with the given inputs.

Example

from mknapsack import solve_multiple_knapsack

res = solve_multiple_knapsack(
    profits=[78, 35, 89, 36, 94, 75, 74, 100, 80, 16],
    weights=[18, 9, 23, 20, 59, 61, 70, 75, 76, 30],
    capacities=[90, 100]
)

References

mknapsack.solve_single_knapsack(profits: List[float], weights: List[float], capacity: float, method: str = 'mt2', method_kwargs: Optional[dict] = None, verbose: bool = False) → ndarray

Solves the single 0-1 knapsack problem.

Given a set of items with profits and weights and a knapsack with given capacity, which items should we pick in order to maximize profit?

Parameters

  • profits – Profit of each item.

  • weights – Weight of each item.

  • capacity – Capacity of knapsack.

  • method –

    Algorithm to use for solving, should be one of

    • ’mt1’ - provides a global optimum, but may take a long time to solve for larger problem sizes

    • ’mt2’ - provides a fast heuristical solution that might not be the global optimum, but is suitable for larger problems, or an exact solution if required

    • ’mt1r’ - variant of ‘mt1’ but for real numbers

    Defaults to ‘mt2’.

  • method_kwargs –

    Keyword arguments to pass to a given method.

    • ’mt1’

      • check_inputs (int, optional) - Whether to check inputs or not (0=no, 1=yes). Defaults to 1.

    • ’mt2’

      • require_exact (int, optional) - Whether to require an exact solution or not (0=no, 1=yes). Defaults to 0.

      • check_inputs (int, optional) - Whether to check inputs or not (0=no, 1=yes). Defaults to 1.

    • ’mt1r’

      • tolerance (float, optional) - Precision required, two positive values q and r are considered equal if abs(q - r)/max(q, r) .le. tolerance. Defaults to 1e-08.

      • check_inputs (int, optional) - Whether to check inputs or not (0=no, 1=yes). Defaults to 1.

    Defaults to None.

  • verbose – Log details of the solution. Defaults to False.

Returns

Indicator of knapsack assignment for each item, where 0 means that the item was not assigned to a knapsack.

Return type

np.ndarray

Raises

  • FortranInputCheckError – Something is wrong with the inputs when validated in the original Fortran source code side.

  • ValueError – Something is wrong with the given inputs.

Example

from mknapsack import solve_single_knapsack

res = solve_single_knapsack(
    profits=[78, 35, 89, 36, 94, 75, 74, 100, 80, 16],
    weights=[18, 9, 23, 20, 59, 61, 70, 75, 76, 30],
    capacity=190
)

References

mknapsack.solve_subset_sum(weights: List[int], capacity: int, method: str = 'mtsl', method_kwargs: Optional[dict] = None, verbose: bool = False) → ndarray

Solves the subset sum problem.

Given a set of items with weights and a knapsack with capacity, choose items to fill the knapsack to the fullest.

Parameters

  • weights – Weight of each item.

  • capacity – Capacity of the knapsack.

  • method –

    Algorithm to use for solving, should be one of

    • ’mtsl’ - provides a fast heuristical solution or an exact solution if required

    Defaults to ‘mtsl’.

  • method_kwargs –

    Keyword arguments to pass to a given method.

    • ’mtsl’

      • require_exact (int, optional) - Whether to require an exact solution or not (0=no, 1=yes). Defaults to 0.

      • max_items (int, optional) - The maximum number of items in the core problem when require_exact=0. Defaults to 90.

      • check_inputs (int, optional) - Whether to check inputs or not (0=no, 1=yes). Defaults to 1.

    Defaults to None.

  • verbose – Log details of the solution. Defaults to False.

Returns

Indicator of knapsack assignment for each item, where 0

means that the item was not assigned to the knapsack.

Return type

np.ndarray

Raises

  • FortranInputCheckError – Something is wrong with the inputs when validated in the original Fortran source code side.

  • ValueError – Something is wrong with the given inputs.

Example

from mknapsack import solve_subset_sum

res = solve_subset_sum(
    weights=[4, 1, 8, 1, 4, 2],
    capacity=10
)

References

mknapsack.solve_unbounded_knapsack(profits: List[float], weights: List[float], capacity: float, method: str = 'mtu2', method_kwargs: Optional[dict] = None, verbose: bool = False) → ndarray

Solves the unbounded knapsack problem.

Given an unlimited number of items for each item types with given profits and weights, and a knapsack with given capacity, how many of each item type should be picked to maximize profits?

Parameters

  • profits – Profit of each item type.

  • weights – Weight of each item type.

  • capacity – Capacity of knapsack.

  • method –

    Algorithm to use for solving, should be one of

    • ’mtu1’ - provides an exact solution

    Warning

    No input check is performed on ‘mtu’, so please make sure the given inputs satisfy all the conditions as originally defined in the references

    • ’mtu2’ - enhanced version of mtu1 that provides either an exact or approximal solution

    Defaults to ‘mtu2’.

  • method_kwargs –

    Keyword arguments to pass to a given method.

    • ’mtu1’ - None

    • ’mtu2’

      • require_exact (int, optional) - Whether to require an exact solution or not (0=no, 1=yes). Defaults to 0.

      • check_inputs (int, optional) - Whether to check inputs or not (0=no, 1=yes). Defaults to 1.

    Defaults to None.

  • verbose – Log details of the solution. Defaults to False.

Returns

Number of items assigned to the knapsack for each item type.

Return type

np.ndarray

Raises

  • FortranInputCheckError – Something is wrong with the inputs when validated in the original Fortran source code side.

  • ValueError – Something is wrong with the given inputs.

Example

from mknapsack import solve_unbounded_knapsack

res = solve_unbounded_knapsack(
    profits=[16, 72, 35, 89, 36, 94, 75, 74, 100, 80],
    weights=[30, 18, 9, 23, 20, 59, 61, 70, 75, 76],
    capacity=190
)

References