# How to solve a binary LP.

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.

• In general, such a problem is NP-hard. Are you looking for (i) efficient algorithms to solve your problem approximately (approximation algorithm), or (ii) not-that-efficient algorithms to solve it exactly? – Clement C. Mar 24 '16 at 20:48
• I am looking for an efficient algorithm. – mohamed Mar 24 '16 at 20:57
• Then you probably (unless your exact problem is very constrained) have to give up on finding an exact solution. For general introduction (and specific examples) to approximation algorithms, you also may want to have a look at this book (Design of Approximations Algorithms by David P. Williamson and David B. Shmoys, available online for free), esp. Sections 4 and 5. – Clement C. Mar 24 '16 at 21:00
• I usually say: always try a MIP solver first. NP-hard does not prevent a MIP solver to solve some problems really fast. Especially if you don't have to prove optimality,(I.e. stop when gap is small). – Erwin Kalvelagen Mar 25 '16 at 15:49

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.
• use network flow algorithms, adapt them in order to take into account constraints $3)$ and $4)$ (the solution might not be optimal)