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

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 http://www.or.deis.unibo.it/kp/Chapter6.pdf 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