Interdiction of a Mixed-Integer Linear System

A system-interdiction problem can be modeled as a bilevel program in which the upper level models interdiction decisions and the lower level models system operation. This paper studies MILSIP, a mixed-integer linear system interdiction problem, which assumes binary interdiction decisions and models system operations through a mixed-integer linear program. To solve large-scale instances of MILSIP, … Read more

Decomposition Methods for Solving Two-Stage Distributionally Robust Optimization Problems

Decomposition methods have been well studied for solving two-stage and multi-stage stochastic programming problems, see [29, 32, 33]. In this paper, we propose an algorithmic framework based on the fundamental ideas of the methods for solving two-stage minimax distributionally robust optimization (DRO) problems where the underlying random variables take a finite number of distinct values. … Read more

Volumetric barrier decomposition algorithms for two-stage stochastic linear semi-infinite programming

In this paper, we study the two-stage stochastic linear semi-infinite programming with recourse to handle uncertainty in data defining (deterministic) linear semi-infinite programming. We develop and analyze volumetric barrier decomposition-based interior point methods for solving this class of optimization problems, and present a complexity analysis of the proposed algorithms. We establish our convergence analysis by … Read more

Decomposition Methods for Solving Markov Decision Processes with Multiple Models of the Parameters

We consider the problem of decision-making in Markov decision processes (MDPs) when the reward or transition probability parameters are not known with certainty. We consider an approach in which the decision-maker (DM) considers multiple models of the parameters for an MDP and wishes to find a policy that optimizes an objective function that considers the … Read more

Projective Hedging for Stochastic Programming

We propose a decomposition algorithm for multistage stochastic programming that resembles the progressive hedging method of Rockafellar and Wets, but is provably capable of several forms of asynchronous operation. We derive the method from a class of projective operator splitting methods fairly recently proposed by Combettes and Eckstein, significantly expanding the known applications of those … Read more

Split cuts from sparse disjunctions

Split cuts are arguably the most effective class of cutting planes within a branch-and-cut framework for solving general Mixed-Integer Programs (MIP). Sparsity, on the other hand, is a common characteristic of MIP problems, and it is an important part of why the simplex method works so well inside branch-and-cut. In this work, we evaluate the … Read more

A scenario decomposition algorithm for strategic time window assignment vehicle routing problems

We study the strategic decision-making problem of assigning time windows to customers in the context of vehicle routing applications that are affected by operational uncertainty. This problem, known as the Time Window Assignment Vehicle Routing Problem, can be viewed as a two-stage stochastic optimization problem, where time window assignments constitute first-stage decisions, vehicle routes adhering … Read more

On decomposability of the multilinear polytope and its implications in mixed-integer nonlinear optimization

In this article, we provide an overview of some of our recent results on the facial structure of the multilinear polytope with a special focus on its decomposability properties. Namely, we demonstrate that, in the context of mixed-integer nonlinear optimization, the decomposability of the multilinear polytope plays a key role from both theoretical and algorithmic … Read more

Layered graph approaches for combinatorial optimization problems

Extending the concept of time-space networks, layered graphs associate information about one or multiple resource state values with nodes and arcs. While integer programming formulations based on them allow to model complex problems comparably easy, their large size makes them hard to solve for non-trivial instances. We detail and classify layered graph modeling techniques that … Read more

An algorithm for solving infinite horizon Markov dynamic programmes

We consider a general class of infinite horizon dynamic programmes where state and control sets are convex and compact subsets of Euclidean spaces and (convex) costs are discounted geometrically. The aim of this work is to provide a convergence result for these problems under as few restrictions as possible. Under certain assumptions on the cost … Read more