 Column generation decomposition with the degenerate constraints in the subproblemAbdelmoutalib Metrane, François Soumis and Issmail Elhallaoui European Journal of Operational Research, 2010, vol. 207, issue 1, 37-44 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 (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:207:y:2010:i:1:p:37-44 Access Statistics for this article European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati More articles in European Journal of Operational Research from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.