Austin Buchanan
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Austin Buchanan has a total of 27 co-authors. Here are the top co-authors by number of shared publications:
- Hamidreza Validi
Department of Industrial, Manufacturing & Systems Engineering, Texas Tech University, Lubbock, Texas 79409
6 shared publications - Illya V. Hicks
Department of Computational Applied Mathematics and Operations Research, Rice University, Houston, Texas 77005
3 shared publications - Balabhaskar Balasundaram
Oklahoma State University
2 shared publications - Hosseinali Salemi
Department of Industrial and Manufacturing Systems Engineering, Iowa State University, Ames, Iowa 50011
2 shared publications Jack Zhang
Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
2 shared publications- Jose L. Walteros
Department of Industrial and Systems Engineering, University at Buffalo, The State University of New York, Buffalo, USA
2 shared publications
Latest Publications
- 30 September 2026
- Published by Springer Nature in Mathematical Programming Computation
- p. 1-34
Political districting to maximize whole counties
- 30 September 2026
- Published by Springer Nature in Mathematical Programming Computation
- p. 1-34
Political districting to maximize whole counties
- 25 September 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Optimization
The Dantzig–Fulkerson–Johnson TSP Formulation Is Easy to Solve for Few Subtour Constraints
The most successful approaches for the traveling salesman problem (TSP) use the integer programming model proposed in 1954 by Dantzig, Fulkerson, and Johnson (DFJ). Although this model has exponentially many subtour elimination constraints (SECs), it has been observed that relatively few of them are needed to prove optimality in practice. This leads us to wonder, what is the complexity of the DFJ model when just a small number of SECs are imposed? Also, for a given instance, what is the minimum number of SECs required to certify the optimality of one of its TSP tours? We offer both positive and negative results. On the positive side, we give an algorithm to solve the DFJ model that runs in polynomial time when only a constant number of SECs are imposed. With an additional condition, we also find a minimum number of SECs in polynomial time. This provides an explanation for the apparent easiness of some TSP instances despite the intractability of the problem in the worst case. As part of our experiments, we show that the original 49-city TSP instance of DFJ requires a minimum of four SECs, which we generate in a fraction of a second with a simple Python implementation. Funding: The research of E. Vercesi was supported by the Swiss National Science Foundation [Grant 200021_212929/1] “Computational methods for integrality gaps analysis.” The research of A. Buchanan is based on work supported by the National Science Foundation [Grant 1942065] and the Air Force Office of Scientific Research [Grant FA9550-25-1-0277]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoo.2025.0078 .
- 25 September 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Optimization
The Dantzig–Fulkerson–Johnson TSP Formulation Is Easy to Solve for Few Subtour Constraints
The most successful approaches for the traveling salesman problem (TSP) use the integer programming model proposed in 1954 by Dantzig, Fulkerson, and Johnson (DFJ). Although this model has exponentially many subtour elimination constraints (SECs), it has been observed that relatively few of them are needed to prove optimality in practice. This leads us to wonder, what is the complexity of the DFJ model when just a small number of SECs are imposed? Also, for a given instance, what is the minimum number of SECs required to certify the optimality of one of its TSP tours? We offer both positive and negative results. On the positive side, we give an algorithm to solve the DFJ model that runs in polynomial time when only a constant number of SECs are imposed. With an additional condition, we also find a minimum number of SECs in polynomial time. This provides an explanation for the apparent easiness of some TSP instances despite the intractability of the problem in the worst case. As part of our experiments, we show that the original 49-city TSP instance of DFJ requires a minimum of four SECs, which we generate in a fraction of a second with a simple Python implementation. Funding: The research of E. Vercesi was supported by the Swiss National Science Foundation [Grant 200021_212929/1] “Computational methods for integrality gaps analysis.” The research of A. Buchanan is based on work supported by the National Science Foundation [Grant 1942065] and the Air Force Office of Scientific Research [Grant FA9550-25-1-0277]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoo.2025.0078 .
- 12 June 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
Partitioning a Graph into Low-Diameter Clusters
This paper studies the problems of partitioning the vertices of a graph [ ] into (or covering with) a minimum number of low-diameter clusters from the lenses of approximation algorithms and integer programming. Here, the low-diameter criterion is formalized by an s-club, which is a subset of vertices whose induced subgraph has diameter at most s. For these problems, we give [ ]-approximation algorithms for any even integer s, generalizing a previous algorithm for the case [ ]. (The [ ] notation suppresses logarithmic factors and [ ].) Complementing this, we show that for any [ ] the problem is NP-hard to approximate within [ ] and [ ], for each fixed even and odd integer s, respectively, suggesting a contrast in approximability for even and odd values of s. Second, we develop new MIP-based heuristics (inspired by the approximation algorithms) that perform well in practice, solving more than half of previous benchmark instances in less than one second. To handle the remaining instances, we propose a MIP formulation with an exponentially large class of cut-like inequalities that we solve with a branch-and-cut algorithm. With it, we tackle more benchmark instances than previous approaches and in less time. History: Accepted by Alice E. Smith, Russel Bent / Network Optimization: Algorithms & Applications. Funding: This work was supported by the National Science Foundation [Grants 1942065 and 2318790]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1448 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2025.1448 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
- 12 June 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
Partitioning a Graph into Low-Diameter Clusters
This paper studies the problems of partitioning the vertices of a graph [ ] into (or covering with) a minimum number of low-diameter clusters from the lenses of approximation algorithms and integer programming. Here, the low-diameter criterion is formalized by an s-club, which is a subset of vertices whose induced subgraph has diameter at most s. For these problems, we give [ ]-approximation algorithms for any even integer s, generalizing a previous algorithm for the case [ ]. (The [ ] notation suppresses logarithmic factors and [ ].) Complementing this, we show that for any [ ] the problem is NP-hard to approximate within [ ] and [ ], for each fixed even and odd integer s, respectively, suggesting a contrast in approximability for even and odd values of s. Second, we develop new MIP-based heuristics (inspired by the approximation algorithms) that perform well in practice, solving more than half of previous benchmark instances in less than one second. To handle the remaining instances, we propose a MIP formulation with an exponentially large class of cut-like inequalities that we solve with a branch-and-cut algorithm. With it, we tackle more benchmark instances than previous approaches and in less time. History: Accepted by Alice E. Smith, Russel Bent / Network Optimization: Algorithms & Applications. Funding: This work was supported by the National Science Foundation [Grants 1942065 and 2318790]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1448 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2025.1448 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
- 29 May 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
Code and Data Repository for Partitioning a graph into low-diameter clusters
The software and data in this repository are a snapshot of the software and data that were used in the research reported on in the paper Partitioning a Graph into Low-Diameter Clusters by Jack Zhang, Lucas Silveira, Hamidreza Validi, Logan Smith, Austin Buchanan, and Illya V. Hicks.
- 29 May 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
Code and Data Repository for Partitioning a graph into low-diameter clusters
The software and data in this repository are a snapshot of the software and data that were used in the research reported on in the paper Partitioning a Graph into Low-Diameter Clusters by Jack Zhang, Lucas Silveira, Hamidreza Validi, Logan Smith, Austin Buchanan, and Illya V. Hicks.
- 1 September 2025
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 73 (5) , 2330-2350
Political Districting to Optimize the Polsby-Popper Compactness Score with Application to Voting Rights
When drawing political districts, important criteria include district compactness and the ability of minority groups to convert votes into seats. In litigation, compactness is usually measured via the Polsby-Popper score; however, this score has largely been absent from the operations research literature, presumably because of its nonlinear nature. In “Political Districting to Optimize the Polsby-Popper Compactness Score with Application to Voting Rights,” Belotti, Buchanan, and Ezazipour propose new mixed-integer second-order cone programs (MISOCPs) to optimize this score, enabling them to find optimally compact districts built from voting precincts. The methods are extended to find compact plans with many majority-minority districts. This is the task faced by plaintiffs in lawsuits brought under the Voting Rights Act of 1965 who must show that an alternative plan exists in which the minority group could achieve better representation. Computational experiments show that the MISCOP-based methods perform as well (or better) than state-of-the-art approaches for this task, scaling to instances with nearly 200,000 census blocks.
- 1 September 2025
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 73 (5) , 2330-2350
Political Districting to Optimize the Polsby-Popper Compactness Score with Application to Voting Rights
When drawing political districts, important criteria include district compactness and the ability of minority groups to convert votes into seats. In litigation, compactness is usually measured via the Polsby-Popper score; however, this score has largely been absent from the operations research literature, presumably because of its nonlinear nature. In “Political Districting to Optimize the Polsby-Popper Compactness Score with Application to Voting Rights,” Belotti, Buchanan, and Ezazipour propose new mixed-integer second-order cone programs (MISOCPs) to optimize this score, enabling them to find optimally compact districts built from voting precincts. The methods are extended to find compact plans with many majority-minority districts. This is the task faced by plaintiffs in lawsuits brought under the Voting Rights Act of 1965 who must show that an alternative plan exists in which the minority group could achieve better representation. Computational experiments show that the MISCOP-based methods perform as well (or better) than state-of-the-art approaches for this task, scaling to instances with nearly 200,000 census blocks.
- 1 March 2025
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 73 (2) , 752-774
Political Districting to Minimize County Splits
Political Districting to Minimize County Splits When dividing a state into districts for elections, one traditional criterion is that political subdivisions like counties and cities should not be divided unnecessarily. Some states go as far as to say that the number of county splits should be minimized, but previously there was no scalable exact method for determining this. With new integer programming techniques, Shahmizad and Buchanan exactly compute this minimum number for all states and district types (congressional, state senate, state house) across the USA.
- 1 March 2025
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 73 (2) , 752-774
Political Districting to Minimize County Splits
Political Districting to Minimize County Splits When dividing a state into districts for elections, one traditional criterion is that political subdivisions like counties and cities should not be divided unnecessarily. Some states go as far as to say that the number of county splits should be minimized, but previously there was no scalable exact method for determining this. With new integer programming techniques, Shahmizad and Buchanan exactly compute this minimum number for all states and district types (congressional, state senate, state house) across the USA.
- 5 October 2023
- Published by Springer Nature in Optimization Letters
- Vol. 18 (1) , 19-31
Linear-size formulations for connected planar graph partitioning and political districting
- 5 October 2023
- Published by Springer Nature in Optimization Letters
- Vol. 18 (1) , 19-31
Linear-size formulations for connected planar graph partitioning and political districting
- 1 November 2022
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 34 (6) , 3181-3199
On Fault-Tolerant Low-Diameter Clusters in Graphs
Cliques and their generalizations are frequently used to model “tightly knit” clusters in graphs and identifying such clusters is a popular technique used in graph-based data mining. One such model is the s-club, which is a vertex subset that induces a subgraph of diameter at most s. This model has found use in a variety of fields because low-diameter clusters have practical significance in many applications. As this property is not hereditary on vertex-induced subgraphs, the diameter of a subgraph could increase upon the removal of some vertices and the subgraph could even become disconnected. For example, star graphs have diameter two but can be disconnected by removing the central vertex. The pursuit of a fault-tolerant extension of the s-club model has spawned two variants that we study in this article: robust s-clubs and hereditary s-clubs. We analyze the complexity of the verification and optimization problems associated with these variants. Then, we propose cut-like integer programming formulations for both variants whenever possible and investigate the separation complexity of the cut-like constraints. We demonstrate through our extensive computational experiments that the algorithmic ideas we introduce enable us to solve the problems to optimality on benchmark instances with several thousand vertices. This work lays the foundations for effective mathematical programming approaches for finding fault-tolerant s-clubs in large-scale networks. History: Accepted by David Alderson, Area Editor for Network Optimization: Algorithms & Applications. Funding: The computing for this project was performed at the High Performance Computing Center at Oklahoma State University supported in part through the National Science Foundation [Grant OAC-1531128]. This material is based upon work supported by the National Science Foundation under [Grants 1662757 and 1942065]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.1231 .
- 1 November 2022
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 34 (6) , 3181-3199
On Fault-Tolerant Low-Diameter Clusters in Graphs
Cliques and their generalizations are frequently used to model “tightly knit” clusters in graphs and identifying such clusters is a popular technique used in graph-based data mining. One such model is the s-club, which is a vertex subset that induces a subgraph of diameter at most s. This model has found use in a variety of fields because low-diameter clusters have practical significance in many applications. As this property is not hereditary on vertex-induced subgraphs, the diameter of a subgraph could increase upon the removal of some vertices and the subgraph could even become disconnected. For example, star graphs have diameter two but can be disconnected by removing the central vertex. The pursuit of a fault-tolerant extension of the s-club model has spawned two variants that we study in this article: robust s-clubs and hereditary s-clubs. We analyze the complexity of the verification and optimization problems associated with these variants. Then, we propose cut-like integer programming formulations for both variants whenever possible and investigate the separation complexity of the cut-like constraints. We demonstrate through our extensive computational experiments that the algorithmic ideas we introduce enable us to solve the problems to optimality on benchmark instances with several thousand vertices. This work lays the foundations for effective mathematical programming approaches for finding fault-tolerant s-clubs in large-scale networks. History: Accepted by David Alderson, Area Editor for Network Optimization: Algorithms & Applications. Funding: The computing for this project was performed at the High Performance Computing Center at Oklahoma State University supported in part through the National Science Foundation [Grant OAC-1531128]. This material is based upon work supported by the National Science Foundation under [Grants 1662757 and 1942065]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.1231 .
- 1 May 2022
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 34 (3) , 1309-1326
Solving the Distance-Based Critical Node Problem
In critical node problems, the task is to identify a small subset of so-called critical nodes whose deletion maximally degrades a network’s “connectivity” (however that is measured). Problems of this type have been widely studied, for example, for limiting the spread of infectious diseases. However, existing approaches for solving them have typically been limited to networks having fewer than 1,000 nodes. In this paper, we consider a variant of this problem in which the task is to delete b nodes so as to minimize the number of node pairs that remain connected by a path of length at most k. With the techniques developed in this paper, instances with up to 17,000 nodes can be solved exactly. We introduce two integer programming formulations for this problem (thin and path-like) and compare them with an existing recursive formulation. Although the thin formulation generally has an exponential number of constraints, it admits an efficient separation routine. Also helpful is a new, more general preprocessing procedure that, on average, fixes three times as many variables than before. Summary of Contribution: In this paper, we consider a distance-based variant of the critical node problem in which the task is to delete b nodes so as to minimize the number of node pairs that remain connected by a path of length at most k. This problem is motivated by applications in social networks, telecommunications, and transportation networks. In our paper, we aim to solve large-scale instances of this problem. Standard out-of-the-box approaches are unable to solve such instances, requiring new integer programming models, methodological contributions, and other computational insights. For example, we propose an algorithm for finding a maximum independent set of simplicial nodes that runs in time O(nm) that we use in a preprocessing procedure; we also prove that the separation problem associated with one of our integer programming models is NP-hard. We apply our branch-and-cut implementation to real-life networks from a variety of domains and observe speedups over previous approaches.
- 1 May 2022
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 34 (3) , 1309-1326
Solving the Distance-Based Critical Node Problem
In critical node problems, the task is to identify a small subset of so-called critical nodes whose deletion maximally degrades a network’s “connectivity” (however that is measured). Problems of this type have been widely studied, for example, for limiting the spread of infectious diseases. However, existing approaches for solving them have typically been limited to networks having fewer than 1,000 nodes. In this paper, we consider a variant of this problem in which the task is to delete b nodes so as to minimize the number of node pairs that remain connected by a path of length at most k. With the techniques developed in this paper, instances with up to 17,000 nodes can be solved exactly. We introduce two integer programming formulations for this problem (thin and path-like) and compare them with an existing recursive formulation. Although the thin formulation generally has an exponential number of constraints, it admits an efficient separation routine. Also helpful is a new, more general preprocessing procedure that, on average, fixes three times as many variables than before. Summary of Contribution: In this paper, we consider a distance-based variant of the critical node problem in which the task is to delete b nodes so as to minimize the number of node pairs that remain connected by a path of length at most k. This problem is motivated by applications in social networks, telecommunications, and transportation networks. In our paper, we aim to solve large-scale instances of this problem. Standard out-of-the-box approaches are unable to solve such instances, requiring new integer programming models, methodological contributions, and other computational insights. For example, we propose an algorithm for finding a maximum independent set of simplicial nodes that runs in time O(nm) that we use in a preprocessing procedure; we also prove that the separation problem associated with one of our integer programming models is NP-hard. We apply our branch-and-cut implementation to real-life networks from a variety of domains and observe speedups over previous approaches.