[Coin-discuss] bestPossibleObjective for Cbc

Kish Shen kish.shen at crosscoreop.com
Fri Jul 14 11:28:52 EDT 2006 

John,

Thanks for your reply.

On Friday 14 July 2006 15:07, John J Forrest wrote:
> 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?
>

I guess it is possible for a MIP problem whose linear relaxation is unbounded 
to be infeasible for the MIP, but you can't determine this as the MIP search 
does not continue if the linear relaxation is unbounded. In this case, I 
would expect my code to return a `infeasible or unbounded' status to the user 
(rather than just infeasible).

In the specific unbounded example I was testing, the problem definitely have 
feasible MIP solutions, just not a bounded optimal solution. I know it may 
not be possible to determine this with a branch and bound search.

> Try putting the test isProvenDualInfeasible before isProvenInfeasible.
>
> John Forrest

Is this correct? My understanding is that a dual infeasible problem is not 
necessarily primal unbounded -- it could be either primal unbounded or 
infeasible. The logic of the code I have is that a non-optimal problem which 
is not primal infeasible, but is dual infeasible, is primal unbounded.

Cheers,

Kish

>
>
>
> 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

More information about the Coin-discuss mailing list