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 journalArticle

14 Scopus citations

Abstract

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
Volume179
Issue number2
DOIs
StatePublished - 15 Aug 2006

Keywords

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

Fingerprint 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