[Clp] different optimal values with primal and dual methods.
William H. Patton
pattonwh at comcast.net
Mon May 28 11:21:34 EDT 2012
Yor model becomes much simpler and sparser If you pull out some common
dense parts of your rows.
Your blocks of 120 fall into 6 blocks of 20 19 of these have the form
ci + block <= rhs;
Actually the block s in adjacent sections have some type of adjacent
split pattern.
the easy thing is then to add 1 row for each block of form blocvar_i =
block;
then your matrix becomes
- cblock_j - blockvar_i <= -rhs_j_i; with only 3 terms.
for the cost of 1 additional equality var per block .
cut__1_19: -C0000019 -142583.979 C0000120 -75743.2622 C0000121
-64893.5897 C0000122 -54
cut__1_20: -C0000020 -44920.0648 C0000120 -43111.7861 C0000121
-41303.5073 C0000122 -39
cut__1_21: -C0000021 -72044.2459999 C0000120 -61194.5735 C0000121
-50344.9011 C0000122
with later resync. So a leading sublock here
-10645.2274 C0000129 -*13368.9309 *C0000130
-16139.4102 C0000131 -152
-17795.8836 C0000129 -13368.9309 C0000130 -16139.4102
C0000131 -152
-17795.8836 C0000129 *-13368.9309* C0000130
-16139.4102 C0000131 -
cut__1_79: -C0000079 -125083.33 C0000120 -61194.5735 C0000121
-50344.9011 C0000122 ...
cut__1_80: -C0000080 -90416.934 C0000120 -47632.4829 C0000121
-45824.2042 C0000122 ...
cut__1_81: -C0000081 -125083.33 C0000120 -61194.5735 C0000121
-50344.9011 C0000122 ...
It is certain your generator knows the pattern applied so you can
actually easily factor out the common blocks into additional vars.
This amounts to viewing the matrix as a tensor product of (dense
blocks_i_j) X ( Incidence_i_j quite sparse)
It may be that cplex and gurobi have row presolve common pattern
elimination that manage this.
It is still better if yo help recognize the native sparsity and build it
that way.
I believe it is likely that you already know it. Moving to a modeling
language that has Cartesian relations ( AMPL, MATHProg GAMS AIMMS ... )
Should expose this properly. Do not forget to attack the poor scaling.
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
even there you are really just deriving new row definitions so expanding
the sets and populating new data blocks int the subsets.
William
On 5/27/2012 9:06 PM, Akhil langer wrote:
> Thanks Jonathan for your reply.
> I obtained somewhat different values using the clp. 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.
>
> 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.
> 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.
>
> 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.
>
> --Akhil
> On Sun, May 27, 2012 at 6:18 PM, Jonathan Currie
> <jonathan.currie at aut.ac.nz <mailto:jonathan.currie at aut.ac.nz>> wrote:
>
> Hi Akhil,
>
> 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:
>
> Test Problem [LP] Result
>
> --------------------------------------------------
>
> Solver Status Fval Time
>
> cplex OK +79596.2542 0.7609s
>
> mosek FAIL +79596.2164 1.0940s
>
> clp (dual) OK +114009.8970 0.3482s
>
> clp (primal) OK +79605.5292 0.7370s
>
> glpk FAIL +0.0000 1.9977s
>
> qsopt OK +79596.2542 0.8384s
>
> matlab OK +79596.2542 7.7259s
>
> --------------------------------------------------
>
> I assume you obtained the same minimums as above using CLP? How
> was the original model created?
>
> Jonathan Currie
>
> *From:*clp-bounces at list.coin-or.org
> <mailto:clp-bounces at list.coin-or.org>
> [mailto:clp-bounces at list.coin-or.org
> <mailto:clp-bounces at list.coin-or.org>] *On Behalf Of *Akhil langer
> *Sent:* Sunday, 27 May 2012 2:17 p.m.
> *To:* clp at list.coin-or.org <mailto:clp at list.coin-or.org>
> *Subject:* [Clp] different optimal values with primal and dual
> methods.
>
> 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.
>
> Some help as early as possible will be useful as I am in a
> critical phase of my project.
>
> Thanks,
>
> Akhil
>
>
>
>
> _______________________________________________
> Clp mailing list
> Clp at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/clp
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20120528/5ae7e369/attachment.html>
More information about the Clp
mailing list