Let's get started with DIDPPy by modeling and solving a simple knapsack problem.
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.
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}
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 :doc:`tutorial <tutorial>`, but here is a summary:
- State variables
r
andi
, corresponding to r and i, are defined with the target valuesc
and0
, 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 :meth:`~didppy.IntExpr.state_cost`.
- The condition to terminate the recursion is defined by the base case
i == n
.
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 :class:`~didppy.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 :class:`~didppy.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 :ref:`API reference <api-reference:Solvers>`, and their restrictions are described in the individual pages. Also, we provide a :doc:`guideline to select a solver </solver-selection>`.