Models and Algorithms Involving Very Large Scale Stochastic Mixed-Integer Programs
Abstract
Stochastic Mixed Integer Programs (SMIP) are recognized as one of the most formidable classes of mathematical programming problems. Not only are there significant challenges due to potentially large number of scenarios, but, SMIP with integers in the second stage give rise to a non-convex and discontinuous recourse function that may be difficult to optimize. As a result of this project, there have been significant advances in the design of algorithms for solving SMIP problems. Thanks to this project, we are able to report on solution to SMIP problems with over a million binary variables in less than 3 hours of computing on a desk-top machine! These problems arise in a variety of Air Force applications, such as adaptive command and control (AC2) under uncertainty. For instance, consider a situation in which assignments of pilots/aircrafts to targets may be contingent of sensor data revealed during the mission. In such situations, a preliminary set of assignments are made, recognizing that these will be revised once more reliable observations (regarding targets) are available. While such adaptive methods can enhance the effectiveness of C2, uncertainties can vastly enlarge the set of choices, and new algorithmic tools are necessary. Our algorithms solve such problems.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 28, 2011
- Accession Number
- ADA546972
Entities
People
- Suvrajeet Sen
Organizations
- Ohio State University