Research Article
An Improved Decomposition Technique for Solving Integer Linear Programming Problems
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 182 - Issue 23 |
| Published: Oct 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 },
year = { 2018 },
volume = { 182 },
number = { 23 },
pages = { 17-21 },
doi = { 10.5120/ijca2018918023 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2018
%A M. A. I. Bhuiyan
%A M. S. Hossain
%T An Improved Decomposition Technique for Solving Integer Linear Programming Problems%T
%J International Journal of Computer Applications
%V 182
%N 23
%P 17-21
%R 10.5120/ijca2018918023
%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
- Hossain, M. I and Hasan, M.B., An Improved Decomposition Algorithm and Computer Technique For Solving LPs, IJBAS-IJENS Vol. 11 No: 03.
- 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.
- 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.
- Taha. H. A., Operations research: An introduction, 8th Ed. Pearson Preceton hall.
- R. Fourer, D. M. Gay and B. W. Kernighan, AMPL, A Modeling Language of Mathematical programming, 2nd Edition.
- Winston, W.L. (1994), “Linear Programming: Applications and Algorithm”, Duxbury press, Belmont, California, U.S.A.
- Gupta, P.K., D.S. Hira, 2005. Problems in Operations Research Principles and Solution, S. Chand & Copany LTD., New Delhi-110055, 360-405.
- Dantzig, G.B. and P. Wolfe (1961), “The Decomposition Algorithm for Linear Programming”, Econometrica, Vol. 29, No.4.
- Sweeny, D.J. and R.A. Murphy (1979), “A Method of Decomposition for Integer Programs”, Operations Research, Vol. 27, No.6, pp. 1128-1141.
- Ravindran, Philips & Solberg (2000), “Operations Research”, John Wiley and Sons, Second Edition, New York, U.S.A.
- Fisher, M.L. (1979), “The Lagrangean Relaxation Method for Solving Integer Programming Problem”, Management Science, Vol. 27, No.1.
- Dantzig, G.B. (1963), “Linear Programming and Extensions”, Princeton University Press, Princeton, U.S.A.
- Don, E. (2000), “Theory and Problems of Mathematica”, Schaum’s Outline Series, Mc. GRAW-HILL.
Index Terms
Keywords