Skip to Main content Skip to Navigation
Conference papers

Mixed Integer Linear Programming Approach for a Distance-Constrained Elementary Path Problem

Abstract : Given a directed graph G = (V, E, l) with weights l e ≥ 0 associated with arcs e ∈ E and a set of vertex pairs with distances between them (called distance constraints), the problem is to find an elementary path in G that satisfies a maximum number of distance constraints. We describe two MIP formulations for this problem and discuss their advantages.
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/hal-01937008
Contributor : Rumen Andonov <>
Submitted on : Tuesday, November 27, 2018 - 7:13:36 PM
Last modification on : Friday, April 10, 2020 - 11:36:02 AM

File

DCEP_CTW.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01937008, version 1

Citation

Sébastien Francois, Rumen Andonov, Hristo Djidjev, Metodi Traikov, Nicola Yanev. Mixed Integer Linear Programming Approach for a Distance-Constrained Elementary Path Problem. CTW 2018 - 16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Jun 2018, Paris, France. pp.1-4. ⟨hal-01937008⟩

Share

Metrics

Record views

110

Files downloads

236