Product Development Update: CPLEX 2.0

Version 2.0 of all CPLEX products has now been released! We delayed the release a few months to add a some new features that we felt our users would consider worth the wait. In addition to the features reported in the last newsletter (30% performance improvement, dual simplex, new algorithm options, new input/output scheme) we incorporated several additional new features, including:

The CPLEX Network Optimizer is now a standard feature in all CPLEX 2.0 products. NETOPT solves not only pure network problems, but also network problems with an unlimited number of LP side constraints.

A new binary problem format option (SAV format) was added for very fast problem read/write times. Problems that are repeatedly read, optimized, and written will benefit from an almost 10X speed-up in read/write times using SAV format.

The MPS and LP problem file readers can now dynamically allocate memory. This means that users reading large problems need not reset the problem read size parameters in order to successfully read a problem (although proper setting of this parameter is still recommended for the most efficient use of memory).

Version 2.0 now incorporates many of the changes that have been requested by our users. Other recently received suggestions and comments, particularly development items collected in our recent user survey, are already on the list for our next release.

Product Development Update: CPLEX Mixed Integer Development

Development work on the CPLEX Mixed Integer Optimizer and Mixed Integer Library is underway; users can expect a significant 1992 MIP update. All Mixed Integer licensees with current maintenance contracts will automatically receive updates when the new release is completed later this year.

Mixed Integer Optimizer development is currently focussed on the following enhancements:

New default branching algorithms--We are adding a more sophisticated default branching algorithm for improved general performance.

Special ordered sets--Special branching strategies are under development to take advantage of the presence of special ordered sets.

Tree save--A mechanism will be implemented to allow users to save the problem "state" or tree status. Users will then be able to "restore" a previously run problem and re-solve from that point.

Arbitration direction control by variable--This development will provide users greater control over branching. Users can use this feature to specify branching instructions for individual variables.

CPLEX 4Q91 User Satisfaction Survey

We wish to thank those users who received and completed our user survey in December, 1991. The response was tremendous--a very high percentage of those users in the random sampling returned the completed surveys. More importantly, the responses were thoughtful and provided excellent feedback on our current products and services as well as useful guidance on future product development. We were particularly pleased with positive feedback on our level of service and support--we intend to keep responsive service and support a top priority.

Several suggestions from the survey were incorporated into our new release, CPLEX 2.0. Others missed our deadline and will be incorporated into future releases. Numerous comments related to documentation were incorporated into the new CPLEX 2.0 documentation.

Please continue to let us know how we're doing. Suggestions and comments are always encouraged.

CPLEX Callable Library Applications under Extended DOS

Significant improvements in speed and memory have made 80386 and 80486 personal computers economical platforms for developing CPLEX Callable Library applications. Problems that could only be solved on a mainframe five to ten years ago can frequently be solved in less time today on an 80486 using CPLEX. Furthermore, the availability of a wide range of software toolkits simplifies the tasks required to create transparent applications in which the user need not have any knowledge of optimization.

However, the DOS operating system brings memory restrictions that must be either be observed or "worked around" for large, memory-intensive problems. Also, unlike most UNIX systems, DOS does not include all the tools required for compiling and linking applications. It is important to have a thorough appreciation and understanding of DOS memory limitations and the tools required to create callable library applications on a personal computer.

The extended-DOS versions of the CPLEX Callable Library and Mixed Integer Library can handle problems of unlimited size, restricted only by the amount of available memory in the machine (but be aware that many PCs do not support over 16 megabytes of RAM). CPLEX users have run problems accessing over 120 MB RAM on personal computers--although we typically recommend more powerful UNIX workstations for problems of this size.

Developers of PC-based CPLEX Callable Library and Mixed Integer Library applications must compile and link applications with CPLEX routines in the development stage. Developers must therefore become familiar with the process of compiling and linking applications under the extended-DOS environment and acquire two necessary tools. First, to take advantage of the 32-bit architectures of 80386 and 80486 personal computers, a 32-bit compiler is required--CPLEX requires 32-bit Metaware High C 386 V 1.7 for compiling and linking. Second, to accomplish the DOS "extension" beyond 640KB memory, a DOS-extender is required--CPLEX requires the Phar Lap 386|DOS Extender. As a convenience to customers, CPLEX resells both Metaware High C 386 V 1.7 ($795) and the Phar Lap 386|DOS Extender ($450). Phar Lap also offers a "run-time" development license (for a one-time fee) for users interested in distributing multiple copies of extended-DOS compiled applications. If the application also involves a software toolkit, one must make sure the toolkit is compatible with the Metaware High C compiler and the Phar-Lap 386 DOS Extender.

