A computational evaluation of interior point cutting plane algorithms for stochastic programs.

摘要

Stochastic linear programs (SLPs) are a class of problems which are useful in practice but computationally difficult. The algorithm that is currently most popular for solving SLPs is the L-shaped algorithm of Van Slyke and Wets [42]. This "exterior point" cutting plane algorithm is based on the simplex method, and cannot attain polynomial worst case complexity. However, the L-shaped algorithm exhibits good performance on most problems in practice.;Recently, three new classes of algorithms for solving SLPs were introduced [3]. These "interior point" cutting plane algorithms, based on the notions of volumetric centers, analytic centers, and ellipsoids, were shown to have worst case complexities that are polynomial in the size of the problem, and linear in the number of random realizations, in terms of the number of arithmetic operations. The interior point algorithms have been largely untested, however, on real world problems.;A test set of eleven real world problems is presented. The problems, gathered from the literature, are based on various contemporary applications, and exhibit a variety of problem structures. For each problem, a short description of the application area is given, followed by the stochastic linear problem statement, numerical example(s), and notational reconciliation to a standard problem format. Many of the problems also have associated with them computer data files in SMPS format [9].;A software implementation, CPA, was created to evaluate the three new classes of interior point algorithms, assessing their dependence on problem dimensions as well as their efficiency of parallelization. This parallel implementation allows many specific algorithms, including the L-shaped algorithm and several of the interior algorithms, to be run within a unified framework.;Experimental results are given, showing that the exterior cutting plane algorithms exhibited superior performance, but that the performance of the interior algorithms relative to the exterior algorithms improves with the number of random realizations. Both the exterior and interior types of algorithms parallelized very well, with parallel efficiencies near 1.0 in most cases.