/* 

  Generalized Assignment Problem in Picat.

  From GLPK:s example gap.mod
  """
  GAP, Generalized Assignment Problem

  Written in GNU MathProg by Andrew Makhorin <mao@mai2.rcnet.ru>
  
  The Generalized Assignment Problem (GAP) is to assign a set of jobs
  to a set of agents subject to the constraints that each job must be
  assigned exactly to one agent and the total resources consumed by all
  jobs assigned to an agent must not exceed the agent's capacity.
  """

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/


import mip.


main => go.


go =>
  % number of agents 
  m(M),
  % number of jobs 
  n(N),
  % resource consumed in allocating job j to agent i 
  a(A),
  % resource capacity of agent i 
  b(B),
  % cost of allocating job j to agent i 
  c(C),


  X = new_array(M, N),
  X :: 0..1,

  % the objective is to find cheapest assignment (note that gap can also
  % be formulated as maximization problem) 
  Obj #= sum([C[I,J] * X[I,J] : I in 1..M, J in 1..N]),

  % job j must be assigned exactly to one agent 
  foreach(J in 1..N) 
    sum([X[I,J] : I in 1..M]) #= 1
  end,

  % total amount of resources consumed by all jobs assigned to agent i
  %  must not exceed the agent's capacity 
  foreach(I in 1..M)  
    sum([A[I,J] * X[I,J] : J in 1..N])  #<= B[I]
  end,

  solve($[min(Obj)], X),

  println(obj=Obj),

  foreach(Row in X) println(Row.to_list()) end,
  
  nl.

% """
% These data correspond to the instance c515-1 (gap1) from:
%
%   I.H. Osman, "Heuristics for the Generalised Assignment Problem:
%   Simulated Annealing and Tabu Search Approaches", OR Spektrum, Volume
%   17, 211-225, 1995
%
%   D. Cattrysse, M. Salomon and L.N. Van Wassenhove, "A set partitioning
%   heuristic for the generalized assignment problem", European Journal
%   of Operational Research, Volume 72, 167-174, 1994 
%
% The optimal solution is 261 (minimization) or 336 (maximization) 
% """

m(M) => M = 5.

n(N) => N= 15.

a(A) => 
  A = 
 [
 [ 8,15,14,23, 8,16, 8,25, 9,17,25,15,10, 8,24],
 [15, 7,23,22,11,11,12,10,17,16, 7,16,10,18,22],
 [21,20, 6,22,24,10,24, 9,21,14,11,14,11,19,16],
 [20,11, 8,14, 9, 5, 6,19,19, 7, 6, 6,13, 9,18],
 [ 8,13,13,13,10,20,25,16,16,17,10,10, 5,12,23]].

b(B) => B = [36,34,38,27,33].

c(C) => 
 C =
[
[17,21,22,18,24,15,20,18,19,18,16,22,24,24,16],
[23,16,21,16,17,16,19,25,18,21,17,15,25,17,24],
[16,20,16,25,24,16,17,19,19,18,20,16,17,21,24],
[19,19,22,22,20,16,19,17,21,19,25,23,25,25,25],
[18,19,15,15,21,25,16,16,23,15,22,17,19,22,24]].