TITLE: Solving Mixed-Integer Nonlinear Problems: the Non-Convex Case

SPEAKER: Pietro Belotti, Ph.D. ,Postdoctoral Fellow
Tepper School of Business
Carnegie Mellon University

DATE / TIME: Thursday, March 20, 2008 / 1:30 - 2:30 p.m.

LOCATION: Room 451 Mohler Lab, 200 W. Packer Avenue

ABSTRACT: Mixed-Integer Nonlinear Programming (MINLP) problems are ubiquitous in Engineering, Finance, and Bioinformatics among others. The general, non-convex case admits multiple local minima and the global optimum is sought.

I will present a branch&bound for non-convex MINLPs, whose key components are: a linearization technique for factorable problems, to obtain lower bounds; a heuristic to find feasible solutions; bound tightening methods, to reduce the solution space; and branching rules to reduce the integrality and the non-convexity gap.

The implementation of this branch&bound is called Couenne (Convex Over- and Under Envelopes for Nonlinear Estimation). It is available as Open Source software from Coin-OR (http://www.coin-or.org) and it relies on other Open Source software such as Cbc, Ipopt, and Bonmin. Preliminary tests on publicly available MINLP instances will be discussed.


BIOGRAPHY: Pietro Belotti got a PhD in Operations Research at the Dept. of Electronics and Computer Science of the Technical University of Milan in 2003, with a dissertation on the design of survivable telecommunication networks. He then worked on Robust Network Optimization as a postdoc in the same University. Since 2006 he is a postdoctoral fellow at the Tepper School of Business, Carnegie Mellon University, Pittsburgh. He is currently working on a joint project with IBM for the development of Open Source software for Mixed-Integer Nonlinear Programming.