Development of Modularized Software for Empirical Testing of New Algorithms in Linear Programming.

摘要

Empirical research into new strategies and tactics for linear programming requires realistic, large-scale problem-solving tools. The Workbench for Research In (linear) Programming, called WRIP, is a highly modularized system for generating, solving and analyzing instances of linear programs. The core of WRIP is OB1, an advanced optimizer that includes simplex and interior point methods. To support basic operations, OB1 contains a linear algebra library and related routines to process large, sparse matrices. Its modular structure enables algorithm experimentation by modifying one or more of its subroutines. In order to test ideas and gain insight into an algorithm's performance, WRIP includes a modeling language, called MODLER, and a controlled randomization module, called RANDMOD. These enable meaningful randomization on raw data elements and matrix operations, respectively, that preserve the realism of the structure of the linear programming model while applying statistical inference. In addition, an interactive analysis system, called ANALYZE, is included to gain insights into problem and solution properties for deeper analysis of results. All modules are written in FOR /77 and have been tested in a variety of computing environments. WRIP has been distributed to about 30 academics engaged in mathematical programming research, in the U.S. and Europe. In addition, the principal investigators have extended their own insights into algorithm design through experimental rigor made possible by this software. Linear programming, computational experimentation, interior point methods, sparse linear algebra.