CPLEX 6.0: Breathtaking Performance Gains

Beginning on May 1, 1998, the ILOG CPLEX Division began shipping CPLEX 6.0 to all customers. For linear programs, CPLEX 6.0 contains astonishing performance improvements, primarily on large problems. On the CPLEX Division internal test suite of large (>10000 row) problems, the CPLEX 6.0 simplex algorithms were, on average, over 4.5 times faster than CPLEX 5.0. For some large customer problems, we have seen even more dramatic performance improvements. For this same test suite, the CPLEX 6.0 Barrier algorithm performed, on average, 2.3 times faster than CPLEX 5.0 Barrier. The CPLEX 6.0 Barrier Solver crossover (to a basic solution) averaged 3.6 times faster than the crossover feature in CPLEX 5.0.

For mixed integer programming problems, CPLEX 6.0 offers the ability to solve much larger problems with reduced system memory requirements. The redesigned node file feature of the CPLEX Mixed Integer Solver allows models with very large branch-and-bound trees to be solved in less physical memory and with better utilization of overall system resources. See the article on page 5 for more information.

CPLEX 6.0 also introduces features to make it easier to port CPLEX Callable Library applications between Unix and Microsoft Windows NT, Windows 95, and Windows 98 platforms. A new Dynamic-Link Library (DLL) is provided for Windows users along with a Microsoft compiler compatible import library, making it much easier to link Callable Library applications to the CPLEX routines.

Upgrading existing Callable Library applications from Version 5.0 to Version 6.0 requires minimal changes to existing source code so that users can take advantage of the new features of CPLEX 6.0. Most users will simply need to recompile and relink their applications, and users with large-scale linear programs should observe an immediate performance improvement.

By now, all CPLEX licensees subscribing to Maintenance Services should have received their CPLEX 6.0 updates. If your maintenance has expired, call (or email updates@cplex.com) for maintenance renewal information.

Parallel CPLEX for More Platforms
CPLEX 6.0 Parallel Solvers are now available on key shared memory multiprocessor (SMP) parallel architectures, including those available from: DEC, Hewlett-Packard, Silicon Graphics, Sun and Intel-based computer vendors. Parallel versions of the Barrier Solver and Mixed Integer Solver are available on all parallel platforms. Parallel simplex availability varies by platform. Please contact us for more information.

Achieving Your Goal with MIP

What is your goal when solving a Mixed Integer Program (MIP)? Often, the problem nature or time constraints dictate solution criteria short of a provably optimal solution. The CPLEX Mixed Integer Solver provides features that can help you achieve the desired goal. It is important to realize that the default strategies in CPLEX MIP are pre-set to balance optimality and feasibility considerations. While the defaults work well in the majority of cases, we recommend investigating optional strategies that consider the particular goal for your application.

Finding feasible solutions. One goal is to find an integer feasible solution as quickly as possible. CPLEX can be directed to stop after finding the first integer feasible solution by setting the "MIP SOLUTIONS LIMIT" parameter to 1. There are a number of CPLEX options that can help reduce time to the first solution. The root heuristic option (MIP STRATEGY ROOTHEURISTIC) or the node heuristic (MIP STRATEGY HEURISTICFREQ) options are often successful. The root heuristic executes once at the root node by fixing some variables and then doing a depth-first search branch and bound with the specified variable selection strategy. The node heuristic is activated by setting the heuristic frequency parameter to either a positive value to indicate a fixed frequency, or -1 to indicate an automatically determined frequency. The heuristic is applied at nodes at this frequency. Fractional variables are fixed recursively at the selected nodes to find an integer feasible solution. We have found that using the node heuristic is successful on about one-third of our difficult test problems in improving overall solution time, and on an even higher fraction in attaining integer solutions more quickly.

Another means of finding a first feasible solution is to try the strong-branching variable selection strategy (MIP STRATEGY VARIABLESELECT 3). Strong branching sometimes will avoid infeasible branches and thus get to a feasible solution in fewer nodes; as a bonus, the solutions found with this strategy often have good objective values. The best-estimate node selection strategy (MIP STRATEGY NODESELECT 2) can also help to find a first integer solution; this strategy considers objective function value and infeasibility in choosing nodes to explore when backtracking.

