n-step MIR Functions: Facets for Finite and Infinite Group Problems

Kiavash Kianfar (kkianfancsu.edu)
Yahya Fathi (fathincsu.edu)

Abstract: The n-step mixed integer rounding (MIR) functions are used to generate n-step MIR inequalities for (mixed) integer programming problems (Kianfar and Fathi, 2006). We show that these functions are sources for generating extreme valid inequalities (facets) for group problems. We first prove the n-step MIR function, for any positive integer n, generates two-slope facets for the infinite group problem, and then show under appropriate conditions on parameters, these functions also generate facets for the finite master cyclic group problem. We discuss that similar results are true for the group problems with continuous variables.

Keywords: Mixed Integer Rounding; Group Problem; Corner Polyhedron; Facet; Mixed Integer Programming

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Integer Programming (Cutting Plane Approaches )

Citation: Operations Research Technical Report 2006-2, North Carolina State University

Download:

Entry Submitted: 09/25/2006
Entry Accepted: 09/27/2006
Entry Last Modified: 10/26/2007

Modify/Update this entry