Tag Archives: Knapsack

Integer Programming

On to a new section of the appendix!

The problem: Integer Programming.  This is problem MP1 in the appendix.

The description: Given a set of X of pairs (\bar{x},b), where \bar{x} is an m-tuple of integers, and b is an integer.  We’re also given an m-tuple \bar{c} and an integer B.

Can we find an m-tuple of integers \bar{y} such that:

  • \bar{x}*\bar{y} \leq b for each (\bar{x},b) pair
  • \bar{c}*\bar{y} \geq B.

Example: The definition above kind of hides the way we commonly think of integer (or linear) programming.  The X set is the set of constraints, and the \bar{x} and B make the objective function.  So, the set ((1,2,3,4),100) really corresponds to the constraint  1x 1+2x2+3x3+4x4 \leq 100.

Here is a simple Integer Programming problem written in the way we’re probably more used to seeing:

Given constraints:

x1 + x2 \leq 5

10x1 + 6x2 \leq 45

Maximize 5x1 + 4x2 (Or, as a decision problem, can 5x1 + 4x2 be \geq 23?

The answer is yes: If x1=3 and x2 = 2, we satisfy both constraints and get an objective value of 23.

Notice that if we allowed non-integer values for our variables, we would have a linear program, and could get to an objective value of 23.75 by setting x1=3.75 and x2=1.25.

Reduction: Karp’s paper uses 3SAT, which is fine, but it’s hard to see how the objective function works there.  I think a much more natural reduction is from Knapsack.

So we’re given a set of n items, each item i has a profit pi and weight wi.  We’re given a knapsack capacity B and a goal profit K.

Our constraints will be:

x1*w1+… xn*wn \leq B  (keep the total weight at B or less)

xi \leq 1 for all i (I can take at most 1 of each item)

-1*xi \leq 0 for all i (Each xi has to be at least 0)

The last sets of constraints force each xi variable to be either 0 or 1.

The objective function asks:

p1*x1 + … + pn*xn \leq B?

I think it’s pretty clear that this is exactly the rules for Knapsack written as an Integer Programming problem.

Difficulty: 3.  I think this might be too easy for a homework problem because the proof part of the reduction (Knapsack says “yes” if and only if  IP says “yes”) is trivial.  But the need for the last set of constraints (that each variable is >=0, written as a <= equation) is a fun wrinkle that will mess up some people.

Production Planning

This is one of those problems where we eliminate a lot of the parameters and are still left with a version that in NP-Complete.  I guess I would have started with the stripped-down version first, since adding extra parameters keeps the problem NP-Complete.

The problem: Production Planning.  This is problem SS21 in the appendix.

The description: Given a positive number n of time periods, and for each period i, several non-negative parameters: demand (ri), production capacity (ci), setup cost (bi), incremental production cost coefficient (pi), and inventory cost coefficient (hi).  We’re also given an overall bound B.  Can we find a positive production amount (xi)  for each period such that:

  • xi ≤ ci for all i (we never produce more than the production capacity)
  •  The inventory on hand for each period (Ii =\sum_{j=1}^i(xj -rj)  is non-negative
  • \sum_{i=1}^n(pixi+hiIi) + \sum_{x_{i}>0}bi ≤ B?

Example: There are a lot of variables here, but here’s what it’s really saying:

Suppose we have a factory that makes some product, and the factory’s schedule for making the product is split into time periods.  In each time period, we can only make a certain amount (ci) of the product, and it costs a certain amount to use the factory at all during a time period (bi) and then an additional amount to make each instance of the product (pi).   Each time period also has a demand (ri) that has to be met.  We can get ahead of the demand by producing more than we need (leaving Ii extra around at time i), but also at a cost (hi).

Suppose I have 3 time periods:

Time Period Production Capacity Demand Production Cost Inventory Cost Production Setup
1 5 3 2 1 6
2 5 3 4 3 2
3 1 2 20 20 5

Since at time period 3, we have less production capacity than demand, we will have to carry over inventory from a previous time period.  There are basically four strategies to meet the demands:

  1. Produce 4 units at time period 1, 3 at time 2, and 1 at time 3.  At time 1, this costs 6 to set up production, 4×2 to make the goods, and 1×1 to store the extra good (So 15).  At time period 2, it costs 2+3×4+1×3 = 17, and time period 3, it costs 5+1×20+0x20 = 25, for 57 total cost.
  2. Produce 3 units at time period 1, 4 at time 2, and 1 at time 3.  At time 1, this costs 6+3×2+0x1 = 12.  At time period 2, it costs 2+4×4+1×3 = 21. At time period 3, it costs 5+1×20+0x20  25.  This is a total cost of 58.
  3. Produce 5 units at time period 1, 3 at time period 2, and 0 at time period 3.  This would cost 6+5×2+2×1 = 18 at time 1, 2+3×4+2×3 =20, and 0 at time 3, for a cost of 38.
  4. Produce 3 units at time period 1, 5 at time period 2, and 0 at time period 3.  This would cost 6+3×2+0x1 =12 at time 1, 2+5×4+2×3 = 28 at time 2, and 0 at time 3, for a total time of 40.

So option 3 is the best choice.  But if we raised the inventory cost of time period 1 significantly (say, to 50), then option 3 would cost 114, and option 4 would still cost 40, and be best.

Reduction: The paper by Florian, Lenstra, and Rinnooy Kan say they use Knapsack, but by our definitions, the problem is really Sum of Subsets.    So we’re given a set of integers A= {a1 .. an} and a target B.    We will build a production planning instance with n+1 time periods numbered from 1 to n.  The demand of each period is B.  The b costs (to set up production) are 1 at all periods.   The capacity at time period 0 is n*B, and the capacity at time period i > 0 is ai.  The production cost at time period 0 is 0, the production cost at time period i is \frac{a_i -1}{a_i}.  All inventory costs are 0.   The cost bound B’ is equal to the SOS bound B + 1.

Since it costs 1 to make any amount of goods (up to our capacity limit) in time 0, we might as well make all of it that we can.  This gives us n*B goods, and will be enough to supply the demands at all of the other time periods except for the last, leaving B left over to be supplied in the last time period.  Notice that our production cost fraction is built in such a way that if in time period i, we make ai goods, we pay exactly ai cost.  If we build less than ai goods in time period i (but more than 0), we pay more than ai cost in that time period.  So the only to get a total cost of B’ while meeting the demand is to make exactly ai of the good in each time period that makes goods.  This corresponds to a subset of A that sums to exactly B.

Difficulty: 5.  If you do use this in a class, I’d give them a simpler version where you don’t even mention the inventory costs, and where the b cost is always 1, and where the demands are always equal in each time period, since that’s what the reduction does.

Protected: Sequencing With Deadlines and Setup Times

This content is password protected. To view it please enter your password below:

Protected: Knapsack

This content is password protected. To view it please enter your password below: