1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ What specifically prevents you from extending the usual solutions for knapsack? $\endgroup$ – Raphael Oct 11 '16 at 23:28
  • $\begingroup$ This seems to be a partially decisionified version of a multi-criteria optimization problem. As such, it may be harder than usual Knapsack. In particular, it's no longer per se clear what "optimal" means; you get many Pareto-optimal solutions. (Your version does not have this particular problem.) $\endgroup$ – Raphael Oct 11 '16 at 23:31
  • $\begingroup$ Specifically, I guess the way I am looking at it, the z for each of my items is analogous to the "value" in the knapsack problem, and the number of items (c) is analogous to the "weight." It's just like a knapsack problem where very item weighs 1, which is trivial. But I can't figure out where to fit d into the knapsack problem. I can't say something like "if min(avg(w),avg(x),avg(y)) <= d then this item can't be part of our solution" for each iteration, because it's possible that items I might later add will raise my min to an acceptable level. $\endgroup$ – Nathan Williamson Oct 11 '16 at 23:54
  • $\begingroup$ Moreover, if I just build out my entire set of c items, then check against d, and throw the solution if the condition is not met and try the next, then I've devolved into brute force (I think?). So where does d come in? $\endgroup$ – Nathan Williamson Oct 11 '16 at 23:58
  • $\begingroup$ Right. I don't think the Knapsack model is working for you. You are essentially maximising two independent quantities. $\endgroup$ – Raphael Oct 12 '16 at 1:56
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ By "very slow" do you mean intractable? If so, is there a different type of (non-DP) algorithm that would be tractable? $\endgroup$ – Nathan Williamson Oct 12 '16 at 6:58
  • $\begingroup$ @NathanWilliamson, I mean that it runs in pseudopolynomial time but depending on the size of the w,x,y,z-fields and the number of items it might take too long in practice to be feasible. $\endgroup$ – D.W. Oct 12 '16 at 15:54
  • $\begingroup$ Yeah, that seems likely. Oh well. Thanks for your input! $\endgroup$ – Nathan Williamson Oct 12 '16 at 15:59
  • $\begingroup$ Follow-up: I'm looking into solving the problem using integer linear programming and using Java ILP (javailp.sourceforge.net). $\endgroup$ – Nathan Williamson Oct 12 '16 at 17:52
  • $\begingroup$ When you say "then every one of your requirements can be expressed as a linear inequality on the xi's," can you give me an example of what you mean? I'm trying to figure out how to create an input that Java ILP can consume, and I'm having trouble figuring out how to do what you say in that context. $\endgroup$ – Nathan Williamson Oct 12 '16 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.