Uncapacitated Facility Location - Cutting Planes

The following example will illustrate how one might use OSI to simulate the root note of a branch and cut algorithm (i.e., cutting planes) for an integer linear program (ILP). The example in this section is the Uncapacitated Facility Location (UFL) problem which can be described as follows:

Data

• a set of depots $N = \{ 1,...,n \}$, a set of clients $M = \{1,...,m \}$,
• the transportation cost $c_{ij}$ to service client $i$ from depot $j$,
• the fixed cost $f_j$ for using depot $j$

Variables

• $x_{ij}$ is the amount of the demand for client $i$ satisfied from depot $j$
• $y_j$ is 1 if the depot is used, 0 otherwise