<font color="#336666"><font size="2"><font face="verdana,sans-serif">Now with your suggestion, in the new model attachment takes 10 minutes ,and writing the mps file takes 15 minutes.</font></font></font><font color="#336666"><font size="2"><font> Do you think that we can improve it more :) </font></font></font><font color="#336666"><font size="2"><font face="verdana,sans-serif">If this numbers are normal for an instance of this size, I'll leave it. <br>
<br>Thanks a lot for your fast/effective solution :)<br><br>Best regards.<br><br clear="all"></font></font></font><b><span style="font-family: georgia,serif;">-Arman</span></b><br>
<br><br><div class="gmail_quote">On Wed, Sep 15, 2010 at 2:31 PM, Tim Hultberg <span dir="ltr"><<a href="mailto:Tim.Hultberg@eumetsat.int">Tim.Hultberg@eumetsat.int</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<div link="blue" vlink="purple" lang="EN-GB">
<div>
<p class="MsoNormal"><span style="font-size: 11pt; color: rgb(31, 73, 125);">It should not take more than 2 hours!</span></p>
<p class="MsoNormal"><span style="font-size: 11pt; color: rgb(31, 73, 125);"> </span></p>
<p class="MsoNormal"><span style="font-size: 11pt; color: rgb(31, 73, 125);">What is </span><span style="font-size: 10pt; color: rgb(51, 102, 102);">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</span></p>
<p class="MsoNormal"><span style="font-size: 10pt; color: rgb(51, 102, 102);">FlowConservation(V,Z) = SUM(Incidence(V,A), Flow(A,Z) ) ==
Demand(V,Z) </span><span style="font-size: 10pt;"><br>
<br>
</span><span style="font-size: 10pt; color: rgb(51, 102, 102);"></span></p>
<p class="MsoNormal"><span style="font-size: 10pt; color: rgb(51, 102, 102);">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.)</span></p>
<p class="MsoNormal"><span style="font-size: 10pt; color: rgb(51, 102, 102);"> </span></p>
<p class="MsoNormal"><span style="font-size: 10pt; color: rgb(51, 102, 102);">Cheers, Tim </span></p>
<p class="MsoNormal"><span style="font-size: 10pt; color: rgb(51, 102, 102);"> </span><span style="font-size: 11pt; color: rgb(31, 73, 125);"></span></p>
<p class="MsoNormal"><span style="font-size: 11pt; color: rgb(31, 73, 125);"> </span></p>
<div style="border-width: 1pt medium medium; border-style: solid none none; border-color: rgb(181, 196, 223) -moz-use-text-color -moz-use-text-color; padding: 3pt 0cm 0cm;">
<p class="MsoNormal"><b><span style="font-size: 10pt;" lang="EN-US">From:</span></b><span style="font-size: 10pt;" lang="EN-US"> <a href="mailto:flopcpp-bounces@list.coin-or.org" target="_blank">flopcpp-bounces@list.coin-or.org</a>
[mailto:<a href="mailto:flopcpp-bounces@list.coin-or.org" target="_blank">flopcpp-bounces@list.coin-or.org</a>] <b>On Behalf Of </b>Arman Boyaci<br>
<b>Sent:</b> Wednesday, September 15, 2010 1:03 PM<br>
<b>To:</b> <a href="mailto:flopcpp@list.coin-or.org" target="_blank">flopcpp@list.coin-or.org</a><br>
<b>Subject:</b> [FlopCpp] Better way of modeling a graph problem</span></p>
</div><div><div></div><div class="h5">
<p class="MsoNormal"> </p>
<p class="MsoNormal"><span style="font-size: 10pt; font-family: "Garamond","serif"; color: rgb(51, 102, 102);">Hello,<br>
<br>
I am dealing with a multi-commodity flow problem and I am trying to solve a
relatively big instance: <i>800,000</i> variables and<i> 25,000 </i>constraints.<br>
In order to be able to control solver options, I first write the model into an
MPS file. However it takes more than <i>2</i> hours only the model.attach()
process.<br>
<br>
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.<br>
In the multi-commodity flow problem model, the only important set of
constraints is the flow conservation constraints:</span></p>
<p class="MsoNormal" style="margin-bottom: 12pt;"><span style="font-size: 10pt; color: rgb(51, 102, 102);">FlowConservation(V,Z) = SUM(A,
Incidence(V,A)*Flow(A,Z) ) == Demand(V,Z) </span><span style="font-size: 10pt;"><br>
</span><span style="font-size: 10pt; color: rgb(51, 102, 102);"><br>
</span><span style="font-size: 7.5pt; color: rgb(51, 102, 102);">A: arcs<br>
V: vertices<br>
Z: requests</span><br>
<span style="font-size: 7.5pt; color: rgb(51, 102, 102);">Incidence
matrix contains the graph structure</span></p>
<p class="MsoNormal"><span style="font-size: 10pt; font-family: "Garamond","serif"; color: rgb(51, 102, 102);">I am suspecting that this multiplication (incidence*flow) causes
the problem.</span> <br>
<span style="font-size: 10pt; font-family: "Garamond","serif"; color: rgb(51, 102, 102);">Is
there a better way of doing this (with conditional for example)? <br>
<br>
Otherwise what can be other reasons for this problem? Any idea?<br>
<br>
Thanks in advance.<br>
<br clear="all">
</span><b><span style="font-size: 10pt; font-family: "Garamond","serif";">- Arman</span></b></p>
</div></div></div>
</div>
</blockquote></div><br>