Mixed-integer rounding (MIR) inequalities play a central role in the develo
pment of strong cutting planes for mixed-integer programs. In this paper, w
e investigate how known MIR inequalities can be combined in order to genera
te new strong valid inequalities.
Given a mixed-integer region S and a collection of valid "base" mixed-integ
er inequalities, we develop a procedure for generating new valid inequaliti
es for S. The starting point of our procedure is to consider the MIR inequa
lities related with the base inequalities. For any subset of these MIR ineq
ualities, we generate two new inequalities by combining or "mixing" them. W
e show that the new inequalities are strong in the sense that they fully de
scribe the convex hull of a special mixed-integer region associated with th
e base inequalities.
We discuss how the mixing procedure can be used to obtain new classes of st
rong valid inequalities for various mixed-integer programming problems. In
particular, we present examples for production planning, capacitated facili
ty location, capacitated network design, and multiple knapsack problems. We
also present preliminary computational results using the mixing procedure
to tighten the formulation of some difficult integer programs. Finally we s
tudy some extensions of this mixing procedure.