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

[Ted Ralphs]

Lou Hafer wrote:
> Ted writes (commenting on Mike's earlier post)
> 
> 
>>As Mike pointed out, there is no way for the solver to continue if the
>>current solution is integral and not feasible unless the user either
>>generates a cut or implements a special branching rule for this case.
> 
> 
> 	Perhaps I'm missing something obvious, but I don't agree with this.  The
> standard action on discovering a solution is to stash it away and retrieve a new
> node from the live set (i.e., to continue).  Deciding to discard the incumbent,
> the new solution, or both, can be an independent decision.  If the criteria for
> rejection amounts to something like `not aesthetically pleasing', that may not
> be possible to capture in a cut, but it's possible that the next solution the
> solver discovers may have that better look.  I agree that the user will likely
> want to do something beyond letting the solver stumble on blindly through the
> search tree.

Hmmm, I'm not sure I see exactly what you are getting at, but let me try 
to clear up the point I was trying to make. I think there are two 
different issues here that are getting mingled in the discussion. The 
first issue is the mechanism by which the solver actually determines 
whether it has a "solution." You mention a "standard action on 
discovering a solution," but a basic assumption of SYMPHONY (and the 
assumption of the other solvers Mike mentioned) is that the solver has 
no way of knowing when it has a solution. The user must either implement 
their own method for determining the feasibility of an integer solution, 
or tell SYMPHONY that satisfying integrality restrictions is enough, 
i.e., the initial constraints constitute a valid formulation for the 
problem. If the user declares an integral solution infeasible, but does 
not generate a cut or give the solver a way to branch (besides the 
default of branching on variables, which isn't possible with an integer 
solution), then the solver cannot continue the solution process (at 
least not if the user wants a provably optimal solution). In this case, 
SYMPHONY's default action is to punt. I suppose it could continue 
anyway, with a warning that one of the search tree nodes had an 
undetermined status....anyway, this is the situation I was referring to 
in my previous post.

On the other hand, I think you are referring to the possibility that the 
user might want to "reject" a solution that has been declared feasible 
and could in fact be optimal with respect to the current objective, in 
the hope of finding an alternative optimum that is "better" according to 
some criterion. This is in fact a necessary technique in the case of 
solving multi-criteria problems, where the solver must be able to find, 
among all alternative optima with respect to one objective, the one tat 
is best with respect to a second objective. SYMPHONY has this capability 
as well, but even in this case, I think there has to be a systematic way 
for the solver to continue the search. Allowing the user to simply 
declare a solution "undesirable," without providing a secondary 
objective or some other way of continuing that the solver understands 
seems strange to me. It could turn out later that the solution that was 
rejected was actually the best one (even taking into account the 
secondary objective). I suppose you could adopt the policy that is up to 
the user to track the rejected solutions, in case they are needed later, 
but the end result might be that the solver can only declare the optimal 
value in the end and not return a solution. I guess there are a number 
of ways you could go with this and no one of them is correct. Hope this 
long-winded explanation clears things up :).

Cheers,

Ted


-- 
Dr. Ted Ralphs
Assistant Professor
Industrial and Systems Engineering
Lehigh University
(610)758-4784
tkralphs at lehigh.edu
www.lehigh.edu/~tkr2