• 2 min read
New solver tackles 10,000-variable optimization problems
Northeastern’s Cristian Cassella says his Analog Floquet Solver avoided common optimization traps, handling QUBO problems with up to 10,000 variables.
Image: TechXplore
Optimization problems often come down to a huge number of simple yes-or-no choices. In computing, that class of problem is known as quadratic unconstrained binary optimization, or QUBO—a framework used to search for the best combination of binary decisions while minimizing cost or energy use.
As Cristian Cassella, a Northeastern University professor of electrical and computer engineering, put it, QUBO problems “are of fundamental importance in many disciplines, from drug discovery to logistics, as well as wireless communications.”
A ride-sharing surge during World Cup season is one example. With roughly 10,000 active drivers across a city, about half available, the system has to weigh driver-rider matches, routes, traffic, delays, and no-shows. Similar QUBO formulations also show up in protein folding, where researchers model many structural choices to predict stable 3D shapes.
Recommended reading
8,000Hz mice sound fast — most players still don’t need them
The challenge is scale. Alejandro Montanez of the Jülich Supercomputing Center in Jülich, Germany, said the number of possible combinations grows so quickly that many real-world problems with 10 or more choices become extremely hard to solve directly.
One common approach uses Ising machines, which convert QUBO problems into models based on electron spin states in materials such as iron. But these systems can get trapped in a local minimum—a decent answer that is not the best one available.
Cassella and his team say they built an alternative, the Analog Floquet Solver, to help systems escape those traps. Drawing on Floquet theory, which describes systems under periodic forcing, the method adds energy in a way that lets the solver keep “jumping” instead of settling too early.
“We found a way to provide some degree of energy to the system that allows the machine, as it goes down, to keep jumping.”
According to Cassella, the approach solved some previously unsolved problems at record speed, produced accurate answers for equations with as many as 10,000 variables, and delivered nine orders of magnitude of improvement in terms of energy consumption.
The work, republished by Northeastern Global News, points to applications across economics, finance, drug discovery, biology, engineering, and wireless communication.
“In every single area there are problems that are currently unsolvable.”
Computing Editor
Tomas lives in the terminal. He covers chips, laptops, and operating systems with a focus on performance and efficiency. He reads kernel changelogs the way other people read fiction, and he's always on the hunt for the perfect mechanical keyboard switch. If it processes data, Tomas has an opinion on it.
via TechXplore
