A Decomposition Technique For Solving Integer Programming Problems

Autor:	Md. Istiaq Hossain, M Babul Hasan
Rok vydání:	2014
Předmět:	Linear programming relaxation Mathematical optimization Branch and price Integer points in convex polyhedra AMPL Change-making problem Branch and cut Integer programming computer Scheduling (computing) Mathematics computer.programming_language
Zdroj:	GANIT: Journal of Bangladesh Mathematical Society. 33:1-11
ISSN:	2224-5111 1606-3694
DOI:	10.3329/ganit.v33i0.17649
Popis:	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
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::e8c0668593af92bd22e87a7702837843 https://doi.org/10.3329/ganit.v33i0.17649 Zobrazit plný text záznamu