[Coin-discuss] How to cut off "optimal" solution in CBC

[John J Forrest]

Tobias,

I agree with you but I am not sure this is a common enough requirement so 
I was just proposing minimal work solution.

What do people think?

John Forrest



Tobias Achterberg <achterberg at zib.de> 
Sent by: coin-discuss-bounces at list.coin-or.org
08/24/2005 08:19 AM
Please respond to
Discussions about open source software for Operations Research 


To
Discussions about open source software for Operations Research 
<coin-discuss at list.coin-or.org>
cc

Subject
Re: [Coin-discuss] How to cut off "optimal" solution in CBC






Hi John,

you propose to check the feasibility of a solution candidate by calling 
the cut generators. I think,
this is conceptually wrong - I view a cut generator as a method, that may 
separate cuts, but that
may also decide to not search for cuts. A cut generator should be allowed 
to miss certain cuts.
The feasibility test is something different: here, the user has to be 
called in order to decide
whether a given solution is feasible or not. This sometimes can be 
answered much more efficiently
than by searching cuts (and being forced to find one if a violated cut 
exists). You should add
another callback "checkFeasibility()". Here, the user either says 
"FEASIBLE" or "INFEASIBLE", and if
he answers "INFEASIBLE", he might (but should not be forced to) add a cut 
that cuts off the given
solution candidate.

Cheers, Tobi

John J Forrest wrote:
> 
> Jim,
> 
> Good point.  setBestSolution cleans up and checks solution so I think it
> should run before cut generators which are going to use the solution.  I
> expect the generators to generate cuts which may cut off this solution -
> but in your case you also want to reject that solution.
> 
> What I could do is save old solution and cutoff and then if any cut
> generator returns a cut which is "infeasible" (as defined in OsiCut.hpp
> then that says restore old solution (and the infeasible cut is obviously
> discarded).  At the same time you could generate the global cut you
> wanted and that would be added.
> 
> Or some variant e.g. use "effectiveness". 
> 
> Shall I implement and what method of flagging this situation do you
> think is best?
> 
> John Forrest
> 
> So what if I saved old solution
> 
> 
> *"Jim Hurd" <jimh at datagrove.com>*
> Sent by: coin-discuss-bounces at list.coin-or.org
> 
> 08/23/2005 01:47 PM
> Please respond to
> Discussions about open source software for Operations Research 
> 
> 
> 
> To
>                <coin-discuss at list.coin-or.org>
> cc
> 
> Subject
>                [Coin-discuss] How to cut off "optimal" solution in CBC
> 
> 
> 
> 
> 
> 
> 
> 
> I have a cut generator that may cut off a found integer/optimal solution
> when it runs. I have it set to run atSolution, which works, but looking
> at the code for  CbcModel::setBestSolution it seems that the solution is
> installed prior to running the cuts. When I run my Cbc based solver
> branchAndBound terminates with a solution that should be cut off. How do
> I get Cbc to respect these global cuts? There are too many to just put
> them all in the model at the beginning.
> 
> Thanks,
> 
> Jim Hurd
>  _______________________________________________
> 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

-- 
Tobias Achterberg          Konrad-Zuse-Zentrum fuer
                           Informationstechnik Berlin
Tel: +49 (0)30 84185-301   Takustr. 7
Email: achterberg at zib.de   D-14195 Berlin, Germany
_______________________________________________
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/20050824/08aa7e55/attachment.html>