[Coin-discuss] OsiClp initialSolve vs resolve

Wed Feb 8 09:26:09 EST 2006

John,

Thanks again for the quick reply.

I reintroduced my "1e-17"-bug, set both dual and primal tolerences to
1e-20, and told the program to do a "resolve" (where the problem was
occuring) in the second step.
This is the final part of the log:

(PresolveInInitial and PresolveInResolve at default)

Clp0102I 4561 -1.29735e+014 In: C855 Out: C925 dj -0.00764248 distance
1.50099e-019
Clp0102I 4562 -1.29735e+014 In: R928 Out: R925 dj 443.535 distance
-4.73065e-020
Clp0103I Primal nonlinear change 0 (10)
Clp0060I Primal error 7.62939e-006, dual error 14.3856
Clp0006I 4562  Obj -7.11642e+007 Primal inf 7.2896e-010 (10) Dual inf
2.30486e+015 (53)
Clp0017I Looking optimal with tolerance of 1e-020
Clp0011I Stopping as close enough
Clp0000I Optimal - objective value 3.29729e+015

I'm not certain what this means.. "Dual inf 2.30486e+015" ?

Turning presolve off gets me

Clp0102I 5402 -2.28159e+015 In: R432 Out: C587 dj 6.12933e+007 distance
-1.24915e-011
Clp0103I Primal nonlinear change 6.76267e+012 (5)
Clp0060I Primal error 7.62939e-006, dual error 13.2812
Clp0023I Possible loop - 1 matches (2) after 557 checks

The same 1e-20 tolerances, but now with an "initialSolve" in the second
step results in

(PresolveInInitial and PresolveInResolve turned OFF)

Clp0102I 1321 1.74851e+014 In: R1251 Out: C1114 dj 3265.58 distance
-6.98162e-027
Clp0103I Primal nonlinear change 3.00563e+012 (8)
Clp0060I Primal error 7.62939e-006, dual error 119.994
Clp0006I 1321  Obj -7.11638e+007 Primal inf 2.31641e-008 (8) Dual inf
9.11709e+016 (57)
Clp0017I Looking optimal with tolerance of 1e-020
Clp0011I Stopping as close enough
Clp0000I Optimal - objective value 6.78363e+014

At the same time, i'm doing a writeMps. The resulting file solves fine
with the command line "interactive" clp executable, with tolerances of
1e-20 (and similarly with 1e-7). This was to be expected, since a second
"initialSolve" in stead of "resolve" also solves without any problem. The
optimal objective function value here is -7.11638e+007.

Oh, and I forgot to mention yesterday that those coefficient that I'm
changing between the first and second step are NOT the 1e-17's.

But again, I already found my bug (and, unfortunately, I wont have a lot
of time available in the next few days for chasing this)
Thanks again,

Jan-Willem

