Is the Network Simplex Algorithm Efficient for Mixed Binary and Linear Flows in Network Flow Problems?

Question

I'm working on a network flow problem where the flow on all edges originating from the source node must be binary. Beyond this initial stage, the flows can be linear, and given the capacities are strictly between 0 and 1, these flows will be non-integer. Initially, I considered solving this with the standard branch-and-bound approach, utilizing the simplex method for linear relaxations. However, I've come across suggestions that the network simplex algorithm might offer a speed advantage. According to this post, the key benefit of the network simplex algorithm is its efficiency in scenarios typically requiring extensive branch-and-bound tree enumerations.

Given that my problem will definitely involve non-integer flows for some edges, I'm questioning whether the network simplex method would indeed be faster for my specific case. Could someone provide insights or experiences with using network simplex under such conditions?

Answer 1

Just to make sure I understand, for edges other than those coming directly from the source, the capacity will be some fraction between 0 and 1 (inclusive).

I would like to address something in the post that you linked. The answerer is comparing solving a network flow problem to solving an MILP with branch and bound. As it seems you are aware, if all of the input data of a network flow problem is integral, the solution will also be integral. But this also means that if you run the branch and bound algorithm on a network flow problem, the solution to the linear relaxation is integral so there is no branching that needs to be done. So their answer explains why it is beneficial to model a problem as a network flow problem, but fails to explain why network simplex is better than "regular" simplex for solving (linear) network flow problems.

I would also like to point out that the network simplex algorithm is only guaranteed to return an integral solution when the data is integral. So you would still need to perform branch-and-bound (or some other algorithm) only you could replace the use of the simplex algorithm with the network simplex algorithm. In fact, you could replace it with any algorithm for your network flow problem (max-flow or min-cost flow), but there are certain properties you would probably want the algorithm to have.

Now, let us compare the regular simplex algorithm and the network simplex algorithm. The "general wisdom" that I was taught was that the network simplex algorithm is indeed faster than the simplex algorithm. More generally "combinatorial" algorithms are faster than numeric ones. The simplex algorithm requires computing an inverse matrix at each step, which is costly. I believe there are tricks you can do to avoid having to do the full inverse calculation each time, but still these kinds of matrix manipulations are slow. In the corresponding step of the network simplex algorithm, you just need to find a cycle in a graph which can be done via BFS.

However, details of implementation could be a larger influence than the choice of algorithm. As someone mentions in the comments of the post you linked, experts in the field believed that then-current implementations of simplex were as fast or faster than implementations of network simplex. This is likely due to the fact that there are commercial solvers like CPLEX and Gurobi. A lot of time, thought, effort, and money has gone into making these as fast as can be. So, solving your problem with one of these commercial solvers is most likely going to be fastest option (especially since it doesn't require you to code any part of the algorithm). However, if you were planning on creating your own implementation then I would suspect that your implementation of network simplex would be faster than your implementation of regular simplex.