CUTS WHICH DO NOT CONFORM TO THE TEMPLATE PARADIGM FOR GENERAL MIXED INTEGER PROBLEMS

Mixed integer (linear) programming (or MIP), are optimization problems in which the objective function and all the constraints are linear, and where some or all variables are restricted to have integer or discrete values.

The strength of the MIP modeling paradigm has been recognized almost from the beginning of its introduction, but it has been the developments of the last 20 years that has truly made it an applicable one. Nowadays it is used in a wide spectrum of applications, from the classic airline scheduling problem, passing through combinatorial auctions, and planning in general.

The standard approach to solve MIP problems is a mixture of two algorithms. The first algorithm was introduced by Lang and Doig [LD60] and further improved by Little et al. [LMSK63] and Dakin [Dak65], and is commonly known as the branch-and-bound algorithm. The second algorithm, introduced by Dantzig, Fulkerson and Johnson [DFJ54], is known as the cutting plane algorithm. The resulting hybrid method is known as the branch-and-cut algorithm, and is arguably the most successful approach to-date to tackle general MIP problems.

An interesting new approach to the cutting-generation procedure for the traveling salesman problem (TSP) was introduced by Applegate et al. [ABCC95, ABCC01, ABCC03]. They introduce a procedure to generate cuts that relies on the equivalence between optimization and separation to get cuts resulting from small GTSP problems that are the result of a mapping of the original problem. This methodology to find cuts for the TSP allowed the authors to greatly improve both the total running time on all instances (by 26% on medium size instances, and by over 50% on larger instances), increase the number of problems solved at the root node of the branch and cut procedure (from 42 without using local cuts, to 66), and also to solve the then largest TSP instances with 13,509 and 15,112 cities respectively.

As part of the author’s Ph.D. thesis [Esp06], this technique was extended to general mixed integer problems. This extension include a precise definition of a mapping function and space where the actual separation is performed, and conditions under which we can guarantee the algorithm to find a violated valid cut for the problem. Preliminary computational experiments hints that this approach may have a positive impact on general MIP. This feeling is reinforced by the spectacular success of this approach on the traveling salesman problem, one of the most studied and well known N P -complete problem.

The first objective of this research project is to find mappings that generate strong cuts based both on optimal tableau information and on the integer structure underlying each problem, using for example information from the conflict graph associated with pure 0-1 integer problems.

The second objective of this research is to test these ideas on commercially available software for MIP problems such as CPLEX or XPRESS to assess its potential usability in practice, using the problems on the MIPLIB collection and randomly generated problems as our test set.