Solving Stochastic and Bilevel Mixed-Integer Programs via a Generalized Value Function

We introduce a generalized value function of a mixed-integer program, which is simultaneously parameterized by its objective and right-hand side. We describe its fundamental properties, which we exploit through three algorithms to calculate it. We then show how this generalized value function can be used to reformulate two classes of mixed-integer optimization problems: two-stage stochastic … Read more

Totally Unimodular Multistage Stochastic Programs

We consider totally unimodular multistage stochastic programs, that is, multistage stochastic programs whose extensive-form constraint matrices are totally unimodular. We establish several sufficient conditions and identify examples that have arisen in the literature. Citation Ruichen (Richard) Sun, Oleg V. Shylo, Andrew J. Schaefer, Totally unimodular multistage stochastic programs, Operations Research Letters, Volume 43, Issue 1, … Read more

Scenario-Tree Decomposition: Bounds for Multistage Stochastic Mixed-Integer Programs

Multistage stochastic mixed-integer programming is a powerful modeling paradigm appropriate for many problems involving a sequence of discrete decisions under uncertainty; however, they are difficult to solve without exploiting special structures. We present scenario-tree decomposition to establish bounds for unstructured multistage stochastic mixed-integer programs. Our method decomposes the scenario tree into a number of smaller … Read more

Two-Stage Quadratic Integer Programs with Stochastic Right-Hand Sides

We consider two-stage quadratic integer programs with stochastic right-hand sides, and present an equivalent reformulation using value functions. We fi rst derive some basic properties of value functions of quadratic integer programs. We then propose a two-phase solution approach. The first phase constructs the value functions of quadratic integer programs in both stages. The second phase … Read more

A Hierarchy of Bounds for Stochastic Mixed-Integer Programs

Strong relaxations are critical for solving deterministic mixed-integer programs. As solving stochastic mixed-integer programs (SMIPs) is even harder, it is likely that strong relaxations will also prove essential for SMIPs. We consider general two-stage SMIPs with recourse, where integer variables are allowed in both stages of the problem and randomness is allowed in the objective … Read more

On Adaptive Multicut Aggregation for Two-Stage Stochastic Linear Programs with Recourse

Outer linearization methods for two-stage stochastic linear programs with recourse, such as the L-shaped algorithm,generally apply a single optimality cut on the nonlinear objective at each major iteration, while the multicut version of the algorithm allows for several cuts to be placed at once. In general, the L-shaped algorithm tends to have more major iterations … Read more

Inverse Stochastic Linear Programming

Inverse optimization perturbs objective function to make an initial feasible solution optimal with respect to perturbed objective function while minimizing cost of perturbation. We extend inverse optimization to two-stage stochastic linear programs. Since the resulting model grows with number of scenarios, we present two decomposition approaches for solving these problems. Citation Unpublished: 07-1, University of … Read more

Totally Unimodular Stochastic Programs

We consider totally unimodular stochastic programs, that is, stochastic programs whose extensive-form constraint matrix is totally unimodular. We generalize the notion of total unimodularity to apply to sets of matrics and provide properties of such sets. Using this notion, we give several sufficient conditions for specific classes of problems. When solving such problems using the … Read more