| - | ||||
|
|
New Relaxations for Binary Quadratic Problems Using Second-Order Cone Programming
Bissan Ghaddar(bghaddar Abstract: We present a general framework for conic relaxations based on polynomial programming. Using this framework, we can re-derive previous relaxation schemes and provide new ones for general binary quadratic optimization. In particular, we propose a second-order cone programming relaxation that can be strengthened by adding triangle inequalities. Computational tests on the max-cut problem, the unconstrained version of binary quadratic optimization, show that the strengthened second-order cone-based relaxation outperforms the semidefinite-based relaxation in terms of computational efficiency and is comparable in terms of bounds. In order to gain insight into the performance of our approach on constrained quadratic binary problems, we also compare the second-order cone relaxation for the quadratic knapsack problem to the strongest semidefinite relaxation in the literature. The computational results confirm that using the second-order cone relaxation with triangle inequalities provides a bound that is competitive with the semidefinite bound strengthened with triangle inequalities but the former relaxation is computationally more efficient. Keywords: polynomial optimization, second-order cone programming, semidefinite programming, binary quadratic problem Category 1: Linear, Cone and Semidefinite Programming Category 2: Nonlinear Optimization Category 3: Combinatorial Optimization Citation: Download: [PDF] Entry Submitted: 10/31/2009 Modify/Update this entry | ||
| Visitors | Authors | More about us | Links | |
|
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository
|
Submit Update Policies |
Coordinator's Board Classification Scheme Credits Give us feedback |
Optimization Journals, Sites, Societies | |
|
||||