Large-scale Optimization for Robust Multi-Class Prediction and Resource Allocation

In November of 2022, Earth's human population surpassed 8 billion. To support the day-to-day needs of our ever increasing population, large scale optimization can play a crucial role in making our resource-constrained urban systems robust and resilient to different sources of uncertainty. In this thesis we develop different optimization based methodologies to deal with uncertainty arising from data, first in the context of robust multi-class prediction and second for prescriptive analytics for medical resource allocation. In the first part of this thesis, we make progress on training a robust multi-class classifier using error-correcting output codes (ECOC). We propose linear and non-linear integer programming (IP) formulations for the codebook design problem. By making connections with graph-theory such as edge-clique covering and graph-coloring we develop tractable solutions approaches to both linear and non-linear IP formulations while maintaining low optimality gaps, estimated using Plotkin's bound. We provide extensive computational experiments on small class datasets including MNIST and CIFAR10. In the nominal setting, our IP-generated compact codebooks outperform commonly used large codebooks. Furthermore, in the adversarial setting, our IP-generated codebooks achieve non-trivial robustness. This is surprising due to three reasons: (1) We do not employ any {adversarial training}; (2) Most other codebooks (except Dense) do not exhibit any robustness even when they use more than twice the number of columns; (3) The robustness that we obtain is not simply because of the large network capacity. On large class datasets such as CIFAR100, Caltech-101 and Caltech-256, we leverage transfer-learning to overcome the large computational expense associated. We provide experiments under two different settings, first when the source classifier is nominally trained and second when it is adversarially trained. ECOC based classifiers achieve better classification performance in comparison to multiclass CNNs in both settings. These experiments indicate that our large-scale discrete optimization approaches for designing ECOC based classifiers can be extremely useful for robust operation of modern urban-systems. In second part of this thesis, we shift our focus from robust prediction to developing new tools for prescriptive analytics. We make progress on the problem of uncertainty informed medical resource (vaccine) allocation to a set of different sub-populations to control the spread of a pandemic such as Covid-19. The two major challenge CEE Dissertation Defense in this prescriptive analytics problem for resource allocation are: (1) To develop a principled data-driven approach to model and estimate uncertainty in ODE model parameters. (2) To develop tools to solve a largescale non-linear optimization problem which is constrained by non-linear ODE dynamics with uncertain parameters. We provide a data-driven approach to generate a tractable scenario set by first estimating the posterior distribution on the model parameters using Bayesian inference with Gaussian processes. Second, using kmeans clustering we reduce the number of samples in the posterior distribution to obtain the reduced scenarios et to achieve tractability in the uncertainty informed resource allocation optimization problem. Using the reduced scenario set, we provide the nominal and stochastic programming (i.e. uncertainty informed) based vaccine allocation optimization formulations. We develop a parallelized solution algorithm to efficiently solve both nominal and stochastic programming optimization problems. Importantly our scenario-set estimation procedure, optimization formulations and solution approach are all flexible in that they are not limited to any particular class of ODE models. This is in sharp contrast to literature, where most approaches are limited to only linear disease transmission models. We provide experiments with two different non-linear epidemiological ODE models under multiple different setups. Our computational experiments indicate that accounting for uncertainty in key epidemiological parameters can improve the efficacy of time-critical allocation decisions by 4-8%.

THESIS COMMITTEE:

Prof. Saurabh Amin (advisor)

Prof. Patrick Jaillet (committee chair)

Prof. John Williams