joint work with Nicolo Gusmeroli, Franz Rendl
We are interested in solving linearly constrained binary quadratic problems (BQP) by transforming the problems into unconstrained ones and using a max-cut solver. This is in the spirit of "exact penalty methods", but optimizing the penalized function over the discrete set. We improve on a method investigated by Lasserre (2016) who computed a sufficiently large penalty paramter by solving two semidefinite programs. Our new parameters lead to a better performance when solving the transformed problem. We present preliminary computational results demonstrating the strength of this method.
joint work with Miguel Anjos, Lucas Létocart, Jean Maeght, Emiliano Traversi
The Alternating Current Optimal Power Flow (ACOPF) problem is a challenging problem due to its significant nonconvexity. To prove global optimality, Semidefinite Relaxations (SDRs) are a powerful tool: the rank-one SDR is often exact and when it is not, the Lasserre hierarchy SDRs achieve global optimality. However, solving large-scale semidefinite problems is still a computational challenge. We propose a conic-bundle algorithm to solve SDRs of ACOPF based on a clique decomposition arising from an ad-hoc chordal extension of the power network.
In this talk we revisit completely positive cone programs. A simple reformulation as a fixed point problem leads us to a family of (globally convergent) outer algorithms. NP-hardness of the original problem is shifted to the completely positive projection operator. Its sequential (approximate) evaluations are then tackled by exploiting the underlying structure in combination with powerful local optimization tools. Finally some promising numerical results on small dimensional maximum stable set problems are presented, indicating that the resulting heuristics often perform well in practice.