[Coin-discuss] OsiClp initialSolve vs resolve

Tue Feb 7 09:41:06 EST 2006

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/coin-discuss/attachments/20060207/a084334a/attachment.html>