RT info:eu-repo/semantics/article
T1 Similarity-based decomposition algorithm for two-stage stochastic scheduling
A1 Montes López, Daniel Alberto
A1 Pitarch Pérez, José Luis
A1 Prada Moraga, César de
K1 Production planning
K1 Mathematical programming
K1 Uncertainty
K1 Progressive hedging
K1 Mixed-integer optimization
AB 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.
PB Elsevier
SN 0360-8352
YR 2024
FD 2024
LK https://uvadoc.uva.es/handle/10324/73165
UL https://uvadoc.uva.es/handle/10324/73165
LA eng
NO Computers & Industrial Engineering, agosto 2024, vol. 194, 110393
NO Producción Científica
DS UVaDOC
RD 22-ene-2025