IEM research focuses on balanced graph partitioning

Tuesday, October 21, 2025

Media Contact: Tanner Holubar | Communications Specialist | 405-744-2065 | tanner.holubar@okstate.edu

Researchers in the College of Engineering, Architecture and Technology are developing new mathematical methods to solve problems where large networks must be divided into equal parts.   

From dividing workloads on computers to splitting territories for military recruitment, these datasets present a challenge. The data commonly changes or can be uncertain, leading to inconsistent results if not planned for in advance.   

Dr. Austin Buchanan, an associate professor and the graduate program director in the School of Industrial Engineering and Management, is the lead investigator on a project titled “Balanced Graph Partitioning Under Uncertainty.” This is made possible through a $600,000 Department of Defense grant through the DoD’s Defense Established Program to Stimulate Competitive Research. Oklahoma State University researchers are working alongside researchers at the University of Wisconsin-Madison on this project.   

Balanced graph partitioning is about dividing large, complex systems into smaller, more balanced parts. Current methods use stable, predictable data. This research will incorporate real-world uncertainty to reach more equal outcomes.   

This three-year project will look to develop new mathematical models and algorithms to create tools that decision-makers can then use to make more balanced decisions between their competitive needs with fairness, cost and efficiency, even when data changes over time.  

“The project is all about dividing a network into connected parts, with one aim being that the parts should have roughly equal weight or to be ‘balanced,’” Buchanan said. “One motivating application is the design of military recruitment market territories, where we want recruiter workloads to be balanced and remain balanced over time. The research team has experts in mathematical optimization, operations research, integer programming and stochastic programming.”  

In the first year of the project, the OSU and UW teams will work together on developing the methodology for balanced graph partitioning. In the second year, the OSU team will expand the approach to include discrete resources, such as how military recruiters are assigned to specific territories, with the UW team focusing on modeling uncertainty.   

The third year will see both teams come together again to simultaneously handle discrete resources and uncertainty.   

One motivating application for the project is the design of recruiting territories. The DoD employs around 3.4 million people, including 1.3 million active-duty personnel and more than 760,000 reserve and guard members.   

“These personnel are recruited from all across the country, in part, via these geographically distributed recruiting offices,” Buchanan said. “For example, the U.S. Army Recruiting Command uses 7,000 recruiters spread across 1,300 stations to enlist 60,000 recruits each year; these stations are grouped into companies to better balance control responsibilities. Over time, as parts of the U.S. grow and shrink in population, enlistments in military recruitment market territories can be come imbalanced, prompting a re-balancing that can take weeks of sustained effort by rooms full of subject matter experts.”