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

[achterberg at zib.de]

I don't see your point that the solver cannot do anything if the user just
says the current integral LP solution is infeasible. In SCIP, I do the
following:

- If all integral variables are fixed: the node is declared infeasible (in
my definition of the "Constraint Integer Program" I want to solve with
SCIP, I demand that fixing all integer variables results in a Linear
Program.)
- Otherwise, I call the branching plugins in order to generate a
branching. If no branching plugin can handle integral solutions, I just
branch on the first unfixed variable in a three-way branch: 1. x <= x'-1,
2. x == x', 3. x >= x'+1. In the second case x == x', the current solution
is not cut off and is reproduced in the child node, but one additional
variable is fixed. That means, at some point all integer variables will be
fixed and we are in the case above, where the problem is declared
infeasible, if the user rejects the optimal LP solution. However, it is
very likely, that due to the fixing of the integer variable, domain
propagation can tighten the bounds of other variables, thereby cutting off
the current LP solution.


In SCIP, I divided the separation callback into two methods: the
SEPA-Method has the task to tighten the LP relaxation by heuristically
producing cuts. It should do everything it thinks that is reasonable
(e.g., only producing some cuts, abort the search if it doesn't seem to be
promising, only look at some constraints that were useful in the past,
...).
The second method is called ENFORCE. This is called after the SEPA-Loop,
if no more cuts have been found. The task is to decide whether the current
LP solution is feasible. In this method, the user has to check every
single constraint for violation. If a constraint is violated by the LP
solution, the user has to do something:
1. Produce a cut that cuts off the LP solution -> continue with the
SEPA-Loop.
2. Produce a branching.
3. Just say "infeasible".

If all constraints are feasible, the LP solution is accepted as new
encumbent. If at least one constraint was declared infeasible, and no cut
or a branching was produced, the stupid 3-way branching on the first
unfixed integer variable I mentioned above is applied.

This construction leads (with the restriction to my definition of
Constraint Integer Programs) always to an optimal solution. However, if
the user is lazy and does not produce branchings or cuts and only says
"infeasible" if an LP solution violates a constraint, this leads to the
complete enumeration of the search space of integer variables.


My suggestion for COIN is to include a "checkFeasibility" callback, and
allow the user in this callback to produce cuts or branchings if the
solution is infeasible. If he just says "infeasible", do a 3-way branch on
an unfixed integer variable (probably one should branch on a variable that
is currently on one of its bounds; then the branch would still be a 2-way
branch).


Cheers,  Tobi