Gradientmethods for binary Integer Programming

Chien Yuan Huang, Ta-Chung Wang

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

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
Event41st International Conference on Computers and Industrial Engineering 2011 - Los Angeles, CA, United States
Duration: 2011 Oct 232011 Oct 25

Other

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

Fingerprint

Integer programming
Gradient methods
Linear programming
Lagrange multipliers
Scheduling
Aircraft

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • Industrial and Manufacturing Engineering

Cite this

Huang, C. Y., & Wang, T-C. (2011). Gradientmethods for binary Integer Programming. In 41st International Conference on Computers and Industrial Engineering 2011 (pp. 330-336)
Huang, Chien Yuan ; Wang, Ta-Chung. / Gradientmethods for binary Integer Programming. 41st International Conference on Computers and Industrial Engineering 2011. 2011. pp. 330-336
@inproceedings{eb804cabc948460d9ccddcbafb534544,
title = "Gradientmethods for binary Integer Programming",
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.",
author = "Huang, {Chien Yuan} and Ta-Chung Wang",
year = "2011",
language = "English",
isbn = "9781627486835",
pages = "330--336",
booktitle = "41st International Conference on Computers and Industrial Engineering 2011",

}

Huang, CY & Wang, T-C 2011, Gradientmethods for binary Integer Programming. in 41st International Conference on Computers and Industrial Engineering 2011. pp. 330-336, 41st International Conference on Computers and Industrial Engineering 2011, Los Angeles, CA, United States, 11-10-23.

Gradientmethods for binary Integer Programming. / Huang, Chien Yuan; Wang, Ta-Chung.

41st International Conference on Computers and Industrial Engineering 2011. 2011. p. 330-336.

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

TY - GEN

T1 - Gradientmethods for binary Integer Programming

AU - Huang, Chien Yuan

AU - Wang, Ta-Chung

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84886898221&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84886898221&partnerID=8YFLogxK

M3 - Conference contribution

SN - 9781627486835

SP - 330

EP - 336

BT - 41st International Conference on Computers and Industrial Engineering 2011

ER -

Huang CY, Wang T-C. Gradientmethods for binary Integer Programming. In 41st International Conference on Computers and Industrial Engineering 2011. 2011. p. 330-336