Title: Analytic centers methods, mixed integer programming and variational inequalities.

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 semi-definite 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.

Biography
The author was born in Brussels in July 1944, and graduated in Electrical Engineering at the Universit\'e Libre de Bruxelles, with a thesis that was, in retrospect, an optimization problem subject to semi-infinite constraints. He joined the IEOR department at Berkeley in 1967, on the outdated assumption that George Dantzig was there, and graduated in 1971, under the supervision of Richard Karp, with a thesis on "Solving Linear Inequalities by the Relaxation Method". He came to Montreal in 1972, when he joined HEC, and then moved to McGill in 1976, where he is a Professor in the Faculty of Management, and an associate member of the Department of Mathematics. He is a founding member of GERAD as well as an associate member of LOGILAB/Geneva. He was a visiting scholar at Stanford in 80--81, and a visiting professor at Louvain-la-Neuve (CORE) in 87--88.