[Clp] Postsolve and quadratic problems

[Vincent Devillierse]

Hi,

My mistake, I switched the values in the first mail, -4114185.3 is actually
the optimal solution according to Cplex using barrier solver.

*Barrier - Optimal:  Objective = -4.1141853374e+06
Solution time =    0.27 sec.  Iterations = 23*

It's also the same according to Gurobi (using barrier solver too)
*Barrier solved model in 19 iterations and 0.13 seconds
Optimal objective -4.11418533e+06*

And so -182704.15 is the "wrong" optimal value.

According to your comment I tried to go directlty with the barrier method.
I didn't find the documentation really clear about the setAlgo() or
setSolveType() methods, so I directly called
OsiClpSolverInterface->getModelPtr()->barrier().

That worked quite well at the beginning, but later I ended up with the
message "primal off to infinity" and no solution on several problems.
I could fix it by calling primal() instead of barrier() (the optimal values
are ok, even if the performances are now a little slower).*
Clp0006I 2313  Obj -4114185.3*
*
Clp0000I Optimal - objective value -4114185.3
*
I think the only reason it's working now is because the postsolve is
disabled if you solve the problem this way (which appears to be just a
coincidence in this case).
So I still think the postsolve may be acting weird in the first case.

I would be interested to switch the presolve off, but haven't find any
methods in the documentation of OsiClpSolverInterface or ClpSimplex to do
that.

Vincent



2013/7/24 William H. Patton <pattonwh at comcast.net>

