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

Muter, İbrahim and Birbil, Ş. İlker and Bülbül, Kerem (2010) Simultaneous column-and-row generation for large-scale linear programs with column-dependent-rows. [Working Paper / Technical Report] Sabanci University ID:SU_FENS_2010/0004

[thumbnail of crg_Muter_et_al_final.pdf] PDF

Download (466kB)


In this paper, we develop a simultaneous column-and-row generation algorithm for 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. These constraints 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 an efficient solution method. We emphasize that the generated rows are structural constraints and distinguish our work from the branch-and-cut-and-price framework. We first characterize the underlying assumptions for the proposed column-and-row generation algorithm and then introduce the associated set of pricing subproblems in detail. The proposed methodology is demonstrated on numerical examples for the multi-stage cutting stock and the quadratic set covering problems.
Item Type: Working Paper / Technical Report
Uncontrolled Keywords: linear programming; column generation; column-and-row generation; row-and-column generation; pricing subproblem; multi-stage cutting stock; quadratic set covering; column-dependent-rows.
Subjects: T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
Q Science > QA Mathematics
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Manufacturing Systems Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Kerem Bülbül
Date Deposited: 10 Aug 2010 11:57
Last Modified: 26 Apr 2022 10:48

Actions (login required)

View Item
View Item