Quick Start

Let’s get started with DIDPPy by modeling and solving a simple knapsack problem.

Dynamic Programming for Knapsack

In the knapsack problem, we are given the set of items \(N = \{ 0, ..., n-1 \}\) with weights \(w_i\) and profits \(p_i\) for \(i \in N\) and a knapsack with capacity \(c\). We want to maximize the total profit of the items in the knapsack.

Consider selecting the items one by one from \(0\) to \(n - 1\). If we pack item \(0\), the remaining problem is to select items to pack from \(\{ 1, ..., n - 1 \}\) into a knapsack with capacity \(c - w_0\). Otherwise, we use a knapsack with capacity \(c\) for the remaining items. Let \(V(r, i)\) be the maximum profit of selecting items to pack from \(\{ i, ..., n - 1 \}\) into a knapsack with capacity \(r\). We compute \(V(c, 0)\) using the following recursive equation, which is the dynamic programming (DP) formulation.

\[\begin{split}V(r, i) = \begin{cases} \max\{ p_i + V(r - w_i, i + 1), V(r, i + 1) \} & \text{if } i < n \land r \geq w_i \\ V(r, i + 1) & \text{if } i < n \land r < w_i \\ 0 & \text{otherwise.} \end{cases}\end{split}\]

Modeling in DIDPPy

Now, let’s model the above DP formulation in DIDPPy. Suppose that \(n = 4\), \(w_0 = 10\), \(w_1 = 20\), \(w_2 = 30\), \(w_3 = 40\), \(p_0 = 5\), \(p_1 = 25\), \(p_2 = 35\), \(p_3 = 50\), and \(c = 50\). We add a dummy item \(4\) with \(w_4 = 0\) and \(p_4 = 0\) to terminate the recursion.

import math

import didppy as dp

n = 4
weights = [10, 20, 30, 40]
profits = [5, 25, 35, 50]
capacity = 50

model = dp.Model(maximize=True, float_cost=False)

item = model.add_object_type(number=n + 1)
r = model.add_int_resource_var(target=capacity, less_is_better=False)
i = model.add_element_var(object_type=item, target=0)

w = model.add_int_table(weights + [0])
p = model.add_int_table(profits + [0])

pack = dp.Transition(
    name="pack",
    cost=p[i] + dp.IntExpr.state_cost(),
    effects=[(r, r - w[i]), (i, i + 1)],
    preconditions=[i < n, r >= w[i]],
)
model.add_transition(pack)

ignore = dp.Transition(
    name="ignore",
    cost=dp.IntExpr.state_cost(),
    effects=[(i, i + 1)],
    preconditions=[i < n],
)
model.add_transition(ignore)

model.add_base_case([i == n])

remaining_items = model.add_set_table(
    [list(range(i, n)) for i in range(n + 1)], object_type=item
)
model.add_dual_bound(math.floor(dp.fractional_knapsack(remaining_items[i], r, p, w)))

We will explain the details in the tutorial, but here is a summary:

  • State variables r and i, corresponding to \(r\) and \(i\), are defined with the target values c and 0, which states that we want to compute \(V(c, 0)\).

  • Given \(i\), a state with larger \(r\) is better, so we define r using add_int_resource_var() and set less_is_better=False.

  • Recursive equations are defined by transitions, which change the state variables and the cost.

  • The cost of the subproblem on the right-hand side of the recursive equations is represented by state_cost().

  • The condition to terminate the recursion is defined by the base case i == n.

  • The dual bound is defined by the fractional knapsack problem (fractional_knapsack()), which is a relaxation of the knapsack problem.

Solving the Model

Once you have the model, you can use solvers provided by DIDPPy to solve the model. You do not need to implement the DP algorithm yourself. Let’s use CABS to solve the model.

solver = dp.CABS(model)
solution = solver.search()

for i, t in enumerate(solution.transitions):
    if t.name == "pack":
        print(f"pack {i}")

print(f"profit: {solution.cost}")

The solvers are listed in the API reference, and their restrictions are described in the individual pages. Also, we provide a guideline to select a solver.