MIT IAP Software Tools for Operations Research 2013: Integer Programming Callbacks

The Operations Research Center offered a new course this IAP, 15.S60 SSIM: Software Tools for Operations Research. The course consisted of the following modules (as summarized by Iain Dunning here):

• introductory and advanced classes on R (Allison O’Hair, Andre Calmon, John Silberholz),
• data visualization (Virot Chiraphadhanakul),
• using Python for mathematical modelling (Iain Dunning),
• convex optimization (Vishal Gupta),
• distributed computing for optimization (John Silberholz),
• customizing integer programming solvers with callbacks (me).

The tutorial I gave has a self contained wiki that is available to the public here. Briefly, the tutorial covered the following topics for MIP:

• Good object oriented design for integer programming
• Separation over exponentially many constraints with User Cuts (UserCutCallback) and Lazy Constraints (LazyConstraintCallback)
• Giving CPLEX a starting solution (addMIPStart)
• Generating integer solutions during branch and bound with a construction heuristic (HeuristicCallback)
• Improving integer solutions found by CPLEX during branch and bound with an improvement heuristic (IncumbentCallback with HeuristicCallback)
• Profiling and testing for IP solvers

The traveling salesmen problem is used as a running example. The implementation uses the Java interface to CPLEX.