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

From: Paul Cannongeyser <paul_dice_2_at_...75...>
Date: Fri, 25 Oct 2013 10:12:20 -0700 (PDT)
Trying to code 0-1 Multiple Knapsack Problem.

I ran this example.  My results don't agree with the answer in the book.

----- knapsack_6.ecl
% Multiple Knapsack Problem Example.

% Run in this way: main(Cost, Vars).
% From http://www.or.deis.unibo.it/kp/Chapter6.pdf entitled 0-1 Multiple knapsack problem, Example 6.2
/*
Results:
?- main(Cost, Vars).
Cost = 593.0
Vars = [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, ...]
Yes (0.05s cpu)

[1, 0, 1, 0, 1, 0, 0, 0, 0, 0]
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0]

Their solution (on page 176):

1 0 1 0 0 1 0 0 0 0 for first knapsack.
0 0 0 1 1 0 0 0 1 0 for second knapsack.

*/

:- lib(eplex).

:- eplex_instance(prob).  

main(Cost, Vars) :-
        Vars = [X1,X2,X3,X4,X5,X6,X7,X8,X9,X10,Y1,Y2,Y3,Y4,Y5,Y6,Y7,Y8,Y9,Y10], 
        prob: (Vars $:: 0..1), % Either pack it or leave it behind.

        prob: (18*X1 + 9*X2 + 23*X3 + 20*X4 + 59*X5
               + 61*X6 + 70*X7 + 75*X8 + 76*X9 + 30*X10 $=< 103),
   % Sum of the weights constrained by the capacity for first knapsack.
        prob: (18*Y1 + 9*Y2 + 23*Y3 + 20*Y4 + 59*Y5
               + 61*Y6 + 70*Y7 + 75*Y8 + 76*Y9 + 30*Y10 $=< 156),
               % Sum of the weights constrained by the capacity for second knapsack.

        prob: integers([X1,X2,X3,X4,X5,X6,X7,X8,X9,X10,
                        Y1,Y2,Y3,Y4,Y5,Y6,Y7,Y8,Y9,Y10]),  % This is a mixed integer problem.
        prob: eplex_solver_setup(max(
               78*X1 + 35*X2 + 89*X3 + 36*X4 + 94*X5 + 75*X6 + 74*X7 + 79*X8 + 80*X9 + 16*X10
+ 78*Y1 + 35*Y2 + 89*Y3 + 36*Y4 + 94*Y5 + 75*Y6 + 74*Y7 + 79*Y8 + 80*Y9 + 16*Y10)),
                % Maximize the value.

        %——————————- End of Modelling code

        prob: eplex_solve(Cost),  
        (foreach(V, Vars) do
            prob: eplex_var_get(V, typed_solution, V) 
        ),
        writeln([X1,X2,X3,X4,X5,X6,X7,X8,X9,X10]),
        writeln([Y1,Y2,Y3,Y4,Y5,Y6,Y7,Y8,Y9,Y10]).
-----

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.

I suppose I could do it this way:

     X1 + Y1 $=< 1,
     X2 + Y2 $=< 1,
     X3 + Y3 $=< 1, etc.
 
i.e.,
 
 X1 Y1
 -- --
  0  0  Permissible
  1  0  Permissible
  0  1  Permissible
  1  1  Not permissible
  
Is this the correct (or generally accepted) approach?
Received on Fri Oct 25 2013 - 17:16:20 CEST

This archive was generated by hypermail 2.2.0 : Mon Jul 09 2018 - 02:05:30 CEST