Page Not Found
Page not found. Your pixels are in another canvas.
Sitemap
A list of all the posts and pages found on the site. For you robots out there is an XML version available for digesting as well.
Pages
Everything can be optimized
Everything can be optimized
Page not in menu
This is a page not in th emain menu
Posts
Future Blog Post
Published:
This post will show up by default. To disable scheduling of future posts, edit config.yml and set future: false.
Blog Post number 4
Published:
This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.
Blog Post number 3
Published:
This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.
Blog Post number 2
Published:
This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.
Blog Post number 1
Published:
This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.
portfolio
Portfolio item number 1
Short description of portfolio item number 1
Portfolio item number 2
Short description of portfolio item number 2
publications
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
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
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
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
Variable Ordering for Decision Diagrams: A Portfolio Approach
Published:
Studying the use of portfolios of variable orderings on the performance of a decision diagram based algorithm for finding graph coloring lower bounds
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.
From Cliques to Colorings and Back Again
Published:
We present an exact algorithm for graph coloring and maximum clique problems based on SAT technology.
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.