Eigendecomposition-based reformulations for convex MINLP in the SHOT solver

Jan Kronqvist; Andreas Lundell

Eigendecomposition-based reformulations for convex MINLP in the SHOT solver

Jan Kronqvist^*, Andreas Lundell

^*Corresponding author for this work

Information Technology

Research output: Chapter in Book/Conference proceeding › Conference contribution › Scientific

Abstract

In this extended abstract, we describe how the SHOT solver utilizes
eigendecomposition to perform a lifted reformulation for convex mixed-integer problems with non-separable quadratic expressions. An eigenvalue decomposition is first performed on the non-diagonal matrices defining quadratic expressions in the problem, and is used for transforming the quadratic expressions into convex additively separable constraints. The resulting additively separable constraints are then further lifted into a form where SHOT generates polyhedral outer approximations of convex quadratic univariate functions. The reformulations have been integrated into SHOT’s automatic problem reformulation functionality.

Original language	English
Title of host publication	Journal of Global Optimization
Subtitle of host publication	Special Issue on Global Optimization: HUGO
Publisher	Springer
Pages	107-110
Number of pages	4
Publication status	Published - Sept 2022
MoE publication type	B3 Non-refereed article in conference proceedings
Event	Hungarian Global Optimization Workshop HUGO 2022 - Szeged, Hungary Duration: 5 Sept 2022 → 8 Sept 2022

Publication series

Name	Journal of Global Optimization
ISSN (Print)	0925-5001
ISSN (Electronic)	1573-2916

Conference

Conference	Hungarian Global Optimization Workshop HUGO 2022
Abbreviated title	HUGO
Country/Territory	Hungary
City	Szeged
Period	05/09/22 → 08/09/22

Keywords

Mixed-integer nonlinear programming (MINLP)
eigendecomposition
Supporting hyperplane optimization toolkit (SHOT)
lifting reformulations
convex mixed-integer programming

Cite this

@inproceedings{06060a628c9744df98734fd166f2c517,

title = "Eigendecomposition-based reformulations for convex MINLP in the SHOT solver",

abstract = "In this extended abstract, we describe how the SHOT solver utilizeseigendecomposition to perform a lifted reformulation for convex mixed-integer problems with non-separable quadratic expressions. An eigenvalue decomposition is first performed on the non-diagonal matrices defining quadratic expressions in the problem, and is used for transforming the quadratic expressions into convex additively separable constraints. The resulting additively separable constraints are then further lifted into a form where SHOT generates polyhedral outer approximations of convex quadratic univariate functions. The reformulations have been integrated into SHOT{\textquoteright}s automatic problem reformulation functionality.",

keywords = "Mixed-integer nonlinear programming (MINLP), eigendecomposition, Supporting hyperplane optimization toolkit (SHOT), lifting reformulations, convex mixed-integer programming",

author = "Jan Kronqvist and Andreas Lundell",

note = "Ej {\"a}nnu publicerat?; Hungarian Global Optimization Workshop HUGO 2022, HUGO ; Conference date: 05-09-2022 Through 08-09-2022",

year = "2022",

month = sep,

language = "English",

series = " Journal of Global Optimization",

publisher = "Springer",

pages = "107--110",

booktitle = "Journal of Global Optimization",

}

TY - GEN

T1 - Eigendecomposition-based reformulations for convex MINLP in the SHOT solver

AU - Kronqvist, Jan

AU - Lundell, Andreas

N1 - Ej ännu publicerat?

PY - 2022/9

Y1 - 2022/9

N2 - In this extended abstract, we describe how the SHOT solver utilizeseigendecomposition to perform a lifted reformulation for convex mixed-integer problems with non-separable quadratic expressions. An eigenvalue decomposition is first performed on the non-diagonal matrices defining quadratic expressions in the problem, and is used for transforming the quadratic expressions into convex additively separable constraints. The resulting additively separable constraints are then further lifted into a form where SHOT generates polyhedral outer approximations of convex quadratic univariate functions. The reformulations have been integrated into SHOT’s automatic problem reformulation functionality.

AB - In this extended abstract, we describe how the SHOT solver utilizeseigendecomposition to perform a lifted reformulation for convex mixed-integer problems with non-separable quadratic expressions. An eigenvalue decomposition is first performed on the non-diagonal matrices defining quadratic expressions in the problem, and is used for transforming the quadratic expressions into convex additively separable constraints. The resulting additively separable constraints are then further lifted into a form where SHOT generates polyhedral outer approximations of convex quadratic univariate functions. The reformulations have been integrated into SHOT’s automatic problem reformulation functionality.

KW - Mixed-integer nonlinear programming (MINLP)

KW - eigendecomposition

KW - Supporting hyperplane optimization toolkit (SHOT)

KW - lifting reformulations

KW - convex mixed-integer programming

M3 - Conference contribution

T3 - Journal of Global Optimization

SP - 107

EP - 110

BT - Journal of Global Optimization

PB - Springer

T2 - Hungarian Global Optimization Workshop HUGO 2022

Y2 - 5 September 2022 through 8 September 2022

ER -

Eigendecomposition-based reformulations for convex MINLP in the SHOT solver

Abstract

Publication series

Conference

Keywords

Fingerprint

Cite this