Simultaneous column-and-row generation for solving large-scale linear programs with column-dependent-rows

Muter, İbrahim (2011) Simultaneous column-and-row generation for solving large-scale linear programs with column-dependent-rows. [Thesis]

[thumbnail of IbrahimMuter_411247.pdf] PDF

Download (1MB)


In this thesis, we handle a general class of large-scale linear programming problems. These problems typically arise in the context of linear programming formulations with exponentially many variables. The defining property for these formulations is a set of linking constraints, which are either too many to be included in the formulation directly, or the full set of linking constraints can only be identified, if all variables are generated explicitly. Due to this dependence between columns and rows, we refer to this class of linear programs as problems with column-dependent-rows. To solve these problems, we need to be able to generate both columns and rows on-the-fly within a new solution method. The proposed approach in this thesis is called simultaneous column-and-row generation. We first characterize the underlying assumptions for the proposed column-and-row generation algorithm. These assumptions are general enough and cover all problems with column-dependent-rows studied in the literature up until now. We then introduce, in detail, a set of pricing subproblems, which are used within the proposed column-and-row generation algorithm. This is followed by a formal discussion on the optimality of the algorithm. Additionally, this generic algorithm is combined with Lagrangian relaxation approach, which provides a different angle to deal with simultaneous column-and-row generation. This observation then leads to another method to solve problems with column-dependent-rows. Throughout the thesis, the proposed solution methods are applied to solve different problems, namely, the multi-stage cutting stock problem, the time-constrained routing problem and the quadratic set covering problem. We also conduct computational experiments to evaluate the performance of the proposed approaches.
Item Type: Thesis
Uncontrolled Keywords: Integer programming. -- Linear programming. -- Column generation. -- Tam sayılı programlama. -- Doğrusal programlama. -- Kolon türetme.
Subjects: T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Industrial Engineering
Faculty of Engineering and Natural Sciences
Depositing User: IC-Cataloging
Date Deposited: 06 Jul 2014 00:51
Last Modified: 26 Apr 2022 10:01

Actions (login required)

View Item
View Item