Thesis title: Decomposition Methods in Column Generation and Data-Driven Stochastic Optimization

Advisors:

George Nemhauser, Department of Industrial and Systems Engineering, Georgia Institute of Technology

Alejandro Toriello, Department of Industrial and Systems Engineering, Georgia Institute of Technology

Committee members:

Kibaek Kim, Mathematics and Computer Science Division, Argonne National Laboratory

Mathieu Dahan, Department of Industrial and Systems Engineering, Georgia Institute of Technology

Santanu Dey, Department of Industrial and Systems Engineering, Georgia Institute of Technology

Date and time: Monday, November 22, 2021, at 11:00 am (ET)

Location: https://bluejeans.com/458323584/5439

Abstract:

In this thesis, we are focused on tackling large-scale problems arising in two-stage stochastic optimization and the related Dantzig-Wolfe decomposition. We start with a deterministic setting, where we consider linear programs with a block-structure, but data cannot be stored centrally due to privacy concerns or due to being stored in a decentralized fashion. The larger portion of the thesis is dedicated to the stochastic setting, where we study two-stage distributionally robust optimization under the Wasserstein ambiguity set to tackle problems with limited data.

In Chapter 2, we propose a fully distributed Dantzig-Wolfe decomposition (DWD) algorithm using the Alternating Direction Method of Multipliers (ADMM) method. DWD is a classical algorithm used to solve large-scale linear programs whose constraint matrix is a set of independent blocks coupled with a set of linking rows. In a typical implementation, the algorithm alternates between solving a master problem centrally and a set of independent subproblems in parallel. In certain cases, solving the master problem centrally is undesirable or infeasible, due to privacy concerns or decentralized storage of data. In the former, the independent blocks represent agents who desire privacy of information. In the latter, data is stored in decentralized servers due to memory limitations, or as a protection against attackers or failures. To this end, we develop a consensus-based Dantzig-Wolfe decomposition algorithm, where the dual of the master problem is solved using consensus-based ADMM at each iteration. We discuss the benefits of using ADMM over other consensus methods and working on the dual over the primal problem, and detail the computational and algorithmic challenges. We provide bounds on the optimality gap and feasibility violation, and perform extensive computational experiments on instances of the cutting stock problem and synthetic instances using a Message Passing Interface (MPI) implementation, where we obtain high-quality solutions in reasonable time. Although our main contribution is to tackle decentralized storage of data and privacy, our method also shows a potential computational benefit for instances with a large number of variables.

In Chapter 3 and 4, we turn our focus to stochastic optimization, specifically applications where data is scarce and the underlying probability distribution is difficult to estimate. We study two-stage distributionally robust optimization (DRO) under the Wasserstein ambiguity set in different settings, where the Wasserstein set is a ball in the space of probability distributions centered at an empirical distribution obtained from historical data.

In Chapter 3, we consider two-stage conic DRO under the Wasserstein set with zero-one uncertainties. We are motivated by problems arising in network optimization, where binary random variables represent failures of network components. We are interested in applications where such failures are rare and have a high impact, making it difficult to estimate failure probabilities. Due to our support set being non-convex, we cannot use typical duality tools to obtain a tractable convex program. By using ideas from bilinear programming and penalty methods, we reformulate our two-stage DRO model by decomposing the inner maximization into a maximization problem for each sampled scenario over mixed-integer conic sets. We use Lovász-Schrijver approximations to get outer approximations of the convex hulls of the inner problems, permitting us to dualize and obtain a model which can be solved using commercial solvers. We illustrate the computational performance and out-of-sample performance of our method on the optimal power flow problem with random transmission line failures and a multi-commodity network design problem with random node failures.

In Chapter 4, we study a two-stage model which arises in natural disaster management applications, where the first stage is a facility location problem, deciding where to open facilities and pre-allocate resources, and the second stage is a fixed-charge transportation problem, routing resources to affected areas after a disaster. We solve a two-stage DRO model under the Wasserstein set to deal with the lack of available data. The presence of binary variables in the second stage significantly complicates the problem. We develop a column and constraint generation algorithm, where we generate scenarios as needed, and leverage the structure of our support set and second stage value function to efficiently generate new scenarios.  We show our results extend to the case where the second stage is a fixed-charge network flow problem. We end the chapter with computational experiments on synthetic instances and a case study of hurricane threats on the coastal states of the United States.