An Exact Penalty Method over Discrete S...

Binary quadratic programming is an important modelling tool for combinatorial optimization problems. This topic has been widely studied in the last thirty years due to the huge number of real-world applications. For some combinatorial optimization problems, e.g., the max-cut problem, tailored algorithms have been developed.

However, solving general binary quadratic programs is an NP-hard problem, thus no polynomial time algorithm for finding the optimal value of a binary quadratic problem exists unless P = NP.

By proposing a new algorithm, this thesis further contributes to solving binary quadratic problems subject to linear constraints.

We introduce the concept of an exact penalty method over discrete sets by stating the algorithm EXPEDIS. This allows the reformulation of a binary quadratic problem subject to linear constraints into a max-cut instance, which is one of the most studied and challenging problems in combinatorial optimization.

In order to obtain an exact reformulation, a threshold and a penalty parameter must be defined. The value of the latter parameter is of crucial importance since it affects the weights of the edges of the final max-cut problem. It is desirable for the penalty parameter to be small in order to reduce the weights. A comprehensive study is performed, in which both the smallest possible as well as some efficient and computable parameters are proposed.

Furthermore, we introduce some improvement to the current state-of-the-art branch-and-bound solvers for the max-cut problem, where the bounding routine is strengthened by including additional cutting planes.

Finally, we develop BiqBin, a solver for binary quadratic problems subject to linear constraints, which combines the exact penalty method over discrete sets EXPEDIS and a semidefinite programming-based branch-and-bound algorithm. In this thesis we present the theoretical background of BiqBin, as well as an empirical proof of the importance of using a small penalty parameter in the reformulation. Moreover, we compare of the numerical results for BiqBin and other solvers on previous and new benchmark instances both of unconstrained, e.g., max-cut, and linearly constrained binary quadratic problems, e.g., max k-cluster.

We created new instances of a larger size for various test problems that have long been considered in the literature. In order to solve these instances, we implemented a parallel version of BiqBin, which runs on a high-performance computer. The computational results demonstrate the strength of BiqBin compared to other state-of-the-art solvers.