American Institute of Mathematical Sciences

Advanced
April  2008, 4(2): 363-384. doi: 10.3934/jimo.2008.4.363

Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming

René Henrion 1, , Christian Küchler 2, and  Werner Römisch 2,

1. 

Weierstrass Institute for Applied Analysis and Stochastics, Mohrenstraße 39, 10117 Berlin, Germany
2. 

Humboldt-Universität zu Berlin, Institut für Mathematik, 10099 Berlin, Germany, Germany

Received  July 2007 Revised  February 2008 Published  April 2008

Polyhedral discrepancies are relevant for the quantitative stability of mixed-integer two-stage and chance constrained stochastic programs. We study the problem of optimal scenario reduction for a discrete probability distribution with respect to certain polyhedral discrepancies and develop algorithms for determining the optimally reduced distribution approximately. Encouraging numerical experience for optimal scenario reduction is provided.
Keywords: Kolmogorov metric., chance constraints, scenario reduction, discrepancy, two-stage, Stochastic programming, mixed-integer.
Mathematics Subject Classification: Primary: 90C1.
Citation: René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 363-384. doi: 10.3934/jimo.2008.4.363
[1]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[2]

Tengteng Yu, Xin-Wei Liu, Yu-Hong Dai, Jie Sun. Variable metric proximal stochastic variance reduced gradient methods for nonconvex nonsmooth optimization. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021084
[3]

Li Chu, Bo Wang, Jie Zhang, Hong-Wei Zhang. Convergence analysis of a smoothing SAA method for a stochastic mathematical program with second-order cone complementarity constraints. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1863-1886. doi: 10.3934/jimo.2020050
[4]

Jinye Shen, Xian-Ming Gu. Two finite difference methods based on an H2N2 interpolation for two-dimensional time fractional mixed diffusion and diffusion-wave equations. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021086
[5]

G. Deugoué, B. Jidjou Moghomye, T. Tachim Medjo. Approximation of a stochastic two-phase flow model by a splitting-up method. Communications on Pure & Applied Analysis, 2021, 20 (3) : 1135-1170. doi: 10.3934/cpaa.2021010
[6]

Yunfei Lv, Rong Yuan, Yuan He. Wavefronts of a stage structured model with state--dependent delay. Discrete & Continuous Dynamical Systems, 2015, 35 (10) : 4931-4954. doi: 10.3934/dcds.2015.35.4931
[7]

David Cantala, Juan Sebastián Pereyra. Endogenous budget constraints in the assignment game. Journal of Dynamics & Games, 2015, 2 (3&4) : 207-225. doi: 10.3934/jdg.2015002
[8]

Hsin-Lun Li. Mixed Hegselmann-Krause dynamics. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021084
[9]

Pengyu Chen, Xuping Zhang, Zhitao Zhang. Asymptotic behavior of time periodic solutions for extended Fisher-Kolmogorov equations with delays. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021103
[10]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[11]

Mohammed Abdelghany, Amr B. Eltawil, Zakaria Yahia, Kazuhide Nakata. A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2051-2072. doi: 10.3934/jimo.2020058
[12]

Alberto Bressan, Ke Han, Franco Rampazzo. On the control of non holonomic systems by active constraints. Discrete & Continuous Dynamical Systems, 2013, 33 (8) : 3329-3353. doi: 10.3934/dcds.2013.33.3329
[13]

Manuel de León, Víctor M. Jiménez, Manuel Lainz. Contact Hamiltonian and Lagrangian systems with nonholonomic constraints. Journal of Geometric Mechanics, 2021, 13 (1) : 25-53. doi: 10.3934/jgm.2021001
[14]

Miguel R. Nuñez-Chávez. Controllability under positive constraints for quasilinear parabolic PDEs. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021024
[15]

Huy Dinh, Harbir Antil, Yanlai Chen, Elena Cherkaev, Akil Narayan. Model reduction for fractional elliptic problems using Kato's formula. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021004
[16]

Xiaofei Liu, Yong Wang. Weakening convergence conditions of a potential reduction method for tensor complementarity problems. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021080
[17]

Palash Sarkar, Subhadip Singha. Classical reduction of gap SVP to LWE: A concrete security analysis. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021004
[18]

Yue Qi, Xiaolin Li, Su Zhang. Optimizing 3-objective portfolio selection with equality constraints and analyzing the effect of varying constraints on the efficient sets. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1531-1556. doi: 10.3934/jimo.2020033
[19]

Yuta Ishii, Kazuhiro Kurata. Existence of multi-peak solutions to the Schnakenberg model with heterogeneity on metric graphs. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021035
[20]

Tao Wang. Variational relations for metric mean dimension and rate distortion dimension. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021050

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (37)
  • HTML views (0)
  • Cited by (18)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences