Home > Research > Publications & Outputs > On a hierarchy of polytopes for integer quadrat...

Associated organisational unit

Electronic data

  • miqpbits_ods25_REV

    Rights statement: 12m

    Accepted author manuscript, 329 KB, PDF document

    Embargo ends: 1/01/50

View graph of relations

On a hierarchy of polytopes for integer quadratic programming

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNChapter (peer-reviewed)peer-review

Forthcoming
Publication date8/05/2025
Host publicationMathematics, Algorithms and the Art and Science of Decision-Making
EditorsMichele Barbato, Nicola Bianchessi, Alberto Boggio Tomasaz
PublisherSpringer
<mark>Original language</mark>English

Abstract

A folklore result in integer programming is that bounded integer variables can be replaced with binary variables, using bit representation. Under certain conditions, this can be used to reformulate mixed-integer quadratic programs as mixed-integer linear programs, and thereby render them easier to solve. In fact, several reformulation strategies can be found in the literature. We conduct a systematic comparison of these strategies by focusing on integer quadratic programs with box constraints, and present a hierarchy for the associated polytopes.