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\), \(v_0 = 5\), \(v_1 = 25\), \(v_2 = 35\), \(v_3 = 50\), and \(c = 50\).

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)
r = model.add_int_var(target=capacity)
i = model.add_element_var(object_type=item, target=0)

w = model.add_int_table(weights)
p = model.add_int_table(profits)

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])

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)\).
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.

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 ForwardRecursion to solve the model.

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

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

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

This solver is the most generic, i.e., it can handle almost any model you can formulate in DIDPPy. However, if your DP model has a particular structure, you can use more efficient solvers. For example. you can use CABS for this model.

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

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

print("profit: {}".format(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.