Optimization Online


Layered graph approaches for combinatorial optimization problems

Luis Gouveia (legouveia***at***fc.ul.pt)
Markus Leitner (markus.leitner***at***univie.ac.at)
Mario Ruthmair (mario.ruthmair***at***univie.ac.at)

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: Layered graphs, integer programming, extended formulations, reformulation techniques, decomposition methods

Category 1: Applications -- OR and Management Sciences

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Computers & Operations Research 102, pages 22-38, 2019 doi: 10.1016/j.cor.2018.09.007

Download: [PDF]

Entry Submitted: 04/09/2018
Entry Accepted: 04/09/2018
Entry Last Modified: 11/18/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society