Mixed Integer Nonlinear Optimization: Formulation and Computation

Qie He
Seminar

Mixed-integer nonlinear optimization (MINO) is a powerful modeling tool for design and operation of complex systems such as the power grid and transportation network. To make the MINO model tractable, however, requires a good understanding of the optimization theory, algorithm, and computation in addition to the underlying problem structure. We illustrate that through two examples. The first example is a vehicle routing problem which attracts extensive attentions recently in green logistics. All the algorithms for the problem in the literature are based on heuristics or meta-heuristics. We approach this problem in two different ways. We first solve a special case by a branch-and-price algorithm. The size of the instances that we solve doubles that reported in the literature. We then formulate the problem as a mixed integer convex program, and solve it exactly by a branch-and-cut algorithm. The second example is motivated by cancer treatment planning and closely related to nonlinear switched systems in control theory. We model the problem as an MINO with ordinary-differential-equation constraints, and then obtain solutions by solving an approximate mixed integer linear program.