Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

More than 50 years of development have made mixed integer linear programming (MILP) an extremely successful tool. MILP’s modeling flexibility allows it describe a wide range of problems in business, engineering, science and statistics. Furthermore, while MILP is NP-hard, many of these problems are routinely solved in practice thanks to state-of-the-art solvers that nearly double their machine-independent speeds every year. Inspired by this success, the last decade has seen a surge of activity on the solution and application of mixed integer convex programming (MICP), which extends MILP’s versatility by allowing the use of convex constraints in addition to linear inequalities. In this talk we cover various recent developments concerning theory, algorithms and computation for MICP. In particular, given that solvers for MICP can be significantly more effective than those for more general non-convex optimization, one question we consider is that of "MICP representability": what classes of non-convex constraints can be modeled through MICP?

With regards to MICP representability we start by giving the first precise characterization of MICP representability with bounded integer variables. We then focus on general MICP representability with unbounded integer variables by presenting simple impediments to general MICP representability, considering regularity properties of general MICP representable sets, and discussing the role of irrational unbounded directions on this regularity. Finally, we cover various topics concerning the modeling and computational solution of MICP problems using the Julia programming language and the JuMP modeling language for optimization. In particular, we show how mixed integer optimal control problems where the variables are polynomials can be easily modeled and solved by seamlessly combining several Julia packages and JuMP extensions with the Julia-written MICP solver Pajarito.