In this paper we study an exact separation algorithm for mixed knapsack sets with the aim of evaluating its effectiveness in a cutting plane algorithm for Mixed-Integer Programming. First proposed by Boyd in the 90’s, exact knapsack separation has recently found a renewed interest. In this paper we present a “lightweight” exact separation procedure for mixed knapsack sets and perform a computational experience on a wide set of mixed-integer programming instances from MIPLIB 2003 and “Mittleman” sets. Computational experiments confirm that MIR inequalities are the most important class of valid inequalities form a computational viewpoint. Nevertheless there are several difficult instances where exact separation is able to further raise lower bounds.
Citation
Working paper