Layered graph approaches for combinatorial optimization problems

Luis Gouveia; M. Leitner; Mario Ruthmair

doi:10.1016/j.cor.2018.09.007

Layered graph approaches for combinatorial optimization problems

Luis Gouveia, M. Leitner, Mario Ruthmair

Operations Analytics

Research output: Contribution to Journal › Article › Academic › peer-review

331 Downloads (Pure)

Abstract

Extending the concept of time-space networks, layered graphs associate information about one or multiple resource state values with nodes and arcs. While integer programming formulations based on them allow to model complex problems comparably easy, their large size makes them hard to solve for non-trivial instances. We detail and classify layered graph modeling techniques that have been used in the (recent) scientific literature and review methods to successfully solve the resulting large-scale, extended formulations. Modeling guidelines and important observations concerning the solution of layered graph formulations by decomposition methods are given together with several future research directions.

Original language	English
Pages (from-to)	22-38
Number of pages	17
Journal	Computers and Operations Research
Volume	102
Early online date	21 Sept 2018
DOIs	https://doi.org/10.1016/j.cor.2018.09.007
Publication status	Published - Feb 2019

Funding

This work is supported by National Funding from FCT - Fundação para a Ciência e a Tecnologia, under the project UID/MAT/04561/2013 and by the Vienna Science and Technology Fund (WWTF) through project ICT15-014 .

Funders	Funder number
Vienna Science and Technology Fund	ICT15-014
Instituto Nacional de Ciência e Tecnologia para Excitotoxicidade e Neuroproteção	UID/MAT/04561/2013
Fundació Catalana de Trasplantament

Keywords

Decomposition Methods
Extended Formulations
Integer Programming
Layered Graphs
Reformulation Techniques

Access to Document

10.1016/j.cor.2018.09.007

Layered graph approaches for combinatorial optimization problemsFinal published version, 1.04 MBLicence: Article 25fa Dutch Copyright Act

Persistent URL (handle)

Persistent link

Cite this

@article{73c25c11f996429dba470ce59908a0b7,

title = "Layered graph approaches for combinatorial optimization problems",

abstract = "Extending the concept of time-space networks, layered graphs associate information about one or multiple resource state values with nodes and arcs. While integer programming formulations based on them allow to model complex problems comparably easy, their large size makes them hard to solve for non-trivial instances. We detail and classify layered graph modeling techniques that have been used in the (recent) scientific literature and review methods to successfully solve the resulting large-scale, extended formulations. Modeling guidelines and important observations concerning the solution of layered graph formulations by decomposition methods are given together with several future research directions.",

keywords = "Decomposition Methods, Extended Formulations, Integer Programming, Layered Graphs, Reformulation Techniques",

author = "Luis Gouveia and M. Leitner and Mario Ruthmair",

year = "2019",

month = feb,

doi = "10.1016/j.cor.2018.09.007",

language = "English",

volume = "102",

pages = "22--38",

journal = "Computers and Operations Research",

issn = "0305-0548",

publisher = "Elsevier Ltd",

}

TY - JOUR

T1 - Layered graph approaches for combinatorial optimization problems

AU - Gouveia, Luis

AU - Leitner, M.

AU - Ruthmair, Mario

PY - 2019/2

Y1 - 2019/2

N2 - Extending the concept of time-space networks, layered graphs associate information about one or multiple resource state values with nodes and arcs. While integer programming formulations based on them allow to model complex problems comparably easy, their large size makes them hard to solve for non-trivial instances. We detail and classify layered graph modeling techniques that have been used in the (recent) scientific literature and review methods to successfully solve the resulting large-scale, extended formulations. Modeling guidelines and important observations concerning the solution of layered graph formulations by decomposition methods are given together with several future research directions.

AB - Extending the concept of time-space networks, layered graphs associate information about one or multiple resource state values with nodes and arcs. While integer programming formulations based on them allow to model complex problems comparably easy, their large size makes them hard to solve for non-trivial instances. We detail and classify layered graph modeling techniques that have been used in the (recent) scientific literature and review methods to successfully solve the resulting large-scale, extended formulations. Modeling guidelines and important observations concerning the solution of layered graph formulations by decomposition methods are given together with several future research directions.

KW - Decomposition Methods

KW - Extended Formulations

KW - Integer Programming

KW - Layered Graphs

KW - Reformulation Techniques

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

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

U2 - 10.1016/j.cor.2018.09.007

DO - 10.1016/j.cor.2018.09.007

M3 - Article

SN - 0305-0548

VL - 102

SP - 22

EP - 38

JO - Computers and Operations Research

JF - Computers and Operations Research

ER -

Layered graph approaches for combinatorial optimization problems

Abstract

Funding

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this