Skip to content

Knapskack Environment#

We provide here a Jax JIT-able implementation of the knapskack problem.

The knapsack problem is a famous problem in combinatorial optimization. The goal is to determine, given a set of items, each with a weight and a value, which items to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

The decision problem form of the knapsack problem is NP-complete, thus there is no known algorithm both correct and fast (polynomial-time) in all cases.

When the environment is reset, a new problem instance is generated, by sampling weights and values from a uniform distribution between 0 and 1. The weight limit of the knapsack is a parameter of the environment. A trajectory terminates when no further item can be added to the knapsack or the chosen action is invalid.

Observation#

The observation given to the agent provides information regarding the weights and the values of all the items, as well as, which items have been packed into the knapsack.

  • weights: jax array (float) of shape (num_items,), array of weights of the items to be packed into the knapsack.

  • values: jax array (float) of shape (num_items,), array of values of the items to be packed into the knapsack.

  • packed_items: jax array (bool) of shape (num_items,), array of binary values denoting which items are already packed into the knapsack.

  • action_mask: jax array (bool) of shape (num_items,), array of binary values denoting which items can be packed into the knapsack.

Action#

The action space is a DiscreteArray of integer values in the range of [0, num_items-1]. An action is the index of the next item to pack.

Reward#

The reward can be either:

  • Dense: the value of the item to pack at the current timestep.

  • Sparse: the sum of the values of the items packed in the bag at the end of the episode.

In both cases, the reward is 0 if the action is invalid, i.e. an item that was previously selected is selected again or has a weight larger than the bag capacity.

Registered Versions 📖#

  • Knapsack-v1: Knapsack problem with 50 randomly generated items, a total budget of 12.5 and a dense reward function.