I have the optimization problem given below

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


$\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.

  • $\begingroup$ 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? $\endgroup$ – Clement C. Mar 24 '16 at 20:48
  • $\begingroup$ I am looking for an efficient algorithm. $\endgroup$ – mohamed Mar 24 '16 at 20:57
  • $\begingroup$ 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. $\endgroup$ – Clement C. Mar 24 '16 at 21:00
  • 1
    $\begingroup$ 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). $\endgroup$ – Erwin Kalvelagen Mar 25 '16 at 15:49

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).
  • $\begingroup$ I guess using Lagrangian relaxation would result in finding an upper bound on the solution. Am I right?. What if I want to find the exact solution. Also, if i use Lagrangian relaxation, you suggest relaxing C3 and C4, right?. $\endgroup$ – mohamed Mar 28 '16 at 13:06
  • $\begingroup$ How big is your problem? If it is small enough, perhaps a integer programming solver can solve the problem on its own (as Erwin suggests). If not, then you have to help it, for example by giving the solver upper bounds from a Lagrangian relaxation (so to answer your question, yes, lagrangian relaxation typically gives an upper bound for a max problem). $\endgroup$ – Kuifje Mar 28 '16 at 16:09
  • $\begingroup$ Regarding your second question: if you relax constraints c3 and c4, you will end up with a pure flow problem, which is very easy to solve, but which also has the integrity property. This means that the upper bound you will end up with will be as bad as the continuous relaxation, and we are back to square 1. Ideally, you need to relax a constraint so as to end up with a weakly NP-hard problem: one that you can solve with pseudo-polynomial algorithms. $\endgroup$ – Kuifje Mar 28 '16 at 16:12
  • $\begingroup$ Kuifje. please have a look to this formulation. cs.stackexchange.com/questions/57540/… $\endgroup$ – mohamed May 17 '16 at 21:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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