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
Silvano Martello, Paolo Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley, 1990, ISBN: 0-471-92420-2, LC: QA267.7.M37.
- 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
Silvano Martello, Paolo Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley, 1990, ISBN: 0-471-92420-2, LC: QA267.7.M37.
- 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
Silvano Martello, Paolo Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley, 1990, ISBN: 0-471-92420-2, LC: QA267.7.M37.
- 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
Silvano Martello, Paolo Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley, 1990, ISBN: 0-471-92420-2, LC: QA267.7.M37.
- 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
Silvano Martello, Paolo Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley, 1990, ISBN: 0-471-92420-2, LC: QA267.7.M37.
- 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
Silvano Martello, Paolo Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley, 1990, ISBN: 0-471-92420-2, LC: QA267.7.M37.
- 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
Silvano Martello, Paolo Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley, 1990, ISBN: 0-471-92420-2, LC: QA267.7.M37.
- 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
Silvano Martello, Paolo Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley, 1990, ISBN: 0-471-92420-2, LC: QA267.7.M37.
- 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
Silvano Martello, Paolo Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley, 1990, ISBN: 0-471-92420-2, LC: QA267.7.M37.