Column generation decomposition with the degenerate constraints in the subproblem |
| |
Authors: | Abdelmoutalib Metrane François Soumis Issmail Elhallaoui |
| |
Institution: | 1. Université Hassan 1, Ecole Nationale des Sciences Appliquées de Khouribga, Hay El Jadid, El Biout “OCP”, B.P. 77, Khouribga, Morocco;2. École Polytechnique de Montréal and GERAD, Département de Mathématiques et de Génie Industriel, C.P. 6079, Succ. Centre-Ville, Montréal, Québec, Canada H3C 3A7 |
| |
Abstract: | In this paper, we propose a new Dantzig–Wolfe decomposition for degenerate linear programs with the non degenerate constraints in the master problem and the degenerate ones in the subproblem. We propose three algorithms. The first one, where some set of variables of the original problem are added to the master problem, corresponds to the Improved Primal Simplex algorithm (IPS) presented recently by Elhallaoui et al. 7]. In the second one, some extreme points of the subproblem are added as columns in the master problem. The third algorithm is a mixed implementation that adds some original variables and some extreme points of a subproblem to the master problem. Experimental results on some degenerate instances show that the proposed algorithms yield computational times that are reduced by an average factor ranging from 3.32 to 13.16 compared to the primal simplex of CPLEX. |
| |
Keywords: | Linear programming Primal simplex algorithm Column generation Degeneracy |
本文献已被 ScienceDirect 等数据库收录! |
|