Network solver

[nico...@gmail.com]

Hi all, 

I would like to a question about the options that are made available by Gurobi to solve linear programs. 

In the reference manual, I am not seeing a "network simplex" option. Does that mean networks simplex is not provided in linear program solver?

The reason I ask this is because I have a network formulation that has integral input, and I want to use network solver to make sure the solution is also integral. If I solve it as a general linear program with Gurobi, will I guarantee to obtain a integral solution?

Thanks,

Liang

[Tobias Achterberg]

If you have a pure network, then the constraint matrix is totally unimodular, so
any vertex solution will be integral. And since the simplex algorithm always
returns a vertex solution (if one exists), your solution will be integral.

Note that in our experience, a network simplex algorithm is not faster than the
dual simplex, which is the reason why Gurobi does not provide a network simplex.

Tobias

[Liang Lv]

Thank you Tobias for your explanation. We are actually using another well known solver (let me keep the name anonymous) to solve network problems. But the thing is that because we haven't represented the problem as a standard network lp (totally unimodular), even we specify to use network simplex, the solver will resort to dual simplex. To properly trigger network simplex, we need to add artificial nodes and bounds to the model which we really do not want to do. So my question is that is there anyway for general linear program solver to leverage the network structure in the problem formulation?

--

--- You received this message because you are subscribed to the Google Groups "Gurobi Optimization" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gurobi+un...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

Liang Lu

PhD

Operations Research Scientist at Amazon.com

SEA27.03.308

345 Boren Ave N

Seattle, WA 98109, United States

Mobile: 412-251-6591

E-mail: lia...@amazon.com

 

[Tobias Achterberg]

I am not aware of special things you could add to the dual simplex algorithm
that would improve performance on network models. As I said, in our experience,
the dual simplex in its current state-of-the-art (exploiting hyper-sparsity and
the like) is already pretty fast on network models, at least if compared with a
network simplex solver.

[Liang Lv]

I see. Thanks!

Liang

On Mon, Jan 18, 2016 at 6:53 AM, Tobias Achterberg <achte...@gurobi.com> wrote:

I am not aware of special things you could add to the dual simplex algorithm that would improve performance on network models. As I said, in our experience, the dual simplex in its current state-of-the-art (exploiting hyper-sparsity and the like) is already pretty fast on network models, at least if compared with a network simplex solver.

--

--- You received this message because you are subscribed to the Google Groups "Gurobi Optimization" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gurobi+un...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.