CPLEX 4.0 Available

CPLEX 4.0 is now shipping. All commercial customers with up-to-date maintenance services should have or will be receiving their 4.0 updates shortly. Academic users will receive upgrade offer packages. As always, this new release features enhanced performance and robustness, as well as many new features. The Mixed Integer Solver features improved memory utilization and new "user callbacks" enabling user-customized branching strategies. Quadratic Programming has been added as a standard feature of the Barrier Solver. The Callable Library has been significantly updated to facilitate programming in modern programming environments. Perhaps most exciting, CPLEX 4.0 is also available in the form of record-shattering parallel algorithms (see articles below).

Parallel CPLEX 4.0

With Version 4.0, CPLEX has extended parallel programming to include Parallel MIP and Parallel Dual Simplex, in addition to Parallel Barrier (which has been further enhance with 4.0). These parallel algorithms are available today on Silicon Graphics Power Challenge machines.

CPLEX Parallel Solver performance on SGI Power Challenge systems is record-breaking; problem solution speeds have exceeded 3 gigaflops (see the article "SGI World Record" below). This is truly a "paradigm shift" in linear programming technology. Call CPLEX to arrange a benchmark or to obtain more details.

Callable Library 1996 Training Dates

CPLEX Callable Library training will be conducted at the CPLEX Incline Village, Nevada office on the following dates:

These two-day sessions cover the fundamentals of using the CPLEX Callable Library 4.0, and help users take full advantage of the power and flexibility of Callable Library routines. Some familiarity with C programming is recommended. Registration will be limited to keep classes small, so reserve space early.

The CPLEX Incline Village office is located on the north shore of Lake Tahoe. Discounted rooms have been reserved for participants at the nearby Hyatt Regency Lake Tahoe Hotel/Casino in Incline Village. Please call us for additional details and registration information.

CPLEX Personnel News

The cheerful voice that greets most CPLEX callers is that of our new office administrator, Wendy Ferris, replacing Lorrie Harlem who was promoted to Operations Manager.

Richard Guy has joined the CPLEX sales team as Executive Sales Director. Previously, Rich led the Sendout product group for EMA/EDS. Many of you have already benefited from Rich's enthusiastic and customer-oriented approach to sales and sales support.

We're also pleased to announce the birth of twin girls, Kristen Alana and Corinne Michelle, to Todd & Janet Lowe. If Todd and Janet seem a little out of breath, now you know why.

Technical Update: Feasibility Tolerances

Those developing linear programming models and using the CPLEX solvers often misunderstand how CPLEX determines if a problem is feasible. Because of the limited precision of the computer, the solution obtained by CPLEX is feasible within a specified feasibility tolerance. If the constraints of the linear program are:

	Ax = b
	x >= 0

then the solution found by CPLEX's primal simplex method satisfies

 	Ax + r = b
	x >= -e
	-e <= r <= e

where r is a vector of residuals (one per row), and e is the feasibility tolerance. Note that this test corresponds to the scaled infeasibilities, since CPLEX automatically scales the problem when it is loaded.

CPLEX's presolve routines can detect when certain constraints imply the problem is infeasible. Sometimes the presolve routine will claim that a problem is infeasible, while the simplex method can actually find a solution that satisfies the feasibility tolerance. It is up to the user to decide what is causing CPLEX to make these contradictory conclusions.

Consider the following example, which is derived from an actual customer problem:

Minimize
  obj: x1
Subject To
  c1: - x2 + x3  = 0
  c2: 0.002 x3 - x4  = 0
  c3: - x4 - x5 + x6  = 0
  c4: - 0.0001 x6 - 0.2 x7 + x8  = 0
  c5: 0.001 x5 + x9  = 0
  c6: - 0.001 x7 - 0.0001 x9 + x10  = 0
  c7: x7 <=  0
  c8: - x7 + x8 + x10  = 0
  c9: x2 - x11  = 0.9
Bounds
  0.09 <= x11 <= 0.81

The CPLEX presolve routines make the following reductions on this problem in order to conclude that the problem is infeasible.

1) Constraint c9 implies that x11 can be eliminated and x2 is given new bounds of 0.99 <= x2 <= 1.7
2) Constraint c7 implies that x7 is zero.
3) Because of (2), constraint c8 implies that x8 and x10 are zero.
4) Because of (2) and (3), constraint c6 implies that x9 is zero.
5) Because of (4), constraint c5 implies that x5 is zero.
6) Because of (2) and (3), constraint c4 implies that x6 is zero.
7) Because of (6), constraint c3 implies that x4 and x5 are zero.
8) Because of (7), constraint c2 implies that x3 is zero.
9) Because of (8), constraint c1 implies that x2 must be zero.
This contradicts the bounds derived by (1), and hence it is concluded that the problem is infeasible.

If the above problem is input to CPLEX and solved with CPLEX's presolve and aggregate options turned off ("set pre pre n" and "set pre agg n"), CPLEX will find a solution to the above problem that satisfies the feasibility tolerance. After optimizing, if you type "display quality", CPLEX reports:

