Generalized Mixed Integer Rounding Valid Inequalities for Mixed Integer Programming Problems

group problem;cutting planes;valid inequalities;mixed integer rounding;mixed integer programming

Kianfar, Kiavash ; Dr. Bibhuti Bhattacharyya, Committee Member,Dr. Yahya Fathi, Committee Chair,Dr. Shu-cherng Fang, Committee Member,Dr. Henry L. W. Nuttle, Committee Member,Kianfar, Kiavash ; Dr. Bibhuti Bhattacharyya ; Committee Member ; Dr. Yahya Fathi ; Committee Chair ; Dr. Shu-cherng Fang ; Committee Member ; Dr. Henry L. W. Nuttle ; Committee Member

University:North Carolina State University

关键词: group problem;    cutting planes;    valid inequalities;    mixed integer rounding;    mixed integer programming;   

Others  :  https://repository.lib.ncsu.edu/bitstream/handle/1840.16/5413/etd.pdf?sequence=1&isAllowed=y

美国|英语

来源: null

【 摘 要 】

Many decision-making problems in practice can be formulated as Mixed Integer Programming (MIP) problems, which are NP-hard in their general form. Over the past few decades, an enormous amount of research has been carried out to develop the theory and algorithms for solving MIP problems. Valid inequalities are a crucial part of these developments since they can be added to the MIP problem as cutting planes to tighten the feasible region of its linear programming relaxation toward the convex hull of its MIP solutions.Mixed Integer Rounding (MIR) is a fundamental approach to generating cutting planes for general MIP problems. Recently, MIR has received special attention from several researchers. MIR inequalities are obtained from facets of certain simple mixed integer sets (MIR facets). A significant contribution in this context has been the work by Dash and Gunluk (2006) who introduced the 2-step MIR inequalities. The work of Dash and Günlük is also one of the recent advancements in the area of valid inequalities related to Gomory's group problems. These problems are of special significance in the context of MIP because facets of their corresponding polyhedra are sources for generating valid inequalities for MIP problems.In this dissertation, we generalize the concept of MIR valid inequalities. Based on this generalization, we develop new families of MIR inequalities for general MIP problems and show that they define (new) facets for the finite and infinite group polyhedra, and hence are potentially strong cuts. More specifically, the contributions of this research are as follows:First, we show that MIR facets are not limited to 1-step or 2-step facets, but for any positive integer n, n facets of a certain (n+1)-dimensional mixed integer set can be obtained through a process which includes n consecutive applications of MIR. The last of these facets is of special importance and we call it the n-step MIR facet. As a result, we generate an infinite number of MIR facets (one for each n), which we then use to generate valid inequalities for MIP problems.Second, we develop a procedure which, for any n, uses the n-step MIR facet to generate a family of valid inequalities for the feasible set of a general MIP constraint. We refer to these as the n-step MIR inequalities. The well-known Gomory Mixed Integer Cut and the 2-step MIR inequality of Dash and Gunluk are simply the first two families corresponding to n=1,2, respectively. The n-step MIR inequalities are easily produced using closed-form periodic functions, which we call the n-step MIR functions. None of these functions dominates the other on its whole period.Third, we establish a significant connection between the n-step MIR functions and facets of Gomory's group polyhedra. We prove that for any n, the n-step MIR inequalities define new families of facets for the finite and the infinite group polyhedra, and hence are potentially strong cuts. Many of these facets are new facets that have not been introduced in the literature before.