[FlopCpp] Better way of modeling a graph problem

[Arman Boyacı]

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>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] *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/20100917/852ff8e1/attachment.html