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

Muter, İbrahim and Birbil, Ş. İlker and Bülbül, Kerem (2018) Benders decomposition and column-and-row generation for solving large-scale linear programs with column-dependent-rows. European Journal of Operational Research, 264 (1). pp. 29-45. ISSN 0377-2217 (Print) 1872-6860 (Online)

This is the latest version of this item.

[thumbnail of This is a RoMEO green journal -- author can archive pre-print (ie pre-refereeing)] PDF (This is a RoMEO green journal -- author can archive pre-print (ie pre-refereeing))
Benders.pdf

Download (469kB)

Abstract

In a recent work, Muter et al. (2013a) identified and characterized a general class of linear programming (LP) problems - known as problems with column-dependent-rows (CDR-problems). These LPs feature two sets of constraints with mutually exclusive groups of variables in addition to a set of structural linking constraints, in which variables from both groups appear together. In a typical CDR-problem, the number of linking constraints grows very quickly with the number of variables, which motivates generating both columns and their associated linking constraints simultaneously on-the-fly. In this paper, we expose the decomposable structure of CDR-problems via Benders decomposition. However, this approach brings on its own theoretical challenges. One group of variables is generated in the Benders master problem, while the generation of the linking constraints is relegated to the Benders subproblem along with the second group of variables. A fallout of this separation is that only a partial description of the dual of the Benders subproblem is available over the course of the algorithm. We demonstrate how the pricing subproblem for the column generation applied to the Benders master problem does also update the dual polyhedron and the existing Benders cuts in the master problem to ensure convergence. Ultimately, a novel integration of Benders cut generation and the simultaneous generation of columns and constraints yields a brand-new algorithm for solving large-scale CDR-problems. We illustrate the application of the proposed method on a time-constrained routing problem. Our numerical experiments confirm the outstanding performance of the new decomposition method.
Item Type: Article
Uncontrolled Keywords: large-scale optimization; linear programming; column-dependent-rows; column generation; column-and-row generation; Benders decomposition; pricing subproblem; quadratic set covering; time-constrained routing problem.
Subjects: T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering > T57.6-57.97 Operations research. Systems analysis
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Industrial Engineering
Faculty of Engineering and Natural Sciences
Depositing User: Kerem Bülbül
Date Deposited: 10 Sep 2017 13:45
Last Modified: 16 May 2023 14:43
URI: https://research.sabanciuniv.edu/id/eprint/33424

Available Versions of this Item

Actions (login required)

View Item
View Item