Innovative Algorithm Slashes Time to Solve Massive Optimization Problems

Research paper by Bjørnar Luteberget and Giorgio Sartor wins 2024 FICO® Xpress Best Paper Award; the algorithm is now in FICO® Xpress Solver

BOZEMAN, Mont.--(BUSINESS WIRE)--FICO (NYSE: FICO): Global analytics software leader FICO today announced that the 2024 FICO® Xpress Best Paper Award went to a team that developed an algorithm for finding solutions to difficult optimization problems with millions of variables and constraints in just a few seconds. The paper from Bjørnar Luteberget and Giorgio Sartor of SINTEF, one of Europe’s largest independent research institutes, presents the “Feasibility Jump” algorithm that accelerates the time for finding a first feasible solution to a massive optimization problem. The algorithm has been integrated into FICO® Xpress Solver.

More information: https://community.fico.com/s/blog-post/a5QQi000002rzAfMAI/fico5205

“When solving a very large computational problem, optimization solvers can require significant computational time to find a first feasible solution,” said Dr. Timo Berthold, director of Mixed-Integer Optimization at FICO who co-manages the contest. “The innovative work done by Luteberget and Sartor is a heuristic algorithm for Mixed-Integer Programming (MIP) problems that ‘jumps’ past the need to first develop a Linear Programming solution to the problem. It is a Lagrangian relaxation heuristic that can be very effective in quickly producing feasible solutions to large-scale, complex MIP problems.”

Feasibility Jump was initially developed for the MIP 2022 Computational Computation, which challenged participants to develop LP-free MIP heuristics. After winning the competition, a question was left hanging in the air: How does Feasibility Jump compare with state-of-the-art commercial solvers, and can it be used to complement them? This is where the FICO® Xpress Solver entered the picture.

“One of Feasibility Jump's main features is its efficiency: with a modern laptop, it can perform up to a million variable assignments per second,” said Giorgio Sartor, one of the paper’s co-authors. “This can represent the difference between obtaining the first feasible solution in seconds instead of minutes. The high customization capabilities and low-level control possibilities of FICO Xpress Solver were essential to properly integrate and rigorously test Feasibility Jump inside a cutting-edge MIP solver.”

Torkel Andreas Haufmann, research manager at SINTEF, adds: “At SINTEF we take pride in transforming research findings into real-world, practical solutions. This work is a great example of groundbreaking research combined with an application-oriented mindset!”

“We at FICO congratulate Bjørnar and Giorgio on winning the 2024 FICO Xpress Best Paper Award,” said Berthold. “Amidst numerous strong contenders, their remarkable research stood out prominently. The award jury was impressed by its originality and practical relevance. The awarded paper significantly contributed to the development of MIP technology and showed remarkable results in challenging instances.”

The winning paper was published in Mathematical Programming Computation 15.2 (2023): Luteberget, Bjørnar, and Giorgio Sartor. "Feasibility Jump: an LP-free Lagrangian MIP heuristic."

In 2022, the FICO® Xpress Best Paper Award was introduced to acknowledge exceptional research in mathematical optimization, operations research and related fields. Nominations for the 2025 award are due by January 31.

Recognized as one of the fastest and most powerful optimization solvers, FICO® Xpress Solver gives business users, data scientists and researchers greater power and flexibility when solving complex problems in supply chain optimization, energy, pricing and many other applications.

About FICO

FICO (NYSE: FICO) powers decisions that help people and businesses around the world prosper. Founded in 1956, the company is a pioneer in the use of predictive analytics and data science to improve operational decisions. FICO holds more than 200 US and foreign patents on technologies that increase profitability, customer satisfaction and growth for businesses in financial services, insurance, telecommunications, health care, retail and many other industries. Using FICO solutions, businesses in more than 80 countries do everything from protecting 4 billion payment cards from fraud, to improving financial inclusion, to increasing supply chain resiliency. The FICO® Score, used by 90% of top US lenders, is the standard measure of consumer credit risk in the US and has been made available in over 40 other countries, improving risk management, credit access and transparency. Learn more at www.fico.com.

Learn more at https://www.fico.com/en.

Join the conversation at https://twitter.com/fico & https://www.fico.com/blogs/.

For FICO news and media resources, visit https://www.fico.com/en/newsroom.

FICO is a registered trademark of Fair Isaac Corporation in the U.S. and other countries.