Warehouse location

Describes the problem and presents the model and data files.

Warehouse location is another typical integer-programming problem. Suppose a company that is considering a number of locations for building warehouses to supply its existing stores. Each possible warehouse has a fixed maintenance cost and a maximum capacity specifying how many stores it can support. In addition, each store can be supplied by only one warehouse and the supply cost to the store differs according to the warehouse selected. The application consists of choosing which warehouses to build and which of them should supply the various stores in order to minimize the total cost, i.e., the sum of the fixed and supply costs. The instance used in this section considers five warehouses and 10 stores. The fixed costs for the warehouses are all identical and equal to 30. Table 1 depicts the transportation costs and the capacity constraints.

Table 1. Instance data for the warehouse-location problem
	Bonn	Bordeaux	London	Paris	Rome
capacity	1	4	2	1	3
store1	20	24	11	25	30
store2	28	27	82	83	74
store3	74	97	71	96	70
store4	2	55	73	69	61
store5	46	96	59	83	4
store6	42	22	29	67	59
store7	1	5	73	59	56
store8	10	73	13	43	96
store9	93	35	63	85	46
store10	47	65	55	71	95

The key idea in representing a warehouse-location problem as an integer program consists of using a 0-1 variable for each (warehouse, store) pair to represent whether a warehouse supplies a store. In addition, the model also associates a variable with each warehouse to indicate whether the warehouse is selected. Once these variables are declared, the constraints state that each store must be supplied by a warehouse, that each store can be supplied by only an open warehouse, and that each warehouse cannot deliver more stores than its allowed capacity. The most delicate aspect of the modeling is expressing that a warehouse can supply a store only when it is open. These constraints can be expressed by inequalities of the form

  forall( w in Warehouses, s in Stores )
    ctUseOpenWarehouses:
      Supply[s][w] <= Open[w];
  forall( w in Warehouses )
    ctMaxUseOfWarehouse:         
      sum( s in Stores ) 
        Supply[s][w] <= Capacity[w];

which ensures that when warehouse w is not open, it does not supply store s. This follows from the fact that open[w] == 0 implies supply[w][s] == 0.

As an alternative, you can write:

  forall(c in Connections)
    ctCapacity:             
      sum( <p,c> in Routes ) 
        Trans[<p,c>] <= Capacity;

This formulation implies that a closed warehouse has no capacity.

A warehouse-location model (warehouse.mod) describes an integer program for the warehouse-location problem, and Data for the warehouse-location model (warehouse.dat) depicts some instance data.

A warehouse-location model (`warehouse.mod`)

int Fixed = ...;
{string} Warehouses = ...;
int NbStores = ...;
range Stores = 0..NbStores-1;
int Capacity[Warehouses] = ...;
int SupplyCost[Stores][Warehouses] = ...;
dvar boolean Open[Warehouses];
dvar boolean Supply[Stores][Warehouses];


minimize
  sum( w in Warehouses ) 
    Fixed * Open[w] +
  sum( w in Warehouses , s in Stores ) 
    SupplyCost[s][w] * Supply[s][w];
    

subject to{
  forall( s in Stores )
    ctEachStoreHasOneWarehouse:
      sum( w in  Warehouses ) 
        Supply[s][w] == 1;
  forall( w in Warehouses, s in Stores )
    ctUseOpenWarehouses:
      Supply[s][w] <= Open[w];
  forall( w in Warehouses )
    ctMaxUseOfWarehouse:         
      sum( s in Stores ) 
        Supply[s][w] <= Capacity[w];
}

{int} Storesof[w in Warehouses] = { s | s in Stores : Supply[s][w] == 1 };
execute DISPLAY_RESULTS{
  writeln("Open=",Open);
  writeln("Storesof=",Storesof);
}

Data for the warehouse-location model (`warehouse.dat`)

Fixed = 30;
Warehouses = {Bonn,Bordeaux,London,Paris,Rome};
NbStores = 10;
Capacity = [1,4,2,1,3];
SupplyCost = [ 
       [ 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 ] ];

The statement declares the warehouses and the stores, the fixed cost of the warehouses, and the supply cost of a store for each warehouse. The problem variables

dvar boolean Open[Warehouses];
dvar boolean Supply[Stores][Warehouses];

represent which warehouses supply the stores, i.e., supply[s][w] is 1 if warehouse w supplies store s and zero otherwise.

The objective function

minimize
  sum( w in Warehouses ) 
    Fixed * Open[w] +
  sum( w in Warehouses , s in Stores ) 
    SupplyCost[s][w] * Supply[s][w];

expresses the goal that the model minimizes the fixed cost of the selected warehouses and the supply costs of the stores.

The constraint

  forall( s in Stores )
    ctEachStoreHasOneWarehouse:
      sum( w in  Warehouses ) 
        Supply[s][w] == 1;

states that a store must be supplied by exactly one warehouse.

The constraint

  forall( w in Warehouses, s in Stores )
    ctUseOpenWarehouses:
      Supply[s][w] <= Open[w];
  forall( w in Warehouses )
    ctMaxUseOfWarehouse:         
      sum( s in Stores ) 
        Supply[s][w] <= Capacity[w];

expresses the capacity constraints for the warehouses and makes sure that a warehouse supplies a store only if the warehouse is open.

A solution to warehouse.mod

For the instance data shown in Data for the warehouse-location model (warehouse.dat), OPL returns the optimal solution


Optimal solution found with objective: 383
open= [1 1 1 0 1]
storesof= [{3} {1 5 6 8} {7 9} {} {0 2 4}]