Development Update

The CPLEX development team has been exceptionally busy. Here is a preview of developments which will appear in the next CPLEX release (scheduled for the second quarter of 1994):

The primal and dual simplex CPLEX algorithms have seen significant enhancements, specifically in the pricing and LU-update routines. These improvements are particularly effective for larger problems (over 5000 rows), where speed improvements of 10 to 30% are common.

Enhancement of the CPLEX mixed integer algorithms is continuing as a high priority. The existing branching and subproblem solution algorithms continue to be improved, with better node and variable selection and faster solution times. These improvements will result in performance improvements for most problems. In addition, some entirely new algorithmic improvements will be introduced, including:

MIP Presolve–New presolve features specifically adapted for MIP problems include coefficient reduction and bound improvement.

Strong Branching–A new branching strategy has proven quite effective on some large, difficult MIP models. Strong branching selects a variable for branching after evaluating the actual objective degradations that occur when forcing variables to integer values.

Branch and Cut–A new "branch and cut" algorithm can dramatically reduce the number of nodes evaluated on pure integer problems.

The CPLEX network optimizer has been significantly improved for the next release. CPLEX will be able to better locate "embedded" networks–even network structures that are quite obscured. Since network problems typically solve quite rapidly, users may find that their existing problems benefit significantly from the new network extractor.

All CPLEX products will be updated to include an infeasibility diagnostic tool. When a problem is determined to be infeasible, it is often quite difficult to identify the source of the infeasibility. The CPLEX Infeasibility Finder serves as a useful diagnostic tool for simplifying this task.

All CPLEX Library users will appreciate a new "lint" program designed to identify problems in their programs. To assist in application de-bugging, the "lint" will identify common mistakes in user-written programs calling CPLEX, particularly in problem set up.

The CPLEX MPS reader will be revised to be even faster and to allow for 16-character names and up to 25-character numeric fields. If you regularly use MPS format files, please see the additional article inside this newsletter.

Rethinking Mixed Integer Model Formulations: Fixed Charges

A careful formulation for a mixed integer program (MIP) can lead to solution of the model in a reasonable amount of time, while a not-so-careful formulation can make the model practically unsolvable. What is a careful formulation? The over-riding principle is to make the feasible region described by the linear programming relaxation as close as possible to the feasible region that contains only feasible integer solutions. A more tightly constrained model is better than a less tightly constrained model, even if the LP subproblems are more difficult. This article, which focuses on models involving fixed charges, is the first in a series devoted to formulating MIP problems thoughtfully.

To model a fixed charge, that is, a cost that is incurred once when a process is used, but is not proportional to the level of the process, a "Big M" formulation is usually used. The level of the process is a continuous variable y and the "on-off" binary variable is x. The objective function coefficient for y is the cost for each additional unit of y and the coefficient for x is the fixed charge. The constraint that describes the relationship between x and y is

y <= Mx.

For y to be positive, x must be 1. The value of the constant M has to be chosen large enough so that when x is 1, the constraint does not limit y below its true upper bound.

