We propose a new formulation of robust regression by integrating all realizations of the uncertainty set and taking an averaged approach to obtain the optimal solution for the ordinary least-squared regression problem. We show that this formulation surprisingly recovers ridge regression and establishes the missing link between robust optimization and the mean squared error approaches … Read more
\(\) Symmetry handling inequalities (SHIs) are an appealing and popular tool for handling symmetries in integer programming. Despite their practical application, little is known about their interaction with optimization problems. This article focuses on Schreier-Sims (SST) cuts, a recently introduced family of SHIs, and investigate their impact on the computational and polyhedral complexity of optimization … Read more
\(\) We present generalizations of Newton’s method that incorporate derivatives of an arbitrary order \(d\) but maintain a polynomial dependence on dimension in their cost per iteration. At each step, our \(d^{\text{th}}\)-order method uses semidefinite programming to construct and minimize a sum of squares-convex approximation to the \(d^{\text{th}}\)-order Taylor expansion of the function we wish … Read more
LTL freight carriers operate consolidation networks that utilize cross-docking terminals to facilitate thetransfer of freight between trailers and enhance trailer utilization. This research addresses the problem ofdetermining an optimal schedule for unloading inbound trailers at specific unloading doors using teams ofdock workers. The optimization objective is chosen to ensure that outbound trailers are loaded with … Read more
We present a proof system for establishing the correctness of results produced by optimization algorithms, with a focus on mixed-integer programming (MIP). Our system generalizes the seminal work of Bogaerts, Gocht, McCreesh, and Nordström (2022) for binary programs to handle any additional difficulties arising from unbounded and continuous variables, and covers a broad range of … Read more
Congestion games allow to model competitive resource sharing in various distributed systems. Pure Nash equilibria, that are stable outcomes of a game, could be far from being socially optimal. Our goal is to identify combinatorial structures that limit the inefficiency of equilibria. This question has been mainly investigated for congestion games defined over networks. Instead, … Read more
\(\) The simplified Wasserstein barycenter problem consists in selecting one point from \(k\) given sets, each set consisting of \(n\) points, with the aim of minimizing the sum of distances to the barycenter of the \(k\) points chosen. This problem is known to be NP-hard. We compute the Wasserstein barycenter by exploiting the Euclidean distance … Read more
In this paper, we propose ROBIST, a simple, yet effective, data-driven algorithm for optimization under parametric uncertainty. The algorithm first generates solutions in an iterative manner by sampling and optimizing over a relatively small set of scenarios. Then, using statistical testing, the robustness of the solutions is evaluated, which can be done with a much … Read more
In this paper, we consider a theoretical framework for comparing branch-and-bound with classical lift-and-project hierarchies. We simplify our analysis of streamlining the definition of branch-and-bound. We introduce “skewed $k$-trees” which give a hierarchy of relaxations that is incomparable to that of Sherali-Adams, and we show that it is much better for some instances. We also … Read more
The maximum independent set (MIS) seeks to find a subset of vertices with the maximum size such that no pair of its vertices are adjacent. This paper develops a recursive fixing procedure that generalizes the existing polytime algorithm to solve the maximum independent set problem on chordal graphs, which admit simplicial orderings. We prove that … Read more