[Coin-discuss] double calls of BB_lp::test_feasibility

[Laszlo Ladanyi]

Hi Viet,

The most likely culprit is this this piece of code from BCP_lp_main_loop.cpp:

 	  if (BCP_lp_fix_vars(p) ||
 	      (p.lp_solver->canDoSimplexInterface() &&
 	       !p.lp_solver->basisIsAvailable())) {
 	    // during variable fixing primal feasibility is lost (must be due
 	    // to logical fixing by the user) OR we can do simplex, but for
 	    // some reason the basis is lost (generally when the LP solver
 	    // discards the basis if bounds are changed). Go back and resolve,
 	    // but keep the same iteration number
 	    --p.node->iteration_count;
 	    continue;
 	  }

As you say, reduced cost fixing fixed a few vars. Then the basis is still be 
optimal, but some LP solvers discard the basis if bounds are changed (even if 
the current solution is still feasible). There is nothing wrong with that, 
it's a very conservative way of dealing with bound changes. Since Bcp does 
need the basis, it goes back to the top of the loop to resolve (and thus to 
get back a basis).

Given that this is necessary how can you avoid running the whole body of the 
feasibility testing? Well, it's not too difficult:

Have two data members in your user class that stores the current node index 
and iteration count within the node. Initialize then to -1. At the beginning 
of test_feasibility call current_index() and current_iteration(). Compare it 
to the data members. If they are the same then you are in the bad situation 
and just simply return. Otherwise update the saved values and execute the body 
of the method.

Note that you may run into the same problem during strong branching, because 
test_feasibility is invoked for branch of every candidate. The solution here 
is to raise/lower a flag in the modify_lp_parameters method whose second 
argument indicates whether the next LP solution (and afterwards feasibility 
testing) will be done in the main loop or in strong branching. Then in 
test_feasibility you can check the value of this flag and decide what you want 
to do.

I hope this helps,
--Laci


On Fri, 8 Feb 2008, Viet Hung NGUYEN wrote:

> Hi all,
> I am using BCP for a branch-and-cut algorithm and I have remarked that
> the function BB_lp::test_feasibility is called twice whenever the
> reduced cost fixing
> has changed on some of my variables. As I include heavy cuts generation
> subroutines in
> BB_lp::test_feasibility, I would like not to see them  to be doubly called.
> Could someone help me to avoid that.
> Many thanks in advance.
> Best regards,
> Viet
>
> _______________________________________________
> Coin-discuss mailing list
> Coin-discuss at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-discuss
>