Sourabh K. Choudhary
PhD Candidate in OR
ISyE, Georgia Tech

Thesis Committee
1 Dr. Nick Sahinidis (ISYE, Georgia Tech) (Advisor)
2 Dr. Santanu Dey (ISYE, Georgia Tech) (Advisor)
3 Dr. Oktay Gunluk (ISYE, Georgia Tech)
4 Dr. Alejandro Toriello (ISYE, Georgia Tech)
5 Dr. Joseph Scott (ChBE, Georgia Tech)

Abstract
Many real-world decision problems can be formulated as mixed-integer nonlinear programs (MINLPs), but solving such problems to high quality remains challenging due to nonconvexities, combinatorial structure, and large-scale formulations. This dissertation investigates how linear programming (LP) and mixed-integer linear programming (MILP) techniques can be leveraged to address difficult classes of nonconvex optimization problems.

First, I examine binary polynomial optimization (BPO) through the lens of structural sparsity. In particular, I develop LP formulations based on treewidth of the underlying graph structure, showing how exploiting problem structure can lead to smaller LP equivalents.

Next, I study water network optimization problems, which are important in the design and operation of infrastructure systems and are often modeled as difficult nonconvex MINLPs. I show how mixed integer linear reformulations and MILP-guided strategies can help produce strong feasible solutions and improve computational tractability on these practically relevant instances.

Finally, I present a primal heuristic for MINLP, called Contraction Aided Search (CAS), which uses solutions of mixed-integer linear relaxations/approximations to guide the search for high-quality feasible solutions of the original mixed integer nonlinear problem. The approach is particularly effective for challenging mixed-integer quadratically constrained quadratic programs (MIQCQPs), where finding strong feasible solutions early can improve solvers' practical performance.

Overall, this dissertation highlights the power of LP- and MILP-based methods as a unifying framework for tackling challenging nonconvex optimization problems.