Jesus De Loera; Chance-Constrained Convex Mixed-Integer Programs and Beyond.

Apr 26, 2016, 4pm
GUG 204
Jesus De Loera, UC Davis

Abstract:  Chance-constrained convex mixed integer optimization, a branch of stochastic optimization,  concerns convex mixed-integer programming problems in which constraints are imprecisely known but the problems need to be solved with a minimum probability of reliability or certainty.  Such problems arise quite naturally in many areas of finance (e.g., portfolio planning where losses should not exceed some risk threshold), telecommunication (services agreements where contracts require network providers to guarantee with high probability that packet losses will not exceed a certain percentage), and facility location (for medical emergency response stations, while requiring high probability of coverage overall possible emergency scenarios).

Such problems are notoriously difficult to solve, because the feasible region is often not convex and the exact probabilities can be hard to compute exactly. We propose a  sampling approach that overcomes those obstacles. We generalized a 2006 sampling algorithm of Calafiore-Campi’s  for continuous variables that reduces the problem to solving deterministic convex mixed integer programming.  A new generalization of Helly’s theorem is necessary to rigorously prove the sampling algorithms work as planned.

If time allows this talk will take a pick on the future of $S$-optimization theory, a powerful generalization of the traditional continuous, integer, and mixed-integer optimization, where now the variables take values in special proper subsets of $\R^d$. All new theorems are joint work with R. La Haye, D. Oliveros, E. Roldan-Pensado.