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

[Francois Margot]

>
> As Francois pointed out, SYMPHONY has a separate feasibility check, but
> in hindsight, I'm not sure that was quite the right way to go. 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. There may be
> efficiency gains in combining the feasibility check and cut generation
> steps. In cases where the feasibility check generates a cut as a natural
> by-product, the user will be forced to regenerate that same cut later
> (either from scratch or by retrieving a cached copy) if the two are
> separated. By combining the two functions, this is avoided. Right now, I
> cannot really see a good reason to have them separated.
>

I dislike the fact to have generate cuts or branching rules in a feasibility
check procedure or vice-versa. I would like to write cutting code in the 
cutting procedure, branching code in the branching procedure, and 
feasibility check code in the feasibility check procedure.

The problem is that the ordering of the feasibility check,
and cutting steps is not reconfigurable by the user. Depending
on the application, the logical way of doing things differ. One way around
this is to have two feasibility check procedures.

Consider the following three typical applications (these cover all the cases 
that I have met; there are complications when multi-objectives are involved, 
but I have never looked at these problems):

Let x be the optimal solution of the LP relaxation at a node.

Application I): If x is integer, then x is optimal for the subproblem.

Application II) If x is integer but not "really" feasible, I have a cut 
generator that always generates a cut for x.

Application III): If x is integer but is not "really" feasible, I have a cut 
generator that may generate a cut for x, but not always. When the cut 
generator fails, I would like to have the possibility of labeling x as 
infeasible and continue.

In Application I), I would like the order to be:
feasibility check, cutting, branching.

In Application II), I would like the order to be:
cutting, feasibility check, branching.

In Application III), I would like the order to be:
either the order for I or the order for II, or even
feasibility check A, cutting, feasibility check B, branching

My preference is for having two feasibility check procedures, one
before cutting and one after cutting. The return value of these
checking procedures is either "feasible" or "infeasible". In the first
case, the solver grabs x, compares it with the currently best known solution
and fathom the node. In the second case, the solver continues. To handle
the case where an integer x is labeled infeasible, but no cuts were 
generated, a special branching rule is used (for example, the one Tobias 
suggested) or an error is raised by the solver (if the user is responsible 
for implementing the exotic branching and did not).

Francois