We study the minimization of a rank-one quadratic with indicators and show that the underlying set function obtained by projecting out the continuous variables is supermodular. Although supermodular minimization is, in general, difficult, the specific set function for the rank-one quadratic can be minimized in linear time. We show that the convex hull of the … Read more
We consider a general conic mixed-binary set where each homogeneous conic constraint involves an affine function of independent continuous variables and an epigraph variable associated with a nonnegative function, $f_j$, of common binary variables. Sets of this form naturally arise as substructures in a number of applications including mean-risk optimization, chance-constrained problems, portfolio optimization, lot-sizing … Read more
In real-time traffic management, a new schedule for the vehicles must be computed whenever a deviation from the current plan is detected, or periodically after some time. If this time interval is relatively small, then each two consecutive instances are likely to be similar. We exploit this aspect to derive an exact reoptimization framework for … Read more
As an important problem in modern data analytics, classification has witnessed varieties of applications from different domains. Different from conventional classification approaches, fair classification concerns the issues of unintentional biases against the sensitive features (e.g., gender, race). Due to high nonconvexity of fairness measures, existing methods are often unable to model exact fairness, which can … Read more
Many practical applications require the solution of numerically challenging linear programs (LPs) and mixed-integer programs (MIPs). Scaling is a widely used preconditioning technique that aims at reducing the error propagation of the involved linear systems, thereby improving the numerical behavior of the dual simplex algorithm and, consequently, LP-based branch-and-bound. A reliable scaling method often makes … Read more
We propose a new solution method for two-stage mixed-integer recourse models. In contrast to existing approaches, we can handle general mixed-integer variables in both stages, and thus, e.g., do not require that the first-stage variables are binary. Our solution method is a Benders’ decomposition, in which we iteratively construct tighter approximations of the expected second-stage … Read more
The Capacitated Vehicle Routing Problem (CVRP) consists of finding the cheapest way to serve a set of customers with a fleet of vehicles of a given capacity. While serving a particular customer, each vehicle picks up its demand and carries its weight throughout the rest of its route. While costs in the classical CVRP are … Read more
We study how to efficiently plan the daily bus dispatch operation within a public transport terminal working with a fleet of electric buses. This requires to formulate and solve a new variant of the Vehicle Scheduling Problem model, in which one has to assign trip itineraries to each vehicle considering that driving ranges are limited, … Read more
We propose an exact global solution method for bilevel mixed-integer optimization problems with lower-level integer variables and including nonlinear terms such as, \eg, products of upper-level and lower-level variables. Problems of this type are extremely challenging as a single-level reformulation suitable for off-the-shelf solvers is not available in general. In order to solve these problems … Read more
For a binary integer program (IP) $\max c^\T x, Ax \leq b, x \in \{0,1\}^n$, where $A \in \R^{m \times n}$ and $c \in \R^n$ have independent Gaussian entries and the right-hand side $b \in \R^m$ satisfies that its negative coordinates have $\ell_2$ norm at most $n/10$, we prove that the gap between the value … Read more