Analytic Centers Methods, Mixed Integer Programming and Variational Inequalities

Jean-Louis Goffin

Faculty of Management

McGill University

The most effective way to solve realistic MIPs (mixed integer programs) is branch and price, which is based on Lagrangean relaxation. Lagrangean relaxation provides better bounds than the traditional branch and bound method, which relax the integer requirement.

At every node of the B&B tree, a nondifferentiable convex function (NDO) needs to be optimized. The classical NDO techniques, such as the Dantzig-Wolfe decomposition algorithm or subgradient optimization, have weaknesses, such as unreliable convergence or the lack of a rigorous termination criterion. The analytic center cutting plane method (ACCPM) attempts to improve over this.

We will sketch a full branch and price method that uses extensions of ACCPM, including hot starts at the child nodes, using a dual Newton method.

Extensions of ACCPM to the case of quadratic or SDP cuts will also be reported. Theoretical results show that a central SDP cut can be added in O(p log p) Newton steps, where p is the dimension of the added SDP cut, while a central quadratic cut can be added in O(1) steps. A

use of this in solving monotone variational inequalities will also be alluded to.