Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2602.19051 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915811185131520 |
|---|---|
| author | Lu, Cheng Fei, Yu Zhou, Jing Deng, Zhibin Qu, Guangtai |
| author_facet | Lu, Cheng Fei, Yu Zhou, Jing Deng, Zhibin Qu, Guangtai |
| contents | It is well-known that the quadratic convex reformulation (QCR) technique can speed up some general-purpose solvers such as CPLEX and Gurobi. Recently, the method of quadratic nonconvex reformulation (QNR) was proposed, which provides an alternative way for accelerating a solver via reformulation technique. This paper proposes several new reformulations for 0-1 quadratic programming problems using the QNR technique. Such a technique provides more flexibility in adding nonconvex quadratic constraints into the problem formulation, so that some valid inequalities, such as the triangle inequalities, can be incorporated into the formulation to tighten the lower bound of the problem. We analyze the effects of the proposed reformulations on the lower bounds implemented in the solver, and propose some methods to maximize the McCormick relaxation bounds of the reformulations. Our numerical experiments compare the proposed reformulations with the existing quadratic convex reformulations, showing the effectiveness of the proposed reformulations on 0-1 quadratic programming problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_19051 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | New reformulations for 0-1 quadratic programming problem using quadratic nonconvex reformulation techniques and valid inequalities Lu, Cheng Fei, Yu Zhou, Jing Deng, Zhibin Qu, Guangtai Optimization and Control It is well-known that the quadratic convex reformulation (QCR) technique can speed up some general-purpose solvers such as CPLEX and Gurobi. Recently, the method of quadratic nonconvex reformulation (QNR) was proposed, which provides an alternative way for accelerating a solver via reformulation technique. This paper proposes several new reformulations for 0-1 quadratic programming problems using the QNR technique. Such a technique provides more flexibility in adding nonconvex quadratic constraints into the problem formulation, so that some valid inequalities, such as the triangle inequalities, can be incorporated into the formulation to tighten the lower bound of the problem. We analyze the effects of the proposed reformulations on the lower bounds implemented in the solver, and propose some methods to maximize the McCormick relaxation bounds of the reformulations. Our numerical experiments compare the proposed reformulations with the existing quadratic convex reformulations, showing the effectiveness of the proposed reformulations on 0-1 quadratic programming problems. |
| title | New reformulations for 0-1 quadratic programming problem using quadratic nonconvex reformulation techniques and valid inequalities |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2602.19051 |