Data Science MS Thesis Defense | Ryan Killea | "A Level-Set Approach for Solving Nonlinear Integer Optimization Problems"

DATA SCIENCE 

MS Thesis Defense

Ryan Killea, MS Candidate

Thursday, July 27th, 2023 | 3:00PM - 4:00PM

Location: Morgan 208 Conference Room, Campus Center

Zoom: https://wpi.zoom.us/my/rbkillea

Thesis Committee:

Dr. Fabricio Murai, WPI

Dr. Andrew Trapp, WPI Advisor

Title: A Level-Set Approach for Solving Nonlinear Integer Optimization Problems

Abstract: This thesis contributes a new general solution approach to nonseparable, nonconvex, polynomial integer programs with separable constraints. Storing the value function in a way that allows its efficient maintenance and search during and after the incremental construction is proposed to accelerate the queries during and after construction. The problem is broken down into subproblems that incrementally add to a Minimal R∗ Tree(MR∗T) data structure new level set optimal vectors one at a time, building up and benefiting from a value function lower bound. New ways of directly comparing the upper bounds at these subproblem nodes to the existing value function lower bound are considered to improve the performance of the approach. The specific optimization routines used for the value function bounds at these subproblems are also tailored to the task of reasoning over a range of right-hand sides (equivalently, resource levels). Computational experiments explore solving a frequent problem of the applicable class – quadratic knapsack: nonseparable, nonconvex, polynomial knapsack problems with several linear constraints. For the considered problem class, reasoning over very large range of right-hand sides (on the order of hundreds of thousands), we demonstrate the ability to construct an optimal structure in as little as six to 35 conventional, state of the art (Gurobi) solver solves with a single right-hand side. Thus, for problems that are repeatedly solved over varying resource vectors, this promises substantial savings. Furthermore, sensitivity analysis results, unobtainable via conventional solver solves due to the lack of a strong integer dual, are easily recoverable from the optimal structure at a speed of < 2 milliseconds for even complex directional sensitivity queries. This thesis gives a first step in solving a broader context of optimization problems with a value function approach than previously possible.