| 1 |
/*** |
| 2 |
!Test |
| 3 |
expected: |
| 4 |
- !Result |
| 5 |
solution: !Solution |
| 6 |
Total: 383 |
| 7 |
cost: [30, 27, 70, 2, 4, 22, 5, 13, 35, 55] |
| 8 |
objective: 383 |
| 9 |
open: [true, true, true, false, true] |
| 10 |
supplier: [5, 2, 5, 1, 5, 2, 2, 3, 2, 3] |
| 11 |
***/ |
| 12 |
|
| 13 |
%----------------------------------------------------------------------------- |
| 14 |
% Warehouse allocation |
| 15 |
% (Problem 034 in CSPLib) |
| 16 |
% vim: ft=zinc ts=2 sw=2 et tw=0 |
| 17 |
% |
| 18 |
% Guido Tack, [email protected] |
| 19 |
% 2007-02-22 |
| 20 |
% |
| 21 |
% Ported from the Gecode example |
| 22 |
%----------------------------------------------------------------------------- |
| 23 |
% A company needs to construct warehouses to supply stores with goods. Each |
| 24 |
% warehouse possibly to be constructed has a certain capacity defining how many |
| 25 |
% stores it can supply. Constructing a warehouse incurs a fixed cost. Costs |
| 26 |
% for transportation from warehouses to stores depend on the locations of |
| 27 |
% warehouses and stores. |
| 28 |
% |
| 29 |
% Determine which warehouses should be constructed and which warehouse should |
| 30 |
% supply which store such that overall cost (transportation cost plus |
| 31 |
% construction cost) is smallest. |
| 32 |
%----------------------------------------------------------------------------- |
| 33 |
|
| 34 |
include "globals.mzn"; |
| 35 |
|
| 36 |
%----------------------------------------------------------------------------- |
| 37 |
% Instance |
| 38 |
|
| 39 |
n_suppliers = 5; |
| 40 |
n_stores = 10; |
| 41 |
building_cost = 30; |
| 42 |
|
| 43 |
capacity = [1,4,2,1,3]; |
| 44 |
|
| 45 |
cost_matrix = |
| 46 |
[|20, 24, 11, 25, 30 |
| 47 |
|28, 27, 82, 83, 74 |
| 48 |
|74, 97, 71, 96, 70 |
| 49 |
| 2, 55, 73, 69, 61 |
| 50 |
|46, 96, 59, 83, 4 |
| 51 |
|42, 22, 29, 67, 59 |
| 52 |
| 1, 5, 73, 59, 56 |
| 53 |
|10, 73, 13, 43, 96 |
| 54 |
|93, 35, 63, 85, 46 |
| 55 |
|47, 65, 55, 71, 95|]; |
| 56 |
|
| 57 |
%----------------------------------------------------------------------------- |
| 58 |
% Model |
| 59 |
|
| 60 |
int: n_suppliers; |
| 61 |
int: n_stores; |
| 62 |
int: building_cost; |
| 63 |
array[1..n_suppliers] of int: capacity; |
| 64 |
array[1..n_stores,1..n_suppliers] of int: cost_matrix; |
| 65 |
|
| 66 |
int: MaxCost = max(i in 1..n_stores, j in 1..n_suppliers)(cost_matrix[i,j]); |
| 67 |
int: MaxTotal = (n_suppliers * building_cost) |
| 68 |
+ sum(i in 1..n_stores, j in 1..n_suppliers)(cost_matrix[i,j]); |
| 69 |
|
| 70 |
array[1..n_stores] of var 1..n_suppliers: supplier; |
| 71 |
array[1..n_suppliers] of var bool: open; |
| 72 |
array[1..n_stores] of var 1..MaxCost: cost; |
| 73 |
var 1..MaxTotal: Total; |
| 74 |
|
| 75 |
constraint |
| 76 |
sum (i in 1..n_suppliers) (building_cost * bool2int(open[i])) + |
| 77 |
sum (i in 1..n_stores) (cost[i]) |
| 78 |
= Total; |
| 79 |
|
| 80 |
constraint |
| 81 |
forall (i in 1..n_stores) ( |
| 82 |
cost_matrix[i,supplier[i]] = cost[i] |
| 83 |
); |
| 84 |
|
| 85 |
constraint |
| 86 |
forall (i in 1..n_suppliers) ( |
| 87 |
let { |
| 88 |
var int: use |
| 89 |
} in |
| 90 |
count(supplier,i,use) /\ use <= capacity[i] |
| 91 |
); |
| 92 |
|
| 93 |
constraint |
| 94 |
forall (i in 1..n_suppliers) ( |
| 95 |
(exists (j in 1..n_stores) (supplier[j] == i)) == open[i] |
| 96 |
); |
| 97 |
|
| 98 |
solve |
| 99 |
:: int_search( |
| 100 |
supplier ++ cost ++ [bool2int(open[i]) | i in 1..n_suppliers], |
| 101 |
first_fail, |
| 102 |
indomain_split, |
| 103 |
complete |
| 104 |
) |
| 105 |
minimize Total; |
| 106 |
|
| 107 |
output |
| 108 |
[ "warehouses:" ] |
| 109 |
++ |
| 110 |
[ "\nTotal = ", show(Total) ] |
| 111 |
++ |
| 112 |
[ "\nsupplier = [\n" ] |
| 113 |
++ |
| 114 |
[ "\t" ++ show(supplier[i]) ++ |
| 115 |
if i = n_stores then "\n]" |
| 116 |
elseif i mod 5 = 0 then ",\n" |
| 117 |
else "," |
| 118 |
endif |
| 119 |
| i in 1..n_stores |
| 120 |
] |
| 121 |
++ |
| 122 |
[ "\ncost = [\n" ] |
| 123 |
++ |
| 124 |
[ "\t" ++ show(cost[i]) ++ |
| 125 |
if i = n_stores then "\n]" |
| 126 |
elseif i mod 5 = 0 then ",\n" |
| 127 |
else "," |
| 128 |
endif |
| 129 |
| i in 1..n_stores |
| 130 |
] |
| 131 |
++ |
| 132 |
[ "\nopen = [\n" ] |
| 133 |
++ |
| 134 |
[ "\t" ++ show(open[i]) ++ |
| 135 |
if i = n_suppliers then "\n]\n" |
| 136 |
elseif i mod 5 = 0 then ",\n" |
| 137 |
else "," |
| 138 |
endif |
| 139 |
| i in 1..n_suppliers |
| 140 |
] |
| 141 |
|
| 142 |
%----------------------------------------------------------------------------- |
| 143 |
%----------------------------------------------------------------------------- |