Evaluating Direct Higher-Order Formulations Improves Performance in Combinatorial Optimization Problems

Combinatorial optimisation problems, which underpin many areas of science and engineering, often involve complex relationships that are difficult for computers to solve. Kazuki Ikeuchi from Keio University, Yoshiki Matsuda from Fixstars Corporation, and Shu Tanaka from Keio University investigate a new approach to tackling these challenges, moving beyond traditional methods that struggle with complex interactions. Their work evaluates the performance of directly solving problems with higher-order terms, rather than simplifying them into more manageable, but potentially less accurate, forms. The team demonstrates that a high-performance solver, capable of handling these complex relationships, consistently achieves better solutions and greater stability than conventional methods, offering a significant step towards more efficient and accurate optimisation for real-world applications.

Higher-Order Ising Machines for Combinatorial Optimisation

This research explores advanced methods for solving combinatorial optimization problems, challenges that involve finding the best solution from a vast number of possibilities. The team investigates the use of Ising Machines, specialized computers designed to tackle these problems, and focuses on improving their ability to handle complex interactions between variables. These interactions, known as higher-order relationships, are often simplified in traditional approaches, potentially sacrificing solution quality. The study emphasizes the importance of benchmark problems and robust evaluation metrics for accurately assessing the performance of different optimization techniques.

The researchers demonstrate that representing optimization problems with higher-order terms can provide a more accurate and expressive model of the underlying relationships. They explore methods for directly implementing these higher-order formulations on Ising Machines, using techniques like factor graphs to map the problem onto the hardware. This direct implementation avoids the approximations often required by conventional methods, potentially leading to improved results. The team also investigates various binary sequence generation techniques and multi-objective optimization approaches to further enhance performance.

The study highlights the importance of carefully evaluating optimization algorithms using standardized benchmark problems, such as the MaxCut problem, graph coloring, and vehicle routing. By comparing the performance of different approaches on these benchmarks, researchers can gain valuable insights into their strengths and weaknesses. The team utilizes metrics like the hypervolume indicator and merit factor to assess the quality of solutions and the effectiveness of different optimization strategies. This work contributes to the development of more powerful and efficient optimization solvers for a wide range of applications.

PUBO Solver Outperforms QUBO for Complex Problems

This work presents a significant advancement in solving complex combinatorial optimization problems by directly addressing higher-order interactions without relying on traditional order-reduction techniques. Researchers compared two approaches using the Fixstars Amplify Annealing Engine to determine the benefits of directly handling polynomial unconstrained binary optimization (PUBO) formulations versus conventional quadratic unconstrained binary optimization (QUBO). The study demonstrates that the PUBO solver consistently achieves superior solution quality and stability compared to its QUBO counterpart, while maintaining comparable computational time. Experiments utilized the low autocorrelation binary sequence (LABS) problem and the vehicle routing problem with distance balancing, both of which naturally include higher-order interactions.

Results show the PUBO solver consistently outperforms the QUBO solver across both benchmarks, indicating a clear advantage in handling complex relationships within the data. Crucially, the PUBO solver requires no order-reduction compilation, eliminating the introduction of additional variables and constraints that can degrade solution quality in traditional methods. The team measured performance based on solution quality and stability, demonstrating that the PUBO approach delivers consistently better results without sacrificing computational efficiency. The PUBO solver’s ability to directly handle up to fourth-order terms without transformation represents a key breakthrough, as many real-world problems, such as polymer sampling, protein folding, and molecular adsorption, inherently involve these higher-order interactions. This research establishes a promising new direction for optimization solvers, paving the way for more effective solutions to increasingly complex problems across diverse fields.

PUBO Solver Outperforms QUBO on Hard Problems

This research demonstrates the effectiveness of directly solving complex optimization problems using a high-performance simulated annealing solver, without relying on traditional methods that simplify the problem and potentially reduce solution quality. The team successfully implemented a solver capable of handling polynomial unconstrained binary optimization (PUBO) formulations, which include higher-order terms, and compared its performance against a conventional quadratic unconstrained binary optimization (QUBO) solver on the same hardware. Results consistently show that the PUBO solver achieves superior solution quality and stability when tackling challenging problems such as the low autocorrelation binary sequence (LABS) problem and the vehicle routing problem with distance balancing. Importantly, the PUBO solver maintains comparable computational time to the QUBO solver, while avoiding the need for order-reduction compilation, a process that can compromise the accuracy of solutions. This suggests a significant advantage in directly addressing the complexity of optimization problems, rather than simplifying them for existing hardware.