Development Update

Once again, our development investments over the past year will culminate in a CPLEX 2.1 update for both LP and mixed integer solvers (planned release: first quarter of 1993). CPLEX 2.1 will include significant enhancements and performance improvements for both linear programming and mixed integer programming solvers. And several other major CPLEX development projects are underway for 1993.

Linear Programming Enhancements in CPLEX 2.1:
Presolver and Aggregator--CPLEX 2.1 will include a new presolver for reducing problems and enhancing performance. Before the CPLEX LP solver is even invoked, Presolve identifies opportunities to simplify problems for faster LP solution. For some models, reductions of up to 80% in problem size are achieved, resulting in dramatic performance improvements. The CPLEX Presolve uses a variety of advanced techniques for problem reduction. The Presolve will activate at default settings, but may optionally be turned off by the user. All solution values are returned in terms of the original, unreduced problem formulation.

Enhanced dual--the new dual simplex option introduced in CPLEX 2.0 has been substantially improved for performance and also numerical stability. Performance improvements of up to 100% can be expected for many problems. For many problems, dual simplex is now superior in performance to primal simplex (still the default LP algorithm). Dual simplex also now includes a new optional pricing algorithm. With 2.1, even more than before, we encourage users to try dual simplex on their problems--even if the default primal method provides satisfactory results.

Improved primal simplex--Our development on dual simplex revealed opportunities to improve the primal algorithm as well. CPLEX has always maintained a reputation for numerical stability; but CPLEX 2.1 adds even more provisions to ensure numerical stability and overall reliability.

Mixed Integer Enhancements in CPLEX 2.1:
Special Ordered Sets--CPLEX 2.1 adds special algorithms which take advantage of "Special Ordered Sets" or "SOSs" of Types 1, 2, and 3. Where these sets exist, SOS branching algorithms can provide significant performance gains. To allow users to define SOS relationships within integer problems, our MPS file format has been revised, and a new SOS file format has been added. We have also added the optional capability to scan for SOS Type 3 sets, then automatically invoke SOS branching for any SOS Type 3 sets found.

Other MIP algorithmic options--CPLEX 2.1 mixed integer software now includes a new algorithm for variable selection using "pseudo-costs". CPLEX 2.1 will also allow users to more directly control how often CPLEX backtracks within the branch and bound tree. And the 2.1 update will include a new optional provision for using node integer estimates, rather than node objective values, to determine the next node to be explored when backtracking.

User-selectable subproblem algorithm--CPLEX 2.1 will allow users to specify the LP algorithm to be used for subproblems. While dual simplex, as used in CPLEX 2.0, will be the default and best subproblem choice for most problems, other options benefit certain problem types.

Other new features--With CPLEX 2.1, users will be able to set branching direction by variable (as well as globally, as allowed in 2.0). CPLEX 2.1 will include an absolute mipgap tolerance in addition to the relative mipgap tolerance included in CPLEX 2.0.

Finally, the improvements to dual and primal simplex algorithms mentioned above as LP enhancements will speed up performance on subproblems at each node, providing a significant benefit for MIP problems as well.

Other Development News
Even before CPLEX 2.1 is issued, development is proceeding on several other fronts. We continue to focus on algorithmic improvements for solving larger and more difficult mixed integer programming problems.

Also, look for several exciting CPLEX announcements in the first half of 1993. CPLEX Optimization will be expanding the "toolset" for optimization and math programming with several new, premium quality software products.

Have You Tried NETOPT Lately?

Occasionally we encounter users unaware that their problems could run even faster using the CPLEX Network Optimizer. Other users forget that the Network Optimizer can accept side constraints; that is, the problem need not be a "pure network" problem to benefit from using NETOPT. The Network Optimizer will find and "solve" the network portion of the problem, and then either simplex or dual simplex can be used to continue with the non-network portion.

On the pure network portion of a problem, NETOPT can be up to 100 times faster than either primal or dual simplex! Special properties of network problems permit the implementation of algorithms which are simpler and faster than alternative LP algorithms. So if the network constraints represent a fairly significant portion of the problem, the solution to the network piece may provide a superior starting basis. On the other hand, if the network represents only a very small percentage of the problem, this may not be true.

The best way to find out if NETOPT will benefit your problem is to simply try it. In the interactive versions of CPLEX, The Network Optimizer is invoked simply by executing the following command once a problem has been entered:

NETOPT {option}

