Split-and-Merge Method for Accelerating Convergence of Stochastic Linear Programs

Stochastic program optimizations are computationally very expensive, especially when the number of scenarios are large. Complexity of the focal application, and the slow convergence rate add to its computational complexity. We propose a split-and-merge (SAM) method for accelerating the convergence of stochastic linear programs. SAM splits the original problem into subproblems, and utilizes the dual constraints from the subproblems to accelerate the convergence of the original problem. Our initial results are very encouraging, giving up to 58% reduction in the optimization time. In this paper we discuss the initial results, the ongoing and the future work.

@inproceedings{DBLP:conf/icores/Langer14,
  author    = {Akhil Langer and
               Udatta Palekar},
  title     = {Split-and-Merge Method for Accelerating Convergence of Stochastic Linear Programs},
  booktitle = {{ICORES} 2015 - Proceedings of the 4th International Conference on
               Operations Research and Enterprise Systems, Lisbon, Portugal, January 10-12, 2015.},
  year      = {2015},
}