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

[Jim Hurd]

Thank you both for great replies. I have a work around which is to just run
my cut generator all the time (it's not that inefficient) so mainly I wanted
to make sure I wasn't doing something wrong. Please don't make a change just
for my use.

I think Tobi's solution is elegant, but John's solution is more like what I
expected from reading the existing documentation without looking at the
source code. Either one would be useful in my estimation. 

Thanks,

Jim

-----Original Message-----
From: coin-discuss-bounces at list.coin-or.org
[mailto:coin-discuss-bounces at list.coin-or.org] On Behalf Of Tobias
Achterberg
Sent: Wednesday, August 24, 2005 8:19 AM
To: Discussions about open source software for Operations Research
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