[Coin-lpsolver] solving a small MIP

[John J Forrest]

Stefan,

No good deed goes unpunished -  I should never have added branch and bound
to OsiClp as soon people will want more and more features which is what Cbc
is meant to give.

What you are getting is correct in some perverse way.  The dual objective
limit reached means nothing after branch and bound but this is what is
happening:

Whenever a valid solution of X is obtained then the dual cutoff is set to
X-epsilon.  At the end of the first search you get a solution but when you
test it it is slightly worse than cutoff.  Then you do an ordinary solve
which works as continuous solution is better than X-epsilon.  Then you do
branch and bound again and it does not find a better integer solution than
X-epsilon so isProvenOptimal is false and objective limit reached is random
(would be result from last solve inside branch and bound).

I have modified code so cutoff is set back to X+epsilon at end of a
successful search.

John Forrest


                                                                           
             Stefan Vigerske                                               
             <stefan at mathemati                                             
             k.hu-berlin.de>                                            To 
             Sent by:                  coin-lpsolver at list.coin-or.org      
             coin-lpsolver-bou                                          cc 
             nces at list.coin-or                                             
             .org                                                  Subject 
                                       [Coin-lpsolver] solving a small MIP 
                                                                           
             04/14/06 01:01 PM                                             
                                                                           
                                                                           
                                                                           
                                                                           




Hi,

I try to solve MIPs with OsiClpSolverInterface and got a bit confused about

return codes and others.
I've tried now the simple example
max 4x1 -  x2
             7x1 - 2x2    <= 14
             x2    <= 3
             2x1 - 2x2    <= 3
             x1 in Z+, x1<=10, x2 >= 0
It's a little modified version (adding x1<=10) of one of the unit tests.
Since the variables are bounded and (x1,x2)=(0,0) is a feasible point,
there
should be now problem for Clp to solve it.

I first called branchAndBound(). After that, isProvenOptimal() returns
true,
but also isDualObjectiveLimitReached() returns true.

After that, I wanted to solve the LP relaxation only. But having a look at
the
B&B code shows that at the end of the B&B the bounds of the integer
variables
are fixed to the integer solution. So I'm calling setColBounds(0, 0., 10.)
to
set a proper bound again and call resolve().
This solves the model, isProvenOptimal() returns true and
isDualObjectiveLimitReached() returns false.

Next, running branchAndBound() again, the first two nodes in the B&B turn
out
to be infeasible and the algorithm stops, even when the problem is the same

as in the beginning. isProvenOptimal() returns false and
isDualObjectiveLimitReached() returns true.

Here comes the complete output. I'm attaching the sourcefile.

B&B: m.setInteger(0); m.branchAndBound();
Coin0506I Presolve 2 (-1) rows, 2 (0) columns and 4 (-1) elements
Clp0006I 0  Obj 0 Dual inf 2.13809 (1)
Clp0006I 1  Obj -8.42857
Clp0000I Optimal - objective value -8.42857
Coin0511I After Postsolve, objective -8.42857, infeasibilities - dual 0
(0),
primal 0 (0)
Clp0032I Optimal objective -8.428571429 - 1 iterations time 0.002, Presolve

0.00
Clp0006I 0  Obj -8.42857 Primal inf 0.267261 (1)
Clp0001I Primal infeasible - objective value -8.42857
Clp0006I 0  Obj -8.42857 Primal inf 1.60357 (1)
Clp0006I 2  Obj -7.5
Clp0000I Optimal - objective value -7.5
Integer solution of -7.5 found after 2 iterations and 3 nodes
Search took 2 iterations and 3 nodes
Clp0000I Optimal - objective value -7.5
isProvenOptimal: 1
isDualObjectiveLimitReached: 1

Resolve: m.setColBounds(0, 0., 10.); m.resolve();
Clp0006I 0  Obj -31.5 Primal inf 14.4443 (2)
Clp0006I 2  Obj -8.42857
Clp0000I Optimal - objective value -8.42857
isProvenOptimal: 1
isDualObjectiveLimitReached: 0

B&B again: m.branchAndBound();
Clp0006I 0  Obj -8.42857
Clp0006I 0  Obj -8.42857
Clp0000I Optimal - objective value -8.42857
Clp0006I 0  Obj -8.42857 Primal inf 0.267261 (1)
Clp0001I Primal infeasible - objective value -8.42857
Clp0006I 0  Obj -8.42857 Primal inf 1.60357 (1)
Clp0006I 2  Obj -7.5
Clp0001I Primal infeasible - objective value -7.5
Search took 2 iterations and 2 nodes
isProvenOptimal: 0
isDualObjectiveLimitReached: 1

Stefan

--
Stefan Vigerske
Humboldt University Berlin, Numerical Mathematics
http://www.math.hu-berlin.de/~stefan
[attachment "clptest1.cpp" deleted by John J Forrest/Watson/IBM]
_______________________________________________
Coin-lpsolver mailing list
Coin-lpsolver at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/coin-lpsolver