Priority orders can also be very helpful in obtaining a first integer feasible solution. If you know that certain variables in your MIP need to be considered before others, CPLEX can use that knowledge to make better branching decisions. If you don&##146;t wish to construct the orders file yourself, CPLEX has some heuristics for generating priority order files based on problem structure; one of the MIP ORDERTYPE options might generate a good order file for your problem.

Finding many feasible solutions. A second goal might be to obtain as many feasible solutions as possible in a prespecified amount of time, by setting the TIMELIMIT parameter. The features used to obtain a first integer solution can be used to attain this goal. One additional feature is to set the backtrack parameter to a large number. This forces the branch and bound process to stay deeper in the tree.

Proving optimality. A third possible goal is to prove optimality as quickly as possible, because you already have a solution which you think is optimal. In this case, try the strong branching variable selection parameter. Its aim is to move the best bound more quickly by choosing variables that have a large effect on the objective. The node selection strategy should be best-bound (MIP STRATEGY NODESELECT 1), and a MIP STRATEGY BACKTRACK parameter value of 0 will force the branch and bound process to stay high in the tree. If you have obtained the solution by some other set of strategies than those suggested here, you might want to discard the branch and bound tree and start again to prove optimality. The MIP start feature allows you to save the solution and use it when starting a new tree.

Priority orders can also be useful for proving optimality. You would want to specify the priorities so that the variables with the largest effect on the objective are branched upon first.

Some consider solving MIPs a bit of an art rather than a science; use the suggestions above as an inspiration to allow you to solve your MIPs according to your goals.

ILOG CPLEX Callable Library Training Dates
ILOG&##146;s CPLEX Division will offer two-day training sessions to help CPLEX users take full advantage of the Callable LIbrary. Both sessions will be held near the CPLEX offices in Incline Village, Nevada on the North Shore of Lake Tahoe.

Session 1: September 21 & 22, 1998

Session 2: April 19 & 20, 1999

Please visit our web page for full details and registration information.

Using the CPLEX 6.0 Node File Feature for MIP

The redesigned node file feature of CPLEX Version 6.0 allows you to solve MIP problems that generate large branch and bound trees in a smaller amount of memory and with less overall impact on system resources. We have actually solved a MIP that generated a tree of size 1.5 gigabytes on a PC with 32 megabytes (MB) of real memory, using the node file option for disk with compression. For most problems, using the node file feature results in only a small performance degradation. Within the ILOG CPLEX Division, we use the node file feature whenever we solve a MIP that generates a large tree.

The branch and bound tree will be stored in-memory until the tree memory limit is reached. That limit should be set to some portion of the system memory of your computer. For example, on a computer with 32 MB of memory, set the tree memory to 16 MB. On a computer with more than 64 MB of memory, we have found that setting the tree memory limit to about 32 MB is sufficient for good performance.

Once the tree memory limit is reached, the least promising nodes of the tree are transferred to a series of node files. The user can choose whether the node files are stored in-memory or on disk, and whether or not the node files should be compressed. When these nodes are needed for processing, they are transferred from the node file data structure (i.e., from memory or disk) to the in-memory tree. The compression option reduces the size of the node files by 2X to 5X, adding very little processing time.

Here is an example, run on a 32MB PC running CPLEX under Windows 95. The model was run for 200,000 nodes. The &##145;No node file&##146; run was made with no limit on the tree memory; the other options used a 16MB tree memory limit. When the node file was in memory and compressed, the total memory utilization for the tree and the node files was 20.5 megabytes.

* For this problem, the OS + CPLEX process memory requirements exceeded available memory, and some swapping to disk occurred, impacting performance.

CPLEX is Year 2000 Compliant

ILOG CPLEX Division is occasionally asked to document its products&##146; ability to deal with the change from year 1999 to 2000. Happily, the answer is simple: CPLEX will work correctly in the new century. This has been the case at least since CPLEX Version 4.0, released in December, 1995.

Internally, CPLEX is designed to use ANSI C standard functions, conforming to ANSI/ISO 9899-1990, that return values in terms of an offset from a base year, rather than a specific number of decimal digits. Thus, there is no special programming required to handle the year 2000 and beyond. Issues such as leap year are not relevant to CPLEX&##146;s functioning, and in any case are handled by the above functions.

