Layered graph approaches for combinatorial optimization problems. (February 2019)

• Record Type: Journal Article
• Authors: Gouveia, Luis; Leitner, Markus; Ruthmair, Mario
• Is Part Of: Computers & operations research. Volume 102(2019)
• Page Start: 22
• Page End: 38
• Publication Date: 2019-02
• Subjects: Layered graphs -- Integer programming -- Extended formulations -- Reformulation techniques -- Decomposition methods; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2018.09.007
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: Detailed explanation and classification of layered graph modeling techniques. Review of methods to solve the resulting large-scale, extended formulations. Provide modeling guidelines and observations concerning the solution of layered graph formulations. Suggestions for future research directions. 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.