Buy all items of a shopping list with minimum price and distance travelled

Question

I have a list of 20 items that I want to buy i = (1,...,20), and there is 5 supermarkets in town j = (1,...5), there are two given entries:

Cij: the price of item "i" in supermarket "j"

Dj: the cost to travel between my house and the supermarket "j"

For convenience, I want to buy all the items in at most 2 markets (all the items are in all the markets). And after a trip to a market i always come back home, how can I formulate a Integer Linear Problem model to minimize my costs?

Answer 1

A simple MILP-model implemented in MiniZinc (with only three items for simplicity). In the model x_ij denotes whether item j is bought from store i, z_i denotes whether store i is visited.

int: Stores = 5;
int: Items = 3;

set of int: STORE = 1..Stores;
set of int: ITEM = 1..Items;

array[STORE,ITEM] of int: C = [| 5, 4, 5
                               | 3, 2, 5 
                               | 5, 5, 2 
                               | 8, 1, 5 
                               | 1, 8, 2 |];

array[STORE] of int: D = [5, 4, 5, 2, 3];
    
array[STORE,ITEM] of var 0..1: x;
array[STORE] of var 0..1: z;

% visit at most two shops
constraint sum(i in STORE)(z[i]) <= 2;

% buy each item once
constraint forall(j in ITEM)
    (sum(i in STORE)(x[i,j]) = 1);

% can't buy from a shop unless visited
constraint forall(i in STORE)
    (sum(j in ITEM)(x[i,j]) <= Items*z[i]);

var int: cost = sum(i in STORE)(2*D[i]*z[i]) + sum(i in STORE, j in ITEM)(C[i,j]*x[i,j]);

solve minimize cost;

output ["cost=\(cost)\n"] ++ 
["x="] ++ [show2d(x)] ++
["z="] ++ [show(z)];

Running gives:

cost=14
x=[| 0, 0, 0 |
     0, 0, 0 |
     0, 0, 0 |
     0, 1, 0 |
     1, 0, 1 |]
z=[0, 0, 0, 1, 1]