%-----------------------------------------------------------------------------
% Uncapacitated Warehouse Location Problem
% (relaxation of Problem 034 in CSPLib)
%
% Guido Tack, tack@gecode.org
% 2007-02-22
%
% Ported from the Gecode example
%-----------------------------------------------------------------------------
% A company needs to construct warehouses to supply stores with goods.
% Constructing a warehouse incurs a fixed cost.  Costs
% for transportation from warehouses to stores depend on the locations of
% warehouses and stores.
%
% Determine which warehouses should be constructed and which warehouse should
% supply which store such that overall cost (transportation cost plus
% construction cost) is smallest.
%
% Capacity of each warehouse is not restricted, 
% this makes the problem a pure quadratic optimization problem
% Uncapacitated version by Simon de Givry @ INRA
% 2013-11-15
%-----------------------------------------------------------------------------

include "globals.mzn";

%-----------------------------------------------------------------------------
% Instance

%n_suppliers = 5;
%n_stores = 10;
%building_cost = 30;

%capacity = [1,4,2,1,3];

%cost_matrix =
% [|20, 24, 11, 25, 30
%  |28, 27, 82, 83, 74
%  |74, 97, 71, 96, 70
%  | 2, 55, 73, 69, 61
%  |46, 96, 59, 83,  4
%  |42, 22, 29, 67, 59
%  | 1,  5, 73, 59, 56
%  |10, 73, 13, 43, 96
%  |93, 35, 63, 85, 46
%  |47, 65, 55, 71, 95|]; 

%-----------------------------------------------------------------------------
% Model

int: n_suppliers;
int: n_stores;
array[1..n_suppliers] of int: building_cost;
% array[1..n_suppliers] of int: capacity;
array[1..n_stores,1..n_suppliers] of int: cost_matrix;

int: MaxCost = max(i in 1..n_stores, j in 1..n_suppliers)(cost_matrix[i,j]);
int: MaxTotal =   sum(i in 1..n_suppliers)(building_cost[i])
                + sum(i in 1..n_stores, j in 1..n_suppliers)(cost_matrix[i,j]); 

array[1..n_stores] of var 1..n_suppliers: supplier;
array[1..n_suppliers] of var bool: open;
array[1..n_stores] of var 0..MaxCost: cost;
var 0..MaxTotal: objective;

constraint
  sum (i in 1..n_suppliers) (building_cost[i] * bool2int(open[i])) +
  sum (i in 1..n_stores) (cost[i])
  = objective;

constraint
  forall (i in 1..n_stores) (
    cost_matrix[i,supplier[i]] = cost[i]
  );

%constraint
%  forall (i in 1..n_suppliers) (
%    let {
%      var int: use
%     } in
%    count(supplier,i,use) /\ use <= capacity[i]
%  );

constraint
  forall (i in 1..n_suppliers) (
%    (exists (j in 1..n_stores) (supplier[j] == i)) == open[i]
     forall (j in 1..n_stores) ((supplier[j] != i) \/ open[i])
  );

%
% solution checker for cap41.dzn: objective=9326144
%
%constraint
%   forall(i in 1..16) (
%   	   open[i] = [true,true,true,true,false,true,true,true,true,false,true,true,true,false,false,false][i]
%   );
%constraint
%   forall(i in 1..50) (
%   	   supplier[i] = 1 + ([7,11,0,5,7,0,1,2,7,7,3,10,5,0,6,7,3,8,3,6,3,6,10,0,11,10,12,10,10,0,0,10,0,2,11,11,5,5,7,5,10,3,7,6,12,7,7,6,5,11][i])
%   );

solve
  :: int_search(
    supplier ++ cost ++ [bool2int(open[i]) | i in 1..n_suppliers],
    first_fail,
    indomain_split,
    complete
  )
  minimize objective;

output
  [ "warehouses:" ]
  ++
  [ "\nobjective = ", show(objective) ]
%  ++
%  [ "\nsupplier = [\n" ]
%  ++
%  [ "\t" ++ show(supplier[i]) ++
%    if i = n_stores then "\n]"
%    elseif i mod 5 = 0 then ",\n"
%    else ","
%    endif
%  | i in 1..n_stores
%  ]
%  ++
%  [ "\ncost = [\n" ]
%  ++
%  [ "\t" ++ show(cost[i]) ++
%    if i = n_stores then "\n]"
%    elseif i mod 5 = 0 then ",\n"
%    else ","
%    endif
%  | i in 1..n_stores
%  ]
  ++
  [ "\nopen = [\n" ]
  ++
  [ "\t" ++ show(open[i]) ++
    if i = n_suppliers then "\n]\n"
    elseif i mod 5 = 0 then ",\n"
    else ","
    endif
  | i in 1..n_suppliers
  ]

%-----------------------------------------------------------------------------
%-----------------------------------------------------------------------------