We prove that computing a shortest monotone path to the optimum of a linear program over a simple polytope is NP-hard, thus resolving a 2022 open question of De Loera, Kafer, and Sanit\`{a}. As a consequence, finding a shortest sequence of pivots to an optimal basis with the simplex method is NP-hard. In fact, we … Read more
This paper revisits momentum in the context of min-max optimization. Momentum is a celebrated mechanism for accelerating gradient dynamics in settings like convex minimization, but its direct use in min-max optimization makes gradient dynamics diverge. Surprisingly, Gidel et al. 2019 showed that negative momentum can help fix convergence. However, despite these promising initial results and … Read more
We investigate the integration of Nesterov-type acceleration into primal-dual methods for structured convex optimization. While proximal splitting algorithms efficiently handle composite problems of the form min_x f(x) + g(x) + h(Kx), accelerating their convergence with respect to the smooth term f is notoriously challenging due to the rotational dynamics in the primal-dual space. In this … Read more
Many large-scale optimization problems decompose into a master problem and scenario subproblems, a structure that can be exploited by Benders decomposition. In Benders decomposition, each iteration may generate many cuts from scenario subproblems, and adding all of them as constraints then causes the master problem to grow rapidly. These are constraints that may need to … Read more
Modern energy grid expansion planning, by necessity, includes timeseries data to accurately model storage and renewable assets. Representative time periods are commonly used as a way to decrease problem size and therefore mitigate the increased complexity from this inclusion. However, there are many choices around these representative periods: length; location in planning horizon; boundary conditions. … Read more
We study the problem of minimizing a multivariate polynomial function over the unit hypercube. By representing the polynomial through a hypergraph and exploiting its sparsity structure, we establish a new sufficient condition under which the problem can be solved in time polynomial in the encoding length of the input. Our approach identifies a subset of … Read more
This paper presents a practical architecture for last-mile delivery routing at scales reaching one million stops under realistic operational conditions, including vehicle capacity, package volume, route stop limits, and time windows. Unlike conventional systems that require pre-partitioning or large-scale infrastructure, the proposed system addresses the full fleet planning problem through a single coherent planning pipeline … Read more
We study optimistic robust bilevel problems with uncertainty in the follower’s problem, where the follower adopts a so-called wait-and-see approach. In this setting, the leader decides without knowledge of the specific realization of the uncertainty. Then, the uncertainty realizes in a worst-case manner, and afterward the follower makes her own decisions. For this challenging problem … Read more
Two-stage stochastic integer programs provide a powerful framework for modeling decision-making under uncertainty, but they are notoriously difficult to solve at scale due to their high dimensionality and intrinsic nonconvexity. Decomposition-based algorithms such as Benders methods and Branch-and-Price (related dual decomposition methods) have become standard computational approaches for such problems and demonstrate excellent empirical performance … Read more
We consider unconstrained derivative-free optimization problems in which only inexact function evaluations are available. Specifically, we study the setting where the oracle returns function values with partially controllable inexactness, with the error bounded linearly by a user-specified accuracy parameter, but with an unknown proportionality constant. This framework captures optimization problems arising from approximate simulations or … Read more