Column Generation in the Integral Simplex Method

• The integral simplex method for set partitioning problems allows onlypivots-on-one to be made, which results in a primal all-integer method. Inthis technical note we outline how to tailor the column generationprinciple to this method. Because of the restriction topivots-on-one, only local optimality can be guaranteed, and to ensureglobal optimality we consider the use of implicit enumeration.

Ämnesord

NATURVETENSKAP  -- Matematik -- Beräkningsmatematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Computational Mathematics (hsv//eng)

Nyckelord

integer programming

set partitioning

column generation

quasi-integrality

Optimization, systems theory

Optimeringslära, systemteori

Publikations- och innehållstyp

ref (ämneskategori)

art (ämneskategori)