Oktay Günlük

A robust-to-dynamics optimization (RDO) problem is an optimization problem specified by two pieces of input: (i) a mathematical program (an objective function [ ] and a feasible set [ ]) and (ii) a dynamical system (a map [ ]). Its goal is to minimize f over the set [ ] of initial conditions that forever remain in [ ] under g. The focus of this paper is on the case where the mathematical program is a linear program and where the dynamical system is either a known linear map or an uncertain linear map that can change over time. In both cases, we study a converging sequence of polyhedral outer approximations and (lifted) spectrahedral inner approximations to [ ]. Our inner approximations are optimized with respect to the objective function f, and their semidefinite characterization—which has a semidefinite constraint of fixed size—is obtained by applying polar duality to convex sets that are invariant under (multiple) linear maps. We characterize three barriers that can stop convergence of the outer approximations to [ ] from being finite. We prove that once these barriers are removed, our inner and outer approximating procedures find an optimal solution and a certificate of optimality for the RDO problem in a finite number of steps. Moreover, in the case where the dynamics are linear, we show that this phenomenon occurs in a number of steps that can be computed in time polynomial in the bit size of the input data. Our analysis also leads to a polynomial-time algorithm for RDO instances where the spectral radius of the linear map is bounded above by any constant less than one. Finally, in our concluding section, we propose a broader research agenda for studying optimization problems with dynamical systems constraints, of which RDO is a special case. Funding: O. Günlük was partially supported by the Office of Naval Research [Grant N00014-21-1-2575]. This work was partially funded by the Alfred P. Sloan Foundation, the Air Force Office of Scientific Research, Defense Advanced Research Projects Agency [Young Faculty Award], the National Science Foundation [Faculty Early Career Development Program Award], and Google [Faculty Award].

Leveraging Dantzig–Wolfe Decomposition in the Original Variable Space for Mixed-Integer Programming Dantzig–Wolfe decomposition has been extensively applied to solve large-scale mixed-integer programs with decomposable structures, leading to exact solution approaches, such as branch and price. However, these approaches would require solving the problem in an extended variable space and are not readily present in off-the-shelf solvers. In “Recovering Dantzig–Wolfe Bounds by Cutting Planes,” Chen, Günlük, and Lodi propose a computational effective approach for generating cutting planes from Dantzig–Wolfe decomposition to enhance branch and cut in the space of original variables. The proposed approach requires a relatively small number of cutting planes to recover the strength of the Dantzig–Wolfe dual bound and should be easy to implement in general-purpose mixed-integer programming solvers. The authors show that these cutting planes typically lead to a formulation with lower dual degeneracy and hence, a better computational performance than naïve approaches, such as the objective function cut.

We study the warehouse problem, arising in the area of inventory management and production planning. Here, a merchant wants to decide an optimal trading policy that computes quantities of a single commodity to purchase, store and sell during each time period of a finite discrete time horizon. Motivated by recent applications in energy markets, we extend the models by Wolsey and Yaman (2018) and Bansal and Günlük (2023) and consider markets with multiple vendors and a more general form of the complementarity constraints. We show that these extensions can capture various practical conditions such as surge pricing and discounted sales, ramp-up and ramp-down constraints and batch pricing. We analyze the extreme points of the underlying non-linear integer program and provide an algorithm that exactly solves the problem. Our algorithm runs in polynomial time under reasonable practical conditions. We also show that the absence of such conditions renders the problem NP-Hard.

Dantzig-Wolfe (DW) decomposition is a well-known technique in mixed-integer programming (MIP) for decomposing and convexifying constraints to obtain potentially strong dual bounds. We investigate cutting planes that can be derived using the DW decomposition algorithm and show that these cuts can provide the same dual bounds as DW decomposition. More precisely, we generate one cut for each DW block, and when combined with the constraints in the original formulation, these cuts imply the objective function cut one can simply write using the DW bound. This approach typically leads to a formulation with lower dual degeneracy that consequently has a better computational performance when solved by standard MIP solvers in the original space. We also discuss how to strengthen these cuts to improve the computational performance further. We test our approach on the Multiple Knapsack Assignment Problem and the Temporal Knapsack Problem, and show that the proposed cuts are helpful in accelerating the solution time without the need to implement branch and price.

This paper considers the learning of Boolean rules in disjunctive normal form (DNF, OR-of-ANDs, equivalent to decision rule sets) as an interpretable model for classification. An integer program is formulated to optimally trade classification accuracy for rule simplicity. We also consider the fairness setting and extend the formulation to include explicit constraints on two different measures of classification parity: equality of opportunity and equalized odds. Column generation (CG) is used to efficiently search over an exponential number of candidate rules without the need for heuristic rule mining. To handle large data sets, we propose an approximate CG algorithm using randomization. Compared to three recently proposed alternatives, the CG algorithm dominates the accuracy-simplicity trade-off in 8 out of 16 data sets. When maximized for accuracy, CG is competitive with rule learners designed for this purpose, sometimes finding significantly simpler solutions that are no less accurate. Compared to other fair and interpretable classifiers, our method is able to find rule sets that meet stricter notions of fairness with a modest trade-off in accuracy.

This paper studies an open question in the warehouse problem where a merchant trading a commodity tries to find an optimal inventory-trading policy to decide on purchase and sale quantities during a fixed time horizon in order to maximize their total pay-off, making use of fluctuations in sale and cost prices. We provide the first known polynomial-time algorithms for the case when there are fixed costs for purchases and sales, optional complementarity constraints that prohibit purchasing and selling during the same time period, and bounds on purchase and sales quantities. We do so by providing an exact characterization of the extreme points of the feasible region and using this to construct a suitable network where a min-cost flow computation provides an optimal solution. We are also able to provide polynomial extended linear formulations for the original feasible regions. Our methods build on the work by Wolsey and Yaman (Discrete Optimization 2018). We also consider the problem without fixed costs and provide a fully polynomial time approximation scheme in a setting with time-dependent bounds.