MPC

MPC 2017, ISSUE 3



Mathematical Programming Computation, Volume 9, Issue 3, September 2017

Convex quadratic relaxations for mixed-integer nonlinear programs in power systems

Hassan Hijazi, Carleton Coffrin, Pascal Van Hentenryck

This paper presents a set of new convex quadratic relaxations for nonlinear and mixed-integer nonlinear programs arising in power systems. The considered models are motivated by hybrid discrete/continuous applications where existing approximations do not provide optimality guarantees. The new relaxations offer computational efficiency along with minimal optimality gaps, providing an interesting alternative to state-of-the-art semidefinite programming relaxations. Three case studies in optimal power flow, optimal transmission switching and capacitor placement demonstrate the benefits of the new relaxations.

Full Text: PDF



Mathematical Programming Computation, Volume 9, Issue 3, September 2017

Extended formulations in mixed integer conic quadratic programming

Juan Pablo Vielma, Iain Dunning, Joey Huchette, Miles Lubin

In this paper we consider the use of extended formulations in LP-based algorithms for mixed integer conic quadratic programming (MICQP). Extended formulations have been used by Vielma et al. (INFORMS J Comput 20: 438–450, 2008) and Hijazi et al. (Comput Optim Appl 52: 537–558, 2012) to construct algorithms for MICQP that can provide a significant computational advantage. The first approach is based on an extended or lifted polyhedral relaxation of the Lorentz cone by Ben-Tal and Nemirovski (Math Oper Res 26(2): 193–205 2001) that is extremely economical, but whose approximation quality cannot be iteratively improved. The second is based on a lifted polyhedral relaxation of the euclidean ball that can be constructed using techniques introduced by Tawarmalani and Sahinidis (Math Programm 103(2): 225–249, 2005). This relaxation is less economical, but its approximation quality can be iteratively improved. Unfortunately, while the approach of Vielma, Ahmed and Nemhauser is applicable for general MICQP problems, the approach of Hijazi, Bonami and Ouorou can only be used for MICQP problems with convex quadratic constraints. In this paper we show how a homogenization procedure can be combined with the technique by Tawarmalani and Sahinidis to adapt the extended formulation used by Hijazi, Bonami and Ouorou to a class of conic mixed integer programming problems that include general MICQP problems. We then compare the effectiveness of this new extended formulation against traditional and extended formulation-based algorithms forMICQP.We find that this new formulation can be used to improve various LP-based algorithms. In particular, the formulation provides an easy-to-implement procedure that, in our benchmarks, significantly improved the performance of commercial MICQP solvers.

Full Text: PDF



Mathematical Programming Computation, Volume 9, Issue 3, September 2017

New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem

Matthias Köppe, Yuan Zhou

We describe new computer-based search strategies for extreme functions for the Gomory–Johnson infinite group problem. They lead to the discovery of new extreme functions, whose existence settles several open questions.

Full Text: PDF




Imprint and privacy statement

For the imprint and privacy statement we refer to the Imprint of ZIB.
© 2008-2020 by Zuse Institute Berlin (ZIB).