Research

Overview

Broadly speaking, my research is in the field of optimization. For example, the goal of a recent project was to develop a heuristic to support government entities in the Chesapeake Bay Watershed; given a fixed budget, the heuristic recommends a collection of management programs that minimize pollution runoff. Another current project seeks to determine the locations of amenities in urban areas so that access is more equitable across diverse racial groups to address the problems such as food deserts and access to election polling locations, for example.  Applied problems like these are recent additions to my research program, which I actively sought to generate opportunities for collaboration with midshipmen (Naval Academy students). 

Much of my research focus is on optimization methodology.  An optimization problem has the form:

  (P) minimize f(x)

       subject to x ∈ A,

where x is a vector of real-valued decision variables, f is a function of x that evaluates to a real number, and A is the set of values of x that represent feasible solutions. The feasible region A is described by a collection of algebraic statements (equations or inequalities) involving x, which can require that at least some of the coordinates of x must take integer values in a feasible solution. The statements that describe A are the constraints of P, and f is the objective function of P.  The requirement that the variables are mixed-integer, meaning that at least some of the decision variables must take integer values, is the key ingredient to problems that fall into my subfield: discrete optimization. 

Much of the current work in discrete optimization is targeted at Mixed-Integer NonLinear Optimization (MINLO) problems. In addition to having mixed-integer variables, these problems have nonlinear expressions in the objective function, the constraints, or both. Modern optimization software can handle either mixed-integer variables or nonlinearities very well, even for large scale problems. However, when both of these complicating factors are present in the same problem, i.e., MINLO, modern algorithms are challenged by even moderately sized problems, so there is a lot of room for improvement.  My methodological projects address specific modeling scenarios that occur in a wide range of optimization applications, with the goal of providing insight into handling these scenarios effectively in models and algorithms.

Volume to compare formulations

Algorithms for MINLO repeatedly solve subproblems in which a non-convex feasible region has been “relaxed” to a containing convex region (which is connected, by definition). It may be necessary to solve thousands of these (relaxed) subproblems on the way to solving the original MINLO problem. In either case, the way that the non-convex regions are relaxed, i.e., the selection of the formulation, impacts the overall speed of the algorithm. The general goal is to balance the tightness, or "strength", of the formulation with the simplicity of its description (i.e., the number and type of constraints and variables required).

In the presence of a linear objective, optimal solutions to these convex subproblems are located on the boundary of the feasible region, and so best practice in the context of MILO focuses on boundary characteristics. However, in the presence of a nonlinear objective function (in MINLO), an optimal solution could be anywhere in a convex feasible region. Therefore, the focus shifts away from the boundary and towards creating an enclosing convex region that is both small in volume and simply described. Usually, formulations are compared via computational experiments. My collaborators and I compare formulations analytically, using n-dimensional volume as a proxy for the strength of the formulation.  For example, see Volume MP and  BQP DAM.

Perspective reformulations

In a recent body of work we use volumetric analysis to gain insight into a common modeling scenario in which a binary variable, z, indicates whether another variable, x, is positive or zero.  If x is positive, x is constrained to a nonnegative closed interval [l, u], and has an associated convex cost, f(x). In a realistic application, there would be many x variables representing activities that have operating limits and costs (for example, financial portfolio selections). Each z variable indicates whether or not the associated x activity has been selected.  This scenario would typically be introduced to a MINLO solver by adding another variable, y, to a minimizing objective function to represent the cost associated with x. We would include the constraint y ≥ f(x) to algebraically connect y to the cost of x. 

Therefore, we are faced with the task of finding a tight, simply-defined connected, convex container for the 3-dimensional set of points (x, y, z) consisting of the origin (0, 0, 0) (representing the case that x is “off”), along with the 2-dimensional set in the plane z = 1 and “above” f(x) (representing the case that x is “on”).  This disjunctive region, which we call D, is shown below.