Stochastic-Equilibrium in Network Expansion Planning Under Uncertainty, Se-Nep

Date: Mon, Apr 1 - Fri, Apr 5 2019

Hour: 10:00

Location: BCAM Seminar room

Speakers: Laureano F. Escudero (Unviersidad Rey Juan Carlos)

DATES: 1-5 April 2019 (5 sessions)
TIME: 10:00 - 12:00 (a total of 10 hours)
LOCATION: BCAM Seminar room

A new scheme is presented for dealing with uncertainty in scenario trees for dynamic mixed 0-1 optimization problems with strategic and tactical/operational stochastic parameters. Let us generically name this type of problems as hub and non-hub Network Expansion Planning (NEP) in a given system, e.g., supply chain, production, rapid transit network, energy generation and transmission network, etc. The strategic scenario tree is usually a multistage one with replicas of the strategic nodes rooted structures in the form of either a special scenario graph or a two-stage scenario tree, depending on the type of tactical/operational activity in the system. Those tactical/operational scenario structures impact in the constraints of the model and, thus, in the decomposition methodology for solving usually large-scale instances. A scheme is presented for scenario reduction based on hunging the tactical/operational stochastic nodes on strategic nodes. A strong modeling framework for NEP is also presented, being based on the step-variable concept as a counterpart to the impulse one. Two types of risk-averse measures are considered. The first one is a time-inconsistent mixture of the chance-constrained and second-order stochastic dominance functionals of the value of a given set of functions up to the strategic nodes in selected stages along the time horizon, The second type is a strategic node-based time-consistent SSD functional for the set of tactical/operational scenarios in the strategic nodes at selected stages. The stochastic Equilibrium in NEP is presented by considering a mixed 0-1 bilinear bilevel primal-model for the multi-period NEP, where different agents are competing on an open market. The huge problem´s dimensions (due to the network size of realistic instances as well as the cardinality of the strategic tree and tactical/operational subtrees) renders unrealistic to seek for an optimal solution. It motivates the development of several versions of a matheuristic algorithm based on the Nested Stochastic Decomposition methodology for problem-solving, where a solution optimality gap is guaranteed in the Lagrangean-based versions and a good estimation of that gap is given in a heuristic Benders-based version. Its advantages and drawbacks are also presented as well as the framework for some schemes to, partially at least, avoid those drawbacks. A broad computational experience is studied based on realistic problems so diverse as Non-Close-Loop Supply Network Management, Close-Loop SCM, Rapid Transit Network design Management, Tall Assignment NEP and Forest harvestry NEP.

PROGRAMME:
1. Introduction to Network Expansion Planning and Multistage Stochastic mixed 0-1 Optimization.
2. Stochastic multistage Strategic scenario trees, multiperiod Tactical scenario graphs and Operational two-stage trees. Scenario reduction.
3. Hub and non-hub Network Expansion Planning strong modeling and its Stochastic Equilibrium via multistage stochastic bi-level optimization.
4. Risk averse functionals. Motivation of time-inconsistent and time-consistent versions of Average Value-at-Risk and Stochastic Dominance measures.
5. Nested Stochastic Decomposition methodology for problem-solving and computational experience study for some realistic problems.

REFERENCES:
[1] U. Aldasoro, L.F. Escudero, M. Merino, J.F. Monge and G. Pérez. On parallelization of a Stochastic Dynamic Programming algorithm for solving large-scale mixed 0-1 problems under uncertainty. TOP, 23:703-742, 2015.
[2] A. Alonso-Ayuso, L.F. Escudero, M. Guignard, A. Weintraub. On dealing with strategic and tactical decision levels in forestry planning under uncertainty. Submitted, 2018
[3] S. Baptista, A.P. Barbosa-Povoa, L.F. Escudero, M.I. Gomes and C. Pizarro. On risk management for a two-stage stochastic mixed 0-1 model for designing and operation planning of a closed-loop supply chain. European Journal of Operational Research, 274:91-107, 2019.
[4] J.R. Birge and F.V. Louveaux. Introduction to Stochastic Programming. Springer, 2nd edition, 2011.
[5] L. Cadarso, L.F. Escudero and A. Marín. On strategic multistage operational two-stage stochastic 0-1 optimization for the Rapid Transit Network Design problem. European Journal of Operational Research, 271:577-593, 2018.
[6] S. Dempe, V. Kalashnikov, G. Pérez-Valdés and N. Kalashnikova. The classical KKT transformation. Bilevel Programming: Theory, Algorithms and Applications to Energy Networks, Section 3.5. Springer, 2015.
[7] L.F. Escudero, M.A. Gar ́ın, C. Pizarro and A. Unzueta. On efficient matheuristic algorithms for Multi-period Stochastic Facility Location-assignment Problems. Computational Optimization and Applications, 70:865-888, 2018.
[8] L.F. Escudero, A. Gar ́ın and A. Unzueta. Cluster Lagrangean decomposition for risk averse in multistage stochastic optimization. Computers & Operations Research, 85:154-171, 2017.
[9] L.F. Escudero and J.F. Monge. On capacity expansion planning under strategic and operational uncertainties based on stochastic dominance risk averse management. Computational Management Science, 15:479-500, 2018.
[10] L.F. Escudero, J.F. Monge and A.M. Rodr ́ıguez-Ch ́ıa. On stochastic equilibrium for network expansion planning. A multi-period bilevel approach under uncertainty. Submitted, 2019.
[11] L.F. Escudero, J.F. Monge and D. Romero-Morales. On the time-consistent stochastic dominance risk averse measure for tactical supply chain planning under uncertainty. Computers & Operations Research, 100:270-286, 2018.
[12] M. Fischetti, I. Ljubic, M. Monaci and M. Sinnl. On the use of intersection cuts for bilevel optimization. Mathematical Programming, Ser. B, 172:77-103, 2018.
[13] M. Labb ́e, P. Marcotte and G. Savard. A bilevel model of taxation and its application to optimal highway pricing. Management Science, 44:1608-1622, 1988.
[14] M.V.F. Pereira and L.M.V.G. Pinto. Multistage stochastic optimization applied to energy planning. Mathematical Programming, 52:359-375, 1991.
[15] G.Ch. Pflug and A. Pichler. Multistage stochastic optimization. Springer, 2014.
[16] A. Shapiro, D. Dentcheva and A. Ruszczy ́nski. Lectures on Stochastic Programming, MPS-SIAM
Series on Optimization, 253-332, 2009.
[17] J.Zou, S. Ahmed and X.A.Sun. Stochastic Dual Dynamicintger Programming. Optimization Online, org, 2016.
[18] J. Zou, S. Ahmed and X.A. Sun. Multistage stochastic unit commitment using Stochastic Dual Dynamic intger Programming. Mathematical Programming, doi.org/10.1007/s10107-018-1249-5, 2018.



*Registration is free, but mandatory before March 29th: So as to inscribe go to https://bit.ly/2UNDfQw and fill the registration form. Student grants are available. Please, let us know if you need support for travel and accommodation expenses when you fill the form.

Organizers:

BCAM 

 

Confirmed speakers:

Laureano F. Escudero (Unviersidad Rey Juan Carlos)