Modeling for Computation: Examples from Network Design

Thomas L. Magnanti

Dean, School of Engineering

Massachusetts Institute of Technology

In optimization, generally, and especially integer programming, the choice from alternative models can have a significant impact on the time to solve a given problem or even determine the viability of solving the problem at all.   This talk will illustrate the importance of modeling for effective computation through examples drawn from the field of network design.  For example, in one application--the design of a diameter-constrained minimum spanning tree--a commercial integer-programming solver was unable to solve a standard formulation of a modest-sized problem in over one week of computation, but could solve an alternative model in less than one second.