binary quadratic optimization – Optimization Online

What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO

Published: 2015/05/04, Updated: 2017/04/23

Meta Heuristics, Optimization Software Benchmark binary quadratic optimization, computational testing, heuristics, hyper-heuristics, interpretable machine learning, max-cut problem, reproducible research, test bed

Though empirical testing is broadly used to evaluate heuristics, there are shortcomings with how it is often applied in practice. In a systematic review of Max-Cut and Quadratic Unconstrained Binary Optimization (QUBO) heuristics papers, we found only 4% publish source code, only 14% compare heuristics with identical termination criteria, and most experiments are performed with … Read more

Quadratic combinatorial optimization using separable underestimators

Published: 2012/10/24, Updated: 2018/02/27

Christoph Buchheim

Emiliano Traversi

0-1 Programming, Quadratic Programming, Semi-definite Programming binary quadratic optimization, quadratic shortest path problem, separable underestimators

Binary programs with a quadratic objective function are NP-hard in general, even if the linear optimization problem over the same feasible set is tractable. In this paper, we address such problems by computing quadratic global underestimators of the objective function that are separable but not necessarily convex. Exploiting the binary constraint on the variables, a … Read more