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

[Michael Hennebry]

On Mon, 29 Aug 2005, John J Forrest wrote:

> I agree with adding in a feasibility checker which has as input where it
> is being called from.  However to complicate matters there are at present
> three places in CBC where a solution can be found-

The other issue is the degree, if any, to which cut
generation and feasibilty checking should be separate.

> 1) In normal branching - this is the situation which has been discussed.
> 2) As a by product of strong branching.
> 3) As the result of a heuristic.  I think it is still worth having a final
> check so that users can pick up other peoples heuristics.
>
> So I would propose 4 input states (2 for case 1).

I'm not clear on how case 1 is being split.

> Output would be 0 - continue
>   1 accept as valid integer solution
>    2 treat as an infeasible node (not for heuristic call)

I take it this means treat the node as if it were LP-infeasible.
It would seem necessary for the checker to have
tableau information, not just the solution itself.
The cut generator might be a better place for this.

>    3 exit from while loop (not for heuristic or strong branching calls)

I'm not clear on this either.


I propose the following principles.

1.  A solution is feasible if fcc declares it feasible.
The solver should not assume that it will satisfy
subsequently generated constraints.

2.  A solution, even a heuristic, is not deemed
feasible until fcc declares it so.
On my own, I'd have exempted heuristics on the
theory that generating feasible solutions is
what heuristics are for.  If this makes it easier
to use other people's heuristics, lets do it.

3.  The fcc should be allowed,
but not required, to generate cuts.
To this end, input to the fcc should
include the origin of the testee.
One might not want to generate
a cut based on a heuristic.

4.  The fcc should be allowed,
but not required, to generate heuristic solutions.
To this end, input to the fcc should
include the origin of the testee,
lest one try to generate heuristic solutions
from heuristic solutions ad infinitum.

5.  The cut generator callback would be invoked
only on an infeasible LP-feasible node of the
B&B tree, thus the only alternative processing
for the node is branching.

6.  The cgc should be allowed, but not required,
to generate heuristic solutions.


In the standard case, a solution that satifies
integrality and the original linear constraints
is feasible.
The fcc can check for integrality.
It need not generate any cuts or heuristics.
The cgc need not generate any cuts,
but doing so might be useful.

In the case where there are too many constraints too list,
feasiblity and cut generation are linked.
If a solution is non-integral,
fcc can declare it infeasible and be done.
If a solution is integral, fcc must check further.
If the solution fails that check, e.g. the solution
has a subcycle, there will usually be a readily derived cut.
The fcc can send it to the solver.
If the fcc does so, gcg need not generate any cuts,
but doing so might be useful.

Once one has a feasible solution,
one might want to force subsequent solutions to be better.
In the case of a binary LP, facets of the knapsack cx< current_best
might make good constraints.

When I have an unmixed binary LP,
I get my feasible solutions by rounding.
Suppose my feasibility checker is asked
whether (.1, .1, .1, .1) is feasible.
It will check (0, 0, 0, 0) and if it's feasible declare it
to be a feasible solution.
It will also generate the cut x1 + x2 + x3 + x4 >= 1 .
Doing this gets around some precision problems.
In the case of (.3, .3, .3, .3), it would not generate
the cut because the cut would not be violated.
My cut generator will generate other cuts.

-- 
Mike   hennebry at web.cs.ndsu.NoDak.edu
"There are three kinds of people,
those who can count and those who can't."