Once compiled and linked, a PC application which has been developed using the PC 386 Extended-DOS CPLEX Callable Library or Mixed Integer Library would allow transparent user access to all available memory. The end user of such an executable application would not require any knowledge of extended-DOS technology nor any additional tools beyond standard DOS.

CPLEX offers special terms for developers interested in distributing (either internally or for resale) applications with "embedded optimization" capabilities through our Value Added Reseller program and "run-time" licensing options. Please call us for additional details on these programs.

New CPLEX Staff

We are pleased to announce a new member of the CPLEX team, Ed Klotz. Ed will assist in providing CPLEX user support and will also manage special development and customer projects.

Ed received a PhD in Operations Research from Stanford University, and has over 5 years of industrial experience in optimization software and end-user applications development and support. We are pleased to have Ed on board and know you will appreciate interacting with Ed for product and special project support.

Q&A

Q: When I write a solution file after using the CPLEX Linear Optimizer, I notice that the signs of the dual variables are the opposite of the signs of the dual variables I see when I use the "display dual" command. Why is this?

A: CPLEX adheres to the MPS standard convention of printing the negative dual variables in solution files so they correspond in sign to the reduced costs in the columns section of the solution file. The "display dual" command, on the other hand, displays the true values of the dual variables. The true values also appear in the piout array after a call to solution in a Callable Library application.

Q: Can I solve large LP and mixed integer problems using 386 or 486 personal computers? For what size problems are PC platforms really feasible?

A: Due to the popularity, attractive pricing, and availability of fast personal computers, this is a frequently asked question. Our executable PC-386/486 Extended-DOS Linear Optimizer and Mixed Integer Optimizer can solve problems of ANY size on a personal computer--provided sufficient memory is installed and available. But for very large applications, we typically recommend UNIX systems for performance reasons; for example, a desktop HP 9000/720 is over 10 times faster than a 20 MHz 386. Even very low-cost UNIX workstations typically come with at least 16 megabytes of RAM and a C compiler, and therefore might actually be comparable in price to a comparably-configured PC with significantly lower performance.

We have included an article in this issue on PC-based Callable Library applications to help CPLEX users considering PC-based applications understand extended-DOS memory issues and development tool requirements. Also, the U.S. Postal Service application described on the back page illustrates a very large real application running successfully on a PC configured with over 120 megabytes of random access memory.

U.S. Postal Service Scheduling

An interesting CPLEX-based application is in use at the U.S. Postal Service. This application, called POSKED by the USPS, is used to schedule USPS workers and equipment within major post offices. POSKED prescribes the optimal personnel schedule which ensures that all mail is promptly processed.

POSKED is a particularly interesting application for two reasons: first, the Postal Service is familiar to all of us and impacts us daily; and second, it is an example of a large-scale personal computer-based application. Customers frequently ask us if they can run large problems on a PC; POSKED generates problems with millions of non-zeros and runs successfully on a fast PC.

The POSKED objective is to minimize the total number of work hours required to process various types of mail over a 1-week schedule. The application currently uses one-hour scheduling "blocks" or intervals, but will ultimately evolve to accommodate 30-minute intervals. Constraints and bounds govern such issues as availability of various types of processing equipment, "carryover" of work from one time interval to the next, availability of workers with specific job skills within each time interval, and schedule restrictions (limits on part time work, daily job duration requirements and restrictions, etc.).

For a large post office example with 116 "mail types", the weekly one-hour interval scheduling model described above generates a 28 MB problem file consisting of 24,000 constraints and 2 million non-zeros. Stu Fox at the USPS is currently solving these large POSKED models successfully using a 80486 PC configured with more than 120 megabytes of random access memory (RAM).

While the 486 PC platform is currently viable for this application, the USPS is considering moving the POSKED application to a UNIX workstation platform. This move is planned to improve solution speed and in anticipation of the evolution to even larger problems.