WA8 - Integer Programming

Neutral atom quantum computers (NAQCs) have emerged as a promising quantum computing platform for solving the maximum weighted independent set (MWIS) problem. However, currently available quantum protocols face two key limitations: Constraints of the atomic layout on realizable graph geometries and the absence of performance guarantees. We introduce Lp-Quts, a hybrid quantum-classical framework that integrates an NAQC sampler into a classical cutting-plane algorithm. At each iteration, a relaxed linear program (RLP) bounds the MWIS and induces a reduced graph from which independent sets are sampled using an analog quantum sampler. A novel sample-informed separation problem guides odd-cycle cut selection and accelerates convergence. For t-perfect graphs, Lp-Quts inherits polynomial-time convergence guarantees from the classical theory of cutting planes. We evaluate our approach on instances with up to 300 vertices—a scale that exceeds the capabilities of current NAQCs hardware. In this regime, Lp-Quts reaches solutions within 5–10\% of optimality, outperforming competing quantum protocols and greedy baselines under equal sampling budgets. As expected, simulated annealing remains the strongest sample-based solver at this scale. These results demonstrate how quantum samplers can be effectively embedded within classical operations research frameworks to deliver near-optimal solutions with reduced quantum resources while preserving formal guarantees. More broadly, I will present my group's focus on merging quantum algorithms into operations research workflows.

Degree-based topological indices in mathematical chemistry are numerical values used to analyze the structure of molecules and predict their physicochemical behaviour. For any number of atoms and chemical bonds of a molecule, its chemical graph optimizing such indices always belongs to a set of extreme points. Using a parametrized version of the reverse-search algorithm of Avis and Fukuda, we solve linear systems of equations in parametric form in order to determine these extreme points.

We propose decision policies encoding the feasible set of integer linear programs (ILPs) into a decision tree. After its construction, this structure allows retrieving optimal solutions for any cost vector in a polynomial number of arithmetic operations. Our approach also reveals an intriguing geometric connection between ILPs nearest neighbor problems.

The parameter configuration problem aims to identify solver settings that maximize performance. We propose a framework for parameter tuning of MIP solvers based on iterated local search. The approach exploits parallelism by evaluating multiple configurations simultaneously. Designed for single-instance training, it highlights the strong impact of parameter choices on solver performance.