|
CPLEX 5.0 Is Here!
CPLEX has just begun shipping CPLEX 5.0, our fastest and most efficient version ever!
Here are some of the highlights of this newest release: Better performance and robustness:
All algorithms have been improved, but MIP users will see the most significant performance
improvements, due to algorithmic innovations including improved strong branching
algorithm, multipass Presolve and Aggregator reductions, new MIP heuristics, enhanced
cover cuts, new alternate best-estimate search method, new starting point input ability,
new ability to generate a default priority order, new heuristic callbacks, and much more.
Users of all algorithms will benefit from improvements in CPLEX's Presolve and Aggregator,
doing more problem reductions in less memory. The Barrier Solver has been updated to
better handle primal infeasible problems.
More efficient use of memory: MIP users will see reductions in amount of memory
required to solve their problems with CPLEX 5.0. Huge memory usage reductions-50% or
more-are common using CPLEX 5.0 on MIP problems. The CPLEX Presolve has also been improved
to use less memory, so all problems can benefit. Since CPLEX relies on in-core access to
LP and MIP data structures for blazing speed, improved memory efficiency means that users
can solve larger problems with better performance.
New memory model: For developers, the most notable change in CPLEX 5.0 is the adoption
of a new memory model for creating LP problems and passing them to CPLEX. The new model is
simpler and more friendly to C++ developers. For all developers, the new model is more
intuitive and flexible. See the article on P. X for more complete information.
More information and control: We've added a number of features to give application
programmers more information, more control, and more flexibility. More solution progress
information is available. And there are more "hooks" into the algorithms
themselves, allowing users to have more influence on performance. The display command
options in the Base System interface have been upgraded to add more options. Parallel
algorithms on more platforms: CPLEX 5.0 is available with record-shattering Parallel Dual
Simplex, Parallel MIP, and Parallel Barrier algorithmic options. With this release, CPLEX
Parallel algorithms are available on additional parallel computing environments, including
systems from Sun, Hewlett Packard and Digital Equipment. For SGI parallel systems, the
first parallel environment supported, parallel support has been extended to primal as well
as dual simplex.
And much more: C++ programmers will appreciate not only the new memory model, but also
the C++ example wrapper class we've provided for CPLEX 5.0 (in source code form). Our file
readers have been improved, as have many display options.
CPLEX 5.0 has already begun shipping for new licenses. CPLEX licensees subscribing
to Maintenance Services will be receiving updates shortly. Academic users of
earlier versions should consult our web page for upgrade ordering information.
As always, we're hard at work on the next release, even before the ink is dry
on 5.0 documentation. Any enhancement or feature addition suggestions from users
are more than welcome! Call, fax, or email your thoughts to us.
CPLEX Merges with ILOG
CPLEX merged with ILOG effective 8/20/97. Besides the fact we now answer the phone
"ILOG CPLEX", what does this mean for CPLEX customers? You won't see many
changes short-term; but over the long run, this should mean lots of exciting new things
are coming. The CPLEX team is now the ILOG CPLEX Division. The entire team is intact, and
still working together with exactly the same objective: to develop, market and support the
world's best linear and mixed integer programming optimization algorithms. CPLEX products
will not disappear; development for future releases continues just as before. The ILOG
merger simply means CPLEX will be infused with new resources and new ideas, and gain
better international exposure. ILOG management respects CPLEX's position in the OR/MS
community, and wants to keep our proven and successful business model in place.
There have been no major organizational or staffing changes within the CPLEX Division;
you will interact with exactly the same personnel as before. Our business systems,
policies and practices are basically the same as before. And we will remain in our same
offices here in Incline Village.
For our international customers, ILOG's world-wide sales force brings local sales and
support capabilities for CPLEX products. So it will soon be much more convenient to buy
and receive support for our products in other countries.
ILOG's broader product line also brings additional opportunities for CPLEX
customers. ILOG's family of C++ class libraries extend customers' options in
several ways. The ILOG constraint-logic optimizers broaden the range of problems
that can be solved quickly, particularly difficult combinatorial problems such
as scheduling problems. ILOG offers rule-based systems and a broad suite of
additional application development components such as those for creating graphical
user interfaces, managing data acquisition and much more. Many of these components
are available in Java as well as C++.
- Learn more about ILOG by pointing your browser to http://www.ilog.com/.
- If you have any questions regarding the merger, please feel free to contact
your sales representative (or email sales@cplex.com).
CPLEX Callable Library
Training Dates
CPLEX has scheduled two more sessions of the popular 2-day Callable Library training
sessions in Incline Village, Nevada on the scenic north shore of Lake Tahoe:
Session I November 6-7, 1997
Session II April 20-21, 1998
These classes are designed for developers and analysts who wish to use the Callable
Library most effectively. Participants will learn to take full advantage of CPLEX
functionality and to create efficient links to user-written applications.
Please check the training web page for registration details, or email
lharlem@cplex.com for more information.
CPLEX Personnel News
Dr. Roland Wunderling joined the CPLEX development team in March after receiving his
Ph.D. at TU Berlin. Roland brings expertise in LP algorithmic development, C++
programming, and parallel algorithm development. Roland speaks four languages fluently and
is a talented singer. He and his wife, Viola, are expecting their first child any minute.
Dr. Ed Rothberg became a CPLEX employee in September. Ed received his Ph.D. in Computer
Science from Stanford in 1992. Ed spent two years in the Intel Supercomputing Systems
group developing parallel sparse linear system solvers and parallel MIP implementations.
For the next three years, Ed was employed at Silicon Graphics working on a variety of
projects including collaborative efforts with CPLEX to develop the first commercial
parallel barrier code, sparse matrix ordering methods, a computational steering system for
visualizing the progress of mixed integer programming problems, parallel versions of
airline fleet and crew scheduling systems, and the first out-of-core implementation of
barrier.
Terry Stallman joined CPLEX in May as a client services administrator. Many of you have
(or soon will) communicate directly with Terry as he assumes first line responsibility for
license administration. Terry brings with him over 20 years of customer support
experience, in both telecom and software support. Terry is married, has a daughter, and
enjoys fishing, camping, and restoring classic automobiles.
Lorrie Harlem, who almost all CPLEX users have known for years as their licensing
contact, has been promoted to Manager of Client Services. Lorrie will make sure all our
client services benefit from her dedication to customer support.
The New CPLEX 5.0 Memory Model
Dr. Irvin Lustig
Version 5.0 introduces a fundamental change in the memory model used by the CPLEX
Callable Library. Callable Library users will benefit in a number of ways. First, the
responsibility of memory management of the CPLEX problem data is now removed from the
user. Memory required for calling the CPLEX routines can be allocated before a call to a
CPLEX routine, and freed immediately thereafter. Secondly, the new memory model offers
more ways to provide problem data to CPLEX. The user can create problems constraint by
constraint using calls to CPXaddrows(), or column by column using calls to CPXaddcols(),
or can provide a list of matrix coefficients using the new routine CPXchgcoeflist().
Thirdly, the new memory model makes it much easier for C++ programmers to use CPLEX. With
Version 5.0, source is provided for an example C++ wrapper class that implements some of
the functionality of the Callable Library. Finally, for those users who wish to read in a
problem from a CPLEX LP, MPS or SAV file, a single call to the routine CPXreadcopyprob()
can be used instead of the cumbersome data file reading routines.
Prior to Version 5.0, a Callable Library user was responsible for allocating memory for
a problem, filling the corresponding data arrays, and passing those arrays into CPLEX via
the routines CPXloadlp(), CPXloadlpwnames() or CPXloadprob(). After making a call to one
of these routines, it was the responsibility of the user to not change any of the elements
of the arrays, and to remember the addresses of the arrays so that the arrays could be
freed after a call to CPXunloadprob() or CPXfreeprob(). Hence, the user was required to
manage the memory that represented the entire problem that the user wished to solve.
Furthermore, the user was required to represent their coefficient matrix using a column
oriented sparse matrix data structure.
In CPLEX 5.0, the responsibility for managing this memory is now removed. A user first
creates a "problem object" via a call to CPXcreateprob(). This routine returns a
pointer to a linear program with zero constraints, zero variables, and an empty constraint
matrix. The user can then pass the data representing their problem using a number of
different methods. A user who wishes to continue to use the arrays that were used in prior
versions of CPLEX can call one of the new routines CPXcopylp() or CPXcopylpwnames() to
pass this same data into CPLEX. However, these arrays can be immediately freed after the
call, since CPLEX will copy the data into the problem object, rather than taking
"ownership" of the user's arrays. (For more information on converting existing
applications, see the Q&A in this newsletter.)
Other methods are also possible for passing the representation of linear, mixed
integer, or quadratic programs into CPLEX. It is no longer required to represent the
coefficient matrix in the column oriented sparse matrix data structure. It is now possible
to give a problem representation in pieces, using problem modification routines like
CPXaddrows() and CPXaddcols(). Three new routines, CPXnewrows(), CPXnewcols(), and
CPXchgcoeflist(), have been added to further assist the user in populating the problem
object with data. In particular, it is now possible to represent the coefficient matrix by
a row-oriented sparse matrix data structure, using the routines CPXaddrows() and
CPXnewcols() to pass the problem data to CPLEX. The Callable Library user no longer needs
to be concerned about whether there is space for problem modifications--CPLEX
automatically manages the memory for representing the problem data. CPLEX Callable Library
users should find that their Callable Library applications simplify after they begin to
use the new memory model. A small investment in time to convert an existing application
will yield great advantages for the future.
Memory Model Q&A
Q: The new memory model available in CPLEX 5.0 looks great. But how do
I convert my existing CPLEX Callable Library application built with an earlier version of
CPLEX?
A: First of all, CPLEX 5.0 still supports the memory model used in
Versions 4.0 and earlier, so conversion is not mandatory. But the new model is more
flexible, more intuitive, and much more consistent with object-oriented programming
practices, so many users will want to begin taking advantage of these benefits right away.
Also, the old memory model is no longer documented and may be removed from future CPLEX
releases, so we strongly suggest that you convert any applications you expect to maintain.
Converting such an application to the new memory model requires very few changes. The
difference in memory model affects only the way you pass problem data to CPLEX. The new
memory model simplifies this process, as you no longer need consider the maintenance of
the problem data arrays passed to CPLEX, and no longer need to consider memory allocation
issues.
Conversion steps are simply:
- Use CPXcreateprob() and CPXcopylp() instead of CPXloadlp() to instantiate the
problem.
- Free the problem data arrays immediately after calling CPXcopylp(). CPLEX has its own
copy of the problem after the CPXcopylp(), so freeing the problem data at the end of the
program wastes memory during the optimization.
- Remove code used to resize problem data arrays, since CPLEX now does this whenever the
need arises.
- If the application called CPXunloadprob() to free the problem, change the call to
CPXfreeprob(). CPXunloadprob() was relevant only with the old memory model.
Q: I have a problem that is infeasible. I notice that CPLEX returns
different sums of infeasibilities depending on particular parameter settings. Why?
A: Most linear programming texts discuss the phase I problem of
finding a feasible solution in terms of minimizing a sum of artificial variables. However,
CPLEX uses a slightly different approach involving a piecewise linear function to
represent the sum of infeasibilities. This function depends on the current basis and its
associated infeasibilities. Different parameter settings can result in a different
sequence of bases during phase I. As a result, CPLEX can determine a problem to be
infeasible at many different infeasible solutions with different sums of
infeasibilities.
|
