Column Elimination: An Iterative Approach to Solving Arc-Flow Formulations
Operations Research · 20.11.2026
DOI: 10.1287/opre.2024.1404 ↗Kurz gefasst
Fachartikel in der Zeitschrift Operations Research, online erschienen am 20.11.2026. Verfasst von Anthony Karahalios und 1 weiteren Autor:innen.
Abstract (Originalsprache)
We present column elimination as a general framework for solving problems whose solutions can be represented as a collection of decision sequences. We show how such problems can be modeled as arc-flow formulations, using a dynamic program to represent the set of feasible decision sequences and their costs, and an integer linear program over the corresponding state-transition graph. Because the exact arc-flow formulation can be exponentially large, we introduce relaxed dynamic programs to compactly represent a superset of the feasible decision sequences. Column elimination solves the exact model by starting with a relaxed dynamic program, which induces a relaxed arc-flow formulation, and iteratively refining the relaxation by eliminating infeasible sequences in optimal solutions. Doing so, we generalize earlier approaches that were developed for decision-diagram based network models. We apply our general column elimination framework to three new applications: the vehicle routing problem with time windows, the pickup-and-delivery problem with time windows, and the graph multicoloring problem. The computational results show that column elimination is competitive with or outperforms state-of-the-art methods, closing several previously open benchmark instances across these domains, including one vehicle routing problem with time windows on 1,000 locations.
Zitieren
APA
Karahalios, A., & Hoeve, W. V. (2026). Column Elimination: An Iterative Approach to Solving Arc-Flow Formulations. Operations Research. https://doi.org/10.1287/opre.2024.1404
Vancouver
Karahalios A, Hoeve WV. Column Elimination: An Iterative Approach to Solving Arc-Flow Formulations. Operations Research. 2026. doi:10.1287/opre.2024.1404
BibTeX
@article{Karahalios2026,
author = {Karahalios, Anthony and Hoeve, Willem-Jan Van},
title = {Column Elimination: An Iterative Approach to Solving Arc-Flow Formulations},
journal = {Operations Research},
year = {2026},
doi = {10.1287/opre.2024.1404}
}
EUVIMED