Name
Title | ||
|---|---|---|
Using DRL* relaxations for quadratically constrained pseudoboolean optimization: application to robust Min-Cut |
Abstract | ||
|---|---|---|
In this work we focus on solving quadratically constrained pseudoboolean optimization problems with quadratic objective as mixed integer linear programs. The standard mixed integer linear formulation of such problems is strengthened using valid inequalities derived from solving Reformulation-Linearization relaxation called partial DRL* relaxation. The proposed PDRL* relaxation features block-decomposable structure which are exploited to improve computational efficiency. We present computational results obtained with the rank 2 PDRL*, showing that the proposed mixed integer linear formulation gives rise to significant reduction factors (typically more than 1000) in the size of the branch and bound trees on instances of robust minimum cut problem with weight constraints. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.endm.2010.05.154 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
mixed integer programming,robust optimization,rlt,branch and bound,optimization problem,minimum cut | Discrete mathematics,Mathematical optimization,Combinatorics,Quadratically constrained quadratic program,Branch and cut,Branch and price,Minimum cut,Integer programming,Linear programming relaxation,Optimization problem,Mathematics,Special ordered set | Journal |
Volume | ISSN | Citations |
36 | Electronic Notes in Discrete Mathematics | 0 |
PageRank | References | Authors |
0.34 | 6 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michel Minoux | 1 | 741 | 100.18 |
| Hacene Ouzia | 2 | 18 | 1.69 |