CPLEX 3.0 Release

3.0 Release: The CPLEX 3.0 release was completed on schedule in 2Q94. All commercial users with current maintenance/update services either already have or soon will receive 3.0 update shipments. CPLEX 3.0 includes many new features and performance enhancements which benefit all products. We encourage all users to load CPLEX 3.0 and begin taking advantage of these new features right away.

If you are not currently covered by maintenance/update services, please call us to find out how you can upgrade to CPLEX 3.0.

Academic users were mailed a 3.0 upgrade information package in May. If any academic users have not received this information about upgrading academic licenses to CPLEX 3.0, please contact Lorrie Harlem by phone, fax, or email (lharlem@cplex.com).

CPLEX Development Update

Development for the next CPLEX update (mid-1995) is already underway. We will continue to focus on improved performance and reliability for all solvers, with particular emphasis on performance for difficult MIP problems. A new quadratic programming solver is also in the works.

Early in the release development cycle, we are particularly interested in user requests or suggestions for new features or enhancements. Please send us any comments, suggestions, or requests that could benefit your models or applications.

CPLEX PC User Update: Windows Development

As the number of choices for PC development environments expands, so does the number of CPLEX PC products. CPLEX continues to support extended DOS, OS/2, and SCO UNIX. In addition, CPLEX is available for development in Windows 3.1 and Windows NT environments.

Windows 3.1: A CPLEX Callable Library version is now available for Windows 3.1 development. The CPLEX Callable Library for Windows 3.1 is a special object code library which does not require the PharLap DOS extender and which can readily be converted to a Windows Dynamic Link Library (DLL) using Watcom C/C++ 9.5. See the Q&A section for further discussion.

In the DLL form, you can use 16-bit compilers like Microsoft Visual Basic and Visual C++ or Borland C++for application development. These products are popular for creating graphical application interfaces and for their ability to interface with external data sources such as spreadsheets and databases.

Windows NT:CPLEX is also available for Windows NT. Windows NT, unlike Windows 3.1, is a true 32-bit operating system, eliminating the need for such things as DOS-extenders.

CPLEX Floating Licenses

With CPLEX 3.0, we have introduced floating licenses for UNIX networks. Floating licenses are particularly beneficial for very large workgroups who want to make CPLEX available to a large number of potential users (but only a fraction are expected to be using CPLEX at any one time).

Floating licenses are available for UNIX workstations connected on a network with active NFS services. Both academic and commercial floating licenses are available.

If you are interested in adding floating licenses, or in upgrading your existing license to include floating capability, please call or send email (info@cplex.com) for more information.

At Last: CPLEX Callable Library Training

We have received repeated requests to conduct training seminars for CPLEX software, particularly for Callable Library application development. While we have worked hard to make the Callable Library software as easy to use as possible, we recognize that many users could benefit from our experience in helping users develop compact, efficient Callable Library applications as productively as possible.

One or more 2-3 day training seminars entitled "Using the CPLEX Callable Library" will be scheduled for Fall of this year. Please contact Janet Lowe by phone, fax, or email (janet@cplex.com) if you are interested in attending a Callable Library training seminar, and what topics you would like covered. If sufficient interest exists, we can schedule several sessions.

If you have other specific training requirements, please let us know. For companies with enough users to justify on-site training services, special arrangements can be made.

Rethinking Mixed Integer Model Formulations

Part 2: "Tightening" Models by adding Constraints or Variables

Sometimes a model can be formulated using a smaller number of constraints. When solving continuous LPs, a formulation with fewer constraints would solve more quickly. For a MIP, however, the solution will commonly take longer, because aggregating the constraints leads to a larger feasible region where some of the integer nature of the feasible region is lost.

This can be illustrated graphically with a two-variable problem. A condition can be modeled by the constraint

x1 + x2 <= 2

where x1 and x2 are both binary integer variables.

A "tighter" representation of the integer feasible region is given by using the two constraints

x1 <= 1

x2 <= 1

because the corners of the original feasible region are not included.

Of course, the constraints above are already in the formulation as bounds, so this example is contrived; but the principle applies to larger sets of variables which cannot be depicted graphically.

Suppose there is a condition that if one of a set of processes is used (y1, y2, or y3), then a charge is incurred. This is an extension of the fixed charge formulation discussed in Part 1 of this series. Let x be the variable which is 1 if y1, y2, or y3 is used and 0 otherwise. The upper bound for each y variable is 1. One set of constraints describing this condition is:

y1 + y2 + y3 <= 3x.

Note that in this constraint, any value larger than 3 could be used, but the smallest possible value is chosen to avoid "Big M" troubles (see Part 1 in 12/93 newsletter).

A better representation is

y1 <= x

y2 <= x

y3 <= x

