1
$\begingroup$

In combinatorial optimization, there are many problems that can be formulated as either Network Flow model or Mixed Integer Programming (MIP), e.g. supply chains, transportation, and graph-base problems. Some solvers make use of logical and/or graph-base syntax to efficiently solve network problems. And then the Network Simplex method is applied.

Also, As stated in Bazaraa, M.S., Jarvis, J.J. , and Sherali, H.D.; Linear programming and network flows, 4th Edition, Hoboken, New Jersey: Wiley & Sons, Inc., 2010; page 453:

We discuss appropriate data structures that facilitate the implementation of such a graph-theoretic procedure on the computer. The overall efficiency with which such a procedure operates enables one to solve problems 200-300 times faster than with a standard simplex approach that ignores any inherent special structures other than sparsity.

Practically speaking, from the aspect of time efficiency, are there any significant differences between modelling as a mixed integer programming and modeling as a network problem? And why (other than sparsity)?

Which optimization solvers are computationally fast at solving Network problems?

$\endgroup$
  • 1
    $\begingroup$ Maybe you should read the rest of that chapter. $\endgroup$ – David Ketcheson Oct 26 '14 at 5:18
1
$\begingroup$

Practically speaking, from the aspect of time efficiency, are there any significant differences between modelling as a mixed integer programming and modeling as a network problem? And why (other than sparsity)?

Yes. The reason network simplex is faster primarily has to do with exploiting the total unimodularity of network matrices -- basically, network matrices are always structured such that their submatrices have integral inverses. This property means that for network problems, instead of having to enumerate a branch-and-bound tree to obtain an integral solution, we can invert the columns of the coefficient matrix corresponding to variables in the simplex basis and obtain an integral solution. These inversion operations are cheaper than solving the branch-and-bound tree, in that they run in worst-case polynomial time (even better than ordinary simplex, which runs in worst-case exponential time, but typically in linear time); branch-and-bound runs in worst-case exponential time, and also typically runs in exponential time for general mixed-integer programs.

Sure, sparsity is nice too, and a typical property of network problems, but the main speed gains come from being able to use regular linear algebra operations to obtain integral solutions instead of branch-and-bound, which is a glorified guess-and-check scheme.

$\endgroup$
  • $\begingroup$ And which optimization solvers are specifically tailored to manage network flow problems? $\endgroup$ – Moh_NA_X Oct 26 '14 at 8:11
  • $\begingroup$ Any commercial LP solver will have solvers specialized for network flow problems expressible as LPs. The two best commercial LP solvers out there are CPLEX and Gurobi, which routinely outperform other software by at least an order of magnitude, and benchmarks are usually presented yearly at the annual INFORMS meeting to back up these performance claims. Open source solvers might also have network simplex-type algorithms. $\endgroup$ – Geoff Oxberry Oct 26 '14 at 17:32
  • $\begingroup$ What I've heard (from a talk by Bob Bixby) is that current simplex implementations are about as fast, or slightly faster, than current network simplex implementations. $\endgroup$ – tmyklebu Oct 26 '14 at 22:46
  • $\begingroup$ I tried to find a written reference for Bixby's talk and could not find one. Do you have a link or a paper reference? According to CPLEX's user docs, using network simplex yields speedups of up to 10-100x on network problems compared to primal or dual simplex algorithms. (According to Bixby, dual simplex is typically used.) $\endgroup$ – Geoff Oxberry Oct 27 '14 at 0:03

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.