Assortment optimization selects a subset of items to maximize expected revenue under a discrete choice model and is widely used in revenue management and online platforms. Its combinatorial nature creates a practical tension among generality, scalability, and provable guarantees: model-specific algorithms can be strong when their structural assumptions hold, but are hard to adapt across … Read more
The Precedence Constrained Knapsack Problem (PCKP) asks for a maximum-profit subset of items, subject to a knapsack capacity constraint and precedence constraints encoded by a directed acyclic graph. We study the structure of optimal solutions of the Linear Programming (LP) relaxation of the natural Integer Linear Programming formulation of the PCKP. We introduce the notion … Read more
We study exact semidefinite programming (SDP) relaxation for a given sparse quadratically constrained quadratic program (QCQP). The SDP relaxation is exact if, whenever it has an optimal solution, it admits a rank-at-most-one optimal solution that corresponds to an optimal solution of the QCQP. Using the maximal cliques of a chordal extension of the aggregate sparsity … Read more
We present the Quadratic-Quasi-Newton (QQN) algorithm, a novel optimization method that combines gradient descent and quasi-Newton directions through quadratic interpolation. QQN constructs a parametric path d(t) = t(1 − t)(−∇f) + t 2 d L-BFGS and performs univariate optimization along this path, creating an adaptive interpolation that requires no additional hyperparameters beyond those of its … Read more
This paper investigates the emerging autonomous aerial cableway technology to reduce the negative impacts of urban freight transportation. We focus on the infrastructure design problem to minimize the road-transportation externalities, taking pricing, investment costs, and the physical footprint into account. The network design problem is formulated as a mixed-integer linear programming (MILP) model that explicitly … Read more
We study adjustable robust network design for potential-based flows with controllable elements under load uncertainty. The resulting problem combines discrete here-and-now expansion decisions with wait-and-see operational decisions governed by nonconvex flow constraints. Moreover, controllable elements introduce adjustable integer decisions, which are algorithmically challenging. We equivalently characterize robust feasibility and robust optimality of a fixed network … Read more
Modern experimentation in business and public policy often studies targeted interventions whose effects depend on the heterogeneous attributes of individuals. We examine heterogeneous treatment effects through the lens of optimal design of experiments, which allocates treatment decisions to maximize the precision of estimated treatment-covariate interactions. We introduce the D-optimal partitioning problem for balancing the information … Read more
We present PyROS, a Python-based meta-solver that automates a generalized cutting-set algorithm for the solution of nonconvex two-stage robust optimization (RO) problems with uncertain equality constraints. Freely available through the open-source optimization software package Pyomo, PyROS is designed to operate on a user-provided deterministic model and uncertainty set, such that a solution to the RO … Read more
We are interested in exactness, strong conic duality and dual attainability in copositive relaxations of quadratic optimization problems (QPs) of a special form, in which any (feasible) QP can be recast. By using our results, the celebrated Frank-Wolfe theorem on the attainability of any bounded QP even over unbounded polyhedra, regardless of whether the objective … Read more
We consider mixed-integer linear-quadratic generalized Nash equilibrium problems, i.e., games in which each player solves a mixed-integer program subject to linear constraints in her own and rivals’ strategies as well as an objective which is quadratic in her own strategies and bilinear in her own and rivals’ strategies. For this class of games, we study … Read more