Development Update

New Platform: PowerMac
The CPLEX Callable Library is now available for the Macintosh PowerMac. Initial performance testing information for this platform is impressive (similar to Pentium performance). PowerMac pricing is the same as that for 386/486/Pentium IBM-compatible computers. For Callable Library development, the MetroWerks C Compiler for the PowerMac is also required.

Quadratic Solver
The CPLEX Quadratic Programming Solver is now complete and ready for beta testing. Any users with CPLEX Barrier licenses and quadratic programming problems interested in participating as beta testers should contact us.

Ongoing Development
The CPLEX development staff is already working on the next major CPLEX release. Current priorities include improved memory utilization and mixed integer enhancements (user-defined branching algorithms, improved pre-processing, and new branching/node selection strategies). We are also concentrating on parallel MIP development.

Callable Library Training

In response to a high level of interest in Callable Library training, a CPLEX Callable Library training session has been scheduled for this December in San Francisco. Additional sessions are planned in 1995 on the East Coast.

San Francisco (Marriott Fisherman's Wharf)
Using the CPLEX Callable Library December 7 & 8, 1994
Using the CPLEX Callable Library for December 9, 1994
Windows to create applications with DLLs

The two-day session "Using the CPLEX Callable Library" will focus on general aspects of using CPLEX libraries to efficiently link CPLEX routines with user applications. This session will be generalized for all computer platforms. The cost to attend the two-day session will be $845 per person.

Following the two-day general session will be an optional one-day supplemental class, "Using the CPLEX Callable Library for Windows to create applications with DLLs". Anyone attending this session should also plan to attend the preceding general 2-day session. The cost for the supplemental session will be $495.

Discounted room rates have been arranged at the Marriott Fisherman's Wharf. Please contact Janet Lowe for registration and accommodation details.

We have also developed an on-site training program for groups of 5 or more which can be scheduled at the customer's location under special arrangements. This training can be customized to fit the customers' specific computing environment and application requirements. Please call Janet Lowe (or send email to janet@cplex.com) to schedule a customized training session or to obtain more details.

Rethinking Mixed Integer Model Formulations

Part 3: Avoiding Symmetry

In previous articles in this series, we focussed on making the feasible region of the LP relaxation closer to the feasible region of the MIP. In this article, we address reducing the symmetry of a MIP&##150;reducing the number of equivalent solutions&##150;which will reduce the amount of work needed in the branch and bound process.

One way to reduce symmetry is to formulate with patterns instead of assignments. We will illustrate with two different formulations for the same problem, one using assignments, the other using patterns.

There are twenty-five trucks, differentiated by cost and by capacity. The truck capacities are 100, 80, 60, 50, 40 and their respective costs are 98, 76, 60, 50, 40. Twenty loads must be assigned to the trucks, and loads cannot be divided between trucks. The loads are of sizes 60, 40, 50, 70, 20, 10, 40, 50, 70, 80, 20, 10, 20, 40, 30, 40, 30, 50, 60, 50.

For the assignment formulation, we will number the trucks from 1 to 25 and denote their capacities by uj and their costs by cj, j = 1, ..., 25. We will denote the load sizes by ai, i = 1, ..., 20. The objective is to find the minimum cost assignment of loads to the trucks.

The decision variables are xij, with xij = 1 indicating that load i will be placed on truck j and yj = 1 indicating that truck j is used. The assignment formulation is

The first set of constraints enforces the capacity of each truck. The second set of constraints and the binary nature of the xij variables enforces that each load must be assigned to exactly one truck.

The symmetry in this problem arises in two ways. First, there are multiple trucks of each type and assigning a load to a given truck is no different than assigning it to a different truck of the same type. Second, there are multiple loads of the same size, and assigning one to a given truck is no different than assigning another of the same size to a given truck.

To see how the symmetry affects the branching process, consider what happens when an lp subproblem splits a load between two trucks, say load 1 is split between trucks 1 and 2. If we branch down on the variable associated with load 1 going on truck 1 (set the variable to zero), the cheapest way to reassign the load, which is what solving the LP subproblem will give, is to re-assign the partial load to one of the other trucks of the same type. With five trucks of each type, we could then see three successive branches that give the same objective value and the same number of infeasibilities. No progress is made until the fourth branch. A formulation that avoids symmetry is to generate all the feasible loading patterns for each type of truck, and choose which loading patterns to use in which quantities.

Now let's consider a pattern formulation. A pattern vector dkl represents the lth possible loading pattern for a truck of type k. Pattern vectors will be as long as the number of different sizes of loads, 8 for this example. A pattern vector is a vector that has an integer in row n, representing how many loads of the nth size are contained in the loading pattern. The feasible loading patterns for a truck of size 40 are: (40), (30, 10), (20, 20), (20, 10, 10) and (10, 10, 10, 10). The corresponding pattern vectors dkl would be (sizes 10 to 80 in rows 1 to 8): (0 0 0 1 0 0 0 0), (1 0 1 0 0 0 0 0), (0 2 0 0 0 0 0 0), (2 1 0 0 0 0 0 0), (4 0 0 0 0 0 0 0). Assume there are Lk loading patterns for each truck type k, k = 1,...,5. Only full-capacity load patterns need be generated, i.e., those with loads summing up to capacity of truck type k.

The demand vector, b, has entries which are the number of loads of the nth size required, for this example, (2, 3, 2, 4, 4, 2, 2, 1).

There is a decision variable associated with each pattern vector, vkl, which is an integer variable and represents how many trucks with this load pattern are used. The reformulated model is as follows.

The first group of constraints uses the pattern vectors and the demand vector to enforce that the demand is at least satisfied. Since only full-capacity patterns were used, the greater than inequality is used.

The second set of constraints sets the limit on the number of trucks of each type to the number of trucks available, in this example, 5 trucks of each type. The cost gk is the cost of using a truck of type k.

The solution gives the number of trucks using each loading pattern to be used. The loads can then be assigned to trucks. If there is excess capacity in the solution for any of the load sizes, some of the trucks will not be full, but the solution will still be valid.

When branching down on a pattern variable, another pattern vector must be selected. The cost may be the same, but the infeasibilities will be different. The branching process will make progress at every step. Often, a pattern formulation also has the benefit of having LP feasible regions that are closer to the MIP feasible region, and that is the case for this example.

The original model provided by a customer using the assignment formulation had 525 binary variables and 45 constraints. It solved in 298 nodes and 63.98 seconds using CPLEX 3.0 with presolve and automatically generated clique cuts (node counts and times will vary for other hardware/software platforms). The solution took much longer without the presolve and clique cuts; they are a way to automatically reformulate this model. The pattern reformulation had 53 integer variables and 13 constraints, and solved in 11 nodes and 0.18 seconds without using any clique cuts.

A drawback of the pattern approach is that the number of patterns is combinatorial, so it grows very rapidly. The answer then is to turn to an approach called column generation, where the pattern columns are not all generated at once, but only during the solution process when it looks like a pattern can be used to obtain a better solution. A column generation algorithm is a decomposition algorithm.

Priorities can be used to alleviate the effect of the symmetry if reformulation is not possible. Giving equal priority to all the yj variables is better than no priorities at all. Splitting the yj variables into groups which overlap the truck types (say three groups) and giving each group a different priority is even better, but the best priority setting of this type was to give each variable for a truck type a different priority. Differing the priority values for trucks of a given type differentiates the trucks in the branching process so the tendency will be away from a series of similar branches.

C programs to generate the two formulations and the corresponding .lp and .mps files are available by ftp (call technical support or send email to support@cplex.com for ftp details).

(This topic was inspired by the tutorial given by Professor George L. Nemhauser of the Georgia Institute of Technology at the recent 15th International Symposium on Mathematical Programming. Further discussions of symmetry in formulations appear in the books Integer and Combinatorial Optimization, G. L. Nemhauser and L. A. Wolsey, John Wiley & Sons, New York, 1988 and Model Building in Mathematical Programming, 3rd. ed., H. P. Williams, John Wiley & Sons, Chichester, 1990.)

CPLEX News

New Arrival: Congratulations to Irv and Susan Lustig, who became the proud parents of a second daughter, Melanie Ruth. Born August 3, 1994, Melanie is happy and healthy, as are both parents.

Q&A

Q: We have more users on our computer system than we have CPLEX licenses. How can I make my Callable Library application communicate a licensing problem or other error condition back to the user?

A: For all Callable Library applications that do not call setscr_ind(1), it is STRONGLY recommended that an error message handler be set up for the cpxerror message channel. To do this, create a function called errmsgfunc that looks something like:

Then at the beginning of your program, add some code that looks like:

The above segment of code tells CPLEX that all error messages generated by CPLEX should be passed to the function errmsgfunc. Inside of errmsgfunc, you can either print a message to the screen, or do something else that is appropriate for your user.

Note that all licensing errors are prefixed with the string "Licensing error:", and you could add code inside of the errmsgfunc function to test for this string.

Q: I have a Callable Library application where I add a significant number of rows and columns to the problem. Unfortunately, I have no way to accurately estimate the increase in problem size. The values of the marsz, macsz, and matsz arguments of the loadprob() routine essentially require that I know the number of additional rows, columns and nonzeros in advance. How can I get around this problem?

A: If you have no accurate estimate of the changes in problem dimension, you can still proceed by unloading the problem when you run out of extra space, reallocating the arrays, then loading the problem again. In other words, make an initial estimate of the change in problem size in your first call to loadprob(). When no space remains to add to the problem, call unloadprob(). You can now reallocate the problem data arrays that are full, then make another call to loadprob() with new values of marsz, macsz, matsz and any other updated parameters. You can repeat this procedure as many times as necessary. Note that you must never reallocate arrays that are part of a loaded problem.

Q: Soon after licensing CPLEX 3.0 I replaced the hard disk on my Unix workstation. All directories, files and environment variables are the same as on the old hard disk, but CPLEX claims there is a licensing problem. Why is this, and what should I do about it?

A: Under Unix based operating systems, the CPLEX 3.0 License Manager requires that the specific licensing directory created during the licensing process be available. A directory with the identical name not created by the licensor will not suffice. So, when reconfiguring a computer in any way that requires copies of the licensing directory or files, you will have to relicense the machine. To do this, simply contact us before reconfiguring, request a license deletion code, then input this deletion code using the cpxlicense utility. This will remove all files and directories involved in the licensing, and return a code confirming that the deletion was complete. Upon receiving this confirming code, the CPLEX License Administrator will issue a new license code which will activate the CPLEX License for the new computer configuration. This process is also used when transferring licenses from one UNIX machine to another.

Q: When using CPLEX Barrier to optimize a problem, when is it preferable to set the ordering parameter to minimum local fill instead of the default multiple minimum degree?

A: Multiple minimum degree and minimum local fill are two different heuristics for permuting the rows of the constraint matrix in order to reduce fill in the Cholesky factorization used in the barrier method. Multiple minimum degree tends to be faster, but minimum local fill usually produces fewer nonzeros in the resulting factorization. So, the choice depends on whether the increased time using minimum local fill will be compensated for by faster barrier iterations. The relative efficiency of a computer's integer computation to double precision computation may also influence the choice. The fill-in heuristics involve integer computations, while the computations involving the Cholesky factorization are primarily double precision. For example, on personal computers, where floating point computations are relatively slow compared to integer computations it is usually desirable to use the minimum local fill heuristic.

Application Feature: AT&T's Telemarketing Site Selection

AT&T's Site Selection System is a decision support tool developed to help AT&T's customers determine "good" locations for their telemarketing centers. The core of the system is a mixed integer programming (MIP) model solved with CPLEX Callable Library mixed integer algorithm functions. The system was one of the finalists of 1989 Edelman's award competition sponsored by TIMS (The Institute of Management Science). The current MIP model was developed by Dr. Anthony J. Brigandi, Dr. Pey-Chun Chen (Alice) and Dr. Thomas Spencer III of Bell Laboratories' Business Operations Analysis Group.

The goal of AT&T's site selection process is to provide structural and objective input to the customer's telemarketing planning process. The model does so by answering the following four questions:

1. How many telemarketing centers should be opened (or closed if there are existing centers)?
2. Where should centers be located?
3. What geographic region will be served by each center?
4. How many attendant positions are required at each location?

The site selection process includes the following three steps: (1) choose candidate sites; (2) determine optimal and next-best solutions; (3) evaluate the alternative solutions using both quantitative and qualitative factors. The MIP model is used to minimize the overall cost (including labor, communication, real estate, etc.) while determining the optimal number of centers, their locations and the geographic region to be served by each center.

The site selection process has addressed a wide range of telemarketing applications (order processing, customer service, sales support and account management), and has benefited a broad scope of industries (retail catalogue, hospitality, freight and package forwarding, banking, airline/travel/railroad/ground transportation, health care, financial, federal government, etc.). The telemarketing centers implemented by single customers have ranged from one to 20 and the size of the center has varied from 30 to 500 agent positions. AT&T estimates supporting several hundred site selection studies per year. These studies are an integral part of AT&T's value-added marketing strategy and is provided through AT&T's regional consulting groups.

New developments have been on-going since the site selection system was first available in 1987. A new module to locate the most preferable centers subject to a budget constraint will be available in early 1995. This module incorporates both quantitative and qualitative factors into the decision making process. It first helps users select candidate sites taking into account users' preferences; solves the site selection model as a cost minimization problem; and then solves the preference maximization problem to get the most preferable sites. The core of the new module is a MIP model and will be solved with CPLEX Callable Library mixed integer algorithm functions.