Mixed-integer Nonlinear Optimization: Problems and Solutions

Friday, August 12, 2016 - 11:00am - 12:30pm
Lind 305
Daniel Bienstock (Columbia University)
Many impactful problems in modern society involve engineering, mathematics, computing and, for lack of a better term, physics. An excellent example is given by the operation of modern power grids. Power grids are electrical circuits, and as such are governed by the laws of physics (namely Ohm's and Kirchhoff's laws), which take the form of bilinear equations (for example, power = current times voltage, and current times impedance = voltage drop). When operating a grid we can for example just control voltages -- how power flows across the grid depends on how our choice of voltages leverages the laws of physics. In addition, in operating a modern grid we have access to binary controls, such as the choice of turning off a given power line, so as to make power flow in a more economical fashion, or the decision as to shut-off a generator in the midst of a cascading blackout, in order to stop the cascade.

The combination of physics and binary choices, so as to attain the most desirable outcome, gives rise to optimization problems with nonlinear constraints plus binary variables that govern whether some features of the problem are present or not.

A consequence is that these problems prove quite challenging -- arguably, they are among the most difficult optimization problems, and the current state-of-the-art algorithms frequently prove insufficient. The challenges arise in several directions, including some unexpected, such as the need to deal with irrational numbers, but fundamentally it is the interplay of nonlinearities with nonconvexity that underlies the complexity.

Further, the underlying mathematics is quite elegant: for example it relates to classical topics in mathematics, such as algebraic geometry and Hilbert's 17th problem. It is fair to say that the study of these problems has a lot for everyone: nice mathematics, challenging intellectual puzzles and demanding computation.

Nonlinear, mixed-integer programming is now a topic of much interest and focus in the optimization community. In this talk we will review several applications of interest, and in the process discuss appropriate mathematical and computational techniques.
MSC Code: