Gradientmethods for binary Integer Programming

Chien Yuan Huang, Ta Chung Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

Integer Programming (IP) is a common problem class where decision variables represent indivisibility or yes/no decisions. IP can also be interpreted as discrete optimizations which are extensively used in the areas of routing decisions, fleet assignment, and aircraft/aircrew scheduling. Solving IP models is much harder than solving Linear Programming (LP) models because of their intrinsically combinatorial nature. In addition, many "real-world" problems have a huge problem size that makes solving the related IP-based model time-consuming. In this paper, we propose a gradient method for binary IP that enable large problems to be solved in a short amount of time. The algorithm is partitioned into two phases. In phase 1 of the algorithm, integrality constraints are modified and the original problem is solved by the LP algorithm. In phase 2, all integrality constraints are modified again and added back. The Lagrange multipliers are then introduced to form a Lagrange dual problem. We then use the gradient method to quickly search for the optimal or nearly optimal solution. After developing the algorithm, we show the effectiveness of this approach by applying it to various kinds of binary IP problems with discussions about the reduction in computation time and the gap between objective functions.

Original languageEnglish
Title of host publication41st International Conference on Computers and Industrial Engineering 2011
Pages330-336
Number of pages7
Publication statusPublished - 2011 Dec 1
Event41st International Conference on Computers and Industrial Engineering 2011 - Los Angeles, CA, United States
Duration: 2011 Oct 232011 Oct 25

Publication series

Name41st International Conference on Computers and Industrial Engineering 2011

Other

Other41st International Conference on Computers and Industrial Engineering 2011
CountryUnited States
CityLos Angeles, CA
Period11-10-2311-10-25

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • Industrial and Manufacturing Engineering

Fingerprint Dive into the research topics of 'Gradientmethods for binary Integer Programming'. Together they form a unique fingerprint.

Cite this