Title: Interior-Point Methods for Integer Programming: heuristics and branch-and-cut

This talk focuses on the use interior point methods to solve integer programming problems.
In the first part, we present an interior-point branch-and-cut algorithm for structured integer programs based on Benders decomposition and the analytic center cutting plane method (ACCPM). The resulting algorithm is tested on two classes of problems: the capacitated facility location problem and the multicommodity capacitated fixed charge network design problem, and was found to outperform classical Benders decomposition, Benders decomposition with pareto optimal cuts, and Benders-based branch-and-cut.
In the second part, we present an algorithm for finding integer feasible solutions based on the notion of analytic centers. The algorithm searches along two line segments connecting the analytic center and two extreme points. Cuts related to the violated constraints are added to shift the analytic center until a feasible integer solution is found. Numerical testing shows that the algorithm finds good quality solutions.
(joint work with Joe Naoum-Sawaya)