Skip Navigation
Oklahoma State University

Austin Buchanan receives NSF funding

IEM Professor Austin Buchanan has received NSF funding for his project entitled, “Imposing Connectivity Constraints in Large-Scale Network Problems”

The design and analysis of networks constitute one of the most important classes of problems in the field of optimization. In practice, network models are used to address such diverse applications as wireless communication, energy distribution, and conservation planning. A network consists essentially of a set of “nodes,” linked in some fashion by “arcs.” Connectedness is often a critical feature of a functioning network. However, enforcing connectivity in optimization models remains a significant computational challenge. 


Dr. Buchanan’s NSF-funded project aims to develop fundamental theoretical and algorithmic advances for effectively imposing these constraints in mixed integer programs (MIPs) in which the key decisions are at the vertex (i.e., node) level. Problems of this type arise when:
• designing aisle space in a high density warehouse;
• choosing contiguous pieces of land for a wildlife preservation;
• selecting contiguous census tracts to form a political district;
• searching for cohesive clusters in social and biological networks;
• intentionally splitting a power grid into self-sufficient subnetworks during a disaster to avoid large-scale blackouts.


Results from the research are expected to allow for the solution of large-scale instances of these problems (with thousands of nodes) to optimality in a reasonable amount of time. The developments may also help to solve related problems that have distance or survivability constraints.

More information can be found in the NSF Award Abstract or at Dr. Buchanan’s webpage.