This paper investigates the estimation of the size of Branch-and-Bound (B&B) trees for solving mixed-integer programs. We first prove that the size of the B&B tree cannot be approximated within a factor of~2 for general binary programs, unless P equals NP. Second, we review measures of the progress of the B&B search, such as the … Read more
We develop a dual decomposition of two-stage distributionally robust mixed-integer programming (DRMIP) under the Wasserstein ambiguity set. The dual decomposition is based on the Lagrangian dual of DRMIP, which results from the Lagrangian relaxation of the nonanticipativity constraints and min-max inequality. We present two Lagrangian dual problem formulations, each of which is based on different principle. We show … Read more
We present a stochastic optimization model for allocating and sharing a critical resource in the case of a pandemic. The demand for different entities peaks at different times, and an initial inventory for a central agency is to be allocated. The entities (states) may share the critical resource with a different state under a risk-averse … Read more
The Traveling Salesperson Problem with Drone (TSP–D) is a routing model in which a given set of customer locations must be visited in the least amount of time, either by a truck route starting and ending at a depot or by a drone dispatched from the truck en route. We study the TSP–D model and … Read more
We consider a class of stochastic programs whose uncertain data has an exponential number of possible outcomes, where scenarios are affinely parametrized by the vertices of a tractable binary polytope. Under these conditions, we propose a novel formulation that introduces a modest number of additional variables and a class of inequalities that can be efficiently … Read more
We study a mobile facility (MF) routing and scheduling problem in which probability distributions of the time-dependent demand for MF services is unknown. To address distributional ambiguity, we propose and analyze two distributionally robust MF routing and scheduling (DMFRS) models that seek to minimize the fixed cost of establishing the MF fleet and maximum expected … Read more
The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 7.0 of the SCIP Optimization Suite. The new version features the parallel presolving library PaPILO as a new addition to the suite. PaPILO 1.0 simplifies … Read more
We consider exact deterministic mixed-integer programming (MIP) reformulations of distributionally robust chance-constrained programs (DR-CCP) with random right-hand sides over Wasserstein ambiguity sets. The existing MIP formulations are known to have weak continuous relaxation bounds, and, consequently, for hard instances with small radius, or with a large number of scenarios, the branch-and-bound based solution processes suffer … Read more
We introduce a new facility layout problem, the so-called T-Row Facility Layout Problem (TRFLP). The TRFLP consists of a set of one-dimensional departments with pairwise transport weights between them and two orthogonal rows which form a T such that departments in different rows cannot overlap. The aim is to find a non-overlapping assignment of the … Read more
We translate the algorithmic question of whether to linearize convex Mixed-Integer Quadratic Programming problems (MIQPs) into a classification task, and use machine learning (ML) techniques to tackle it. We represent MIQPs and the linearization decision by careful target and feature engineering. Computational experiments and evaluation metrics are designed to further incorporate the optimization knowledge in … Read more