Faster integer-feasibility in mixed-integer linear programs by branching to force change
Branching in mixed-integer (or integer) linear programming requires choosing both the branching variable and the branching direction. This paper develops a number of new methods for making those two decisions either independently or together with the goal of reaching the first integer-feasible solution quickly. These new methods are based on estimating the probability of satisfying a constraint at the child node given a variable/direction pair. The surprising result is that the first integer-feasible solution is usually found much more quickly when the variable/direction pair with the smallest probability of satisfying the constraint is chosen. This is because this selection forces change in many candidate variables simultaneously, leading to an integer-feasible solution sooner. Extensive empirical results are given.
|Keywords||Branching, Integer feasibility, Mixed-integer programming|
|Journal||Computers and Operations Research|
Pryor, J. (Jennifer), & Chinneck, J. (2011). Faster integer-feasibility in mixed-integer linear programs by branching to force change. Computers and Operations Research, 38(8), 1143–1152. doi:10.1016/j.cor.2010.10.025