Page Not Found
Page not found. Your pixels are in another canvas.
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.
Page not found. Your pixels are in another canvas.
Everything can be optimized
This is a page not in th emain menu
Published:
This post will show up by default. To disable scheduling of future posts, edit config.yml
and set future: false
.
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.
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.
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.
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.
Short description of portfolio item number 1
Short description of portfolio item number 2
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
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
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
Published in Submitted but not yet published, 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
Published:
Studying the use of portfolios of variable orderings on the performance of a decision diagram based algorithm for finding graph coloring lower bounds
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.
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.
Published:
We present an exact algorithm for graph coloring and maximum clique problems based on SAT technology.
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.
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.
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.
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.
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 Assistant, Carnegie Mellon University, Tepper School of Business, 2021
TA for MBA Math Bootcamp focusing on Calculus and Probability.
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.
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.
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.
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.