dc.description.abstract | We describe a new approach to produce integer feasible columns to a set partitioning problem directly in
solving the linear programming (LP) relaxation using column generation. Traditionally, column generation
is aimed to solve the LP relaxation as quick as possible without any concern of the integer properties of
the columns formed. In our approach we aim to generate the columns forming the optimal integer solution
while simultaneously solving the LP relaxation. By this we can remove column generation in the branch
and bound search. The basis is a subgradient technique applied to a Lagrangian dual formulation of the set
partitioning problem extended with an additional surrogate constraint. This extra constraint is not relaxed
and is used to better control the subgradient evaluations. The column generation is then directed, via the
multipliers, to construct columns that form feasible integer solutions. Computational experiments show that
we can generate the optimal integer columns in a large set of well known test problems as compared to both
standard and stabilized column generation and simultaneously keep the number of columns smaller than
standard column generation. | nb_NO |