##### Bank accounts, submodular set functions, and location problems

**Abstract:**

In this presentation I will make a tour through some important algorithmic results for facility location problems, starting with the seminal paper by

Cornuéjols, Fisher, and Nemhauser from 1977.

##### Exact robust counterparts of ambiguous stochastic Constraints under mean and dispersion information

**Abstract:**

In this talk, we will study optimization problems with ambiguous stochastic constraints where only partial information consisting of means and dispersion measures of the underlying random parameter is available. Whereas the past literature used the variance as the dispersion measure, here we use the mean absolute deviation from the mean (MAD). The approach is based on the availability of *tight *upper and lower bounds on the expectation of a convex function of a random variable, first discovered in 1972. We then use these bounds to derive exact robust counterparts of expected feasibility of convex constraints and to construct new safe tractable approximations of chance constraints. We test the applicability of the theoretical results numerically on various practical problems in Operations Research and Engineering.

##### Sparse Linear Regression and Optimal Trees using Convex and Mixed Integer Optimization

**Abstract:**

Convex and mixed integer optimization have witnessed revolutionary advances in the last 30 years in no small measure due to the contributions of Arkady and George. In the same period the field of machine learning has advanced using heuristic algorithms.

Using convex and integer optimization methods pioneered by Arkady and George I present modern optimization based approaches for two of the most significant problems in ML: Sparse linear regression and classification and regression trees.

We reformulate the problem of sparse regression, as a convex binary optimization problem using convex optimization methods and we solve it using cutting planes. We show that our approach solves sparse regression problems to provable optimality with number of points n=100,000 and number of variables p=100,000 in seconds that is faster than the principal heuristic method of Lasso. The ability to solve problems in these dimensions allows us to observe three phase transition phenomena: in running time, in accuracy and in the false alarm rate. There is a threshold nt, such that for n> nt the running time is in seconds the solution recovers 100% of the true signal and the false alarm rate is 0%, that is exact sparse regression recovers the truth and only but the truth. In contrast Lasso also recovers 100% of the true signal but for n> n1 > nt but with positive false alarm rate. For n < nt our approach takes a significant amount of time to solve the problem, but it does not recover the true signal. The phase transition in time is contrary to traditional complexity theory which suggests that the difficulty of a problem increases with problem size, while the sparse regression problem becomes easier with increasing n.

We present optimal trees for classification and regression solved by CART heuristically. We present optimal solutions that partition the space using both partitions parallel to the axis as well as using hyperplanes. We show that surprisingly in a large number of real-world problems a single optimal tree outperforms random forests and boosted trees.

##### Attacking NP-hard Problems

**Abstract:**

A prominent theme of George Nemhauser’s research has been the study of computational tools to attack NP-hard models in discrete optimization. We highlight this aspect of George’s work, discussing current techniques,

results, and research directions.