Title: Analytic centers cutting plane methods and multilevel Lagrangean relaxation


			Jean-Louis Goffin
			McGill University
		  1001 Sherbrooke Street West, 
		Montreal, Quebec, H3A 1G5 Canada 
	      e-mail: jean-louis.goffin@.mcgill.ca



Abstract}


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 non-differentiable 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.

Many MIPs have a multi-stage structure; we will look at the
production--distribution example common in supply chain
optimization [plants, warehouses, customers]. A traditional
approach is to relax (i.e. dualize) most of the constraints so the
subproblems are easy to solve (i.e. knapsacks). This leads to weak
bounds and very large B&B trees.

The approach used here uses the multilevel or multistage structure
of the problem, and dualizes fewer constraints, leading to
subproblems that are CFLSS (Capacitated Facility Location with
Single Sourcing) which can be out of the reach of general purpose
solvers. Therefore these subproblems themselves need to be solved
by an ACCPM B&P approach, with now knapsack subproblems, leading
to a 3-level approach (B&P calling B&P calling Cplex).

This has been implemented, and works quite well on medium size
problems.

This is joint work with Prof. Elhedhli (U of Waterloo).