Analyzing Decomposition Procedures in LP and Unraveling for the Two Person Zero Sum Game and Transportation Problems

Analyzing Decomposition Procedures in LP and Unraveling for the Two Person Zero Sum Game and Transportation Problems

Haridas Kumar Das (University of Dhaka, Bangladesh) and Abir Sutra Dhar (University of Dhaka, Bangladesh)
Copyright: © 2020 |Pages: 21
DOI: 10.4018/IJSVST.2020010102


This paper studies some decomposition methods, including Dantzig-Wolfe decomposition (DWD), decomposition-based pricing (DBP), Benders decomposition (BD), and a recently proposed improved decomposition (ID) method for solving linear programs (LPs). The authors then develop a new decomposition algorithm for solving LPs in a general form, allowing authors to combine the concept of Benders decomposition and decomposition-based pricing methods. The authors generate conditions for solving problems that have either infeasible or unbounded solutions. As an illustration, the authors give the corresponding models and numerical results for two standard mathematical programs: the two-person zero-sum game and the transportation problem. The authors compare several procedures and identify which one produces the best solution by giving the authors the smallest iteration number. This study reveals that the algorithm along with Benders decomposition produce the most efficient computational solutions of LPs.
Article Preview

2. Literature Review

Over recent decades, LPs are one of the greatest successes to emerge from operations research and management science. It is well developed and widely used. The LP problem consists of a linear objective function that is to be maximized or minimized while subject to a finite number of linear constraints. The coordinating program generates at each cycle a new objective form for each part, and each part generates in turn (from its optimal basic feasible solutions) new activities (columns) for the interconnecting program. LP arose as a mathematical model developed during World War II to analyze expenditures and returns such that it reduces costs to the army and increases losses to the enemy. It was kept secret until 1947. After World War II, George Dantzig, a member of the US Air force, developed the simplex method of optimization in 1947, a procedure used in many mathematical and economical fields. John von Neumann, who developed the theory of the duality in the same year, and Leonid Kantorovich, a Russian mathematician who used similar techniques in economics before Dantzig and won the Nobel Prize in 1975 in economics (Dantzig & Wolfe 1961). This leads to a generalization of the Simplex Algorithm, for which the decomposition procedure becomes a special case. Postwar, many industries used this model in their daily planning.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 4: 2 Issues (2021): Forthcoming, Available for Pre-Order
Volume 3: 2 Issues (2020): 1 Released, 1 Forthcoming
View Complete Journal Contents Listing