### 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 language | English |
---|---|

Title of host publication | 41st International Conference on Computers and Industrial Engineering 2011 |

Pages | 330-336 |

Number of pages | 7 |

Publication status | Published - 2011 |

Event | 41st International Conference on Computers and Industrial Engineering 2011 - Los Angeles, CA, United States Duration: 2011 Oct 23 → 2011 Oct 25 |

### Other

Other | 41st International Conference on Computers and Industrial Engineering 2011 |
---|---|

Country | United States |

City | Los Angeles, CA |

Period | 11-10-23 → 11-10-25 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Computer Science (miscellaneous)
- Industrial and Manufacturing Engineering

### Cite this

*41st International Conference on Computers and Industrial Engineering 2011*(pp. 330-336)

}

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

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 -