16. Locating warehouses

This chapter demonstrates the warehouse location problem. It shows how to use element, global counting (count), and linear constraints.

16.1. Problem

The problem is taken from  (Chapter 10; [71]) , see also CSPLib problem 34 . A company needs to construct warehouses to supply stores with goods. Each candidate warehouse has a certain capacity defining how many stores it can supply. Each store shall be supplied by exactly one warehouse. Maintaining a warehouse incurs a fixed cost. Costs for transportation from warehouses to stores depend on the locations of warehouses and stores.

We want to determine which warehouses should be opened (that is, supply to at least one store) and which warehouse should supply which store such that the overall cost (transportation costs plus fixed maintenance costs) is smallest.

In the following problem instance, the fixed maintenance cost c_fixed for a warehouse is \(30\). There are five candidate warehouses \(w_0, \ldots, w_4\) and ten stores \(s_0, \ldots, s_{9}\). The candidate warehouses have the following capacity:

\(w_0\)

\(w_1\)

\(w_2\)

\(w_3\)

\(w_4\)

1

4

2

1

3

The costs to supply a store by a candidate warehouse are defined by a matrix \(\mathtt{c_supply}_{i,j}\) (\(0\leq i<10\), \(0\leq j < 5\)) as follows:

\(w_0\)

\(w_1\)

\(w_2\)

\(w_3\)

\(w_4\)

\(s_0\)

20

24

11

25

30

\(s_1\)

28

27

82

83

74

\(s_2\)

74

97

71

96

70

\(s_3\)

2

55

73

69

61

\(s_4\)

46

96

59

83

4

\(s_5\)

42

22

29

67

59

\(s_6\)

1

5

73

59

56

\(s_7\)

10

73

13

43

96

\(s_8\)

93

35

63

85

46

\(s_9\)

47

65

55

71

95

16.2. Model

Program 16.1 A script for locating warehouses
...
const int n_warehouses = 5;
const int n_stores = 10;
const int capacity[n_warehouses] = {
  1, 4, 2, 1, 3
};
const int c_fixed = 30;
const int c_supply[n_stores][n_warehouses] = {
  ...
};

class Warehouses : public IntMinimizeScript {
protected:
  // [warehouses:variables]
public:
  Warehouses(const Options& opt)
    // [warehouses:variable initialization]
  {
    {
      // [warehouses:do not exceed capacity]
    }
    // [warehouses:open warehouses]
    // [warehouses:cost for each warehouse]
    // [warehouses:total cost]
    // [warehouses:branching]
  }
  // [warehouses:cost function]
  ...
};

...

Download: warehouses.cpp

The outline for the script implementing our model is shown in A script for locating warehouses . The data definitions are as described in the previous section.

As we need to minimize the total cost which is an integer variable, the script inherits from the class IntMinimizeScript which is a driver-defined subclass (similar to Script and Space) of IntMinimizeSpace (see Support for cost-based optimization ), see Scripts . This in particular means that the class must define a virtual cost() function returning an integer variable, see below.

16.2.1. Variables.

The script declares the following variables:

  IntVarArray  supplier;
  BoolVarArray open;
  IntVarArray  c_store;
  IntVar       c_total;

where:

  • for each store \(s\), there is a variable \(\mathtt{supplier}_s\) such that \(\mathtt{supplier}_s=w\) if warehouse \(w\) supplies store \(s\);

  • for each warehouse \(w\), there is a Boolean variable \(\mathtt{open}_w\) which equals one, if the warehouse \(w\) supplies at least one store;

  • for each store \(s\), there is a variable \(\mathtt{c_store}_s\) which defines the cost for \(s\) to be supplied by warehouse \(\mathtt{supplier}_s\);

  • a variable c_total which defines the total cost.

The variables are initialized as follows:

    : IntMinimizeScript(opt),
      supplier(*this, n_stores, 0, n_warehouses-1),
      open(*this, n_warehouses, 0, 1),
      c_store(*this, n_stores)

We only declare but do not initialize the cost variables c_store and c_total, as we will assign them by results obtained by posting expressions, see Expressions and relations . The difference between declaring variables and initializing them such that new variables are created is explained in detail in Creating integer variables .

16.2.2. Constraints.

For a given warehouse \(w\) the following must hold: the number of stores \(s\) supplied by \(w\) is not allowed to exceed the capacity of \(w\). This can be expressed by a counting constraint count (see Counting constraints ) as follows:

      IntSetArgs c(n_warehouses);
      for (int w=0; w<n_warehouses; w++)
        c[w] = IntSet(0,capacity[w]);
      count(*this, supplier, c, IPL_DOM);

Here, the array of integer sets c defines how many stores can be supplied by a warehouse, where \(\mathtt{c}_w\) contains every legal number of occurrences of \(w\) in supplier. To achieve strong propagation for the count constraint, we choose domain propagation by providing the additional argument IPL_DOM (see Selecting the propagation level ).

For a given warehouse \(w\) the following must hold: if the number of stores \(s\) supplied by \(w\) is at least one, then \(\mathtt{open}_w\) equals one. That is, \(\mathtt{open}_{\mathtt{supplier}_s}\) must be 1 for all stores \(s\). This is expressed by using element constraints (see Element constraints ) as follows:

    for (int s=0; s<n_stores; s++)
      element(*this, open, supplier[s], 1);

16.2.3. Cost computation.

The cost \(\mathtt{c_store}_s\) for each store \(s\) is computed by an element constraint (see Element constraints ), mapping the warehouse supplying \(s\) to the appropriate cost:

    for (int s=0; s<n_stores; s++) {
      IntArgs c(n_warehouses, c_supply[s]);
      c_store[s] = expr(*this, element(c, supplier[s]));
    }

The total cost c_total is defined by the cost of open warehouses (that is, the sum of \(\mathtt{open}_w\) for all warehouses \(w\) multiplied with the fixed maintenance cost for a warehouse) and the cost of stores (that is, the sum of the \(\mathtt{c_store}_s\) for all stores \(s\)):

    c_total = expr(*this, c_fixed*sum(open) + sum(c_store));

Note that the linear expression posted for defining the total cost mixes integer and Boolean variables and is automatically decomposed into the appropriate linear constraints, see Expressions and relations .

16.2.4. Branching.

The branching proceeds in two steps, implemented by two different branchings. The first branching assigns values to the variables \(\mathtt{c_store}_s\) and follows the strategy of maximal regret: select the variable for which the difference between the smallest value and the next larger value is maximal (see Branching on integer and Boolean variables ). The second branching makes sure that all stores are being assigned a warehouse. This branching is necessary as supplying a store could have the same cost for several different warehouses (depending on the data used for the model). Hence, even though all variables in c_store are assigned, not all variables in supplier must be assigned and hence the total cost is also not assigned. The branchings are posted in the appropriate order as follows:

    branch(*this, c_store, INT_VAR_REGRET_MIN_MAX(), INT_VAL_MIN());
    branch(*this, supplier, INT_VAR_NONE(), INT_VAL_MIN());

16.2.5. Cost function.

The cost function cost() to be used by the search engine is defined to return the total cost c_total:

  virtual IntVar cost(void) const {
    return c_total;
  }

16.3. More information

This problem is also available as a Gecode example, see warehouses . The model presented in (Chapter 10; [71]) proposes a better branching than the branching shown in the previous section.