[FlopCpp] Better way of modeling a graph problem

[Tim Hultberg]

Hi Arman,
  I am glad to hear that it helped. I have never really tested generation times for big problems, nor optimised it – the main issue was ‘first order’ efficiency, i.e to make sure that generation time is proportional to the number of non zeros. If somebody have some figures for the generation time with GAMS/AMPL/... for a similar problem I would be very happy to hear it. It would give an idea about if it is very important to look for optimisations – I think that 10 minutes still seem like a lot.

A way to improve further: Each ”index expression” is checked to see if it is within bounds – this is very relevant for models with leads or lags (like I+1), but not for your model.  You should get a good improvement if you find these checks in the source and comment them out.  You can probably find the places yourself, I couldn’t get connection to the coin svn right now and will be away for about a week...

Goodluck, Tim

From: Arman Boyacı [mailto:armanboyaci at gmail.com]
Sent: Friday, September 17, 2010 3:13 PM
To: Tim Hultberg
Cc: flopcpp at list.coin-or.org
Subject: Re: [FlopCpp] Better way of modeling a graph problem

Now with your suggestion, in the new model attachment takes 10 minutes ,and writing the mps file takes 15 minutes. Do you think that we can improve it more :) If this numbers are normal for an instance of this size, I'll leave it.

Thanks a lot for your fast/effective solution :)

Best regards.

-Arman

On Wed, Sep 15, 2010 at 2:31 PM, Tim Hultberg <Tim.Hultberg at eumetsat.int<mailto:Tim.Hultberg at eumetsat.int>> wrote:
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> [mailto: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<mailto: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/20100920/9bca5c26/attachment.html