Faster integer-feasibility in mixed-integer linear programs by branching to force change |
| |
Authors: | Jennifer Pryor John W Chinneck |
| |
Affiliation: | Systems and Computer Engineering, Carleton University, Ottawa, Ontario, Canada K1S 5B6 |
| |
Abstract: | 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: | Mixed-integer programming Branching Integer feasibility |
本文献已被 ScienceDirect 等数据库收录! |