Name
Abstract | ||
|---|---|---|
AbstractA special reformulation-linearization technique based linear conic relaxation is proposed for discrete quadratic programming DQP. We show that the proposed relaxation is tighter than the traditional positive semidefinite programming relaxation. More importantly, when the proposed relaxation problem has an optimal solution with rank one or two, optimal solutions to the original DQP problem can be explicitly generated. This rank-two property is further extended to binary quadratic optimization problems and linearly constrained DQP problems. Numerical results indicate that the proposed relaxation is capable of providing high quality and robust lower bounds for DQP. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1080/10556788.2015.1134528 | Periodicals |
Keywords | Field | DocType |
discrete quadratic program,linear conic relaxation,RLT method | Discrete mathematics,Mathematical optimization,Positive-definite matrix,Quadratic equation,Quadratic programming,Lagrangian relaxation,Conic section,Mathematics,Binary number | Journal |
Volume | Issue | ISSN |
31 | 4 | 1055-6788 |
Citations | PageRank | References |
1 | 0.36 | 15 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tiantian Nie | 1 | 1 | 0.36 |
| Shu-Cherng Fang | 2 | 1153 | 95.41 |
| Zhibin Deng | 3 | 12 | 3.63 |
| John E. Lavery | 4 | 101 | 15.97 |