RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación
Artículo científico (JournalArticle)
Similarity-based decomposition algorithm for two-stage stochastic scheduling
[EN] This paper presents a novel decomposition method for two-stage stochastic mixed-integer optimization problems. The algorithm builds upon the idea of similarity between finite sample sets to measure how similar the first-stage decisions are among the uncertainty realization scenarios. Using such a Similarity Index, the non-anticipative constraints are removed from the problem formulation so that the original problem becomes block-separable on a scenario basis. Then, a term for maximizing the Similarity Index is included in all the sub-problems objective functions. Such sub-problems are solved iteratively in parallel so that their solutions are used to update the weighting parameter for maximizing the Similarity Index. The algorithm obtains a feasible solution when full similarity among scenario first stages is reached, that is, when the incumbent solution is non-anticipative. The proposal is tested in four instances of different sizes of an industrial-like scheduling problem. Comparison results show that the Similarity Index Decomposition provides significant speed-ups compared with the monolithic problem formulation, and provides simpler tuning and improved convergence over the Progressive Hedging Algorithm., This research is funded by the Spanish MCIN/AEI through research projects a-CIDiT (PID2021-123654OB-C31, PID2021-123654OB-C32) and LOCPU (PID2020-116585GB-I00) . The first author has received financial support from the 2020 call of the pre-doctoral contracts of the University of Valladolid, Spain, co-financed by Banco Santander.
Proyecto:
Agencia Estatal de Investigación / Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020 PID2020-116585GB-I00
,
Agencia Estatal de Investigación / Plan Estatal de Investigación Científica y Técnica y de Innovación 2021-2023 PID2021-123654OB-C31
,
Agencia Estatal de Investigación / Plan Estatal de Investigación Científica y Técnica y de Innovación 2021-2023 PID2021-123654OB-C32