Re: [eclipse-clp-users] Trying to code 0-1 Multiple Knapsack Problem.

From: Joachim Schimpf <>
Date: Sun, 27 Oct 2013 01:12:54 +0000
On 25/10/2013 18:12, Paul Cannongeyser wrote:
> Trying to code 0-1 Multiple Knapsack Problem.
> I ran this example.  My results don't agree with the answer in the book.
> % From entitled 0-1 Multiple knapsack problem, Example 6.2
> I now realize that I must add constraints that say that X1 and Y1 cannot both be 1 at the same time, 
> same for X2 and Y2, same for X3 and Y3, etc., in other words, the character packing the two knapsacks 
> has one of each item and can put it into the first knapsack or the second knapsack or leave it behind.

Correct.  Whenever you get a solution that is better than the one
you expect, you are likely to have forgotten a constraint, in this
case constraint (6.3) on page 157.

> I suppose I could do it this way:
>      X1 + Y1 $=< 1,
>      X2 + Y2 $=< 1,
>      X3 + Y3 $=< 1, etc.
> Is this the correct (or generally accepted) approach?

Yes, this is how you would model it with LP/MIP constraints.

However, to save yourself a lot of typing, you should use an array
for modelling, rather than working with individual variables.
Then you have X[1,1] for X1 up to X[2,10] for Y10, and you can
use loops to set up the constraints.

-- Joachim
Received on Sun Oct 27 2013 - 01:13:03 CEST

This archive was generated by hypermail 2.2.0 : Tue Oct 29 2013 - 18:13:26 CET