Announcing Parallel Barrier Solver
CPLEX Parallel Barrier LP solver is now available from CPLEX on Silicon Graphics multiprocessing systems. This exciting new technology breaks all known LP solution time records, with computational speeds exceeding 2 gigaflops on real-world problems!

Until recently, most developers and users have believed that LP algorithms could not be effectively parallelized. Yet CPLEX Parallel Barrier achieves significant parallel speedups of up to 10X.

For existing Callable Library users, only a few minor modifications to existing makefiles are required in order to use the Parallel Barrier software.

Users with difficult problems containing a large number of nonzeros should consider this new enabling technology. Developed in conjunction with Silicon Graphics, the Parallel Barrier Solver is available today for SGI machines. Interested commercial customers are encouraged to send problems for benchmarking. Call for pricing and ordering details.

Callable Library Design Revisions
The next CPLEX release (scheduled for release in Fall/Winter 1995) will include a major re-design of the Callable Library. This re-design is needed to make CPLEX more compatible with emerging computer and software development environments (such as parallel environments and new PC development environments). With the re-design, global and static variables will be eliminated, global namespace requirements will be significantly reduced, more modern/consistent naming conventions will be adopted, certain routine types will be consolidated, and other modifications will be implemented to facilitate the use of CPLEX Callable Library routines inside emerging development environments.

For compatibility, the calling conventions and routine names you are familiar with in CPLEX 3.0 will also be permitted. However, we will encourage developers to convert their applications to adopt the newer conventions. As always, we will take extra steps to provide a smooth migration path for existing users.

CPLEX Quadratic Solver
The CPLEX QP solver remains available for beta testers willing to provide input and feedback on their experience. Any user currently licensed to use CPLEX Barrier can volunteer to add the QP solver at no additional cost. The CPLEX QP solver will become a standard part of the Barrier Solver with the next release. Please call or send email (info@cplex.com) if you are interested in trying the QP solver.

Callable Library Training

Another CPLEX Callable Library training session has been scheduled May 18-19 in Philadelphia. This two-day session "Using the CPLEX Callable Library" will focus on general aspects of efficiently linking CPLEX Callable Library routines with user applications. This session will be generalized for all computer platforms. The cost to attend the two-day session will be $845 per person (the cost for additional attendees from the same company on a single registration order is $725).

The training will once again be conducted by Dr. Irv Lustig, Director of Numerical Optimization for CPLEX. The location will be the Penn's View Inn, an award-winning small hotel in the Philadelphia waterfront area, within walking distance of most Philadelphia historical sites. A block of rooms have been reserved at the Penn's View Inn. Please contact Lorrie Harlem (lharlem@cplex.com) for registration and accommodation details.

Registration will be limited to keep the sessions small (to maximize interaction with the instructor). So please sign up early if you are interested.

Improving MIP Performance using CPLEX Parameters and Features

Prior articles in this series have focussed on improving the formulation of mixed integer problems. This article will examine opportunities to use CPLEX features and adjust CPLEX parameter settings to improve solution performance after the problem has been fully formulated. CPLEX has heuristics based on problem characteristics for setting the default values of the MIP strategy parameters, but often performance can be improved by explicitly resetting these parameters, particularly if you have specific knowledge of your problem's characteristics.

Try the alternate best-estimate node selection strategy. It takes into account infeasibility information, so it is very helpful on problems with tightly clustered objective values. Also try the pseudo-cost variable selection strategy. The best-estimate node selection and pseudo-cost variable selection strategies often work well together, so be sure to try these in combination.

If the first solution is far from the best bound value, or you can not seem to get an integer solution, try strong branching. This strategy seems to be best on problems where the ratio of binary columns to rows exceeds 10 and where no cuts are generated; it has also been very successful on some general integer problems.

Many integer programs have a choice component, that is, one of a set of binary decision variables needs to be set to one and the rest must be zero. The constraint that enforces this is a sum of binary variables either less than or equal to or equal to one. Setting the branch parameter to "up" causes the selected branching variable to be set to one, which then forces all the rest of the variables in the constraint to zero, which eliminates all the infeasibilities in that constraint. Selecting the "down" branch setting is weaker, since only one infeasibility will be eliminated.

Sometimes a good integer solution is found early, but then many nodes must be examined to prove optimality. You can speed the process if you are willing to change the guarantee on optimality. The default relative optimality tolerance is 0.0001; this means that the final integer solution is guaranteed to be within 0.01% of the optimal value. If you can accept a larger variation from optimality, change the relative gap parameter. The absolute gap parameter should be changed instead if the objective values are known to be near zero.

