Stochastic Mixed-Integer Programming Methods

Lewis Ntaimo
Additional contact information
Lewis Ntaimo: Texas A&M University

Chapter Chapter 9 in Computational Stochastic Programming, 2024, pp 387-461 from Springer

Abstract: Abstract This chapter gives an introductory study of two-stage stochastic mixed-integer programming (SMIP). This subject is an extension of deterministic MIP to the stochastic setting. Thus, SMIP inherits the nonconvexity properties of MIP and with its large-scale nature due to data uncertainty, SMIP is very challenging to solve. Therefore, it is not surprising that there are few practical algorithms for SMIP. This motivates the study of SMIP due to its many practical applications. We begin with the basic properties in Sect. 9.2, discuss the design of algorithms in Sect. 9.3, and give an example instance in Sect. 9.4. We explore three solution methods and provide a numerical example to illustrate the steps of each algorithm in detail. We begin with the binary first-stage (BFS) algorithm in Sect. 9.5, then move on to cover the Fenchel decomposition (FD) algorithm in Sect. 9.6. We end with the disjunctive decomposition ( D 2 $$D^2$$ ) algorithm in Sect. 9.7. The BFS algorithm is designed for SMIP with binary first-stage and arbitrary second-stage decision variables. The FD algorithm is a cutting-plane method designed for SMIP with arbitrary first- and second-stage decision variables. The D 2 $$D^2$$ algorithm is also a cutting-plane method, but it is designed for SMIP with binary first stage and mixed-binary second stage. We describe each algorithm with a great level of detail to help with computer implementation as this is not a trivial matter.

Date: 2024
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-031-52464-6_9

Ordering information: This item can be ordered from
http://www.springer.com/9783031524646

DOI: 10.1007/978-3-031-52464-6_9

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().