Dual Decomposition of Two-Stage Distributionally Robust Mixed-Integer Programming under the Wasserstein Ambiguity Set

Categories (Mixed) Integer Linear Programming, Robust Optimization, Stochastic Programming Tags , ,

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

On monotonicity and search traversal in copositivity detection algorithms

Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Quadratic Programming Tags , , ,

Matrix copositivity has an important theoretical background. Over the last decades, the use of algorithms to check copositivity has made a big progress. Methods are based on spatial branch and bound, transformation to Mixed Integer Programming, implicit enumeration of KKT points or face-based search. Our research question focuses on exploiting the mathematical properties of the … Read more

Generation Expansion Planning with Revenue Adequacy Constraints

Categories Applications - Science and Engineering Tags , , , ,

Generation capacity expansion models have traditionally taken the vantage point of a centralized planner seeking to find cost-optimal generation capacity to reliably meet load over decadal time scales. Often assuming perfectly competitive players, these models attempt to provide guidance for system planners without necessarily ensuring that individual generators are adequately remunerated for their generation, flexibility, … Read more

A termination criterion for stochastic gradient descent for binary classification

Categories Convex and Nonsmooth Optimization

We propose a new, simple, and computationally inexpensive termination test for constant step-size stochastic gradient descent (SGD) applied to binary classification on the logistic and hinge loss with homogeneous linear predictors. Our theoretical results support the effectiveness of our stopping criterion when the data is Gaussian distributed. This presence of noise allows for the possibility … Read more

Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems

Categories Cutting Plane Approaches, Integer Programming, Nonlinear Optimization Tags , ,

We study a family of discrete optimization problems asking for the maximization of the expected value of a concave, strictly increasing, and differentiable function composed with a set-union operator. The expected value is computed with respect to a set of coefficients taking values from a discrete set of scenarios. The function models the utility function … Read more

Using gradient directions to get global convergence of Newton-type methods

Categories Unconstrained Optimization

The renewed interest in Steepest Descent (SD) methods following the work of Barzilai and Borwein [IMA Journal of Numerical Analysis, 8 (1988)] has driven us to consider a globalization strategy based on SD, which is applicable to any line-search method. In particular, we combine Newton-type directions with scaled SD steps to have suitable descent directions. … Read more

An Exact Solution Method for the TSP with Drone Based on Decomposition

Categories (Mixed) Integer Linear Programming, Production and Logistics Tags , , ,

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

A Model of Supply-Chain Decisions for Resource Sharing with an Application to Ventilator Allocation to Combat COVID-19

Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Stochastic Programming Tags , , , , ,

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

An inexact scalarized proximal algorithm with quasi- distance for convex and quasiconvex multi-objective minimization

Categories Multi-Criteria Optimization, Nonlinear Optimization Tags

In the paper of Rocha et al., J Optim Theory Appl (2016) 171:964979, the authors introduced a proximal point algorithm with quasi-distances to solve unconstrained convex multi-objective minimization problems. They proved that all accumulation points are ecient solutions of the problem. In this pa- per we analyze an inexact proximal point algorithm to solve convex … Read more

On a class of stochastic programs with exponentially many scenarios

Categories (Mixed) Integer Linear Programming, Polyhedra, Stochastic Programming Tags , ,

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