Originally posted by: davidoff

Hi

I'm implementing my own branching scheme on top of a linear problem that, due to its size , is solved at the root by barrier

When branching on one variable, it is best practice to switch to dual simplex when solving the branch and cut part. That requires a crossover from barrier solution to rebuild a base for initial dual simplex. Thus, we can take advantage of dual simplex to incrementally add constraints typically related to branching (e.g x<=rounddown(x*) on the left branch and x>=roundup(x*) on the right one, if x* is the current fractional value of x in the current node)

My current branching scheme is a little bit different since at every node, I have 4 continuous variables a,b,c,d and my left branch consists in settings a and b to zero, while the right branch sets c and d to zero.

Are these decisions still valid in respect with the previous best practice ? Otherly said, do I keep the benefit of incremental dual simplex when setting two continuous variables to 0. My feeling is 'yes' but I'd like to check !

Thanks

David

Originally posted by: RWunderling

Yes, and optimal basis remains dual feasible when tightening bounds or can be extended to a dual feasible basis when adding constraints. Thus you can warmstart the dual Simplex algorithm directly in phase 2 after such operations.
Since you mentioned crossover:  You should first crossover from your barrier solution before tightening bounds or adding constraints, since otherwise the barrier solution is no longer primal feasible for your modified problem which will typically slow down the crossover considerably.
Also you should tighten bounds rather than adding constraints as to not unneccessarily increase your problem size.

Roland

Originally posted by: davidoff

Thanks Roland,

This is indeed the workflow I implemented Barrier=>CrossOver => Incumbent + Branch Callbacks (the branch call back using a makeBranch API based on the array of variables and the array of new upper bounds that are actually 0)