[Coin-bcpdiscuss] Default select_branching_candidates bug?

[Francois Margot]

Lasse:

On Mon, 20 Mar 2006, Lasse Nisted wrote:

> Hello
>
> Is there a reason why the default select_branching_candidates
> function in BCP_lp_user throws an exception if no
> branching candidates are found?
> Shouldn't it just return BCP_DoNotBranch_Fathomed ?
>

While this could be defensible, so is the current implementation.
If you go in select_branching_candidates(), it means that the current
LP solution does not satisfy all integrality restrictions, as returned
by test_feasibility(). Then, a branching candidate must logically exist.

The problem is probably numerical accuracy: try to change the parameters

BCP_Granularity                       1e-8 // Lower bound on the minimum
                                            // difference between two feasible
                                            // solutions
                                            // Default: 1e-8

BCP_IntegerTolerance                  1e-5 // Tolerance for a number to be
                                            // considered integer
                                            // Default: 1e-5

to larger values. If this does not solve your problem, it might be
another previously reported bug: let L be the value of the LP solution
and let B be the current best known feasible solution value.

When test_feasibility() returns that the current solution is feasible,
Bcp recomputes its value V. Due to numerical errors, it has
L < B < V. So Bcp does not update the best solution value and, as
L < B, looks (incorrectly) for a variable to branch on.

This can be fixed in the user code by adding a boolean variable res_test
that stores if test_feasibility() found that the current LP solution is
integer. Then, in select_branching_variables(), always return 
BCP_DoNotBranch_Fathomed if res_test == true.

Francois


> Or am I missing something?
>
> I have a IP problem which is solved to integer optimality in the root node,
> and then the select_branching_candidates throws an exception because
> no columns are generated and no fractional values exist.
>
> - Lasse
>
>
>