(599r) Logic Cuts for Strengthening the Relaxation Gaps of Network Planning Problems

An important problem in solving mixed-integer programming problems is the closure of the relaxation gap to verify optimality of the solutions. It is well known that the initial relaxation gap is very critical in closing the relaxation gaps for hard problems using branch-and-bound and branch-and-cut algorithms. Different methods have been adopted for generic mixed-integer programming problems to strengthen the relaxation gaps in the literature such as Gomory cuts and mixed-integer rounding inequalities. These methods are shown to be useful in some cases; however they do not yield a much stronger relaxation for most of the hard problems due to the fact that they do not consider the special structure of the problem. In this talk, we present an approach to generate logic cuts that are specific to problem structure. We illustrate the details of the cut generation procedure for the network planning problems. We test the performance of the generated cuts on a large variety of test problems that are generated randomly. The results indicate that the initial relaxation gap can be reduced significantly resulting in several orders of magnitude reductions in the total CPU time to find the optimal solution.