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

[Michael Hennebry]

On Thu, 25 Aug 2005, Francois Margot wrote:

> 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.

I agree.

> 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.

Something like this?

loop {
    if feasibility check succeeds then done

    try to generate cuts
    if successful {
        resolve
        if LP infeasible then done
    } else {
        break
    }
}
branch

Without a feasibility check after cutting,
one could be trying to branch when the current solution is feasible.

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

Like this?

more=false
repeat {
    more=false
    try to generate cuts
    if successful {
        more=true
        resolve
        if LP infeasible then done
    }
} until !more
if feasible done
branch

> 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).

I think that the best answer is to not
restrict cut generation to dedicated callbacks.

At any point, any callback should be allowed to do something
like HereIsACut(problem, cut).
If nothing else, the solver would store the cut for later use.
The solver would know when later would be,
so the user wouldn't have to.
This would be convenient for just about everyone.

more=true
repeat {
    more=false
    test for feasibility
    if feasible done
    if cuts generated {
        more=true
    } else {
        try to generates cuts
        if successful then more=true
    }
    if(more) {
        resolve
        if LP infeasible done
    }
} until !more
branch

How to branch on an infeasible all-integer
solution is a distinct issue.
I'd be inclined to let the solver do whatever it
wants so long as what it wants is documented.


If the MILP has continuous variables,
the integer variables are all integer,
and the solution is still infeasible,
it might be that no branching formula is sufficient.
The feasible set might not be closed,
in which case there might not be an optimal solution.

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