Publications

Column Elimination: An Iterative Approach to Solving Integer Programs

Published in Submitted to Operations Research, 2024

We present column elimination as a general framework for solving (large-scale) integer programming problems. Our experimental evaluation shows that column elimination can be competitive with or outperform state-ofthe-art methods on various problem domains. Specifically, we find that column elimination closes five open instances of the graph multicoloring problem, one open instance with 1,000 locations of the vehicle routing problem with time windows, and six open instances of the pickup-and-delivery problem with time windows.

Recommended citation: A. Karahalios, and W.-J. van Hoeve. "Column Elimination: An Iterative Approach to Solving Integer Programs " Optimization Online. https://optimization-online.org/wp-content/uploads/2024/10/column_elimination.pdf

A Quantum Inspired Bi-level Optimization Algorithm for the First Responder Network Design Problem

Published in Accepted to IJOC, 2024

We introduce the First Responder Network Design Problem (FRNDP) and solve it using a novel hybrid quantum-classical heuristic building on the Graver Augmented Multiseed Algorithm (GAMA).

Recommended citation: Karahalios, Anthony, et al. "A Quantum Inspired Bi-level Optimization Algorithm for the First Responder Network Design Problem." arXiv preprint arXiv:2401.12463 (2024). https://arxiv.org/abs/2401.12463

Column Elimination for Capacitated Vehicle Routing Problems

Published in CPAIOR 2023, 2023

We solve an LP over iteratively improving state-space relaxations to exactly solve the CVRP. Through experimental results, we show our method is competitive with state-of-the-art BCP methods.

Recommended citation: A. Karahalios, and W.-J. van Hoeve. "Column Elimination for Capacitated Vehicle Routing Problems" CPAIOR 2023. https://sites.google.com/view/cpaior2023/home?authuser=0

From Cliques to Colorings and Back Again

Published in Constraint Programming 2022, 2022

We present an exact algorithm for graph coloring and maximum clique problems based on SAT technology.

Recommended citation: Heule, Marijn JH, Anthony Karahalios, and Willem-Jan van Hoeve (2022). "From Cliques to Colorings and Back Again." Constraints 2022. https://drops.dagstuhl.de/opus/volltexte/2022/16655/pdf/LIPIcs-CP-2022-26.pdf

Variable Ordering for Decision Diagrams: A Portfolio Approach

Published in Constraints 2022, 2022

We compare the performance of different portfolios of variable orderings on an algorithm that uses decision diagrams to compute lower bounds on the chromatic number of a graph.

Recommended citation: Karahalios and van-Hoeve (2022). "Variable Ordering for Decision Diagrams." Constraints 2022. https://link.springer.com/article/10.1007/s10601-021-09325-6