EUVIMEDEUVIMED entdecken
Crossref

Column Elimination: An Iterative Approach to Solving Arc-Flow Formulations

Anthony Karahalios, Willem-Jan Van Hoeve

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →