Development News

The CPLEX development team is hard at work on the next CPLEX release, scheduled for later in 1997. As always, performance enhancements are the top priority, particularly mixed integer performance and memory utilization. We're also working on a variety of new features including interface enhancements and licensing simplification.

Upcoming CPLEX Schedule

INFORMS Fall Conference Atlanta Nov. 3-6 1996
AGIFORS Atlanta Nov. 6-10, 1996
Bechtel PIMS USER GROUP Chicago Nov. 7, 1996

CPLEX Value Added Resellers

CPLEX Value Added Resellers (VARs) are Software vendors who license the right to distribute applications embedding CPLEX optimization algorithms to third parties (outside their own organization). The design of the CPLEX Callable Library makes it a natural fit for application developers. Today, an impressive list of prominent industry-specific application providers leverage CPLEX optimizers to deliver high-performance solutions to their customers.

With years of experience assisting VARs, we understand the development issues, licensing terms, and CPLEX services that VARs find invaluable. We've packaged a comprehensive set of terms, services, and procedures designed to lead VARs from initial inquiry to development to distribution and maintenance, augmented with powerful CPLEX marketing support. If you are interested in learning more about the CPLEX VAR program, contact our Channel Marketing Department: channels@cplex.com.

CPLEX in Cyberspace

World Wide Web Home Page: http://www.cplex.com
Internet email addresses:
general information info@cplex.com
sales information sales@cplex.com
channel marketing channels@cplex.com

New Barrier Ordering Options from Silicon Graphics

By Jim Armstrong and Ed Rothberg, Silicon Graphics, Inc.

One of the first steps in solving a linear programming problem using CPLEX's barrier algorithm is to heuristically reorder the rows of the constraint matrix. The ordering of the rows determines the cost of solving the sparse linear system of equations generated at each iteration of the barrier method. CPLEX Barrier 3.0 contained two reordering heuristics: multiple minimum degree (MMD) and minimum local fill-in.

CPLEX 4.0 contains two new ordering methods, both from Silicon Graphics. The first is an approximate minimum degree (AMD) heuristic. The orderings computed by AMD are of comparable quality to those of MMD, but AMD requires less runtime to compute the orderings. This method was developed at CERFACS and the University of Florida. Scientists at Silicon Graphics built an implementation of the method that works within CPLEX Barrier. They found that the reductions in runtime for linear programming matrices were quite dramatic; significantly larger than those in other problem domains (e.g., structural analysis). Ordering runtimes are typically not major bottlenecks in the barrier algorithm. On Silicon Graphics multiprocessors, however, the rest of the barrier algorithm has been parallelized, and can execute at sustained rates of several gigaflops. In this environment, ordering runtimes can become a significant part of the overall runtime. The Silicon Graphics provided AMD implementation is the foundation for the default ordering method in CPLEX Barrier 4.0 on all computer platforms.

The second new ordering method in CPLEX Barrier 4.0, EXTREME ordering, has been available for the Silicon Graphics version of CPLEX since February of 1996. EXTREME ordering is the result of a collaboration between scientists at Silicon Graphics and Sandia National Laboratories, and it takes a very different approach to the ordering from AMD or MMD. It uses a multi-level, vertex-separator, nested dissection method. This approach can produce dramatic improvements in ordering quality. In some cases, the cost of solving the linear systems can be reduced by a factor of 20 or more. The nested dissection approach, however, is not appropriate for all problems. Rather than requiring the user to determine whether this nested dissection approach works well for their particular problem, EXTREME ordering performs both a nested dissection ordering and an AMF ordering (a modified version of AMD). EXTREME then chooses the better of the two.

The following table provides data on the ordering times and the costs of subsequently solving the linear systems after the corresponding ordering is applied. Ordering times are normalized to the cost of MMD ordering (i.e., a value of 0.1 indicates the method requires one-tenth of the runtime of MMD on that problem). The cost of solving the system is expressed here in terms of the number of floating-point operations required for a single system solve. A Silicon Graphics POWER CHALLENGE^TM multiprocessor with MIPS R10000^TM processors was used to collect this data. Data for three different CPLEX ordering options is provided below.

The EXTREME ordering option is only available on Silicon Graphics multiprocessing systems. To select this ordering in the interactive CPLEX Base System, enter the command 'SET BARRIER ORDERING 5'. To select EXTREME ordering in the Callable Library, add the call 'CPXsetintparam ( env, CPX_PARAM_BARORDER, 5)' to your Callable Library application.

Silicon Graphics invested approximately five man-years of development to help bring parallel CPLEX Barrier and EXTREME ordering to their current state. More information on Silicon Graphics operations research technology may be obtained from the SGI OR web page at
http://www.sgi.com/Products/hardware/power/operations/orinfo.html.

Q&A

Q : I am debugging a Callable Library Application and using the CPXlpwrite() routine to write out an LP file of my problem. However, when I read the LP file into the CPLEX interactive optimizer and optimize, although the objective value is the same, I get different solution values for my variables. Why is this?

A : CPLEX's LP format is a row-oriented format. The data structures used to load a problem in the Callable Library are column oriented. As a result, the order of the variables when the interactive CPLEX optimizer reads in an LP file written created by the CPXlpwrite() routine will typically differ from the order in the application that created the LP file. This in turn can change the path taken to an optimal solution, resulting in an alternate optimal solution with different solution values. Even if the order of the variables turns out to be the same, you still may see this behavior because the text representation of matrix coefficients may differ slightly from the precise binary representation in the program.

