Seminar
Tight Linear Relaxations with Emphasis on the Quadratic Assignment Problem, Warren Adams, Clemson University, Fri, 20 May, 2009, 10:00 a.m. A-233
Abstract
Many difficult engineering optimization problems are combinatorial in nature. Classical examples abound in facility layout, machine sequencing, production scheduling, and capital budgeting. These problems are often formulated as mixed-integer programs (MIPs) that contain both discrete and continuous variables.
This talk focuses on obtaining attractive formulations of MIPs. While two different forms can accurately depict the same physical scenario, the mathematical structures can promote solution strategies with vastly different efficiencies. Desirable attributes will be discussed, as well as reformulation strategies for obtaining representations that possess such attributes. Then attention will be placed on a specific instance known as the quadratic assignment problem. This problem is arguably the most classical discrete nonlinear 0-1 program in the operations research literature, having many important applications. However, while it was first introduced over 50 years ago in the context of facility layout and location, it has resisted exact solution strategies. We will discuss reformulations of this problem, analyze methods for exploiting inherent special structures, and provide computational experience to compare these formulations with published works.