Constraint classification, preprocessing and a branch and relax approach to solving mixed integer programming models

Preprocessing in Integer Programming (IP) is acknowledged to be an analytical as well as a logical approach towards resolving many practical IP problems. The effectiveness of IP preprocessing depends heavily on how it exploits the structure of a single or a group of constraints to which it is applied. Identification of certain well-known constraint classes also helps to generate specialized restrictions, which are known to speed up the solution process. In this paper we set out a comprehensive classification of constraints found in a wide range of practical Mixed Integer Programming (MIP) problems. Through an initial preanalysis we identify known structures in the model. We also apply preprocessing at each node to tighten bounds and reduce the subproblems. To take advantage of the structure identification we have extended the branch and bound (B&B) procedure, so that in addition to imposing bounds on variables we can also relax constraints. Experimental results for the well-known set of MIPLIB models as well as other industrial MIP models are given. These results summarize the structure of the models and also illustrate the effectiveness of preprocessing and post-processing in speeding up the solution process within a branch-fix-and-relax paradigm for the tree search.