Mixed integer programming heuristics

This report constitutes the Doctoral Dissertation for Christopher Wallace and is a collection of results on mixed integer programming heuristics that both find and improve feasible solutions.Chapter 1 focuses on local branching comparisons. Local branching is a MIP paradigm, proposed by Fischetti and Lodi, which takes the current best solution and restricts the search to a k-opt neighborhood to find improved solutions. Using local branching, eight algorithm schemes are compared on a variety of mixed integer programs.In Chapter 2 we discuss Pivot and Shift. Pivot and Shift is an extension to general mixed integer programming of Pivot and Complement, the well known 1980's heuristic for pure 0-1 programs. It is essentially a sophisticated rounding procedure, amended with two variants of a neighborhood search. The rounding takes the form of several pivot types meant to eliminate from the basis all integer-constrained variables while keeping the objective function value close to the LP optimum, followed by up and down shifts in the value of the nonbasic integer variables. The neighborhood search is akin to the local branching procedure. When Pivot and Shift is joined to an efficient MIP solver, the combined procedure finds better solutions faster than the MIP solver alone. The procedure has been tested on a multitude of test problems available from the literature or the web.Chapter 3 starts with a comparison of Pivot and Shift with The Feasibility Pump. The comparison leads to an area where possible pivots could be found when The Feasibility Pump reaches a local minimum before it attempts "flipping" to move away from the minimum. An experiment is then created to test combining the pivots with The Feasibility Pump. Lastly, it is shown that the combination creates an advantage over The Feasibility Pump alone, especially in a branch and bound setting where the heuristic would be applied to nodes with an ever decreasing upper bound cutoff.In Chapter 4 we introduce a new pure integer rounding heuristic, ZI Round, and compare this heuristic to recent extremely fast pure integer rounding heuristic Simple Rounding. Simple Rounding was introduced in the non-commercial code SCIP. ZI Round attempts to round each fractional variable while using row slacks to maintain primal feasibility. We use the MIPLIB 2003 library for the test set. The average time in our run per instance for both Simple Rounding and ZI Round was 0.8 milliseconds. ZI Round found more feasible solutions with the same or better objective value than Simple Rounding. Also, the average time to solve the lp relaxation per instance was 2.2 seconds so these two rounding heuristics are several magnitudes faster than other heuristics which must use the lp solver, including diving heuristics. We also show that ZI Round performs well on both a set covering class and a railway crew scheduling class.Both Chapter 2 and Chapter 4 use as part of the test library a set covering problem that arises from computing the 1-width of the incidence matrix of Steiner triples. This series of problems has been very difficult to solve. In fact, after fifty years the largest solved instance has only 243 variables. In Chapter 5 we show: a monotone increasing lower bound, find a new lower upper bound improving on the 1979 bound found by Avis, prove additional properties which might help to find the actual bound, and give two conjectures of possible interest.