Surrogate-RLT cuts for zero–one integer programs

详细信息    查看全文

• 作者：Junsang Yuh ; Youngho Lee
• 关键词：Integer programming ; Cutting plane ; Reformulation–linearization technique ; Surrogate constraint analysis ; Partial convexification cuts ; Surrogate ; RLT cuts
• 刊名：Journal of Global Optimization
• 出版年：2016
• 出版时间：October 2016
• 年：2016
• 卷：66
• 期：2
• 页码：173-193
• 全文大小：502 KB
• 刊物类别：Business and Economics
• 刊物主题：Economics
  Operation Research and Decision Theory
  Computer Science, general
  Real Functions
  Optimization
  
• 出版者：Springer Netherlands
• ISSN：1573-2916
• 卷排序：66

文摘

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.