Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.