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

Din Yuen Chan, Cheng-Yuan Ku*, Ming Chai Li

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


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.

Original languageEnglish
Pages (from-to)484-493
Number of pages10
JournalApplied Mathematics and Computation
Issue number2
StatePublished - 15 Aug 2006


  • Acceleration of computation
  • Branch-and-bound procedure
  • Duality
  • Integer linear programming
  • Operations research


Dive into the research topics of 'A method to improve integer linear programming problem with branch-and-bound procedure'. Together they form a unique fingerprint.

Cite this