pykp.knapsack.Knapsack#

class pykp.knapsack.Knapsack(items: <MagicMock name='mock.ndarray.__getitem__()' id='139960639692080'>, capacity: int, load_from_json: bool = False, path_to_spec: str = None)#

Bases: object

Represents a knapsack problem solver.

items#

An array of items available for the knapsack problem.

Type:

np.ndarray[Item]

capacity#

The maximum weight capacity of the knapsack.

Type:

int

state#

Binary array indicating the inclusion/exclusion of items in the knapsack.

Type:

np.ndarray

value#

The total value of items currently in the knapsack.

Type:

float

weight#

The total weight of items currently in the knapsack.

Type:

float

is_feasible#

Indicates if the knapsack is within its weight capacity.

Type:

bool

is_at_capacity#

Indicates if the knapsack is at full capacity.

Type:

bool

terminal_nodes#

An array of all possible arrangements of items that are under the weight constraint, and at full capacity

Type:

np.ndarray[Arrangement]

optimal_nodes#

An array of optimal solutions to the knapsack problem.

Type:

np.ndarray[Arrangement]

Methods

add(item)

Adds the specified item to the knapsack.

empty()

Empties the knapsack by setting all items to be excluded.

load_from_json(path)

Loads knapsack instance from a .json file.

plot_network([fig, ax, show])

Plots a network of knapsack nodes.

plot_terminal_nodes_histogram()

Plots a histogram of values for possible at-capacity arrangements.

remove(item)

Removes the specified item from the knapsack.

set_state(state)

Sets the knapsack state using the provided binary array.

solve([method, solve_all_nodes])

Solves the knapsack problem and returns optimal arrangements.

solve_all_nodes()

Computes all nodes in the knapsack problem.

solve_branch_and_bound(solve_second_best)

Solves the optimal and second-best terminal nodes using best-first branch-and-bound.

solve_feasible_nodes()

Solves the knapsack problem and returns optimal arrangements.

solve_terminal_nodes()

Solves the knapsack problem and returns optimal arrangements.

summary()

Generates a summary of the knapsack instance.

write_to_json(path)

Writes the knapsack instance to .json.
__init__(items: <MagicMock name='mock.ndarray.__getitem__()' id='139960639692080'>, capacity: int, load_from_json: bool = False, path_to_spec: str = None)#

Initialises a Knapsack instance.

Parameters:

  • items (np.ndarray[Item]) – An array of items for the knapsack

  • problem.

  • capacity (int) – The maximum weight capacity of the knapsack.

  • load_from_json (bool, optional) – Whether to load the instance from a .json spec. Default is False.

  • path_to_spec (str, optional) – Path to json spec file. Default is None.

Methods

__init__(items, capacity[, load_from_json, ...])

Initialises a Knapsack instance.

add(item)

Adds the specified item to the knapsack.

empty()

Empties the knapsack by setting all items to be excluded.

load_from_json(path)

Loads knapsack instance from a .json file.

plot_network([fig, ax, show])

Plots a network of knapsack nodes.

plot_terminal_nodes_histogram()

Plots a histogram of values for possible at-capacity arrangements.

remove(item)

Removes the specified item from the knapsack.

set_state(state)

Sets the knapsack state using the provided binary array.

solve([method, solve_all_nodes])

Solves the knapsack problem and returns optimal arrangements.

solve_all_nodes()

Computes all nodes in the knapsack problem.

solve_branch_and_bound(solve_second_best)

Solves the optimal and second-best terminal nodes using best-first branch-and-bound.

solve_feasible_nodes()

Solves the knapsack problem and returns optimal arrangements.

solve_terminal_nodes()

Solves the knapsack problem and returns optimal arrangements.

summary()

Generates a summary of the knapsack instance.

write_to_json(path)

Writes the knapsack instance to .json.
add(item: Item)#

Adds the specified item to the knapsack.

Parameters:

item (Item) – The item to be added to the knapsack.

