View article

In this paper, we discuss the use of mixed integer rounding (MIR) inequalities to solve mixed integer programs. MIR inequalities are essentially Gomory mixed integer cuts. However, as we wish to use problem structure, we insist that MIR inequalities be generated from constraints or simple aggregations of constraints of the original problem. This idea is motivated by the observation that several strong valid inequalities based on specific problem structure can be derived as MIR inequalities.

Here we present and test a separation routine for such MIR inequalities that includes a heuristic row aggregation procedure to generate a single knapsack plus continuous variables constraint, complementation of variables, and finally the generation of an MIR inequality. Inserted in a branch-and-cut system, the results suggest that such a routine is a useful additional tool for tackling a variety of mixed integer programming problems.