Warehouse Location Problem as an integer progam instead of a mixed-integer program

Question

Given a set of costumers $M = \{1, \dots , m \}$ and a set of of factories $N = \{1, \dots , n\}$ we have

• $c_{ij} \geq 0$ costs to deliver to costumer $i \in M$ from factory $j \in N$
• $F_j \geq 0$ fixed costs to run factory $j \in n$

We try to minimize the costs. Therefor we model the problem as a mixed-integer program:

• $y_j \in \{0,1\}$ and $y_j = 1$ iff we decide to run factory $j$ (integer variable)
• $x_{ij}$ the fraction of the consumption of costumer $i$ which is delivered by factory $j$ (non-integer variable)

We add restistrictions to make it correct:

• $\sum_{j \in N} x_{ij} = 1$ for each $i \in M$ to ensure that factories delivering to $i$ add up to the whole consumption
• $x_{ij} \leq y_j$ for each $i \in M, j \in N$ to ensure that if a factory delivers it is open
• $x_{ij} \geq0 $ for each $i \in M, j \in N$

The function to minimize is

$$\sum_{j \in N} F_jy_j + \sum_{i \in M}\sum_{j \in N}c_{ij}x_{ij}.$$

This is denoted by Warehouse Location Problem (WLP) modeled as a mixed-integer program.

My questions is concerning the solution of such problems. I think that if there is a optimal solution to an instance of a WLP then there is a optimal solution such that

• $y_i \in \{0,1\}$ by definition

but also

• $x_{ij} \in \{0,1\}$.

Because in the optimal solution costumer $i$ will always provided by one cheapest factory $j$. As there is no limit on the capacity of the factories. There is no need to split up. Is that correct?

So the problem could be modeled equivalently as a integer program as well and we would obtain solutions which are optimal? I have taken the definition from a book. Why is it modeled like this? For performance reasons? I thought mixed-integer programs are harder to solve then integer programs.

Answer 1

You're right that in the uncapacitated version of the warehouse location problem the value of $x_{ij}$ will be $0$ or $1$ at the optimal solution. Of course, in the capacitated version this might not be the case.

It is generally somewhat easier to solve mixed-integer programs than integer programs, though. Linear programs are easy; integer programs are hard. The more you can make your problem look like a linear program, then, the easier it will be to solve. In particular, any variables that don't absolutely have to be integers you should leave as reals. That's the reason for the lack of restriction on the $x_i$'s in the warehouse location problem.

To expand on this some, the major techniques for solving integer programs -- Gomory's cutting plane algorithm and branch-and-bound -- actually spend a decent amount of time solving the linear program relaxations of restrictions of the original integer program. Any variables that don't have to be integers cut down on the running time of the algorithm, since you don't have to generate cutting planes that exclude fractional solutions involving them (in Gomory's algorithm) or generate branches involving them (in branch-and-bound).