Name
Title | ||
|---|---|---|
Structured linear reformulation of binary quadratically constrained quadratic programs |
Abstract | ||
|---|---|---|
This paper presents a new linear reformulation to convert a binary quadratically constrained quadratic program into a 0–1 mixed integer linear program. By exploiting the symmetric structure of the quadratic terms embedded in the objective and constraint functions, the proposed linear reformulation requires fewer variables and constraints than other known O(n)-sized linear reformulations. Theoretical proof shows the proposed reformulation provides a tighter linearization for each quadratic term comparing to other known linear reformulations. Extensive numerical experiments support the superior computational efficiency of the proposed reformulation in terms of the running time and number of nodes explored. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1007/s11590-018-1361-8 | Optimization Letters |
Keywords | Field | DocType |
Quadratically constrained quadratic program, Binary program, Linear reformulation, 0–1 mixed integer linear program | Integer,Quadratic growth,Mathematical optimization,Quadratically constrained quadratic program,Quadratic equation,Linear programming,Mathematics,Symmetric structure,Linearization,Binary number | Journal |
Volume | Issue | ISSN |
14 | 3 | 1862-4480 |
Citations | PageRank | References |
0 | 0.34 | 16 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shan Jiang | 1 | 0 | 0.34 |
| Shu-Cherng Fang | 2 | 1153 | 95.41 |
| Tiantian Nie | 3 | 0 | 0.34 |
| Qi An | 4 | 0 | 0.34 |