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.

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.

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);
}

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.

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