A Level-Set Approach for Solving Nonlinear Integer Optimization Problems

Killea, Ryan

Etd

A Level-Set Approach for Solving Nonlinear Integer Optimization Problems

公开 Deposited

This thesis studies new methods to explore and exploit the structure of nonlinear integer optimization problems to create a level set optimal structure for parameterized integer nonlinear optimization problems, conducive to rapid lookup and queries over a wide range of potential resource vectors. The value function is a function that maps resource vectors to their optimal objective function values. General integer nonlinear optimization problems are a class of optimization problems where a nonlinear function is optimized subject to inequality and equality constraints, with all variables being integers. Important subclasses include quadratic integer programs, as well as programs of higher functional order. These problem subclasses are in general NP-hard and so challenging to solve. Certain critical problem contexts, such as discretized model predictive control, disaster response, robust investment optimization, and dynamic energy market allocation, can both be extremely sensitive to time delays and benefit immensely from rapid retrieval of provably optimal results. Further, even in optimization domains where no such urgency exists, it is important from an applied perspective to be able to reason over the maximal values of an optimization problem to understand how it responds both to resource availability as well as to questions of how to best elicit improvements by changing resource levels. Such competing, compelling, demands of optimality and speed call for new methods that allow for fast lookup of provable, pre-computed optima to avoid longer wait times as new resource vector queries arrive. 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.

Creator