>  My guess is that presolve was pretty successful at reducing the problem
> and that the -4114185 was the presolved problem solution
> The inverse presolve steps was then done to recover the base units of
> measure.
> Note that this Coin0511I* After Postsolve,* objective -182704.15 solution
> agrees with Cplex solution and so does not seem to be *visibly false*!
> So try again with presolve off.
> Also try the barrier solver. On the sample share2qp.mps it gives a
> slightly different solution than the standard solve.
>
> >>>>>>>>>>>>>>>>
>
>
> Coin LP version 1.14.4, build Nov 10 2011
> Clp takes input from arguments ( - switches to stdin)
> Enter ? for list of commands or help
> Clp:presolve
> *presolve has value on*
> Clp:import share2qp.mps
> At line 1 NAME          SHARE2B
> At line 2 ROWS
> At line 100 COLUMNS
> At line 482 RHS
> At line 495 QUADOBJ
> Problem SHARE2B has 96 rows, 79 columns and 694 elements
> At line 524 ENDATA
> Model was imported from .\share2qp.mps in 0.002 seconds
> Clp:solve
> *Presolve 93 (-3) rows, 79 (0) columns and 691 (-3) elements*
> *Perturbing problem by 0.001 % *of 11.662247 - largest nonzero change
> 9.8207092e-0
> 05 (% 0.0083883756) - largest zero change 0
> 0  Obj 0 Primal inf 145.87618 (5) Dual inf 15.1756 (9)
> 58  Obj 0
> Optimal - objective value 0
> 0  Obj 1285.1361 Dual inf 1487.2647 (22)
> 42  Obj -400.91701
> Optimal - objective value* -400.91701*
> After Postsolve, objective -398.05931, infeasibilities - dual 0 (0),
> primal 0 (0
> )
> Optimal objective* -398.059309* - 42 iterations time 0.012, Presolve 0.00
> Clp:*presolve off*
> Clp:presolve
> *presolve has value off*
> Clp:solve
> 0  Obj -400.91701
> Optimal - objective value -400.91701
> Optimal objective -400.9170115 - 0 iterations time 0.002
> Clp:import share2qp.mps
> At line 1 NAME          SHARE2B
> At line 2 ROWS
> At line 100 COLUMNS
> At line 482 RHS
> At line 495 QUADOBJ
> Problem SHARE2B has 96 rows, 79 columns and 694 elements
> At line 524 ENDATA
> Model was imported from .\share2qp.mps in 0.004 seconds
> Clp:solve
> 0  Obj 0 Primal inf 145.87619 (5) Dual inf 1.5175601e+011 (11)
> 76  Obj 571.60984 Primal inf 1.3459942 (2) Dual inf 7.9222065e+009 (23)
> 152  Obj -400.89999 Dual inf 1.1847668 (4)
> 153  Obj -400.91701
> Optimal - objective value -400.91701
> Optimal objective* -400.9170115* - 153 iterations time 0.012
> Clp:presolve
> presolve has value off
> Clp:
> Clp:*barrier*
> 2928 elements in sparse Cholesky, flop count 89374
> 0 Primal 1880441 Dual -1.6693328e+008 Complementarity 1.9590728e+008 - 0
> fixed,
> rank 271
> 1 Primal 30581.248 Dual -10443941 Complementarity 26978058 - 0 fixed, rank
> 271
> 2 Primal 1572.4622 Dual -3087057.1 Complementarity 6108433.1 - 0 fixed,
> rank 271
>
> 3 Primal 310.8557 Dual -1459155.3 Complementarity 2507164.8 - 0 fixed,
> rank 271
> 4 Primal 509.42803 Dual -501381.13 Complementarity 606063.42 - 0 fixed,
> rank 271
>
> 5 Primal 967.29319 Dual -105866.26 Complementarity 115919.99 - 0 fixed,
> rank 271
>
> 6 Primal 837.84361 Dual -52400.522 Complementarity 57435.819 - 0 fixed,
> rank 271
>
> 7 Primal 102.95273 Dual -4147.861 Complementarity 4353.3398 - 0 fixed,
> rank 271
> 8 Primal -311.19033 Dual -855.93051 Complementarity 551.31766 - 0 fixed,
> rank 27
> 1
> 9 Primal -349.04464 Dual -618.45146 Complementarity 275.98936 - 0 fixed,
> rank 27
> 1
> 10 Primal -377.72515 Dual -436.0772 Complementarity 59.71886 - 0 fixed,
> rank 271
>
> 11 Primal -393.65235 Dual -415.96868 Complementarity 22.998293 - 0 fixed,
> rank 2
> 71
> 12 Primal -398.79134 Dual -403.89314 Complementarity 5.2467322 - 0 fixed,
> rank 2
> 71
> 13 Primal -400.18831 Dual -401.99952 Complementarity 1.8687018 - 0 fixed,
> rank 2
> 71
> 14 Primal -400.83016 Dual -401.04844 Complementarity 0.22457764 - 0 fixed,
> rank
> 271
> 15 Primal -400.90225 Dual -400.9482 Complementarity 0.045949787 - 13
> fixed, rank
>  271
> 16 Primal -400.9224 Dual -400.92272 Complementarity 0.00031159724 - 13
> fixed, ra
> nk 271
> 17 Primal -400.92254 Dual -400.92254 Complementarity 2.5038999e-006 - 13
> fixed,
> rank 271
> 18 Primal -400.92254 Dual -400.92254 Complementarity 1.7307463e-008 - 50
> fixed,
> rank 271
> 19 Primal -400.92254 Dual -400.92254 Complementarity 1.5460613e-008 - 53
> fixed,
> rank 271
> Exiting - using solution from iteration 17
> At end primal/dual infeasibilities 0/0.078454371, complementarity gap
> 1.4091511e
> -007, objective -400.92254
> Optimal objective* -400.9225413* - 19 iterations time 0.042
>
>
> William
>
>
> On 7/24/2013 10:27 AM, Michael Hennebry wrote:
>
> On Mon, 22 Jul 2013, Vincent Devillierse wrote:
>
> I've tried to solve a non integer quadratic problem with the CLP API.
> CLP seems to find the optimal solution, but after that, executes a
> postsolve phase and the objective value is then totally different (and
> visibly false).
>
> Here is as example of output :
> *Clp0006I 1984  Obj -4113764.5 Dual inf 57.100756 (236)
> Clp0006I 2058  Obj -4114185.3
> Clp0000I Optimal - objective value -4114185.3
> Coin0511I After Postsolve, objective -182704.15, infeasibilities - dual 0
> (0), primal 0 (0)
> Clp0032I Optimal objective -182704.1521 - 2058 iterations time 9.752,
> Presolve 0.02*
>
> -182704.15 is, according to Cplex the optimal objective value.
> I don't know what * *-4114185.3 corresponds to.
>
>
> My guess is that -182704.15 is the optimum to
> some linearization of the quadratic objective.
> Probably it omits some constant term.
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20130725/45ef5e2b/attachment-0001.html>