The objective difference parameters can also be set to speed optimality proving. Setting these parameters helps when there are a lot of integer solutions with similar objective values. Setting these parameters causes the search to skip all potential solutions within the objective difference value of the best integer solution so far. Since the true integer optimum may be in one of the skipped intervals, the objective difference setting also changes the guarantee of optimality. Both relative and absolute settings can be given for the objective difference parameter.

The cutoff parameters can be very helpful in restricting the search. If you know that there are solutions within a certain distance from the initial relaxation, set the upper cutoff parameter for minimization problems and the lower cutoff parameter for maximization problems.

Priority orders can be used to obtain better solutions. Problems that have integer variables for different types of decisions, say variables to activate processes and variables to use processes, should have higher priorities assigned to the variables that should be decided first. Priorities based on the magnitude of objective coefficients are often effective.

If you know a heuristic for obtaining a solution, you can set priorities either to force the heuristic solution or to guide the branch and bound process. To force a first solution, set a priority value and a branching direction for each variable to reflect what the heuristic says should be a solution. Run CPLEX MIP to obtain this first solution and then exit, by setting the parameter to limit integer solutions. Set the order parameter to ignore the priority order, and re-solve.

To use the heuristic to guide branching, use the information from the heuristic to set the priorities. For example, on set covering problems, a greedy heuristic would be to assign columns to the solution ordered by the ratio of cost to rows covered. The cost to coverage ratio can be used as a priority value.

Objective function coefficients are used in various ways to guide the branch and bound search, so it is best if the objective coefficients are in the objective row, not in a constraint row. That is,
min 5 x1 + 7 x2 + 9 x3
is better than the equivalent (but less efficient)
min z
subject to 5 x1 + 7 x2 + 9 x3 - z = 0

The simplex dual gradient should be changed to steepest-edge pricing if the subproblems consistently take more than 100 iterations.

Q & A

Q. What "front-end" modeling products are available for use with CPLEX?

A. By "front ends" most users mean modeling languages or systems. These products act as "interpreters"-they read models written in a concise, generalized algebraic form, and generate the explicit problem matrix that CPLEX (or any other LP solver) requires as input.

CPLEX has been closely linked with several excellent general-purpose modeling languages, including AIMMS, AMPL, GAMS, and MPL. CPLEX is also linked with several more specialized and powerful modeling systems, including MIMI (Chesapeake Decision Sciences), OMNI (Haverly Systems), and PIMS (Bechtel). Please contact CPLEX (or send a fax or email) for information on any of these products.

Q. When should I use a modeling language to create my model, and when is a Callable Library application preferable?

A. These are somewhat different approaches to modeling and working with your problem, each with distinct advantages. (While modeling languages vary, the following comments generally apply to all of them, although to varying degrees.)

By writing a Callable Library application to generate the problem matrix, you maximize the efficiency and performance of your application. Using the Callable Library, the problem may be generated into memory, avoiding any wasted time reading and writing files. Your application can include a sophisticated user interface which completely shields the end user from the complexities of math programming. A Callable Library user has maximum flexibility, and full access to all CPLEX functionality. This approach, however, will require some initial programming, although most users with any programming experience find this relatively easy.

For users who prefer to think of their problem in more generalized, algebraic terms, it may be easier to begin with a modeling language. Most models, even large, complex models, can be expressed as a brief set of model statements using indexing, summations, etc. The model can then be readily modified and maintained. Some investment is required to "learn to speak" a given modeling system's "language", but the time required to become proficient is reasonable.

The modeling language approach will result in faster model development, but it is also less computationally efficient. The interpretation step, in which the general model statements are interpreted and the complete matrix explicitly generated, takes time and consumes computer memory (for many models, more time than actually solving the problem). Also, the problem/solution information is typically then passed to/from CPLEX via files. This entire process is more time consuming and less efficient than a tightly integrated Callable Library application. Once a problem is passed from a modeling language to CPLEX, the user has less control of the optimization process; the user must generally wait until the problem is solved and control returned to the modeling system. In contrast, a Callable Library application allows the user to intervene in the solution process at any time. This capability is critical for users who need to customize the solution process, or access progress information during the solution pr ocess. Finally, modeling languages make only certain CPLEX features available to the user.

