Stochastic Dynamic Mixed-Integer Programming (SD-MIP)

Abstract

Mixed-Integer Programming has traditionally been restricted to deterministic models. Recent research has opened the door to stochastic optimization models, which are typically dynamic in nature. This project lays the foundation for stochastic dynamic mixed-integer and linear programming (SD-MIP). This project has produced several new ideas in connection with a) convexification of two-stage mixed-integer sets and b) multi-stage (including two-stage) stochastic linear programming. Together a) and b) provide the foundations for SD-MIP problems. From new concepts and algorithms to applications and software, this project has made significant breakthroughs in all aspects. This report provides a synopsis of both theoretical and computational results. As a preview, we mention that currently available deterministic MIP solvers, as powerful as they are known to be, are unable to solve SD-MIP models of modest size within an hour of computing. In contrast, our decomposition approach provides provably optimal solutions within the hour time-limit.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 05, 2015
Accession Number
ADA622680

Entities

People

  • Suvrajeet Sen

Organizations

  • University of Southern California

Tags

Communities of Interest

  • Air Platforms
  • Human Systems

DTIC Thesaurus Topics

  • Aircrafts
  • Algorithms
  • Computer Programming
  • Decomposition
  • Department Of Defense
  • Dynamic Programming
  • Electronic Mail
  • Evolutionary Algorithms
  • Integer Programming
  • Linear Programming
  • Mathematical Programming
  • Operations Research
  • Optimization
  • Probability
  • Psychology
  • Random Variables
  • Systems Engineering

Readers

  • Operations Research
  • Systems Analysis and Design