Surrogate-RLT cuts for zero-one integer programs

Yuh, Junsang; Lee, Youngho
October 2016
Journal of Global Optimization;Oct2016, Vol. 66 Issue 2, p173
Academic Journal
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.


Related Articles

  • Global optimization of general nonconvex problems with intermediate polynomial substructures. Zorn, Keith; Sahinidis, Nikolaos // Journal of Global Optimization;Jul2014, Vol. 59 Issue 2/3, p673 

    This work considers the global optimization of general nonconvex nonlinear and mixed-integer nonlinear programming problems with underlying polynomial substructures. We incorporate linear cutting planes inspired by reformulation-linearization techniques to produce tight subproblem formulations...

  • Disjunctive programming and relaxations of polyhedra. Conforti, Michele; Del Pia, Alberto // Mathematical Programming;Apr2014, Vol. 144 Issue 1/2, p307 

    Given a polyhedron $$L$$ with $$h$$ facets, whose interior contains no integral points, and a polyhedron $$P$$, recent work in integer programming has focused on characterizing the convex hull of $$P$$ minus the interior of $$L$$. We show that to obtain such a characterization it suffices to...

  • An Efficient Imperialist Competitive Algorithm for Solving the QFD Decision Problem. Ji, Xue; Gao, Qi; Yin, Fupeng; Guo, Hengdong // Mathematical Problems in Engineering;11/7/2016, p1 

    It is an important QFD decision problem to determine the engineering characteristics and their corresponding actual fulfillment levels. With the increasing complexity of actual engineering problems, the corresponding QFD matrixes become much huger, and the time spent on analyzing these matrixes...

  • A branch and bound method for the solution of multiparametric mixed integer linear programming problems. Oberdieck, Richard; Wittmann-Hohlbein, Martina; Pistikopoulos, Efstratios // Journal of Global Optimization;Jul2014, Vol. 59 Issue 2/3, p527 

    In this paper, we present a novel algorithm for the solution of multiparametric mixed integer linear programming (mp-MILP) problems that exhibit uncertain objective function coefficients and uncertain entries in the right-hand side constraint vector. The algorithmic procedure employs a branch...

  • A geometric approach to cut-generating functions. Basu, Amitabh; Conforti, Michele; Di Summa, Marco // Mathematical Programming;Jun2015, Vol. 151 Issue 1, p153 

    The cutting-plane approach to integer programming was initiated more than 40 years ago: Gomory introduced the corner polyhedron as a relaxation of a mixed integer set in tableau form and Balas introduced intersection cuts for the corner polyhedron. This line of research was left dormant for...

  • AN APPROACH FOR THE OPTIMAL SOLUTION OF MILP PROBLEMS. Ubale, P. V. // Bulletin of Pure & Applied Sciences-Mathematics;Jul-Dec2012, Vol. 31E Issue 2, p169 

    This paper describes an algorithm for finding solutions to optimization problems in which some of the variables must take integer values. The solution of discrete optimization problem to optimality is often an immense job requiring very efficient algorithm. In this paper we describe a Branch and...

  • Reentrant Flow Shop Scheduling considering Multiresource Qualification Matching. Chu, Feng; Liu, Ming; Liu, Xin; Chu, Chengbin; Jiang, Juan // Scientific Programming;7/9/2018, p1 

    With the development of technology and industry, new research issues keep emerging in the field of shop scheduling. Most of the existing research assumes that one job visits each machine only once or ignores the multiple resources in production activities, especially the operators with skill...

  • Hybrid Algorithm for Network Design Problem with Uncertain Demands. Roupec, Jan; Popela, Pavel; Hrabec, Dusan; Novotny, Jan; Olstad, Asmund; Haugen, Kjetil // Proceedings of the World Congress on Engineering & Computer Scie;2013, p1 

    The purpose of the paper is to present a hybrid algorithm to solve a transportation optimization model with random demand parameters and network design variables. At first, the classical deterministic linear transportation model with network design 0-1 variables is introduced. Then, randomness...

  • A matheuristic approach for the two-machine total completion time flow shop problem. Della Croce, Federico; Grosso, Andrea; Salassa, Fabio // Annals of Operations Research;Feb2014, Vol. 213 Issue 1, p67 

    This paper deals with the two-machine total completion time flow shop problem. We present a so-called matheuristic post processing procedure that improves the objective function value with respect to the solutions provided by state of the art procedures. The proposed procedure is based on the...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics