Emiliano Traversi 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
The principal idea of this paper is to exploit Semidefinite Programming (SDP) relaxation within the framework provided by Mixed Integer Nonlinear Programming (MINLP) solvers when tackling Binary Quadratic Problems (BQP). SDP relaxation is well-known to provide strong bounds for BQP in practice. However, the method is not typically implemented in many state-of-the-art MINLP solvers based … Read more
Dantzig-Wolfe decomposition (or reformulation) is well-known to provide strong dual bounds for specially structured mixed integer programs (MIPs). However, the method is not implemented in any state-of-the-art MIP solver as it is considered to require structural problem knowledge and tailoring to this structure. We provide a computational proof-of-concept that the reformulation can be automated. That … Read more
We are given a digraph G = (N, A), where each arc is colored with one among k given colors. We look for a spanning arborescence T of G rooted at a given node and having minimum changeover cost. We call this the Minimum Changeover Cost Arborescence problem. To the authors’ knowledge, it is a … Read more
Dantzig-Wolfe decomposition is well-known to provide strong dual bounds for specially structured mixed integer programs (MIPs) in practice. However, the method is not part of any state-of-the-art MIP solver: it needs tailoring to the particular problem; the typical bordered block-diagonal matrix structure determines the decomposition; the resulting column generation subproblems need to be solved efficiently; … Read more