Dynamic programming: how to solve a problem with multiple constraints?

Question

I've got a real-world issue that I'm trying to come up with a dynamic programming algorithm to solve. It's similar in appearance to the knapsack problem, but it has more constraints, which has got me stumped. A simplified version of the problem:

Suppose I need to fill a basket with an arbitrary number of items c. The items have four properties: w, x, y, and z, each of which has a positive or negative number, with z being equal to the mean of the other three properties. My goal is to pick items such that the average z of my c items is at a maximum, but also

min(avg(w), avg(x), avg(y)) > d

for some arbitrary value d.

So, for example, c items each with w, x, and y (respectively) of (1000, 1000, -1), would have a very high average z (666.3), but would fail the second constraint if we set d >= 0, as the average y is -1.

The input would be the set of items from which to choose and the values of c and d, and the output would be a list of the c items I need to select to make the optimum full basket. Note that an item can only be selected once (no duplicates).

As I mentioned, I can see an obvious similarity to the knapsack problem, but I'm having trouble wrapping my mind around how to modify its basic structure to account for these different constraints. Or perhaps I am barking up the wrong tree trying to use the knapsack problem as a model?

Any input/pseudocode would be appreciated!

Answer 1

The practical solution is to formulate this as an instance of integer linear programming and apply an ILP solver. There will be a clean formulation as ILP, and it might work pretty well. For each item, you have an associated variable $v_i$ that is zero or one according to whether item $i$ is included in the basket or not (one means that it is included); then every one of your requirements can be expressed as a linear inequality on the $v_i$'s.

For example, the requirement that you have exactly $c$ items in the basket corresponds to the linear equality

$$v_1 + v_2 + \dots + v_n = c.$$

The requirement that min(avg(w), avg(x), avg(y)) > d is equivalent to the requirements that the sum of the $w$-fields is at least $c \times d$, and the sum of the $x$-fields is at least $c \times d$, and the sum of the $y$-fields is at least $c \times d$. The former can be expressed as

$$w_1 \cdot v_1 + w_2 \cdot v_2 + \dots + w_n \cdot v_n > c \times d,$$

where $w_i$ is the value of the $w$-field for the $i$th possible item. Note that $w_1,\dots,w_n,c,d$ are all constants (known from the problem statement), and $v_1,\dots,v_n$ are the variables, so this is a linear inequality. Similarly for the sum of the $x$-fields and $y$-fields.

Finally, the goal of maximizing the average of the $z$-fields is equivalent to maximizing the sum of the $z$-fields of the selected items. This corresponds to maximizing the following (linear) objective function:

$$z_1 \cdot v_1 + \dots + z_n \cdot v_n.$$

All of these are linear. Finally, you can express the requirement that each $v_i$ must be either 0 or 1 by adding linear inequalities $0 \le v_i \le 1$ and requiring that $v_i$ be an integer.

---

The dynamic programming solution involves subproblems of the following form:

• What's the maximum achievable value for the sum of $z$-fields, when restricted to choosing exactly $i$ of the first $j$ items, such that the sum of the $w$-fields is at least $\alpha$, the sum of the $x$-fields is at least $\beta$, and the sum of the $y$-fields is at least $\gamma$.

You get a subproblem for each combination of values for $i,j,\alpha,\beta,\gamma$. That's a lot of subproblems, so the dynamic programming algorithm will probably be very slow.