Integer programming: a warehouse location problem

Describes the problem and presents the model and data files.

Warehouse location is a typical discrete optimization problem. A company is considering a number of locations for building warehouses to supply a set of stores. Each possible warehouse has a fixed operating cost and a maximum capacity specifying how many stores it can support. In addition, each store must be supplied by exactly one warehouse and the cost to supply a store depends on the warehouse selected. The model consists of choosing which warehouses to build and which warehouse to assign to each store in order to minimize the total cost, i.e., the sum of the fixed and supply costs. Consider an example with five warehouses and ten stores. The fixed costs for the warehouses are all identical and equal to 30. The instance data for the problem, shown in the following table, reflects the transportation costs and the capacity constraints defined in the data file warehouse.dat.

Table 1. Instance data for the warehouse location problem
Warehouses 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

To represent our warehouse location problem as an integer program, the model, warehouse.mod, uses a 0-1 Boolean variable for each combination of warehouse and store to represent whether or not a warehouse supplies a store. In addition, the model 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.

Warehouse location, as a discrete optimization problem (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);
}

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 

supply[w][s] <= open[w];

which ensure that when warehouse w is not open, it cannot supply store s. This follows from the fact that open[w] == 0 implies supply[w][s] == 0. In fact, these constraints can be combined with the capacity constraints to obtain 

  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];

This formulation implies that a closed warehouse has no capacity.

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 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 warehouse and the supply costs of 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 constraints 

  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];

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

A solution to warehouse.mod

For the instance data depicted in the table Table 1, OPL returns the following optimal solution:

Final Solution with objective 383.0000:
  open = [1 1 1 0 1];
  supply = [[0 0 0 0 1]
            [0 1 0 0 0]
            [0 0 0 0 1]
            [1 0 0 0 0]
            [0 0 0 0 1]
            [0 1 0 0 0]
            [0 1 0 0 0]
            [0 0 1 0 0]
            [0 1 0 0 0]
            [0 0 1 0 0]];