Consensus fixing for two-stage stochastic optimization – applied to stochastic prize collecting TSP

We consider two-stage stochastic optimization problems, where both the first-stage and second-stage problems may contain binary variables. A highly parallel heuristic is presented based on consensus fixing: The problems are solved independently for each scenario using a variable neighborhood search heuristic. Then, the scenarios try to reach consensus about fixing a single first-stage variable, using various score and select functions. The process of alternating between solving independent scenarios and variable fixing is repeated until all first-stage variables have been fixed. Since all second-stage problems are independent, the framework lends itself well to a parallel implementation. The general framework is tested on a two-stage stochastic prize collecting traveling salesman problem. The first-stage customers (subscription customers) are to be served every day, while the second-stage customers (on-demand customers) fluctuate from day to day. Computational results are reported for instances with up to 500 first-stage and 500 second-stage customers involving up to 128 scenarios, showing that high-quality solutions are obtained within a few minutes, and the solution times scale well with the number of scenarios.