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

Journal of Combinatorial Optimization

Quadratization and convexification in polynomial binary optimization

Yves Crama, Sourour Elloumi, Amélie Lambert, Elisabeth Rodríguez-Heck

Published Oct 1, 2025• 6 citations
Publisher
DOI
10.1007/s10878-025-01334-y

Related papers

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

Amélie Lambert, Sourour Elloumi, Arnaud Lazare +1 more

•Dec 3, 2019•0 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

Polynomial time solvable algorithms to a class of unconstrained and linearly constrained binary quadratic programming problems

Shenshen Gu, Rui Cui, Peng Jiao

Neurocomputing•Mar 9, 2016•5 citations

Efficient linear reformulations for binary polynomial optimization problems

Sourour Elloumi, Zoé Verchère

Computers & Operations Research•Apr 5, 2023•6 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
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.