Valid inequalities for the single arc design problem with set-ups

Agostinho Agra, Mahdi Doostmohammadi, Quentin Louveaux

Research output: Contribution to journalArticle

Abstract

We consider a mixed integer set which generalizes two well-known sets: the single node fixed-charge network set and the single arc design set. Such set arises as a relaxation of feasible sets of general mixed integer problems such as lot-sizing and network design problems. We derive several families of valid inequalities that, in particular, generalize the arc residual capacity inequalities and the flow cover inequalities. For the constant capacitated case we provide an extended compact formulation and give a partial description of the convex hull in the original space which is exact under a certain condition. By lifting some basic inequalities we provide some insight on the difficulty of obtaining such a full polyhedral description for the constant capacitated case. Preliminary computational results are presented.

LanguageEnglish
Pages17-35
Number of pages19
JournalDiscrete Optimization
Volume16
DOIs
Publication statusPublished - 31 May 2015

Fingerprint

Valid Inequalities
Arc of a curve
Generalise
Integer
Lot Sizing
Network Design
Convex Hull
Design
Computational Results
Charge
Cover
Partial
Formulation
Vertex of a graph

Keywords

  • facet-defining inequalities
  • mixed integer programming
  • valid inequalities

Cite this

@article{13f119f4356f420997ac5e9a185be577,
title = "Valid inequalities for the single arc design problem with set-ups",
abstract = "We consider a mixed integer set which generalizes two well-known sets: the single node fixed-charge network set and the single arc design set. Such set arises as a relaxation of feasible sets of general mixed integer problems such as lot-sizing and network design problems. We derive several families of valid inequalities that, in particular, generalize the arc residual capacity inequalities and the flow cover inequalities. For the constant capacitated case we provide an extended compact formulation and give a partial description of the convex hull in the original space which is exact under a certain condition. By lifting some basic inequalities we provide some insight on the difficulty of obtaining such a full polyhedral description for the constant capacitated case. Preliminary computational results are presented.",
keywords = "facet-defining inequalities, mixed integer programming, valid inequalities",
author = "Agostinho Agra and Mahdi Doostmohammadi and Quentin Louveaux",
year = "2015",
month = "5",
day = "31",
doi = "10.1016/j.disopt.2014.12.002",
language = "English",
volume = "16",
pages = "17--35",
journal = "Discrete Optimization",
issn = "1572-5286",

}

Valid inequalities for the single arc design problem with set-ups. / Agra, Agostinho; Doostmohammadi, Mahdi; Louveaux, Quentin.

In: Discrete Optimization, Vol. 16, 31.05.2015, p. 17-35.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Valid inequalities for the single arc design problem with set-ups

AU - Agra, Agostinho

AU - Doostmohammadi, Mahdi

AU - Louveaux, Quentin

PY - 2015/5/31

Y1 - 2015/5/31

N2 - We consider a mixed integer set which generalizes two well-known sets: the single node fixed-charge network set and the single arc design set. Such set arises as a relaxation of feasible sets of general mixed integer problems such as lot-sizing and network design problems. We derive several families of valid inequalities that, in particular, generalize the arc residual capacity inequalities and the flow cover inequalities. For the constant capacitated case we provide an extended compact formulation and give a partial description of the convex hull in the original space which is exact under a certain condition. By lifting some basic inequalities we provide some insight on the difficulty of obtaining such a full polyhedral description for the constant capacitated case. Preliminary computational results are presented.

AB - We consider a mixed integer set which generalizes two well-known sets: the single node fixed-charge network set and the single arc design set. Such set arises as a relaxation of feasible sets of general mixed integer problems such as lot-sizing and network design problems. We derive several families of valid inequalities that, in particular, generalize the arc residual capacity inequalities and the flow cover inequalities. For the constant capacitated case we provide an extended compact formulation and give a partial description of the convex hull in the original space which is exact under a certain condition. By lifting some basic inequalities we provide some insight on the difficulty of obtaining such a full polyhedral description for the constant capacitated case. Preliminary computational results are presented.

KW - facet-defining inequalities

KW - mixed integer programming

KW - valid inequalities

UR - http://www.scopus.com/inward/record.url?scp=84921721226&partnerID=8YFLogxK

UR - https://www.sciencedirect.com/journal/discrete-optimization

U2 - 10.1016/j.disopt.2014.12.002

DO - 10.1016/j.disopt.2014.12.002

M3 - Article

VL - 16

SP - 17

EP - 35

JO - Discrete Optimization

T2 - Discrete Optimization

JF - Discrete Optimization

SN - 1572-5286

ER -