Optimizing a Polyhedral-Semidefinite Relaxation of Completely Positive Programs

It has recently been shown (Burer, 2006) that a large class of NP-hard nonconvex quadratic programs (NQPs) can be modeled as so-called completely positive programs (CPPs), i.e., the minimization of a linear function over the convex cone of completely positive matrices subject to linear constraints. Such convex programs are necessarily NP-hard. A basic tractable relaxation … Read more

A p-Cone Sequential Relaxation Procedure for 0-1 Integer Programs

Given a 0-1 integer programming problem, several authors have introduced sequential relaxation techniques — based on linear and/or semidefinite programming — that generate the convex hull of integer points in at most $n$ steps. In this paper, we introduce a sequential relaxation technique, which is based on $p$-order cone programming ($1 \le p \le \infty$). … Read more

A new, solvable, primal relaxation for nonlinear integer programming problems with linear constraints

This paper describes a new primal relaxation for nonlinear integer programming problems with linear constraints. This relaxation, contrary to the standard Lagrangean relaxation, can be solved efficiently. It requires the solution of a nonlinear penalized problem whose linear constraint set is known only implicitly, but whose solution is made possible by the use of a … Read more

A New Second-Order Cone Programming Relaxation for MAX-CUT problems

We propose a new relaxation scheme for the MAX-CUT problem using second-order cone programming. We construct relaxation problems to reflect the structure of the original graph. Numerical experiments show that our relaxation approaches give better bounds than those based on the spectral decomposition proposed by Kim and Kojima, and that the efficiency of the branch-and-bound … Read more

Lagrangian relaxation

Lagrangian relaxation is a tool to find upper bounds on a given (arbitrary) maximization problem. Sometimes, the bound is exact and an optimal solution is found. Our aim in this paper is to review this technique, the theory behind it, its numerical aspects, its relation with other techniques such as column generation. Citation in: Computational … Read more