[FlopCpp] Better way of modeling a graph problem

[Tim Hultberg]

It should not take more than 2 hours!

What is Incidence(V,A)? MP_data? Probably it should be a MP_subset<2> Incidence(V,A); that would turn a 'dense' formulation into a 'sparse' one by writing
FlowConservation(V,Z) = SUM(Incidence(V,A), Flow(A,Z) ) == Demand(V,Z)

If that does not help, I am willing to have a closer look if you send me the complete model. For sure the generation should be fast and proportional to the number of nonzeros (instead of #vars * #contrs.)

Cheers, Tim


From: flopcpp-bounces at list.coin-or.org [mailto:flopcpp-bounces at list.coin-or.org] On Behalf Of Arman Boyaci
Sent: Wednesday, September 15, 2010 1:03 PM
To: flopcpp at list.coin-or.org
Subject: [FlopCpp] Better way of modeling a graph problem

Hello,

I am dealing with a multi-commodity flow problem and I am trying to solve a relatively big instance: 800,000 variables and 25,000 constraints.
In order to be able to control solver options, I first write the model into an MPS file. However it takes more than 2 hours only the model.attach() process.

I am aware that the instance size is not small and it will take time to solve it. But the modeling process time should be shorter, the current situation does not make sense to me.
In the multi-commodity flow problem model, the only important set of constraints is the flow conservation constraints:
FlowConservation(V,Z) = SUM(A, Incidence(V,A)*Flow(A,Z) ) == Demand(V,Z)

A: arcs
V: vertices
Z: requests
Incidence matrix contains the graph structure
I am suspecting that this multiplication (incidence*flow) causes the problem.
Is there a better way of doing this (with conditional for example)?

Otherwise what can be other reasons for this problem? Any idea?

Thanks in advance.

- Arman
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://list.coin-or.org/pipermail/flopcpp/attachments/20100915/9ddabdc7/attachment-0001.html