A Decomposition Technique For Solving Integer Programming Problems

Authors

  • Md. Istiaq Hossain Institute of Natural Science, United International University, Dhaka,
  • M Babul Hasan Department of Mathematics, University of Dhaka,

DOI:

https://doi.org/10.3329/ganit.v33i0.17649

Keywords:

Decomposition, Relaxation, Integer linear programming, Binary integer programming

Abstract

Dantzig-Wolfe decomposition as applied to an integer program is a specific form of problem reformulation that aims at providing a tighter linear programming relaxation bound due to the non-convexity of an integer problem. In this paper, we develop an algorithm for solving large scale integer program relying on column generation method. We implemented our algorithm for solving Capital budgeting and scheduling type problems. Moreover, we used the Computer Aided System (CAS) AMPL to convert our algorithm into programming codes and illustrated the same problem in our program. We demonstrate our method by illustrating some numerical examples.

DOI: http://dx.doi.org/10.3329/ganit.v33i0.17649

GANIT J. Bangladesh Math. Soc.Vol. 33 (2013) 1-11

Downloads

Download data is not yet available.
Abstract
3095
PDF
1408

Downloads

Published

2014-01-13

How to Cite

Hossain, M. I., & Hasan, M. B. (2014). A Decomposition Technique For Solving Integer Programming Problems. GANIT: Journal of Bangladesh Mathematical Society, 33, 1–11. https://doi.org/10.3329/ganit.v33i0.17649

Issue

Vol. 33 (2013)

Section

Articles

License

The copyright of GANIT: Journal of Bangladesh Mathematical Society is reserved by Bangladesh Mathematical Society (web: https://bdmathsociety.org/)