In order to reproduce the problem as precisely as possible, we recommend using the CPXsavwrite() routine to generate a binary SAV file whenever you want to reproduce the behavior of your program with the CPLEX interactive optimizer. Also, be sure that all parameter settings are the same.

Q : I am solving a quadratic program with a positive semi-definite Hessian matrix. However, CPLEX returns the following error message:

CPLEX Error 5002: Q is not positive semi-definite.

By the nature of my problem formulation, I know Q is positive semi-definite. Why does CPLEX reject the matrix?

A : A computer's finite precision during the factorization of the Hessian matrix can result in this type of error message. A common example is when Q can be expressed in the form A'A. For any x, x'Qx >=0, so Q is positive semi-definite. But, if A does not have full row rank, there exists a nonzero vector x such that x'Qx = 0. The finite precision of the computer may then result in x'Qx < 0 by some slight amount, leading to the above error message. There are two ways to deal with this:

1. Perturb the diagonal elements of Q. This will make Q positive definite, and typically it won't have any significant effect on the solution of the problem being solved.
2. If it is known Q is positive semi-definite, Q can be expressed in the form A'A for some matrix A. Add the constraints

y - Ax = 0
y free

to the problem, and use the quadratic form y'y as the objective. The Hessian is now the identity matrix, which is positive definite.

Personnel News

We've added two new employees to the CPLEX team:

John Gregory (email jwg@cplex.com) has joined CPLEX as Technical Projects Manger. For the past nine years, John served as the OR Specialist for Cray Computer. John received his undergraduate degree from Butler University and also has a Masters Degree in OR from Brown University. Prior to working for Cray, John worked at Control Data (associated with the APEX LP application).

Larry Hunt (email larry@cplex.com) is our new Channel Marketing Manager. Larry will develop and implement programs to better serve our Value Added Resellers and Dealers. Larry has held technical and marketing positions in a variety of software companies, including General Manager for SLR Systems, Inc.(provider of linkers, recently acquired by Symantec) and prior to that, as Executive Vice President of Lahey Computer Systems (provider of Fortran language systems). Larry received his degree in computer science and mathematics from Eastern Michigan University. Larry has specialized in the business aspects of marketing development tool software, and has recently provided related consulting services to several well-known software companies.

Roadway Express Tractor & Crew Scheduling

Roadway Express, one of the nation's largest LTL (less than truckload) trucking companies, has implemented a state-of-the-art scheduling application using the CPLEX Mixed Integer Solver. This application schedules sleeper tractors and crews for Roadway's operations west of the Mississippi. According to the developer of this model, Shekhar Khot, Operations Research Scientist, this is the first known instance of optimization applied to crew scheduling in the trucking industry.

The LTL longhaul business is extremely competitive. In 1994, Roadway invested in 262 new sleeper tractors which utilize 2-person crews. These modern tractors, fully equipped with sophisticated satellite communications systems, offered the potential for higher overall speed and better reliability. To optimally deploy these valuable tractor assets, as well as sleeper crews (paid a premium over single-driver tractors), Roadway wisely invested in an operations research model to schedule the tractors and accompanying crews.

The Roadway scheduling model has two distinct phases: a tractor scheduling phase, and a crew scheduling phase. Both phases are set-covering models solved using CPLEX's Mixed Integer Solver.

The first phase, tractor scheduling, generates a least-cost tractor schedule subject to freight availability projections (how many trailers to/from various destinations over the required time period) as well as service timing considerations (when loads must be picked up and delivered to meet advertised service levels, such as 2-day or 3-day service). The model also takes into account some rules and costs associated with driving crews. The resulting weekly tractor schedules are used for a 6-month time period.

Crew scheduling, the second phase, starts with the tractor schedules generated in phase 1, and then examines all feasible tractor/crew combinations over that schedule. The model then maximizes driver miles (maximizing pay opportunities for drivers, who are paid per mile). This model must consider numerous and complex driver rules and restrictions set by national and local labor contracts as well as rules imposed by the Dept. of Transportation. These rules dictate how many continuous hours drivers may work, how long they must be given rest, how long they may be away from their home domicile, etc.

The sleeper tractors scheduling system (phase 1) was completed and fully implemented in October 1994. However, only 50% of Roadway Express' crews have adopted crew scheduling (phase 2), even though the technical effort is complete. Extensive labor negotiations and agreements are required to implement crew scheduling, which requires drivers to give up some of their current scheduling flexibility in exchange for higher average pay (more miles) and the elimination of schedule uncertainty. Those crews that have converted to the new system report a high level of satisfaction with the new system. Under the new crew scheduling program, drivers average about 18% more miles than without crew scheduling.

Overall, Roadway Express reports that the sleeper tractor and crew scheduling models have improved Roadway's on-time performance and reduced overall scheduling uncertainty. Scheduled crews have increased their mileage and pay opportunities and also their quality of life. Bert Dopp, Director of Linehaul Operations, says "The challenge Roadway faced with the introduction of sleeper crews was formidable. I am convinced that without the formalization of tractor and crew schedules, the effort would have failed to achieve our business goals." Labor discussions with the remaining unscheduled crews is continuing.