> Jan-Willem,
>
> The easy answer is that "resolve" is designed mainly for branch and bound
> so has a bias towards the dual algorithm while "initialsolve" does not. So
> initialSolve used primal while resolve used dual.  When there are odd
> values involved or other lack of accuracy the use of tolerances means that
> simplex can get a local optimum (or infeasible solution in this case).
>
> If the problem (with 1.0e-17 element values) is actually infeasible with a
> zero feasibility tolerance then the results are reasonable.  If it should
> be feasible, even with a zero tolerance, then it is a defect in the code.
> If you wish me to investigate further then I can.
>
> John Forrest
>
>
>
> "Jan-Willem Goossens" <j.goossens at t75.nl>
> Sent by: coin-discuss-bounces at list.coin-or.org
> 02/07/2006 08:16 AM
> Please respond to
> Discussions about open source software for Operations Research
> <coin-discuss at list.coin-or.org>
>
>
> To
> "Discussions about open source software for Operations Research"
> <coin-discuss at list.coin-or.org>
> cc
>
> Subject
> [Coin-discuss] OsiClp initialSolve vs resolve
>
>
>
>
>
>
> Dear all,
>
> While attempting to solve my LP problem via OsiClp, I noticed the
> following:
>
> after an initialSolve, I modify the problem (change some coefficients in
> the constraints etc.), and
>
> 1) try a "resolve". This results in "Primal Infeasible"
>
> or, I modify my source code to alternatively
>
> 2) try another "initialSolve". This finds the (correct) optimal solution.
>
>>From the log file, I noticed that I was putting in some 1e-17
> coefficients. After removing these, _both_ approaches above worked fine
> (So I'm happy basically..)
>
> However, I was hoping someone could shed some light on why doing another
> initialSolve works fine, whereas the resolve fails.
>
> With OsiCpx (CPLEX 9.0.2), both the resolve and initialSolve work fine
> even _with_ the 1e-17 coefficients.
>
> Oh, and I'm running today's tarball sources (07/02/2006).
>
> Below are the interesting parts of the two logs.
>
> Thanks in advance,
>
> Jan-Willem
>
>
>
>
> ---------------
> The failing "resolve" log:
>
> ... (here the first solve does its thing)
> Clp0102I 88 1.55291e+007 In: C74 Out: R118 dj ratio 0.00934009 distance 0
> Clp0060I Primal error 1.13687e-013, dual error 1.13671e-016
> Clp0006I 88  Obj 1.55291e+007
> Clp0025I Looking optimal checking bounds with 1e+010
> Clp0013I Going back to original objective
> Clp0060I Primal error 1.13687e-013, dual error 0
> Clp0025I Looking optimal checking bounds with 1e+010
> Clp0000I Optimal - objective value 1.55291e+007
> Clp0033I Dual took 0.67 seconds (total 0.85)
> Coin0511I After Postsolve, objective 1.55291e+007, infeasibilities - dual
> 0 (0), primal 0 (0)
> Clp0032I Optimal objective 15529105.63 - 88 iterations time 0.852,
> Presolve 0.18
> (-----------here the _first_ solve ends)
> Clp1001I Initial range of elements is 1.17553e-017 to 9.25e+006
> Clp1002I Range of elements is 2.42439e-009 to 4.12475e+008
> Clp1002I Range of elements is 4.5576e-005 to 21941.4
> Clp1003I Final range of elements is 3.94313e-006 to 100
> Clp0022I Absolute values of scaled rhs range from 23.5309 to 63574.8,
> minimum gap 1e+100
> Clp0020I Absolute values of scaled objective range from 134289 to
> 1.27223e+006
> Clp0021I Absolute values of scaled bounds range from 0.0704473 to 70.3883,
> minimum gap 0.0704473
> Clp0060I Primal error 1.16173e-005, dual error 7.86685e-011
> Clp0060I Primal error 1.16173e-005, dual error 7.86685e-011
> Clp0006I 0  Obj -3.37723e+008 Dual inf 2.369e+007 (185)
> Clp0060I Primal error 496, dual error 7.86685e-011
> Clp0102I 1 1.83038e+017 In: C1332 Out: R1959 dj ratio 1.26265e+010
> distance 0.000402448
> Clp0102I 2 1.83037e+017 In: C308 Out: R233 dj ratio 3.44977e+009 distance
> 4.02448e-006
> .... (here the resolve does its work, skipping forward)
> Clp0102I 145 8.43696e+006 In: R274 Out: C358 dj ratio 261473 distance
> 1e-018
> Clp0102I 146 8.26764e+006 In: R233 Out: R239 dj ratio 4.20725e+010
> distance 4.33448
> Clp0102I 147 -1.02732e+007 In: C107 Out: C547 dj ratio 2051.92 distance
> 0.0196402
> Clp0102I 148 -2.03486e+008 In: C32 Out: R413 dj ratio -5069.25 distance
> 941.62
> Clp0060I Primal error 7.62939e-006, dual error 5.5607e-011
> Clp0006I 148  Obj -2.03486e+008 Primal inf 1.81325e+009 (161)
> Clp0001I Primal infeasible - objective value -2.03486e+008
>
>
> ---------------
> The "initialSolve"-version log:
>
> ... (here the first solve does its thing (same as above))
> Clp0102I 88 1.55291e+007 In: C74 Out: R118 dj ratio 0.00934009 distance 0
> Clp0060I Primal error 1.13687e-013, dual error 1.13671e-016
> Clp0006I 88  Obj 1.55291e+007
> Clp0025I Looking optimal checking bounds with 1e+010
> Clp0013I Going back to original objective
> Clp0060I Primal error 1.13687e-013, dual error 0
> Clp0025I Looking optimal checking bounds with 1e+010
> Clp0000I Optimal - objective value 1.55291e+007
> Clp0033I Dual took 0.71 seconds (total 0.81)
> Coin0511I After Postsolve, objective 1.55291e+007, infeasibilities - dual
> 0 (0), primal 0 (0)
> Clp0032I Optimal objective 15529105.63 - 88 iterations time 0.812,
> Presolve 0.10
> (-----------here the _first_ solve ends)
> Clp1001I Initial range of elements is 1.17553e-017 to 9.25e+006
> Clp1002I Range of elements is 2.42439e-009 to 4.12475e+008
> Clp1002I Range of elements is 4.5576e-005 to 21941.4
> Clp1003I Final range of elements is 3.94313e-006 to 100
> Clp0022I Absolute values of scaled rhs range from 23.5309 to 63574.8,
> minimum gap 1e+100
> Clp0020I Absolute values of scaled objective range from 134289 to
> 1.27223e+006
> Clp0021I Absolute values of scaled bounds range from 0.0704473 to 70.3883,
> minimum gap 0.0704473
> Clp0103I Primal nonlinear change 0 (6)
> Clp0060I Primal error 7.63312e-006, dual error 7.86685e-011
> Clp0103I Primal nonlinear change 0 (6)
> Clp0060I Primal error 7.63312e-006, dual error 7.86685e-011
> Clp0006I 0  Obj -3.37723e+008 Primal inf 2.23164e-005 (6) Dual inf
> 6.2369e+008 (192)
> Clp0102I 1 -3.37946e+008 In: R43 Out: R43 dj -4.02448e-006 distance
> 3.23169e-006
> Clp0102I 2 -3.37935e+008 In: R234 Out: R234 dj 1e+010 distance
> -1.11759e-006
> Clp0102I 3 -3.37875e+008 In: R430 Out: R430 dj 1e+010 distance
> -6.00517e-006
> Clp0102I 4 -3.3784e+008 In: R757 Out: R757 dj 1e+010 distance
> -3.43844e-006
> Clp0102I 5 -3.3784e+008 In: R1084 Out: R1084 dj -4.02448e-006 distance
> 1.36509e-006
> Clp0102I 6 -3.37804e+008 In: R1275 Out: R1275 dj 1e+010 distance
> -3.64333e-006
> Clp0102I 7 -3.37767e+008 In: R1471 Out: R1471 dj 1e+010 distance
> -3.64333e-006
> Clp0102I 8 -3.37767e+008 In: R1667 Out: R1667 dj -0.000402448 distance
> 2.29105e-007
> Clp0102I 9 -3.37723e+008 In: R1960 Out: R1960 dj 1e+010 distance
> -4.46849e-006
> Clp0029I End of values pass after 9 iterations
> Clp0060I Primal error 1.16173e-005, dual error 7.86685e-011
> Clp0006I 9  Obj -3.37723e+008 Dual inf 2.369e+007 (185)
> Clp0102I 10 -3.30113e+008 In: C102 Out: R569 dj -1.09194e+007 distance
> 0.696859
> ....
> Clp0102I 188 -7.12343e+007 In: C1589 Out: R1996 dj -0.113365 distance
> 1.31753e-008
> Clp0107I For C232 btran dj -0.00855317, ftran dj 0
> Clp0060I Primal error 7.62939e-006, dual error 2.0063e-010
> Clp0006I 188  Obj -7.12343e+007 Dual inf 5766 (26)
> Clp0060I Primal error 7.62939e-006, dual error 2.0063e-010
> Clp0102I 189 -7.12343e+007 In: C232 Out: R19 dj -0.00855317 distance
> 1e-012
> ...
> Clp0102I 213 -7.11638e+007 In: C1586 Out: C1618 dj -0.00262515 distance
> 1.4281e-012
> Clp0060I Primal error 8.26828e-006, dual error 2.0063e-010
> Clp0006I 213  Obj -7.11638e+007
> Clp0017I Looking optimal with tolerance of 1e-007
> Clp0060I Primal error 8.26828e-006, dual error 2.0063e-010
> Clp0000I Optimal - objective value -7.11638e+007
> _______________________________________________
> Coin-discuss mailing list
> Coin-discuss at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-discuss
>
> _______________________________________________
> Coin-discuss mailing list
> Coin-discuss at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-discuss
>