<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
Yor model becomes much simpler and sparser If you pull out some
common dense parts of your rows.<br>
Your blocks of 120 fall into 6 blocks of 20 19 of these have the
form ci + block <= rhs;<br>
Actually the block s in adjacent sections have some type of adjacent
split pattern.<br>
the easy thing is then to add 1 row for each block of form
blocvar_i = block;<br>
<br>
then your matrix becomes<br>
- cblock_j - blockvar_i <= -rhs_j_i; with only 3
terms. for the cost of 1 additional equality var per block .<br>
<br>
cut__1_19: -C0000019 -142583.979 C0000120 -75743.2622 C0000121
-64893.5897 C0000122 -54<br>
cut__1_20: -C0000020 -44920.0648 C0000120 -43111.7861 C0000121
-41303.5073 C0000122 -39<br>
cut__1_21: -C0000021 -72044.2459999 C0000120 -61194.5735 C0000121
-50344.9011 C0000122 <br>
with later resync. So a leading sublock here<br>
-10645.2274 C0000129 -<b>13368.9309 </b>C0000130
-16139.4102 C0000131 -152<br>
-17795.8836 C0000129 -13368.9309 C0000130
-16139.4102 C0000131 -152<br>
-17795.8836 C0000129 <b>-13368.9309</b> C0000130
-16139.4102 C0000131 -<br>
<br>
<br>
cut__1_79: -C0000079 -125083.33 C0000120 -61194.5735 C0000121
-50344.9011 C0000122 ...<br>
cut__1_80: -C0000080 -90416.934 C0000120 -47632.4829 C0000121
-45824.2042 C0000122 ...<br>
cut__1_81: -C0000081 -125083.33 C0000120 -61194.5735 C0000121
-50344.9011 C0000122 ...<br>
<br>
It is certain your generator knows the pattern applied so you can
actually easily factor out the common blocks into additional vars.<br>
<br>
This amounts to viewing the matrix as a tensor product of (dense
blocks_i_j) X ( Incidence_i_j quite sparse)<br>
<br>
It may be that cplex and gurobi have row presolve common pattern
elimination that manage this.<br>
It is still better if yo help recognize the native sparsity and
build it that way.<br>
I believe it is likely that you already know it. Moving to a
modeling language that has Cartesian relations ( AMPL, MATHProg GAMS
AIMMS ... )<br>
Should expose this properly. Do not forget to attack the poor
scaling.<br>
<br>
I think the last 2 can actually loop the solve generation I do not
think that MATHprog can. But your model is so tiny and solves so
fast that<br>
even there you are really just deriving new row definitions so
expanding the sets and populating new data blocks int the subsets.<br>
<br>
William<br>
<br>
On 5/27/2012 9:06 PM, Akhil langer wrote:
<blockquote
cite="mid:CANDF1bYORZyvLNBYfhDTWGMFkSMNiPa19BtHEPc9OFuGwBLGLg@mail.gmail.com"
type="cite">
<div>Thanks Jonathan for your reply.</div>
I obtained somewhat different values using the clp. <span
style="border-collapse:collapse;color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px">178714
and 82187.2 with dual and primal methods respectively. However,
I solved with gurobi and got the same value as cplex, qsopt and
matlab reported by you. </span>
<div>
<font color="#222222" face="arial, sans-serif"><span
style="border-collapse:collapse"><br>
</span></font></div>
<div><font color="#222222" face="arial, sans-serif"><span
style="border-collapse:collapse">I am building the model,
starting with loading of a base model with just 180 rows.
The model is then increased in size by addition of more
rows. No new variables are added. I am doing this in the
context of stochastic optimization. In every iteration of
the stochastic process, I add 120 rows (using the
addRows(CoinBuild) interface of ClpSimplex) and then do a
primal/dual solve on the model. The program reports
infeasibility after 6-7 such iterations i.e. after ~120*6
addition of rows. </span></font></div>
<div><font color="#222222" face="arial, sans-serif"><span
style="border-collapse:collapse">Additionally, I am getting
another artifact. The optimial value of the model should
only increase after every iteration, as only more
constraints are added and hence the minimal value of the
objective function (which is not modified across iterations)
should only increase with iteration number. However, I am
seeing that objective value jumps up and down with the
iteration number.<br>
</span></font></div>
<div>
<div><font color="#222222" face="arial, sans-serif"><span
style="border-collapse:collapse"><br>
</span></font></div>
<div><font color="#222222" face="arial, sans-serif"><span
style="border-collapse:collapse">For clarity, note that
iteration number I refer here is the iteration number of
the stochastic iterative process and not the iterations
referred by the simplex algorithm while optimization.</span></font></div>
<div><font color="#222222" face="arial, sans-serif"><span
style="border-collapse:collapse"><br>
</span></font></div>
<div><font color="#222222" face="arial, sans-serif"><span
style="border-collapse:collapse">--Akhil<br>
</span></font></div>
<div>
<div class="gmail_quote">
On Sun, May 27, 2012 at 6:18 PM, Jonathan Currie <span
dir="ltr"><<a moz-do-not-send="true"
href="mailto:jonathan.currie@aut.ac.nz" target="_blank">jonathan.currie@aut.ac.nz</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div link="blue" vlink="purple" lang="EN-NZ">
<div>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">Hi
Akhil,</span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"> </span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">I'm
not sufficiently experienced to be able to answer
why the solvers give such different answers (I
assume there are multiple factors), however note I
ran your model using the OPTI Toolbox across the
LP solvers I have and found CLP did not return the
minimum (using the default settings) for either
the dual or primal solvers:</span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"> </span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">Test
Problem [LP] Result</span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">--------------------------------------------------</span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">
Solver Status Fval
Time</span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">
cplex OK +79596.2542 0.7609s</span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">
mosek FAIL +79596.2164 1.0940s</span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">clp
(dual) OK +114009.8970 0.3482s</span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">clp
(primal) OK +79605.5292 0.7370s</span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">
glpk FAIL +0.0000
1.9977s</span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">
qsopt OK +79596.2542 0.8384s</span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">
matlab OK +79596.2542 7.7259s</span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">--------------------------------------------------</span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"> </span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">I
assume you obtained the same minimums as above
using CLP? How was the original model created?</span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"> </span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">Jonathan
Currie</span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"> </span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"> </span></p>
<p class="MsoNormal"><b><span
style="font-size:10.0pt;font-family:"Tahoma","sans-serif""
lang="EN-US">From:</span></b><span
style="font-size:10.0pt;font-family:"Tahoma","sans-serif""
lang="EN-US"> <a moz-do-not-send="true"
href="mailto:clp-bounces@list.coin-or.org"
target="_blank">clp-bounces@list.coin-or.org</a>
[mailto:<a moz-do-not-send="true"
href="mailto:clp-bounces@list.coin-or.org"
target="_blank">clp-bounces@list.coin-or.org</a>]
<b>On Behalf Of </b>Akhil langer<br>
<b>Sent:</b> Sunday, 27 May 2012 2:17 p.m.<br>
<b>To:</b> <a moz-do-not-send="true"
href="mailto:clp@list.coin-or.org"
target="_blank">clp@list.coin-or.org</a><br>
<b>Subject:</b> [Clp] different optimal values
with primal and dual methods.</span></p>
<div>
<div>
<p class="MsoNormal"> </p>
<p class="MsoNormal">I am attaching a linear
program model file in mps format. I am trying to
solve it using the driver.cpp program in the
examples directory of the coin-clp distribution.
Surprisingly, I am getting different optimal
values when solved using the dual and primal
methods (model.dual(), model.primal()). Can
someone please look into it and help me resolve
this issue.</p>
<div>
<p class="MsoNormal"> </p>
</div>
<div>
<p class="MsoNormal">Some help as early as
possible will be useful as I am in a critical
phase of my project.</p>
<div>
<p class="MsoNormal"> </p>
</div>
<div>
<p class="MsoNormal">Thanks,</p>
</div>
<div>
<p class="MsoNormal">Akhil</p>
</div>
</div>
</div>
</div>
</div>
</div>
</blockquote>
</div>
<br>
</div>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
Clp mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Clp@list.coin-or.org">Clp@list.coin-or.org</a>
<a class="moz-txt-link-freetext" href="http://list.coin-or.org/mailman/listinfo/clp">http://list.coin-or.org/mailman/listinfo/clp</a>
</pre>
</blockquote>
</body>
</html>