How to solve a binary LP.

Question

I have the optimization problem given below

max $\sum_{i=1}^{N}\sum_{j=1}^{M} x_{ij}R_{ij}$

s.t

$\quad 1)\quad \sum_{j=1}^{M} x_{ij}=1 \quad \forall i$

$\quad 2)\quad x_{ij} \in {0,1}$

$\quad 3)\ \ \sum_{j=1}^{M} x_{ij}R_{ij} \geq R^b_{i} \quad \forall i$

$\quad 4)\ \ \sum_{i=1}^{N} x_{ij}R_{ij} \leq R^u_{j} \quad \forall j$

$\quad 5)\ \ \sum_{i=1}^{N} x_{ij}\leq S_{j} \quad \forall j$

The parameters $N, M, R_{ij},R^b_{i},R^u_{j}, S_{j}$ are given.

It is clear the problem is binary LP. My question is which method I should use to solve it?. Obviously, I can use branch and bound to find the exact solution, but this might be insufficient, particularly for large $N$ and $M$. In literature, they also talk about LP relaxation and Lagrangian relaxation. I would be grateful if somebody can give me a general advice on how to solve such a problem.

Answer 1

Do you have more information about the problem?

It looks very much like a network flow problem, with units of flow going from nodes $\{1,\cdots,N\}$ to nodes $\{1,\cdots,M\}$.

If you ignore constraints $3)$ and $4)$ you have a maximum cost flow problem which is very easy to solve, either with specific flow algorithms, or with a simplex algorithm (flow problems do not require constraints $2)$), therefore branch-and-bound is not necessary.

This suggests at least two options to solve your problem:

• use network flow algorithms, adapt them in order to take into account constraints $3)$ and $4)$ (the solution might not be optimal)
• use a Lagrangian relaxation or a Dantzig-Wolfe decomposition in order to separate your problem into a master problem and slave problems, your slave problems are pure network flow problems and are therefore easy to solve (although this may not be the best strategy: see comments below).