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 weighing 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 size 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.
Citation
D. Montes, J.L. Pitarch, and C. de Prada. Similarity-based Decomposition Algorithm for Two-stage Stochastic Scheduling. Computers & Industrial Engineering 194, 2024, 110393, DOI: 10.1016/j.cie.2024.110393