A binarization of a bounded variable x is obtained via a system of linear inequalities that involve x together with additional variables y(1), ... , y(t) in [0,1] so that the integrality of x is implied by the integrality of y(1), ... , y(t). A binary extended formulation of a mixedinteger linear set is obtained by adding to its original description binarizations of its integer variables. Binary extended formulations are useful in mixed-integer programming as imposing integrality on 0/1 variables rather than on general integer variables has interesting convergence properties and has been studied from both the theoretical and practical points of view. We study the behavior of binary extended formulations with respect to sequential convexification. In particular, given a binary extended formulation and one of its variables x, we study a parameter that measures the progress made toward enforcing the integrality of x via application of sequential convexification. We formulate this parameter, which we call rank, as the solution of a set-covering problem and express it exactly for the classic binarizations from the literature.

Binary Extended Formulations and Sequential Convexification

Aprile, Manuel;Di Summa, Marco
2023

Abstract

A binarization of a bounded variable x is obtained via a system of linear inequalities that involve x together with additional variables y(1), ... , y(t) in [0,1] so that the integrality of x is implied by the integrality of y(1), ... , y(t). A binary extended formulation of a mixedinteger linear set is obtained by adding to its original description binarizations of its integer variables. Binary extended formulations are useful in mixed-integer programming as imposing integrality on 0/1 variables rather than on general integer variables has interesting convergence properties and has been studied from both the theoretical and practical points of view. We study the behavior of binary extended formulations with respect to sequential convexification. In particular, given a binary extended formulation and one of its variables x, we study a parameter that measures the progress made toward enforcing the integrality of x via application of sequential convexification. We formulate this parameter, which we call rank, as the solution of a set-covering problem and express it exactly for the classic binarizations from the literature.
2023
File in questo prodotto:
File Dimensione Formato  
aprile-et-al-2023-binary-extended-formulations-and-sequential-convexification.pdf

Accesso riservato

Tipologia: Published (publisher's version)
Licenza: Accesso privato - non pubblico
Dimensione 2.11 MB
Formato Adobe PDF
2.11 MB Adobe PDF Visualizza/Apri   Richiedi una copia
Submitted_BinaryExtendedFormulationsSequentialConvexification.pdf

accesso aperto

Tipologia: Preprint (submitted version)
Licenza: Accesso libero
Dimensione 254.44 kB
Formato Adobe PDF
254.44 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/3515481
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
  • OpenAlex ND
social impact