Accession Number:

AD1021103

Title:

Reduce-and-Split Cuts: Improving the Performance of Mixed Integer Gomory Cuts

Descriptive Note:

Journal Article - Open Access

Corporate Author:

Carnegie Mellon University Pittsburgh United States

Report Date:

2005-11-01

Pagination or Media Count:

23.0

Abstract:

Mixed integer Gomory cuts have become an integral part of state-of-the-art software for solving mixed integer linear programming problems. Therefore, improvements in the performance of these cutting planes can be of great practical value. In this paper we present a simple and fast heuristic for improving the coefficients on the continuous variables in the mixed integer Gomory cuts. This is motivated by the fact that, in a mixed integer Gomory cut, the coefficient of an integer variable lies between 0 and 1, whereas for a continuous variable, there is no upper bound. The heuristic tries to reduce the coefficients of the continuous variables. We call the resulting cuts reduce-and-split cuts. We found that, on several test problems, reduce-and-split cuts can substantially enhance the performance of a branch-and-bound algorithm.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE