<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv=Content-Type content="text/html; charset=Windows-1254">
<meta name=Generator content="Microsoft Word 12 (filtered medium)">
<style>
<!--
/* Font Definitions */
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
@font-face
{font-family:Verdana;
panose-1:2 11 6 4 3 5 4 4 2 4;}
@font-face
{font-family:Georgia;
panose-1:2 4 5 2 5 4 5 2 3 3;}
@font-face
{font-family:Garamond;
panose-1:2 2 4 4 3 3 1 1 8 3;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
-->
</style>
<!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang=EN-GB link=blue vlink=purple>
<div class=WordSection1>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Hi Arman,<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'> 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.<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>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...<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Goodluck, Tim<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<div style='border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0cm 0cm 0cm'>
<p class=MsoNormal><b><span lang=EN-US style='font-size:10.0pt;font-family:
"Tahoma","sans-serif"'>From:</span></b><span lang=EN-US style='font-size:10.0pt;
font-family:"Tahoma","sans-serif"'> Arman Boyacý [mailto:armanboyaci@gmail.com]
<br>
<b>Sent:</b> Friday, September 17, 2010 3:13 PM<br>
<b>To:</b> Tim Hultberg<br>
<b>Cc:</b> flopcpp@list.coin-or.org<br>
<b>Subject:</b> Re: [FlopCpp] Better way of modeling a graph problem<o:p></o:p></span></p>
</div>
<p class=MsoNormal><o:p> </o:p></p>
<p class=MsoNormal style='margin-bottom:12.0pt'><span style='font-size:10.0pt;
font-family:"Verdana","sans-serif";color:#336666'>Now with your suggestion, in
the new model attachment takes 10 minutes ,and writing the mps file takes 15
minutes.</span><span style='font-size:10.0pt;color:#336666'> Do you think that
we can improve it more :) </span><span style='font-size:10.0pt;font-family:
"Verdana","sans-serif";color:#336666'>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>
</span><b><span style='font-family:"Georgia","serif"'>-Arman</span></b><br>
<br>
<o:p></o:p></p>
<div>
<p class=MsoNormal>On Wed, Sep 15, 2010 at 2:31 PM, Tim Hultberg <<a
href="mailto:Tim.Hultberg@eumetsat.int">Tim.Hultberg@eumetsat.int</a>>
wrote:<o:p></o:p></p>
<div>
<div>
<p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span
style='font-size:11.0pt;color:#1F497D'>It should not take more than 2 hours!</span><o:p></o:p></p>
<p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span
style='font-size:11.0pt;color:#1F497D'> </span><o:p></o:p></p>
<p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span
style='font-size:11.0pt;color:#1F497D'>What is </span><span style='font-size:
10.0pt;color:#336666'>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><o:p></o:p></p>
<p class=MsoNormal style='mso-margin-top-alt:auto;margin-bottom:12.0pt'><span
style='font-size:10.0pt;color:#336666'>FlowConservation(V,Z) =
SUM(Incidence(V,A), Flow(A,Z) ) == Demand(V,Z) </span><o:p></o:p></p>
<p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span
style='font-size:10.0pt;color:#336666'>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><o:p></o:p></p>
<p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span
style='font-size:10.0pt;color:#336666'> </span><o:p></o:p></p>
<p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span
style='font-size:10.0pt;color:#336666'>Cheers, Tim </span><o:p></o:p></p>
<p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span
style='font-size:10.0pt;color:#336666'> </span><o:p></o:p></p>
<p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span
style='font-size:11.0pt;color:#1F497D'> </span><o:p></o:p></p>
<div style='border:none;border-top:solid windowtext 1.0pt;padding:3.0pt 0cm 0cm 0cm;
border-color:-moz-use-text-color -moz-use-text-color'>
<p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><b><span
lang=EN-US style='font-size:10.0pt'>From:</span></b><span lang=EN-US
style='font-size:10.0pt'> <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><o:p></o:p></p>
</div>
<div>
<div>
<p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p>
<p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span
style='font-size:10.0pt;font-family:"Garamond","serif";color:#336666'>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><o:p></o:p></p>
<p class=MsoNormal style='mso-margin-top-alt:auto;margin-bottom:12.0pt'><span
style='font-size:10.0pt;color:#336666'>FlowConservation(V,Z) = SUM(A,
Incidence(V,A)*Flow(A,Z) ) == Demand(V,Z) </span><span style='font-size:10.0pt'><br>
<span style='color:#336666'><br>
</span></span><span style='font-size:7.5pt;color:#336666'>A: arcs<br>
V: vertices<br>
Z: requests</span><br>
<span style='font-size:7.5pt;color:#336666'>Incidence matrix contains the graph
structure</span><o:p></o:p></p>
<p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><span
style='font-size:10.0pt;font-family:"Garamond","serif";color:#336666'>I am
suspecting that this multiplication (incidence*flow) causes the problem.</span>
<br>
<span style='font-size:10.0pt;font-family:"Garamond","serif";color:#336666'>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:10.0pt;font-family:"Garamond","serif"'>- Arman</span></b><o:p></o:p></p>
</div>
</div>
</div>
</div>
</div>
<p class=MsoNormal><o:p> </o:p></p>
</div>
</body>
</html>