1210. Lagrangian Duality for Mixed-Integer Semidefinite Programming and its Applications
Invited abstract in session WC-49: Aspects of Conic Optimization, stream Conic and polynomial optimization.
Wednesday, 12:30-14:00Room: Parkinson B10
Authors (first author is the speaker)
| 1. | Frank de Meijer
|
| Delft Institute of Applied Mathematics, Delft University of Technology | |
| 2. | Renata Sotirov
|
| Tilburg University |
Abstract
Mixed-integer semidefinite programming is the extension of semidefinite programming where some or all of the variables are required to be integer. The combination of positive semidefiniteness and integrality allows to formulate many optimization problems as mixed-integer semidefinite programs (MISDPs). In this talk we consider the Lagrangian duality theory for MISDPs and show how integer Lagrangian dual bounds can be constructed. In particular, we present a hierarchy of Lagrangian dual bounds by exploiting the theory of integer positive semidefinite matrices and propose three algorithms for computing those bounds. We apply our approach to the max-k-cut problem and the box-constrained non-convex quadratic program, which demonstrate that the new bounds are substantially stronger than the semidefinite programming bound obtained by relaxing integrality.
Keywords
- Programming, Semidefinite
- Programming, Mixed-Integer
- Combinatorial Optimization
Status: accepted
Back to the list of papers