Decomposition Algorithms for Very Large Scale Stochastic Mixed-Integer Programs

Abstract

The objectives of this project were to explore decomposition algorithms that solve optimization models under uncertainty. In order to accommodate a variety of future scenarios, our algorithms are designed to address large scale models. The main accomplishments of the project can be summarized as follows. 1) design and evaluate decomposition methods for stochastic mixed-integer programming (SMIP) problems (Yuan and Sen [2008]); 2) accelerate stochastic decomposition (SD) as a prelude to using SD for SMIP as well as a multi-stage version of SD (Sen et al [2007], Zhou and Sen [2008]); 3) develop a theory for parametric analysis of mixed-integer programs, and provide economically justifiable estimates of shadow prices from mixed-integer linear programming models (Sen and Genc [2008]). The first two relate to stochastic programming, whereas the last addresses one of the long-standing open questions in discrete optimization, namely, parametric analysis in MILP models. This paper (listed as [1]) is likely to have a long term impact on a variety of fields including discrete optimization, operations research, and computational economics.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2007
Accession Number
ADA481768

Entities

People

  • Suvrajeet Sen
  • Yang Yuan

Organizations

  • Ohio State University

Tags

Communities of Interest

  • Human Systems

DTIC Thesaurus Topics

  • Algorithms
  • Computer Programming
  • Decomposition
  • Evolutionary Algorithms
  • Integer Programming
  • Linear Programming
  • Mathematical Programming
  • Mathematics
  • Models
  • Operations Research
  • Optimization
  • Parametric Analysis
  • Parametric Programming
  • Scale Models
  • Systems Engineering

Fields of Study

  • Computer science

Readers

  • Astronomy/Astrophysics
  • Operations Research
  • Systems Analysis and Design