Please note that if you intend to test your own CPLEX Callable Library applications for Year 2000 compliance by resetting your system clock, AND if your CPLEX license is temporary rather than perpetual, you will corrupt your CPLEX license by setting the system clock forward and then backward even if your license is valid beyond year 1999. This is a license security feature and is not a Year 2000 issue as such (the choice of forward date is immaterial). Feel free to contact our license administration staff for assistance or advice regarding testing.

CPLEX on the Internet
Be sure to visit our Web site http://www.cplex.com for more information regarding CPLEX. We are continuously updating the site to try to provide more information to our users. One recent addition is a complete archive of all the past CPLEX newsletters. Please send any additional CPLEX web site suggestions to webmaster@cplex.com Other CPLEX e-mail addresses:

Also check out http://www.ilog.com/ to learn more about ILOG and ILOG products! ILOG offers an impressive line of high-performance C++ and Java components for visualization and control as well as optimization.

CPLEX Division Personnel News

Mark Steidel has joined the ILOG CPLEX sales organization as an inside sales representative in charge of the CPLEX academic sales program. After receiving a BS in Journalism from San Jose State University, Mark worked as a freelance journalist for several Bay Area and national publications. In October 1997, he joined ILOG in Mountain View as a sales administration assistant. In March 1998, Mark transferred to his new position at the CPLEX Division office in Incline Village, NV.

You may have noticed a new friendly voice answering the phones at the CPLEX Division office. That belongs to Terri Viehmann, who joined the CPLEX team in February 1998 as the Office Administrator. Terri comes to us with 10 years of experience in office administration, with a background in operations, sales and marketing. Before joining ILOG, Terri worked for Booth Creek Ski Holdings in the Lake Tahoe area; prior to that she worked at Cisco Systems in San Jose. Terri studied Business Administration at San Jose State University.

Dr. Zonghao Gu joined the CPLEX team as a Senior Developer in July 1998. Gu received his PhD in Industrial Engineering from Georgia Tech in 1995. Before joining CPLEX, Gu was a software developer at Retek Information Systems and LINDO Systems Inc. Gu will contribute to CPLEX LP and MIP algorithmic development.

Dr. Irvin Lustig has moved from the CPLEX development team to the ILOG CPLEX Optimization Marketing Team, and is now the Product Manager for Math Programming Products for ILOG.

Congratulations to Ed Rothberg, Senior Developer, and wife Jessica on the April 23, 1998 birth of daughter Rachel (7 lbs, 13 oz).

Congratulations are also due to Wendy Cory (previously Wendy Ferris) on her marriage to Russel Cory.

End User Application Feature:

CPLEX Simulations Used to Evaluate Hydroelectric Facilities

