Description
CCOR Optimalizálási Szeminárium
Abstract:
The field of combinatorial optimization studies optimization problems where the feasible set is usually a large discrete set related to combinatorial objects, and the problems usually fall into the class of NP -hard problems.
Integer programming offers several techniques to (approximately) solve these problems, including the branch-and-bound (B&B) algorithm as a classical approach.
In our talk, we will present how to solve optimization problems where the objective function is non-convex quadratic and the constraints are linear, but the variables are binary (we call them binary quadratic problems).
This family of problems includes several well-known optimization problems, such as the stable set problem, the max-cut problem, the clustering problem, etc.
Our approach is based on a Branch and Bound (B&B) algorithm combined with an exact penalty approach, where the computational core consists of solving large relaxations of semidefinite programming. These problems are very difficult because they contain a large number of linear constraints, which are the so-called hypermetric cutting planes. Therefore, interior point methods are not suitable, and we have to use first order or quasi-Newton methods.
In this talk, we present how to use the Alternating Direction Method of Multipliers (ADMM) and the BFGS method to solve these SDP programmes relatively fast and to obtain a very efficient exact solver.
The final result, the solver BiqBin, was written in C++ and is available as a free web service running on the supercomputer of the University of Ljubljana (http://www.biqbin.eu). Performance optimization for this solver was performed on the Czech national supercomputer in Ostrava via the preparatory PRACE access.
For Zoom access please contact E.-Nagy Marianna (marianna.eisenberg-nagy[at]uni-corvinus.hu).