ABAustin Buchanan

Austin Buchanan

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Austin Buchanan has a total of 27 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • The Dantzig–Fulkerson–Johnson TSP Formulation Is Easy to Solve for Few Subtour Constraints

    by Eleonora Vercesi, Austin Buchanan

    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 .

  • Partitioning a Graph into Low-Diameter Clusters

    by Jack Zhang, Lucas Silveira, Hamidreza Validi, Logan Smith, Austin Buchanan, Illya V. Hicks

    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/ .

  • Code and Data Repository for Partitioning a graph into low-diameter clusters

    by Jack Zhang, Lucas Silveira, Hamidreza Validi, Logan Smith, Austin Buchanan, Illya V. Hicks

    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.


  • Political Districting to Optimize the Polsby-Popper Compactness Score with Application to Voting Rights

    by Pietro Belotti, Austin Buchanan, Soraya Ezazipour

    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.


  • Political Districting to Minimize County Splits

    by Maral Shahmizad, Austin Buchanan

    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.


  • Linear-size formulations for connected planar graph partitioning and political districting

    by Jack Zhang, Hamidreza Validi, Austin Buchanan, Illya V. Hicks


  • On Fault-Tolerant Low-Diameter Clusters in Graphs

    by Yajun Lu, Hosseinali Salemi, Balabhaskar Balasundaram, Austin Buchanan

    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 .


  • Solving the Distance-Based Critical Node Problem

    by Hosseinali Salemi, Austin Buchanan

    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.