Returns:

The updated knapsack state.

Return type:

np.ndarray

empty()#

Empties the knapsack by setting all items to be excluded.

Returns:

The updated knapsack state.

Return type:

np.ndarray

load_from_json(path: str)#

Loads knapsack instance from a .json file.

Parameters:

path (str) – Filepath to instance .json file.

plot_network(fig: <MagicMock name='mock.pyplot.Figure' id='139960639511184'> = None, ax: <MagicMock name='mock.pyplot.Axes' id='139960639931840'> = None, show: bool = False) → tuple[<MagicMock name='mock.pyplot.Figure' id='139960639511184'>, <MagicMock name='mock.pyplot.Axes' id='139960639931840'>]#

Plots a network of knapsack nodes.

Paramaters:

fig (plt.Figure, optional): Figure object. Default is None. ax (plt.Axes, optional): Axes object. Default is None. show (bool, optional): Whether to display the plot. Default

is False.

Returns:

Figure and Axes objects.

Return type:

tuple[plt.Figure, plt.Axes]

plot_terminal_nodes_histogram() → tuple[<MagicMock name='mock.pyplot.Figure' id='139960639511184'>, <MagicMock name='mock.pyplot.Axes' id='139960639931840'>]#

Plots a histogram of values for possible at-capacity arrangements.

Returns:

Figure and Axes objects.

Return type:

tuple[plt.Figure, plt.Axes]

remove(item: Item)#

Removes the specified item from the knapsack.

Parameters:

item (Item) – The item to be removed from the knapsack.

Returns:

The updated knapsack state.

Return type:

np.ndarray

set_state(state: <MagicMock name='mock.ndarray' id='139960640637792'>)#

Sets the knapsack state using the provided binary array.

Parameters:

state (np.ndarray) – Binary array indicating the inclusion/exclusion of items in the knapsack.

Returns:

The updated knapsack state.

Return type:

np.ndarray

solve(method: Literal['branch_and_bound', 'mzn_gecode'] = 'branch_and_bound', solve_all_nodes: bool = False)#

Solves the knapsack problem and returns optimal arrangements.

Parameters:

  • method (Literal["branch_and_bound", "mzn_gecode], optional) – The method to use to solve the knapsack problem. Default is “branch_and_bound”.

  • solve_all_nodes (bool, optional) – Whether to find all nodes in the knapsack, including terminal nodes, and feasible nodes. Note, this method applies brute-force and may be infeasible for large instances. Default is False.

Returns:

Optimal arrangements for the knapsack problem.

Return type:

np.ndarray

solve_all_nodes() → <MagicMock name='mock.ndarray' id='139960640637792'>#

Computes all nodes in the knapsack problem. Populates attributes nodes, feasible_nodes, terminal_nodes, optimal_nodes.

Returns:

All nodes in the knapsack problem.

Return type:

np.ndarray

solve_branch_and_bound(solve_second_best: bool)#

Solves the optimal and second-best terminal nodes using best-first branch-and-bound.

solve_feasible_nodes() → <MagicMock name='mock.ndarray' id='139960640637792'>#

Solves the knapsack problem and returns optimal arrangements. This method will be deprecated in future versions. Use solve with solve_feasible_nodes=True instead.

Parameters:

verbose (bool, optional) – If True, prints the string representation of the knapsack summary. Default is True.

Returns:

Optimal arrangements for the knapsack problem.

Return type:

np.ndarray

solve_terminal_nodes()#

Solves the knapsack problem and returns optimal arrangements. This method will be deprecated in future versions. Use solve with solve_feasible_nodes=True instead.

Returns:

Optimal arrangements for the knapsack problem.

Return type:

np.ndarray

summary()#

Generates a summary of the knapsack instance.

Returns:

Summary DataFrame.

Return type:

pd.DataFrame

write_to_json(path: str)#

Writes the knapsack instance to .json.

Parameters:

path (str) – Filepath to output file.