CFP last date
22 April 2024
Reseach Article

An Improved Decomposition Technique for Solving Integer Linear Programming Problems

by M. A. I. Bhuiyan, M. S. Hossain
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 182 - Number 23
Year of Publication: 2018
Authors: M. A. I. Bhuiyan, M. S. Hossain
10.5120/ijca2018918023

M. A. I. Bhuiyan, M. S. Hossain . An Improved Decomposition Technique for Solving Integer Linear Programming Problems. International Journal of Computer Applications. 182, 23 ( Oct 2018), 17-21. DOI=10.5120/ijca2018918023

@article{ 10.5120/ijca2018918023,
author = { M. A. I. Bhuiyan, M. S. Hossain },
title = { An Improved Decomposition Technique for Solving Integer Linear Programming Problems },
journal = { International Journal of Computer Applications },
issue_date = { Oct 2018 },
volume = { 182 },
number = { 23 },
month = { Oct },
year = { 2018 },
issn = { 0975-8887 },
pages = { 17-21 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume182/number23/30073-2018918023/ },
doi = { 10.5120/ijca2018918023 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-07T01:12:14.733784+05:30
%A M. A. I. Bhuiyan
%A M. S. Hossain
%T An Improved Decomposition Technique for Solving Integer Linear Programming Problems
%J International Journal of Computer Applications
%@ 0975-8887
%V 182
%N 23
%P 17-21
%D 2018
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Decomposition technique is one of the most frequently used technique for solving Linear Programming Problems (LPPs) as well as Integer Linear Programming Problems (ILPPs). There are many existing techniques for solving ILPPs such as Branch and Bound method, Cutting Plane method etc. The purpose of this paper is to develop computer oriented decomposition technique for solving ILPPs using benders decomposition method. Applying decomposition technique anyone can solve ILPPs by dividing original problem into two easier problems, namely Master problem and Sub problem. This paper proposes a new technique for solving a ILLP manually and develops a computer code using a Mathematical Programming Language (AMPL). Also a comparison of manual output and programming output has been presented.

References
  1. Hossain, M. I and Hasan, M.B., An Improved Decomposition Algorithm and Computer Technique For Solving LPs, IJBAS-IJENS Vol. 11 No: 03.
  2. Das, H. K. and Babul Hasan, M., An Improved Decomposition Approach and its Computer Technique For Solving Primal Dual LP & LFP Problems, GANIT, J. Bangladesh mathematical Society Vol. 33, 2013, pp. 65-75.
  3. Sajal chakroborty and M. Babul Hasan, A Chronic of Analyzing Stochasticity in Multi Period Transportation Problems for Uncertainity, IJCA Vol. 113 No: 08, January 2016.
  4. Taha. H. A., Operations research: An introduction, 8th Ed. Pearson Preceton hall.
  5. R. Fourer, D. M. Gay and B. W. Kernighan, AMPL, A Modeling Language of Mathematical programming, 2nd Edition.
  6. Winston, W.L. (1994), “Linear Programming: Applications and Algorithm”, Duxbury press, Belmont, California, U.S.A.
  7. Gupta, P.K., D.S. Hira, 2005. Problems in Operations Research Principles and Solution, S. Chand & Copany LTD., New Delhi-110055, 360-405.
  8. Dantzig, G.B. and P. Wolfe (1961), “The Decomposition Algorithm for Linear Programming”, Econometrica, Vol. 29, No.4.
  9. Sweeny, D.J. and R.A. Murphy (1979), “A Method of Decomposition for Integer Programs”, Operations Research, Vol. 27, No.6, pp. 1128-1141.
  10. Ravindran, Philips & Solberg (2000), “Operations Research”, John Wiley and Sons, Second Edition, New York, U.S.A.
  11. Fisher, M.L. (1979), “The Lagrangean Relaxation Method for Solving Integer Programming Problem”, Management Science, Vol. 27, No.1.
  12. Dantzig, G.B. (1963), “Linear Programming and Extensions”, Princeton University Press, Princeton, U.S.A.
  13. Don, E. (2000), “Theory and Problems of Mathematica”, Schaum’s Outline Series, Mc. GRAW-HILL.
Index Terms

Computer Science
Information Sciences

Keywords

LPP ILPP DWD Benders Decomposition AMPL Master- Problem Sub-Problem.