because the feasible region for the LP relaxation is smaller. The LP solution x = 0.1, y1 = 0.3, y2 = y3 = 0 would be feasible under the first formulation, but not the second.

So we have seen how increasing the number of constraints can sometimes lead to a better MIP formulation. But you would never want to increase the number of integer variables, would you? Wouldn't that increase the difficulty of model? Generally, more variables does mean a more difficult model, but there are exceptions. In particular, aggregation of variables can disguise relationships in the model which could otherwise be exploited.

For example, to model the choice of both a production facility and the process to use, you can have a variable that represents using each process at each site. However, the branch and bound algorithm would work more efficiently with additional variables representing the site selection if priorities are used so that the site selection variables are branched on first. Branching on a site variable results in setting whole groups of related site-process variables to zero all at once.

Another way to use extra variables is to add a variable to an inequality that has all integer variables, integral coefficients and an integral right hand side value. The slack for that inequality must have an integer value, so it can be added as an explicit integer variable and given a high priority order value. Setting the slack to an integer will make it more likely that the integer variables in the inequality will also take on integer values.

Q&A

Q: CPLEX reports that my large problem is infeasible, but the source of infeasibility is not readily apparent. How can I determine the cause?

A: CPLEX provides an Infeasibility Finder (new in CPLEX 3.0) for this specific purpose. This tool computes an Irreducibly Inconsistent Set (IIS) of constraints for an infeasible problem; removing any single constraint from this IIS will eliminate the infeasibility. The Infeasibility Finder thus narrows the search to a smaller set of constraints and bounds, allowing the problem to be pinpointed much more easily.

Q: I want to develop a CPLEX Callable Library application under Windows using Dynamic Link Libraries (DLLs). Can I do this using CPLEX?

A: Absolutely. CPLEX 3.0 for Windows is distributed as a static library which can be made into a DLL using Watcom C 9.5. This way, users can customize the DLL for their specific application requirements. The procedure, which varies according to the compiler being used, consists of writing cover functions for the CPLEX routines called by the Windows application, then combining the resulting object file with the Callable Library into a DLL. The cover functions transform pointers and data from the 16 bit addressing used by Windows 3.1 to the 32 bit addressing used by the Callable Library. A similar approach will work for creating Windows NT DLLs. The CPLEX Callable Library products for Windows 3.1 and Windows NT include instructions and examples.

Q: I have developed a Callable Library application which makes LP functionality transparent to the end user. How can I allow the end-user of my application to interrupt the optimization process without also exiting the calling application?

A: Interrupting optimization may be useful for a variety of reasons. Users of a real-time application may wish to terminate optimization and proceed with other aspects of the application as soon as an adequate solution is reached. Or a developer may want to provide customized status screens (by temporarily interrupting optimization, querying for status information, then resuming optimization, all transparent to the user). With the addition of callback utility functions in CPLEX 3.0, developers can temporarily transfer control back to to their own program, query for status information, and/or resume from where the interruption occurred.

Parallel Branch-and-Bound for Thinking Machines and Intel Computers

For years, math programmers and parallel software developers have recognized the potential for parallel implementations of mixed integer branch-and-bound algorithms. The nature of a branch-and-bound search tree, with many independent subproblems waiting to be solved, seems perfect for distribution to parallel processors. The availability of actual commercial products, however, has proven more elusive, due to the scarcity of large-scale parallel computer hardware and operating systems, and also due to the range of implementation issues and decisions such as centralized vs. decentralized control, processor communication, and load balancing.

Jonathan Eckstein at Thinking Machines Corporation has developed, in cooperation with CPLEX Optimization Inc., a parallel mixed integer solver implementation based on CPLEX for parallel Thinking Machines CM-5 computers. Eckstein's implementation using 64 to 128 parallel processors) solve large mixed integer problems up to several orders of magnitude faster than when solved using serial computation. Similarly, Ed Rothberg at Intel Supercomputers has developed a CPLEX-based MIP solver for use on Intel Paragon machines. Near-linear speedups are realized in both implementations.

Rather than focus on specialized algorithms for various MIP problem classes, these parallel developments used a general-purpose solver approach capable of solving a wide range of problem types efficiently. The objective, to develop an "industrial-strength" parallel implementation of a general-purpose MIP solver, was successfully achieved in both cases.

The speedups are most dramatic on larger problems, exactly where performance improvements are most needed. The problem sets used for testing focussed on real-world problems from commercial applications.

While development on parallel CPLEX algorithms is ongoing, the parallel MIP implementations for Thinking Machine CM-5 machines and Intel supercomputers is available for commercial applications today. Please call us if you are interested in learning more about CPLEX-based parallel algorithms, or in arranging a test on Thinking Machines or Intel computers.