<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:x="urn:schemas-microsoft-com:office:excel" 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=iso-8859-3">
<meta name=Generator content="Microsoft Word 12 (filtered medium)">
<style>
<!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@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: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'>It should not take more than 2 hours!<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'>What is </span><span style='font-size:10.0pt;font-family:"Arial","sans-serif";
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<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif";
color:#336666'>FlowConservation(V,Z) = SUM(Incidence(V,A), Flow(A,Z) ) ==
Demand(V,Z) </span><span style='font-size:10.0pt'><br>
<br>
</span><span style='font-size:10.0pt;font-family:"Arial","sans-serif";
color:#336666'><o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif";
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.)<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif";
color:#336666'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif";
color:#336666'>Cheers, Tim <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif";
color:#336666'> </span><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'><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"'> flopcpp-bounces@list.coin-or.org
[mailto:flopcpp-bounces@list.coin-or.org] <b>On Behalf Of </b>Arman Boyaci<br>
<b>Sent:</b> Wednesday, September 15, 2010 1:03 PM<br>
<b>To:</b> flopcpp@list.coin-or.org<br>
<b>Subject:</b> [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><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='margin-bottom:12.0pt'><span style='font-size:10.0pt;
font-family:"Arial","sans-serif";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><span style='font-size:10.0pt;font-family:"Arial","sans-serif";
color:#336666'><br>
</span><span style='font-size:7.5pt;font-family:"Arial","sans-serif";
color:#336666'>A: arcs<br>
V: vertices<br>
Z: requests</span><br>
<span style='font-size:7.5pt;font-family:"Arial","sans-serif";color:#336666'>Incidence
matrix contains the graph structure</span><o:p></o:p></p>
<p class=MsoNormal><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>
</body>
</html>