With every flipped light switch, plane takeoff, package delivery and even medical procedure embedded in 21st-century life, there’s a series of decisions that have been optimized to make these actions work the most efficiently.
A thriving community is constantly finding the best way to run these systems in order to reduce costs for companies and customers, get the most out of resources, improve medical treatments and to achieve a multitude of desired outcomes.
This week, top minds in the discrete optimization field convene at the annual Mixed Integer Programming Workshop, co-hosted by WID and the UW–Madison campus July 22-25. National and international members of both industry and academia are probing the mathematical and computational challenges behind today’s optimization problems.
Jim Luedtke and Jeff Linderoth, WID researchers who serve on the workshop’s planning committee, say the setup of the grassroots meeting sets it apart from other events in the field. Meeting participants have frequent breaks between talks for discussion and collaboration. Even the workshop’s two-hour lunch break testifies to a dedication to synergistic time for attendees to digest food and ideas. Travel fellowships and a poster session are designed to provide mingling time for young researchers new to the field.
“There are occasional one-time events that are done that have this type of a flavor,” says Luedtke, a Discovery Fellow in WID’s Optimization research group and an Assistant Professor in Industrial and Systems Engineering. “But the idea that this has become an annual event is unique.”
The workshop, which rotates to a different city every year, also remains one of the few gatherings not organized by a major professional or academic society.
“The number of possible solutions in this case is roughly equal to the number of subatomic particles in the universe. The algorithms are powerful enough to find the very best one. It’s just amazing.”
— Jeff Linderoth
Despite the location, topics covered at the workshop affect systems around the world. Mixed integer programming tackles problems with decisions that can be represented with whole number (integer) variables, which are common in virtually every industry.
Luedtke uses the package delivery company UPS as an example.
“Say a company like UPS has routing problems, where it’s trying to find the best route to deliver a set of packages and return back to its depot,” he says. “The company has discrete decisions that are essentially the locations trucks go to, and then you have to complete the loop. The route can be mapped by a series of ‘yes/no’ decisions, which collectively, can be represented as a math problem to solve.”
Researchers take on these math problems and develop algorithms (methods to solve them) that make the most efficient decisions based on the constraints of a given system.
Mixed-integer programming also helps build better infrastructures for water networks, power grids, traffic flows and health care systems. Linderoth points out that the outcome depends on what a given party wants optimized. For example, the same methods can be used to maximize the safety of passengers in scheduling aircraft takeoffs and landings, to maximize the revenue of the airlines by assigning the right-sized aircraft to flight legs, or to minimize the passenger delays when disruptions in the flight schedule occur.
At the workshop, Linderoth and Luedtke say there will be a mix of people: some pushing the limits of what’s mathematically possible, some focused on computational methods, and some dedicating their time to specific applications.
Without mixed integer programming research, it would take an overwhelming amount of time to find the optimal way to do things, says Linderoth, also a Discovery Fellow in WID’s Optimization group and a Professor of Industrial and Systems Engineering.
“I like to give this example when I’m teaching in class. Imagine you were to enumerate all the possibilities of a problem and try the best one,” he says. “And you reach about 250 ‘yes’/‘no’ decisions. The number of possible solutions in this case is roughly equal to the number of subatomic particles in the universe. Even with trillions of supercomputers evaluating possibilities, it would take more than the lifetime of the universe to complete the calculation.”
He says optimization methods are so adept that people routinely solve problems with tens of thousands of these “yes”/“no” decision variables.
“The algorithms are powerful enough to find the very best one,” Linderoth says. “It’s just amazing.”
— Marianne English
You must be logged in to post a comment.