An All-Integer Column Generation Methodology for Set Partitioning Problems
2008 (English)Report (Other academic)
The set partitioning polytope has the quasi-integrality propertythat enables the use of simplex pivot based methods for finding animproved integer solution, which thereby is associated with a linearprogramming basis and a corresponding dual solution. Presented in thispaper is a framework for an all-integer column generation methodologyfor set partitioning problems that utilises the quasi-integralityproperty of the feasible polytope.In the presented methodology, each successively found solution to arestricted master problem is feasible, integer and associated with acorresponding dual solution, which is then used in the columngeneration step. The column generation problem is tailored to producecolumns that maintain integrality when pivoted into the basis.Furthermore, criteria for verifying optimality are presented.
Place, publisher, year, edition, pages
2008. , 23 p.
, Report / Department of Mathematics, Universitetet i Linköping, Tekniska högskolan, ISSN 0348-2960
integer programming, column generation, quasi-integrality, surrogate columns, over-generation
IdentifiersURN: urn:nbn:se:liu:diva-15256OAI: oai:DiVA.org:liu-15254DiVA: diva2:113790