(Note that in CPLEX lp format, you would need to have all the variables to the left of the inequality sign, so you'd enter: y - Mx <= 0.)

Your first thought might be to choose a very large M that wouldn't limit any of the y variables in the problem and use it everywhere an M is needed. This approach has several drawbacks.

First, the value of x in the solution to the LP relaxation will be y/M. (Using a minimal amount of x is preferred since the fixed charge will be large relative to the unit cost.) The objective function value then reflects only y/M of the fixed charge. For example, if y is 10 and M is 10000, only 0.001 of the fixed charge is used, which means the relaxation objective value is far from the integer objective value.

Second, the branching algorithm would also likely try to force x to 0 first, and thus y to 0, because the value of x is already so close to 0. That is not what the LP solution is saying; the LP solution is saying that y should be positive.

Now if M is set to the true upper bound of y which is 15, then the solution to the LP relaxation will be x = 0.6666, so both the objective function value of the relaxation and the the x value reflect more closely what will happen when the integer restriction is enforced through branching. The branching algorithm will have a better idea of how to set x, and the bounding process will have better objective value information.

Using priority orders and preferred branching directions can also speed solution of a fixed charge model. CPLEX allows setting a preferred branching direction for each variable as well as a default preferred direction. Set the branching direction to "up" for any of the fixed charge (x) variables. The x variables should also be assigned a higher ordering value than other integer variables which use the x's.

Announcing CPLEX Barrier

The CPLEX Barrier Solver is now available as an option for users of both interactive and library-format CPLEX software. This new CPLEX solver is a primal-dual logarithmic barrier algorithm with predictor-corrector. For large problems, particularly large sparse problems, CPLEX Barrier can be particularly powerful.

Unique to CPLEX Barrier is the production of basic solutions. In the past, the use of barrier algorithms and interior-point algorithms has been limited by their inability to efficiently produce basic solutions. Breakthrough CPLEX technology solves this problem, automatically converting mid-face solutions to basic solutions. So fast re-starts from a basis are possible after using Barrier; it can even be used to solve MIP subproblems.

Existing CPLEX licensees should receive information about upgrading to the new CPLEX Barrier option. If you have not received this information and want to know more about CPLEX Barrier, please contact us.

MPS File Format Revisions in Next Release

A new CPLEX MPS file reader which is faster and allows for 16-character names and up to 25-character numeric fields has been developed for the next CPLEX release (2Q94). As a result, a few MPS file conventions now accepted by CPLEX will generate errors in the future. The new release will include a "translator" to convert older MPS files so they will be readable; however, you should review your MPS files and model generators now in anticipation of these changes. The new MPS reader will not accept files including any of the following:

blank spaces within names

blank lines

missing fields (such as bound names and RHS names)

any extraneous, uncommented characters

blank repeated name fields like RHS and bound vector names

If you have any comments or questions regarding these planned changes, please contact us.

New CPLEX email Access

CPLEX is now on the internet. Email inquiries to CPLEX can be addressed to:

technical support: support@cplex.com

general information: info@cplex.com

sales information: sales@cplex.com

Q&A

Q: When calling getstat after calling mipoptimize, I get a return value of 110, indicating an unrecoverable failure with no integer solution. How can I identify the specific cause of the failure?

A: It is important to check and distinguish between the value returned from mipoptimize and the value returned from getstat. If mipoptimize fails while solving one of the subproblems, it returns a nonzero value between 2 and 10 indicating the status of the failed LP subproblem. A subsequent call to getstat returns either 109 or 110 corresponding to the solution status for the MIP problem. See page 227 in the User Documentation for a complete explanation of these return codes. In summary, when solving a MIP problem, the return values of both the mipoptimize and the getstat functions are meaningful and relevant.

Q: I encounter a segmentation fault as soon as I call loadprob. I suspect the problem lies in one of the arrays passed into loadprob, but have been unable to pinpoint the problem. Any suggestions?

A: The next release of CPLEX Library products will include source code for CPLEX "Lint", a set of diagnostic routines for CPLEX Library users. These diagnostic routines will perform extensive checking of the problem data for inconsistencies and errors that could be difficult to find using a debugger alone. (This source code is already available; please contact us if you wish to obtain a pre-release copy.)

Application Feature: NHL Scheduling using CPLEX

Who says operations research is all work and no play? The National Hockey League (NHL) derives game schedules using a model solved with the CPLEX Mixed Integer Optimizer. The model was developed by Charles Fleurent and Jacques Ferland at the University of Montreal under a grant from the NHL and NSERC.

The first step is to develop a game allocation setting the number of games teams play against other teams both inside and outside their conference and division. In NHL allocations, each team must play every other team at least once. In addition, the allocation must consider a fair balance of home and away games, and should result in a higher proportion of inter-division and inter-conference games.

Developing an allocation to meet all the NHL criteria is surprisingly complex. For many years, the number of NHL teams remained constant at 21, and each team played exactly 80 games per season. One allocation was developed and re-used every year. However, in the 1991-1992 season, the league added a new team, the San Jose Sharks. Two more teams were added in the 1992-1993 season. The NHL estimates it may have as many as 28 teams by the year 2000. A new allocation must be developed each time the number of teams or games changes.

To illustrate the difficulty of determining allocations, imagine a league with 24 teams (4 divisions with 6 teams each) where every team is to play 80 games. A unique positive integer solution is possible, in which each team plays 4 games against each team inside its division , 4 games against each time inside its conference but outside its division, and 3 games with each team outside the conference . But this solution results in too few inter-divisional and inter-conference games. An alternative solution must be identified such that: (a) each team plays exactly 80 games; (b) more inter-division and inter-conference games are scheduled, and (c) each team's number of home games against the teams from a division differs from its number of away-games by at most one.

Dr. Fleurent and Dr. Ferland developed a generalized integer programming model used by the NHL which incorporates these constraints. The original model resulted in highly fractional solutions to the relaxed problem, and therefore a difficult branch-and-bound process. So the model was re-formulated to solve more readily by replacing some constraints with equivalent alternatives. The new set of constraints resulted in a much more tractable polytope and the branch-and-bound search proved to be very efficient.

The NHL requests that the model be used to generate several allocations for different total number of games to be played (i.e., 80, 82, or 84), different numbers of teams (23, 24, etc) and different numbers of inter-division and inter-conference games. The league managers then review these allocations and select those which look most interesting to them.