So a modeling language approach is typically recommended for users who create or prototype a number of models, and must do so with minimum development time. This approach is also recommended for users with models that change, or who prefer maintaining a generalized model file to maintaining a Callable Library application. A Callable Library approach is recommended for the development of systems that will be used repetitively, or for applications where optimization must be tightly and seamlessly integrated. The Callable Library approach is also recommended when overall application performance is a priority, where complete flexibility and access to CPLEX features are required, where a custom user interface will be incorporated, or where the solution process is to be interrupted/customized. Many users find BOTH approaches useful, even within the same project: a modeling language may be used to rapidly prototype models for project justification, and then a Callable Library application may be created for the final project implementation.

Static & Dynamic Link Libraries for PCs

PC Callable Library versions for Windows 3.1, Windows NT, and OS/2 include the Callable Library in two forms: a static library and a dynamic link library (DLL). Why both? Some developers want to create native Windows or OS/2 applications using our standard static library and the Watcom C/C++ development environment. Developing such applications is similar to creating CPLEX applications on most other platforms (such as UNIX). Other developers require that the interface with CPLEX be through a DLL, most likely because they are working in a different development environment, such as Visual Basic, Borland C, or Visual C/C++. The use of DLLs may also result in reductions in compile time, link time and disk space, without any sacrifice in CPLEX functionality or performance.

CPLEX DLLs have been created using the 32-bit Watcom C compiler. Because Windows NT and OS/2 are 32-bit operating systems, calling the 32-bit DLL from a C program in these environments requires only a few simple modifications. Code written on UNIX or other operating systems can be easily ported. Unlike Windows NT and OS/2, Windows 3.1 is a 16-bit operating system. As a result, some additional work is needed to facilitate the communication of information from the 16-bit Windows operating system to the 32-bit CPLEX DLL for Win 3.1.

To use the CPLEX DLL under Windows 3.1, users must become familiar with the interface between the 16-bit Windows world and the 32-bit Watcom/CPLEX world. All functions in the CPLEX Callable Library expecting pointer arguments expect 32-bit near pointers. Because 16-bit applications have no way to create or dereference such pointers, it is required that the Library user create memory objects in the 32-bit Watcom data space that can be used by the CPLEX Callable Library. Hence, the Win 3.1 CPLEX DLL includes utility functions to allocate memory in the Watcom data space. A Library user can allocate memory in the Watcom memory space, and then use other CPLEX utility functions to copy data to and from the 16-bit Windows memory space to the 32-bit Watcom memory space. Note that when Microsoft releases the 32-bit Windows 95, developers should no longer need to accommodate the 16-bit limitations of Windows 3.1.

With memory management properly set up, 16-bit Windows 3.1 applications can take advantage of the 32-bit speed and power of CPLEX. The Win 3.1 CPLEX DLL has been successfully accessed from Microsoft Visual C/C++, Microsoft Visual Basic, and Borland C/C++. The DLL design emphasizes compiler independence, so other compilers capable of calling a DLL should also be able to access it. However, in the event that another compiler has conventions that prevent it from accessing the DLL, users also have the option of building their own customized DLL based on the CPLEX Callable Library for Windows. Users may also wish to build their own DLL if they want to create their model directly in the 32-bit memory space and avoid maintaining two copies of the problem.

Under Windows NT and OS/2, which are full 32-bit operating systems, memory management is not an such an issue. The CPLEX DLLs for these operating systems can access memory allocated in the calling program, and vice versa. A file of cover functions handles the details of calling CPLEX routines and simplifies the process of porting applications from other platforms. The CPLEX DLLs for Windows NT and OS/2 have been successfully accessed from Watcom C/C++ 32 and Microsoft Visual C/C++. Other compilers capable of calling a DLL should also be able to access them, but users can also build their own customized DLL based on the static version of the CPLEX Callable Library for Windows NT or OS/2.

By using a CPLEX DLL, developers can take advantage of Windows and OS/2 software that permits easy creation of elegant graphical user interfaces without sacrificing optimization performance. The result is that CPLEX becomes accessible to more developers under more development environments.

New CPLEX Home Page on Internet World Wide Web

For those with internet connectivity, check out the new CPLEX "Home Page" on the World Wide Web. CPLEX's World Wide Web server can be accessed via the URL (Uniform Resource Locator) http://www.cplex.com/

Consult the CPLEX Home Page for company and product news and information, answers to frequently asked questions, and technical support information.

As time goes on, we will be adding more features and information to the CPLEX Home Page.