Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

The Impact of Quadratization in Convexification-Based Resolution of Polynomial Binary Optimization

Amélie Lambert, Sourour Elloumi, Arnaud Lazare, Elisabeth Rodríguez-Heck

Published Dec 3, 2019• 0 citations
OpenAlex

Related papers

Quadratization and convexification in polynomial binary optimization

Yves Crama, Sourour Elloumi, Amélie Lambert +1 more

Journal of Combinatorial Optimization•Oct 1, 2025•6 citations

Computing Local Optima in Quadratic Unconstrained Binary Optimization Problems in Randomized Polynomial Time

Lunshan Gao

•Jan 1, 2024•0 citations

Polynomially Solvable Cases of Binary Quadratic Programs

Duan Li, Xiaoling L. Sun, Shenshen Gu +2 more

Springer optimization and its applications•Jan 1, 2010•16 citations

Efficient linear reformulations for binary polynomial optimization problems

Sourour Elloumi, Zoé Verchère

Computers & Operations Research•Apr 5, 2023•6 citations

Quadratic versus Polynomial Unconstrained Binary Models for Quantum Optimization illustrated on Railway Timetabling

Grange, Camille, Marion Lavignac, Valentina Pozzoli +1 more

Quantum Approximate Optimization Algorithm (QAOA) is one of the most short-term promising quantum-classical algorithm to solve unconstrained combinatorial optimization problems. It alternates between the execution of a parametrized quantum circuit and a classical optimization. There are numerous levers for enhancing QAOA performances, such as the choice of quantum circuit meta-parameters or the choice of the classical optimizer. In this paper, we stress on the importance of the input problem formulation by illustrating it with the resolution of an industrial railway timetabling problem. Specifically, we present a generic method to reformulate any polynomial problem into a Polynomial Unconstrained Binary Optimization (PUBO) problem, with a specific formulation imposing penalty terms to take binary values when the constraints are linear. We also provide a generic reformulation into a Quadratic Unconstrained Binary Optimization (QUBO) problem. We then conduct a numerical comparison between the PUBO with binary penalty terms and the QUBO formulations proposed on a railway timetabling problem solved with QAOA. Our results illustrate that the PUBO reformulation outperforms the QUBO one for the problem at hand.

arXiv:2411.10062•Nov 15, 2024•4 citations

On partial convexification cuts for mixed-integer quadratic programs with 0-1 indicators

Rui Ma, Renaud Chicoisne, Pierre Latouche

This paper studies mixed-integer quadratic programming (MIQP) problems with 0--1 indicator constraints.We propose two cut-generation algorithms under three reformulation schemes, which can be seamlessly embedded into a branch-and-bound framework.The algorithms are based on a partial convexification strategy applied to selected subsets of variables, enabling the efficient generation of both quadratic and linear cuts.We provide theoretical insights by characterizing the generated cuts as deepest cuts and by comparing quadratic cuts with their linear counterparts in different variable spaces, thereby bridging convexification theory and practical MIQP solution methods.Furthermore, we develop three practical strengthening techniques that exploit structural properties of the quadratic terms.Extensive computational experiments demonstrate that the proposed cut-generation algorithms meaningfully improve solver performance by accelerating convergence to optimal solutions.

•Jan 20, 2026•0 citations
Quantum Approximate Optimization Algorithm (QAOA) is one of the most short-term promising quantum-classical algorithm to solve unconstrained combinatorial optimization problems. It alternates between the execution of a parametrized quantum circuit and a classical optimization. There are numerous levers for enhancing QAOA performances, such as the choice of quantum circuit meta-parameters or the choice of the classical optimizer. In this paper, we stress on the importance of the input problem formulation by illustrating it with the resolution of an industrial railway timetabling problem. Specifically, we present a generic method to reformulate any polynomial problem into a Polynomial Unconstrained Binary Optimization (PUBO) problem, with a specific formulation imposing penalty terms to take binary values when the constraints are linear. We also provide a generic reformulation into a Quadratic Unconstrained Binary Optimization (QUBO) problem. We then conduct a numerical comparison between the PUBO with binary penalty terms and the QUBO formulations proposed on a railway timetabling problem solved with QAOA. Our results illustrate that the PUBO reformulation outperforms the QUBO one for the problem at hand.
This paper studies mixed-integer quadratic programming (MIQP) problems with 0--1 indicator constraints.We propose two cut-generation algorithms under three reformulation schemes, which can be seamlessly embedded into a branch-and-bound framework.The algorithms are based on a partial convexification strategy applied to selected subsets of variables, enabling the efficient generation of both quadratic and linear cuts.We provide theoretical insights by characterizing the generated cuts as deepest cuts and by comparing quadratic cuts with their linear counterparts in different variable spaces, thereby bridging convexification theory and practical MIQP solution methods.Furthermore, we develop three practical strengthening techniques that exploit structural properties of the quadratic terms.Extensive computational experiments demonstrate that the proposed cut-generation algorithms meaningfully improve solver performance by accelerating convergence to optimal solutions.