[Coin-discuss] bestPossibleObjective for Cbc

[John J Forrest]

Kish,

I think it is correct to return true on isProvenInfeasible if there is no 
valid solution to a MIP - what do other people think?

Try putting the test isProvenDualInfeasible before isProvenInfeasible.

John Forrest



Kish Shen <kish.shen at crosscoreop.com> 
Sent by: coin-discuss-bounces at list.coin-or.org
07/14/2006 12:31 AM
Please respond to
Discussions about open source software for Operations Research 
<coin-discuss at list.coin-or.org>


To
coin-discuss at list.coin-or.org
cc

Subject
Re: [Coin-discuss] bestPossibleObjective for Cbc






On Thursday 13 July 2006 17:53, Kish Shen wrote:
> John,
>
> Thanks. I have just downloaded Coin-Cbc in branches/devel, and the
> bestPossible is indeed working.
>
> I still get a failure instead of unbounded state returned for a simple
> unbounded problem. I need more time to look at the code to see what has
> changed.
>
> I am however having problems with maximising problem -- I was doing my
> unbounded test case with a maximising problem:
>
> max X
>
> X = Y
> X + Y >= 3
> X is integer
>
> but this problem is now returning X, Y = 2, i.e. it seems to be 
minimising
> the problem rather than maximising!
>
> I have not had time to look at this in detail, but thought I should post
> this before I leave today.
>
I should have checked this in more detail before posting, but I was 
rushing to 
leave. This problem is due to a my mistake -- I mistakenly commented out 
the 
code that sets the optimisation sense when I was playing around with 
CoinPackedMatrix...

However, the unbounded integer problem is still reported as a failure. Is 
this 
the problem that have been fixed? The code I now use to test for the state 
of 
a MIP solve try to avoid calling isProvenInfeasible() if the initialSolve 
was 
not optimal, 

                 CbcModel* model = lpd->lp->mipmodel;
                 if (model->isProvenOptimal()) return state_success;  // 
optimal
                 if (model->isInitialSolveProvenOptimal()) 
                 {
        .....
                 }
                 if (model->isInitialSolveAbandoned()) return 
state_lpaborted; 
                 if (model->isInitialSolveProvenPrimalInfeasible()) return 
state_fail;
                 if (model->isInitialSolveProvenDualInfeasible()) return 
state_unbounded;

for the unbounded problem, isInitialSolveProvenPrimalInfeasible() returns 
true.

For the same linear problem (i.e. without the integer constraints), 
isProvenPrimalInfeasible() correctly returns false after a call to 
initialSove() for the OsiCbcSolver.

Cheers,

Kish Shen 
> Cheers,
>
> Kish
>
> On Tuesday 11 July 2006 23:12, John J Forrest wrote:
> > Kish,
> >
> > bestPossible should be fixed in branches/devel - also unbounded.
> >
> > John Forrest
> >
> >
> >
> >              Kish Shen
> >              <kish.shen at crossc
> >              oreop.com> 
> > To Sent by:                  coin-discuss at list.coin-or.org
> > coin-discuss-boun                                          cc
> > ces at list.coin-or.
> >              org 
> > Subject [Coin-discuss]
> >                                        bestPossibleObjective for Cbc
> >              07/10/06 10:24 PM
> >
> >
> >              Please respond to
> >              Discussions about
> >                 open source
> >                software for
> >                 Operations
> >                  Research
> >              <coin-discuss at lis
> >               t.coin-or.org>
> >
> >
> >
> >
> >
> >
> > Hi,
> >
> > I am interested in obtaining the best possible bound on the objective
> > value
> >
> > from a MIP solve. This value is stored in bestPossibleObjective in the
> > CbcModel, but it seems that if the MIP search is exited without 
searching
> > the
> > whole tree, because of setting of the allowable MIP gap (e,g, as
> > specified by
> > CbcAllowableFractionGap), bestPossibleObjective is set to 
bestObjective
> > at the end of the search.
> >
> > For example, in the following MIP solve of the bell3a problem:
> >
> > Cbc0012I Integer solution of 878430 found by heuristic after 150
> > iterations
> >
> > and 2 nodes (1.46 seconds)
> > Cbc0010I After 500 nodes, 156 on tree, 878430 best solution, best
> > possible 876741 (8.18 seconds)
> > Cbc0011I Exiting as integer gap of 1689.38 less than 1e-10 or 0.3%
> > Cbc0001I Search completed - best objective 878430, took 5109 
iterations
> > and
> >
> > 501 nodes (8.19 seconds)
> >
> > the search is exited early, with
> >
> > bestPossibleObjective = 876741
> > bestObjective = 878430
> >
> > but by the time I call getBestPossibleObjValue() immediately after the
> > branchAndBound() call, it is already set to 878430. [I think this is 
done
> > around line 1700 of my copy of CbcModel.cpp]
> >
> > Is there any way I can get the original bestPossibleObjective before 
it
> > was
> >
> > set to bestObjective?
> >
> > Thanks and cheers,
> >
> > Kish
> > _______________________________________________
> > 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
>
> _______________________________________________
> 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

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