Many management problems can be formulated as integer programs. These formulations have become more practical recently due to great improvements made in the last five years in commercial software to solve mixed integer linear programs. The best current software packages use a combination of techniques, including enumeration (branch-and-bound) and several types of cutting planes.
In particular, mixed integer Gomory cuts play a major role in in state-of-the-art software for solving mixed integer linear programs.
Therefore, any improvements in the performance of these cutting planes is of great practical value. In joint work with Kent Andersen and Yanjun Li, we develop a simple and fast heuristic for improving the characteristics of mixed integer Gomory cuts on the continuous variables. This is motivated by the fact that, in a mixed integer Gomory cut, the coefficient of an integer constrained 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 found that, on several test problems, these improved cuts can substantially enhance the performance of a branch-and-bound algorithm.
Another issue in integer programming is that the computing time is highly variable, depending on the instance. In joint work with Miroslav Karamanov and Yanjun Li, we show that the time needed to solve mixed integer programming problems by branch-and-bound can be roughly predicted early in the solution process. We construct a procedure that can be implemented as part of an MIP solver. It is based on analyzing the partial tree resulting from running the algorithm for a short period of time, and modeling the whole tree. The procedure is tested on instances from the literature. This was inspired by the practical applicability of such a result.