Benders Decomposition and Column-and-Row Generation for Solving Large-Scale Linear Programs with Column-Dependent-Rows

Ibrahim Muter, Ş İlker Birbil , Kerem Bülbül

Research output: Contribution to journalArticle

  • 1 Citations

Abstract

In a recent work, Muter, Birbil, and Bülbül (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.
LanguageEnglish
Pages29-45
JournalEuropean Journal of Operational Research
Volume264
Issue number1
Early online date21 Jun 2017
DOIs
StatusPublished - 1 Jan 2018

Fingerprint

Benders Decomposition
Linear Program
Decomposition
Fallout
Dependent
Linking
Linear programming
Costs
Experiments
Problem Decomposition
Mutually exclusive
Column Generation
Routing Problem
Large-scale Problems
Decomposable
Linear program
Benders decomposition
Decomposition Method
Polyhedron
Pricing

Cite this

Benders Decomposition and Column-and-Row Generation for Solving Large-Scale Linear Programs with Column-Dependent-Rows. / Muter, Ibrahim; İlker Birbil , Ş; Bülbül , Kerem.

In: European Journal of Operational Research, Vol. 264, No. 1, 01.01.2018, p. 29-45.

Research output: Contribution to journalArticle

@article{a3013b0564e745cab032cd0848ed0613,
title = "Benders Decomposition and Column-and-Row Generation for Solving Large-Scale Linear Programs with Column-Dependent-Rows",
abstract = "In a recent work, Muter, Birbil, and B{\"u}lb{\"u}l (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.",
author = "Ibrahim Muter and {İlker Birbil}, Ş and Kerem B{\"u}lb{\"u}l",
year = "2018",
month = "1",
day = "1",
doi = "10.1016/j.ejor.2017.06.044",
language = "English",
volume = "264",
pages = "29--45",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "1",

}

TY - JOUR

T1 - Benders Decomposition and Column-and-Row Generation for Solving Large-Scale Linear Programs with Column-Dependent-Rows

AU - Muter, Ibrahim

AU - İlker Birbil , Ş

AU - Bülbül , Kerem

PY - 2018/1/1

Y1 - 2018/1/1

N2 - In a recent work, Muter, Birbil, and Bülbül (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.

AB - In a recent work, Muter, Birbil, and Bülbül (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.

UR - https://doi.org/10.1016/j.ejor.2017.06.044

U2 - 10.1016/j.ejor.2017.06.044

DO - 10.1016/j.ejor.2017.06.044

M3 - Article

VL - 264

SP - 29

EP - 45

JO - European Journal of Operational Research

T2 - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 1

ER -