title   
  

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

Muter, İbrahim and Birbil, Ş. İlker and Bülbül, Kerem (2013) Simultaneous column-and-row generation for large-scale linear programs with column-dependent-rows. Mathematical Programming, 142 (1-2). pp. 47-82. ISSN 0025-5610 (Print) 1436-4646 (Online)

This is the latest version of this item.

[img]
Preview
PDF (This is a RoMEO green journal -- author can archive pre-print (ie pre-refereeing)) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
477Kb

Official URL: http://dx.doi.org/10.1007/s10107-012-0561-8

Abstract

In this paper, we develop a simultaneous column-and-row generation algorithm that could be applied to 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 an efficient solution approach. 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. These assumptions are general enough and cover all problems with column-dependent-rows studied in the literature up until now to the best of our knowledge. 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. To illustrate the proposed approach, the paper is concluded by applying the proposed framework to the multi-stage cutting stock and the quadratic set covering problems.

Item Type:Article
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:Q Science > QA Mathematics
T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering > T57.6-57.97 Operations research. Systems analysis
ID Code:19357
Deposited By:Kerem Bülbül
Deposited On:16 Oct 2012 12:36
Last Modified:21 Jan 2014 14:28

Available Versions of this Item

Repository Staff Only: item control page