A method to improve integer linear programming problem with branch-and-bound procedure

摘要

Integer linear programming (ILP) problems are harder to solve than linear programming (LP) problems. It doesn't work if try to round off the results of LP problems and claim they are the optimum solution. The branch-and-bound (B&B) is the popular method to solve ILP problems. In this paper, we propose a revised B&B, which is demonstrated to be more efficient most of time. This method is extraordinarily useful when facing ILP problems with large differences between constraints and variables. It could reduce the number of constraint and work efficiently when handling ILP problems with many constraints and less variables. Even if the ILP problems have fewer constraints but many variables, we suggest using duality concept to interchange variables with constraints. Then, the revised B&B could be used to compute results very quickly. (c) 2006 Elsevier Inc. All rights reserved.