Anthony Karahalios

Anthony Karahalios

OR / ACO PhD Candidate at Carnegie Mellon University

Posts by Collection

portfolio

publications

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: 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

talks

Graph Coloring With Decision Diagrams: An Analysis Of Variable Ordering

Published:

A decision diagram approach was recently introduced to generate lower bounds for the graph coloring problem. It uses compilation via iterative refinement, which requires a variable ordering to be specified in advance. Oftentimes no single variable ordering dominates all others for a set of problem instances. This work provides an analysis and experimental evaluation of different variable ordering strategies including using portfolios of variable orderings.

Graph Coloring using Decision Diagrams with Zykov Branching

Published:

A recent work by van Hoeve introduced a decision diagram based iterative refinement algorithm for finding multi-path solutions to optimization problems. We study the addition of branch and bound to this algorithm, including the well-known Zykov branching rule for graph coloring.

Comparing Column Elimination and Column Generation

Published:

A method called Column Elimination was recently introduced to generate both lower bounds and optimal solutions for the graph coloring problem. Based on dynamic programming and decision diagrams, this exact method begins with a relaxed state space and refines this space at each iteration. Our work provides methodological and computational comparisons between Column Elimination and Column Generation; it uses the Capacitated Vehicle Routing Problem (CVRP) as a case study.

Column Elimination for Capacitated Vehicle Routing Problems

Published:

We introduce a column elimination procedure for the capacitated vehicle routing problem. Our procedure maintains a decision diagram to represent a relaxation of the set of feasible routes, over which we define a constrained network flow. The optimal solution corresponds to a collection of paths in the decision diagram and yields a dual bound. The column elimination process iteratively removes infeasible paths from the diagram to strengthen the relaxation. The network flow model can be solved as a linear program with a conventional solver or via a Lagrangian relaxation. To solve the Lagrangian subproblem more efficiently, we implement a special successive shortest paths algorithm. We introduce several cutting planes to strengthen the dual bound, including a new type of clique cut that exploits the structure of the decision diagram. We experimentally compare the bounds from column elimination with those from column generation for capacitated vehicle routing problems.

Column Elimination for Large-Scale Integer Programming

Published:

Branch-and-cut-and-price is a state-of-the-art exact method for solving large- scale integer programming models, using column generation to solve linear programming relaxations of its subproblems. Column generation maintains a restricted set of variables and iteratively adds new variables by solving a pricing problem until an optimal basis is found. Recently, a new method has been developed that solves large- scale integer programming problems using branch-and-cut, that directly solves an arc flow formulation instead of solving pricing problems. This new method maintains a relaxed set of variables and iteratively removes infeasible variables until an optimal solution to the relaxation is feasible to the original problem. The method has been used for specific applications, but not yet generalized. In this poster, we generalize this method to solve discrete optimization problems under the name column elimination. We give methodological insights including computational efficiencies and show promising experimental results on applications including the vehicle routing problem with time windows for which column elimination has not yet been applied.

Column Elimination: Solving Discrete Optimization Problems Using Arc Flow Formulations

Published:

We propose an exact algorithm for solving a class of discrete optimization problems that can have their feasible regions represented by an arc flow formulation over the state-transition graph of a dynamic program. We give computational results for solving graph multicoloring problems and vehicle routing problems with time windows.

A New Perspective on Subset Row Inequalities via Column Elimination

Published:

We introduce subset-row inequalities into column elimination. These inequalities are notoriously challenging to implement in related branch-and-cut-and-price methods. We show how these inequalities can be implemented in column elimination in a weakened form that differs from the one used in branch-and-cut-and-price. We show computational results to demonstrate this difference.

teaching

Math Bootcamp Fall 2021 (MBA) (TA)

Teaching Assistant, Carnegie Mellon University, Tepper School of Business, 2021

TA for MBA Math Bootcamp focusing on Calculus and Probability.

45-751 Optimization Spring 2022 (MBA) (TA)

Teaching Assistant, Carnegie Mellon University, Tepper School of Business, 2022

TA for MBA Optimization course that covers fundamental optimization tools for quantitative analysis in the management sciences. The central topics of study are linear integer and nonlinear programming. Special emphasis is placed on linear programming particularly on modeling business applications and on sensitivity analysis. The course follows a practical spreadsheet-based approach to provide hands-on experience with software such as Excel Solver.

46-888 Optimization for Prescriptive Analytics Summer 2022 (MBA) (TA)

Teaching Assistant, Carnegie Mellon University, Tepper School of Business, 2022

TA for MBA Optimization course that focuses on developing such optimization models for operational and strategic decision making. We will consider applications such as resource allocation, network design, and capacity planning, in a variety of business areas including finance, operations, logistics, and marketing. We will primarily focus on deterministic optimization models (i.e., we don’t use probability models or stochastic processes), and use linear, integer, and nonlinear programming as optimization methodologies. We solve problems in these fields using CPLEX in Python.

70-460 Mathematical Models for Consulting Fall 2022 (Undergrad) (Instructor)

Instructor, Carnegie Mellon University, Tepper School of Business, 2022

Instructor for upper-level undergraduate optimization elective course. Fulfilled my teaching requirement for Tepper PhD students by teaching this class of 22 students. The course material includes column generation, integer programming, robust optimization, and a project where teams use these advanced modeling techniques to solve a real world problem. Models are implemented in both Excel and Python using Gurobi.

46-888 Optimization for Prescriptive Analytics Summer 2023 (MBA) (TA)

Teaching Assistant, Carnegie Mellon University, Tepper School of Business, 2023

TA for MBA Optimization course that focuses on developing such optimization models for operational and strategic decision making. We will consider applications such as resource allocation, network design, and capacity planning, in a variety of business areas including finance, operations, logistics, and marketing. We will primarily focus on deterministic optimization models (i.e., we don’t use probability models or stochastic processes), and use linear, integer, and nonlinear programming as optimization methodologies. We solve problems in these fields using CPLEX in Python.