Max. unscaled (scaled) bound   infeas. = 1.98e-07 (1.98e-07)
Max. unscaled (scaled) Ax-b     resid. = 2.77556e-17 (2.77556e-17)

Note that the maximum bound infeasibility is 1.98e-7, which is smaller than the default feasibility tolerance of 1.0e-6. If you then type "set sim tol feas 1.0e-7", CPLEX will then say the problem is infeasible.

The solution found by CPLEX with the default feasibility tolerance is:

Variable Name	Solution Value
x2			0.990000
x3			0.990000
x4			0.001980
x6			0.001980
x11			0.090000

CPLEX also reports the following nonzero slack variable:

Constraint Name	Slack Value
artif c4		0.000000

This gives the clue as to what is happening. The solution computed by CPLEX does not satisfy constraint c4 exactly. The left-hand side of c4 evaluates to:

(-0.0001)(.001980) = 1.98e-7

This is precisely the error shown in the "display quality" output.

The difficulty here is the mix of units in constraint c4. Constraint c4 adds the values of (0.0001)x6 and x8, which indicates that x8 must have a value 4 orders of magnitude less than x6. Since the constraint is an equality constraint, the modeler has asked for strict precision on this constraint. Furthermore, the logical reductions done by CPLEX's presolve routines use constraint c7 to set the variable x7 to 0, rather than setting up an interval for x7 of (-e, e). In fact, if you change the right-hand-side of constraint c7 to 1.0e-6, CPLEX's presolve routines will not find that the problem is infeasible.

One way to handle these problems is to construct a range variable on the sensitive constraint. If constraint c4 is written as

c4: - 0.0001 x6 - 0.2 x7 + x8 + rg = 0

and the variable rg is given bounds of

1.0e-5 <= rg <= 1.0e-5

then CPLEX will find an optimal solution to the problem, and CPLEX presolve will not consider the problem to be infeasible. The error in satisfying constraint c4 has been transferred to the variable rg, and the user can use the optimal value of rg to gain a better understanding of how accurate the overall optimal solution is.

A related issue, the precision of input data, will be discussed in the next newsletter.

SGI World Record

Running CPLEX Parallel Barrier on an SGI Power Challenge parallel server, SGI has achieved a world record in delivered performance for real-world linear programming problems. The SGI Power Challenge parallel server has been clocked at over 3.1 Gigaflops delivered performance running CPLEX Parallel Barrier on the problem GISMONDI (18262 rows, 23211 columns, 136324 nonzeros).

This record was obtained using a 16-processor Power Challenge running Parallel CPLEX Barrier. Silicon Graphics achieved this impressive record through impressive parallel computing hardware technology (SGI Power Challenge systems) coupled with equally remarkable parallel algorithmic technology.

User Application: BNSF Railway Maintenance Routing/Scheduling

Burlington Northern Santa Fe Corporation (BNSF), the largest US railroad, has recently implemented an interesting optimization application to schedule and route locomotives throughout the Western US into maintenance facilities. FRA regulations specify that locomotives must be inspected at regular intervals. Ideally, managers want to route locomotives to maintenance sites in a way that fully "utilizes power" (locomotives pulling trains en route to maintenance facilities) and also.within a narrow time window (too early means more inspection expense and idle time than necessary; too late may mean towing expenses and more idle time). Currently, BNSF routes/schedules 1600 locomotives (representing the Santa Fe lines); soon, an additional 3000 locomotives (the Burlington lines) will be added to the application system.

According to Mike Gorman, director of the BNSF operations research group, prior to this application, BNSF managers scheduled maintenance manually-using their experience and rules-of-thumb. Now, this difficult problem has been automated, improving managers' decision-making and expanding their planning horizon.

The routing/scheduling problem is formulated as a conservation of flow problem over a pure time-space network. For each locomotive due for inspection within the next 7 days, the system tracks the current location of each locomotive (place/time), the final destination of each locomotive (place time), and all trains available to be powered from each location on the system. The application considers the capacity of each maintenance shop, and minimizes all associated costs, such as locomotive-train "mismatches", idle time, shop congestion, earlier-than-necessary maintenance, and late inspection costs.

The application is run every four hours on a dedicated OS/2 machine which interfaces to a DB2 database. The end users, Managers of Locomotive Utilization responsible for deploying locomotives on the railroad system, access the results of the optimization through an internally-developed GUI interface and reports. The managers view the routes suggested as optimal, and decide whether to implement these or override the recommended routes. The application also proactively looks for and eliminates infeasible solutions due to changing conditions. Only recently implemented, the system continues to be improved, and users are still on a learning curve. However, increased power utilization and associated savings have already been demonstrated, so BNSF is currently planning to extend the system to their remaining 3000 locomotives. BNSF also plans to revise the CPLEX Callable Library application to utilize DLLs. Further application refinement will include an expert-system front-end to serve as a "pre-processor" by introducing some heuristics and rules to more realistically depict the complexity of this problem.