where 'option' indicates how to proceed after the Network portion is solved. Allowable inputs for 'option' are 'OPTIMIZE' (continue using primal simplex), 'TRANOPT' (continue using dual simplex), 'STOP' (do not proceed to solve non-network portion), or the {option} statement may be omitted altogether (if omitted, the default is to proceed with primal simplex).

When trying NETOPT for the first time, use the 'STOP' option if your problem is large. This way, you can quickly learn if CPLEX finds a network, and if so, how large the network piece is, without directing CPLEX to proceed to iterate to optimality on the remainder of the problem. If no network is found, CPLEX will issue the message "network small or non-existent".

If CPLEX fails to identify a network, your problem may still contain a network component which, with minor reformulation, would be identified as such by CPLEX. If you suspect your problem DOES have network-type constraints, but CPLEX fails to find them, review pages 32 through 34 of the CPLEX 2.0 documentation describing network format and conventions.

Development is underway to further improve CPLEX's ability to find and extract networks embedded deeply within problems. We anticipate future releases of CPLEX will allow even more users to benefit from NETOPT.

CPLEX News

New Dealers: CPLEX welcomes the addition of two new international Dealers: Fourier Systems, in Israel; and Infosys, in France.

New Additions: Congratulations to Mary Fenelon, our Technical Director, on the October 30th arrival of Steven Robert Fenelon Gregory (8 lbs, 9 oz). We are pleased to report both Mary and Steven to be in excellent health.

New Supported Platform: DEC Alpha AXP

CPLEX will add the new DEC Alpha AXP systems to the supported platform list as soon as the new DEC systems are available in the first quarter of 1993. CPLEX will support the Alpha AXP systems under the OSF/1 operating system.

Q&A

Q. The Example1 1 program from the user documentation won't compile on my computer. The compiler complains about the redefinition of 'index', what's wrong?

A. Certain C compilers extend the C language to include a function called 'index'. If you change the name of the index array in example1.c to something else, say 'ndex', the program should compile cleanly.

Q. I recently licensed CPLEX for my SUN SPARCstation running Sun OS 4.1.x. We plan to upgrade our operating system to Solaris. Will we require a new version of CPLEX?

A. No. CPLEX software for Sun OS 4.1.x will run unaltered under Solaris.

Traveling Salesman Problem: New World Record

A team of researchers, calling CPLEX from custom programs, has successfully solved the largest Traveling Salesman Problem (TSP) ever solved. The team members were David Applegate (AT&T), Robert Bixby (Rice University), Vasek Chv�tal (Rutgers University), and William Cook (Bellcore).

TSP problems are formulated given n "cities," with all direct travel distances between pairs of cities. The object is to start at one city, then visit every city exactly once and do so traveling the minimum total distance. Commercial problems assuming this form include circuit-board drilling and other VLSI layout problems, as well as vehicle routing problems.

The team effort to break the record spanned 4 years, and involved a network of up to 50 computers–including DECstations, Sun SPARCstations, and SGI workstations–many running in parallel. In terms of elapsed computing time, the problem required about 12,000 hours to completely solve. But using knowledge gained from their research along the way, the team can now generate a feasible solution which can be proved to be within 0.1% of actual within five hours. The record-breaking problem covered 3038 cities. The prior record, 2392 cities, is not only significantly smaller, but also a much simpler problem which can now be easily solved, given what the team has learned.

Beyond tenacity, the record-breaking team attributes their success to a unique combination of talents. Says Dr. Bixby: Applegate is "a true data-structure and computer whiz"; Cook "knows more about the broad range of computational integer programming than probably anyone"; and Chv�tal had unique expertise in "the theory of cutting planes". Finally, Dr. Bixby is recognized as a leading leading expert on solving linear programming problems.

In terms of long-term benefit, the members of the research team believe they accomplished their goal to test the limits of what can be solved while at the same time demonstrating the limitations of cutting-plane methods. They also advanced the use of parallelism in a practical, problem-solving application. The team developed new combinatorial algorithms to handle the hard, combinatorial LPs they were faced with. Finally, they increased their understanding of data structures related to cut pools and the generation of many LP subproblems. Oh, and they did also manage to set a record.

Will the record be broken soon? While a larger but easier problem may be solved in the near future, the team considers it unlikely that anyone will top their performance on such a difficult problem anytime soon–unless a major breakthrough is discovered. Besides, according to Dr Bixby, "you'd have to be crazy" to do something like this again.