Abstract
In this paper, we consider the class of 0–1 integer problems and develop an effective cutting plane algorithm that gives valid inequalities called surrogate-RLT cuts (SR cuts). Here we implement the surrogate constraint analysis along with the reformulation–linearization technique (RLT) to generate strong valid inequalities. In this approach, we construct a tighter linear relaxation by augmenting SR cuts to the problem. The level-d SR closure of a 0–1 integer program is the polyhedron obtained by intersecting all the SR cuts obtained from RLT polyhedron formed over each set of d variables with its initial formulation. We present an algorithm for approximately optimizing over the SR closure. Finally, we present the computational result of SR cuts for solving 0–1 integer programming problems of well-known benchmark instances from MIPLIB 3.0.
| Original language | English |
|---|---|
| Pages (from-to) | 173-193 |
| Number of pages | 21 |
| Journal | Journal of Global Optimization |
| Volume | 66 |
| Issue number | 2 |
| DOIs | |
| Publication status | Published - 2016 Oct 1 |
Bibliographical note
Funding Information:This research was supported by Basic Science Research Program and Global Ph.D Fellowship Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (NRF-2012R1A1A2006847, NRF-2012H1A2A1005160).
Publisher Copyright:
© 2015, Springer Science+Business Media New York.
Keywords
- Cutting plane
- Integer programming
- Partial convexification cuts
- Reformulation–linearization technique
- Surrogate constraint analysis
- Surrogate-RLT cuts
ASJC Scopus subject areas
- Computer Science Applications
- Management Science and Operations Research
- Control and Optimization
- Applied Mathematics