Abstract
We describe an improved technique for handling large numbers of cutting planes when using an interior-point method for the solution of linear or semidefinite relaxations in binary quadratic optimization. The approach does not require solving successive relaxations to optimality but chooses cuts at intermediate iterates based on indicators of inequality violation and feasibility of their slacks, which are initialized using a recently proposed warmstart technique without any additional correction steps. Computational tests on instances of max-cut suggest that this new scheme is superior to solving only the final relaxation with all relevant cuts known in advance.
| Original language | English |
|---|---|
| Pages (from-to) | 743-750 |
| Number of pages | 8 |
| Journal | Electronic Notes in Discrete Mathematics |
| Volume | 36 |
| Issue number | C |
| DOIs | |
| Publication status | Published - Aug 2010 |
| Externally published | Yes |
ASJC Scopus Subject Areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics
Fingerprint
Dive into the research topics of 'An improved interior-point cutting-plane method for binary quadratic optimization'. Together they form a unique fingerprint.Cite this
Engau, A., Anjos, M. F., & Vannelli, A. (2010). An improved interior-point cutting-plane method for binary quadratic optimization. Electronic Notes in Discrete Mathematics, 36(C), 743-750. https://doi.org/10.1016/j.endm.2010.05.094