H. R. L. Morrison & Co. is a specialist merchant bank that manages three funds, Infrastructure and Utilities New Zealand Limited, Infratil Australia Limited and Infratil International Limited. The funds invest in electricity, ports, airports and other infrastructure and utility assets around the world. (See http://www.infratil.com) As part of managing these funds, H. R. L. Morrison & Co. must assign a monetary value to electricity generation and transmission assets and hydroelectric power companies in particular.

To accomplish this, Matthew Civil (Matthew_Civil @HRLMorrison.com) has built a generic electricity market model, EMM. This model consists of:

• a static input database describing components of the system
• a control database for selecting components, options, and parameters
• a simulation engine with a linear program at its heart
• an output database for each simulation run; spreadsheets and database queries for input and output analysis

The input database consists of forecast demands, thermal station offers, historical flow data, exogenous inputs, and descriptions of each station and how they are connected. For each country, different samples describe uncertainties in the hydro inflow, demand, and station availability. Given a particular network and scenario, an LP schedules the generation and determines the market clearing prices for a given week over a set of time intervals of varying length. The electricity prices are determined using the dual variables on the demand constraints.

A year&##146;s activity can then be simulated. For each of say 50 Monte Carlo samples, a set of 52 linear programs are solved, one representing each week. So each year involves solving a sequence of over 2500 linear programs with CPLEX. A summary of each week&##146;s results is written to a database. Four major categories are recorded: Prices, generation, link transfers between areas, and the amount of pump storage or peak shifting (i.e., methods for moving the demand around). Revenue is then computed, as well as the fuel costs, contract payments, and transmission rentals.

After simulating a number of scenarios over a number of years, the results are analyzed to determine whether investing in a particular facility is a profitable venture for the investment fund. The model can also be used to suggest how a particular facility can be run more efficiently in order to take advantage of the higher prices that are available during hours of peak demand. H.R.L. Morrison & Co. also uses their model to assist in capacity planning for the power companies that Infratil owns.

By using a linear program, rather than a hand coded heuristic scheduler at the heart of the simulation model, the model:

• is clear, comprehensible, and reliable;
• uses one tenth of the code;
• can be confidently changed and adapted to explore new issues within workable timeframes; typically 20 times faster;
• runs more slowly but is still quite practical at 40 seconds on a 200MMX for each yearly sample.

CPLEX Questions and Answers

Q The CPLEX Callable Library enables me to implement my model by assembling the problem data arrays all at once or by incrementally adding rows, columns or matrix coefficients. Which way is the best?

A The best approach depends on the particular characteristics of your application and models. Relevant considerations include ease of coding, problem generation time relative to total application time, and memory management. You should determine the importance of each of these for your specific application, then decide which one should be given highest priority.

For applications where the top priority is the ease of coding the problem generation step, just create the problem using the easiest method. This will vary depending on your model. Each of the four distinct problem generation methods CPLEX provides is superior for certain types of formulations.

When minimizing the problem generation time is most important, you will probably want to generate the problem by column. CPLEX&##146;s internal data structures represent the matrix by column, so it can process column additions more efficiently than row additions or changes to a group of matrix coefficients.

Whenever you choose to incrementally build a problem, an understanding of how CPLEX manages problem data memory will help your program operate more efficiently. While the default values typically suffice, judicious settings of the problem growth parameters will improve the efficiency of the problem generation and subsequent optimization in certain cases. In particular, try to avoid small values for the row, column or nonzero growth parameters, since that might cause frequent memory reallocations, resulting in both increased time to generate the problem as well as a fragmented memory heap that could affect the subsequent optimization. For example, suppose an application builds a large problem in small increments using modification routines. If reasonably accurate upper bounds on the number of rows, columns, and nonzeros are known beforehand, setting the growth parameters to these bounds would cause CPLEX to perform the fewest memory reallocations. However, keep in mind that overly generous bounds on the problem dimensions could result in excessive memory usage.

Summarizing, a brief evaluation of the relevant model generation issues before you start coding will save significant development and debugging time later in the coding process.

Q I am debugging a Callable Library application that currently results in a segmentation fault during one of the CPLEX routines. CPLEX enables me to write out the problem in my application in LP, MPS or binary SAV format. Which format is most suitable for debugging?

A The best debugging tactic is to write out both MPS and SAV files. By solving both the MPS and SAV files of your problem with the CPLEX base system, you can often obtain more information than by solving the problem in just one of these formats.

MPS format is column-oriented text, while the CPLEX SAV format contains the exact binary representation of the problem data arrays in the program that generated it. If an application faults during a CPLEX routine, the most likely causes are invalid values in the function arguments, or corruption of the application&##146;s memory heap. If the problem data is invalid, the segmentation fault that occurred in the application will probably also occur in interactive CPLEX. But, it will not occur when interactive CPLEX inputs an MPS file. In this case the diagnostic routines in the check.c file that comes with your CPLEX distribution should help you locate the source of the trouble. If the problem arrays contain valid data but the memory heap has been corrupted, then interactive CPLEX will probably solve the problem in both SAV and MPS format. In this case, a memory debugging tool like Purify or Insure will dramatically reduce debugging time. If no memory diagnostics are available, commenting out sections of the application may help isolate the source of the heap corruption.

The CPLEX LP format is the most useful for visual examination of your problem. LP files are row-oriented text files, so you can easily view the variables and constraints in your problem. This is useful for verifying the correctness of the problem generated by your program. However, because they are row-oriented files with finite numerical precision, interactive CPLEX may take a different path to the optimal solution than your application does. Thus, you are less likely to reproduce the behavior of your application using LP files.