Development Update

New LP Algorithms–Newly developed alternative algorithms for solving LPs (particularly large and difficult LPs) are currently being tested. Expect some exciting announcements regarding new algorithms later in 1993.

MIP Enhancements–We continue to place a priority on developing additional mixed-integer algorithms. Most users will benefit from our work toward integrating new LP presolve capability with the MIP solver, and the addition of new node pre-processing strategies. Considerable development effort is also focussed on developing new options and algorithms that will benefit specific (but commonly encountered) classes of problems.

Network Enhancements–Work continues to improve the existing CPLEX network extraction capability (ability to identify and "extract" embedded network structures).

Other Development–A project is underway to add the ability to find and report infeasibilities in user models. Model infeasibilities are often quite difficult to detect; this new feature should save users considerable time in identifying the cause of reported infeasibilities.

We are also investing in the development of closer links with modelling languages.

"Hot Starts": Starting MIP Optimization from Known Solutions

Many CPLEX Mixed Integer software users have a known solution (or at least a good guess for a known solution) to their mixed integer programs. They may have this information from a solution to a similar problem or from specific knowledge of their model. Users frequently ask us if the known solution information can be communicated to CPLEX to provide an initial starting point, or "hot start". The answer is yes, using priority order and branching direction features.

You can use the CPLEX Mixed Integer priority order feature to directly branch to the known solution by setting priorities and preferred branching directions for individual variables. However, note that using a "hot start" approach is not always recommended. Often, the time required to obtain the true optimum using a trial solution is longer than the time if the known solution was not used, even if the first integer solution is reached more quickly. This happens because the tree generated by the trial solution doesn't look at problem information like the normal CPLEX branching process does.

If you want to try a "hot start", first make a priority list of all the variables that you'd like to set (those integer variables that have known solution values). Give them all the same priority value, something other than zero (if the variables fall into groups, where some groups should be looked at first, by all means give those a higher value). For binary variables, specify the preferred branching direction corresponding to the known solution: 1 for up or 0 for down. For general integers, you need to restrict the range to just two values by changing bounds and then specify the branching direction. For example, if the known solution value is 12, you might set the lower bound at 11 and the upper bound at 12, and specify "up" as the branching direction. Usually you will want to set the MIP solution limit to 1, so that optimization will stop after the first integer solution corresponding to the known values is reached (using the interactive command 'SET LIMITS MIPSOLUTIONS 1' or library routine setmslim).

Once the known solution is reached, there are several options. The best choice depends on problem characteristics; experiment with a few problems before deciding. You can either continue from the current branch-and-bound tree, or totally restart (using the "hot start" solution objection function value as a cutoff). In either case, you can use the priority orders already established, use new priority orders, or turn off the priority order feature altogether.

To continue from the current branch-and-bound tree, simply restart the optimization. To start a new branch-and-bound tree, re-read or re-load the problem and use the objective value for the known solution as the cutoff value (using the interactive command 'SET MIPSTRATEGY UPPER/LOWER CUTOFF' or library routines setcutup or setcutlo). Then start the optimization.

If you have restricted the bounds on general integers for the purpose of generating the known solution, you will need to re-set them and begin over with a new branch-and-bound tree, since this change requires re-initializing the branching process.

SOS Documentation Correction

CPLEX 2.1 documentation contains an error regarding Special Ordered Sets Type 2. SOS Type 2 sets can contain non-integer variables. The 2.1 documentation incorrectly states that only integer variables can be included in SOS Type 2 sets. (SOS Type 2 sets, in fact, typically DO include non-integer variables.)

CPLEX New Staff

New staff: CPLEX is pleased to announce the addition of a new employee: Dr. Irv Lustig. Irv received his PhD in Operations Research from Stanford University, and has since gained extensive experience in developing advanced optimization algorithms for both commercial and research applications. Irv's focus will be product development as well as contributing to direct customer support.

New CPLEX PC Versions

Two new versions of CPLEX software for 386/486 PCs are now available:

• OS/2 PC Versions: PC 386/486 versions of all CPLEX software products are now available under the OS/2 Release 2 operating system. Library OS/2 versions use Watcom C for linking and compiling.

• Extended-DOS Watcom C Version: CPLEX Library products (Callable Library and Mixed Integer Library) are now available for use with Watcom C. We will also continue to support a version for use with MetaWare High C.

Satisfaction Survey

If you are one of a random group of commercial users recently mailed a CPLEX satisfaction survey, we encourage you to complete the survey and return it. Feedback through these annual surveys help us to understand how we can improve our service and also help us set priorities among competing development projects.

Even if you did not receive a survey, we always welcome user input. Suggestions are accepted by phone, fax, or email (tlowe@mcimail.com).

Q&A

Q: I have noticed a difference between solving the exact same problem using the CPLEX Callable Library and the CPLEX Linear Optimizer. I thought they used the exact same algorithms and default parameter settings; so what is causing the performance difference?

A: The library and interactive versions DO use the exact same algorithms, but there are a couple important difference in default parameter settings. At default settings for the interactive products, the two problem reduction features (Presolve and Aggregator) are "on" and will automatically be invoked. For the library products, the Presolve and Aggregator are not invoked unless the user specifically resets the Presolve and Aggregator indicators (via the setpreind and setaggind routines). Another important difference between the interactive and library defaults involves the screen indicator setting. There is no screen output from library applications unless the screen indicator is explicitly turned on (using the setscr_ind routine).

Q: CPLEX Presolve reduces the size of my LP, making it five times smaller. Am I doing something wrong in my model formulation?

A: Not necessarily. Many LPs, particularly those generated by modelling languages, have unnecessary rows and columns. You may wish to examine the difference between a presolved model and your original model to determine what kind of LP formulation improvements are possible. This is easily accomplished by following these steps:

1. Read in your LP or MPS format problem file and immediately write out the presolved version (using 'WRITE file.pre' in the interactive versions and the preslvwrite routine in the library versions). Note that this file is in binary SAV format, which is not readable as text, so use the next two steps to create a readable text file.

2. Read the presolved LP file back into CPLEX using the 'READ' command (remember that presolved problem file is in SAV format).

3. Now write out the reduced LP in either LP or MPS format, and directly compare this file to your original problem file.

Application Feature: Garment Cutting Plans

Harvard University researchers have developed a unique algorithm for the apparel industry which includes the use of linear programming. CPLEX is used to solve the LP. Since commercial-scale problems are large and near real-time performance is an objective, fast and reliable LP solutions are critical.

To an apparel company, efficient cutting plans for garment material are crucial elements of competitiveness. In one specific case, an average improvement of 0.3% in cutting plan efficiency saved a large company millions of dollars annually.

Fabric cutting plans are called "markers". Markers define how a given number of pieces will be cut from cloth of a specified width and variable length (corresponding to a bolt of cloth). One marker may be used to cut many layers of cloth. Skilled humans can generate highly efficient markers; however, the process is time-consuming and efficiency varies widely between markers developed by experienced and inexperienced workers.

A group of researchers including Dr. Frederick Abernathy and Dr. Victor Milenkovic at Harvard is developing automated systems for creating markers which approximate the efficiency of skilled humans. This project is a part of a larger project to improve the competitiveness of the US apparel industry. This research is being performed under a contract with the Textile/Clothing Technology Corporation with funds awarded by the Alfred P. Sloan Foundation. The research team has identified three separate sub-tasks for developing markers: (1) panel placement , (2) trim placement, and (3) compaction. In the first task, the larger pieces, or panels, are placed. Next, the smaller trim pieces are placed in available gaps. The third task, compaction, attempts to move the pieces already in place in order to increase efficiency, open up gaps for new pieces, or eliminate any existing overlap.

The researchers have developed algorithms for improving the compaction task using linear programming. The LP formulation can be generalized as follows: First, adjacent pieces are identified and a convex subset of the complement of their Minkowski difference is selected according to a "locality heuristic". Then, for each adjacent pair, a set of linear inequalities constrains the difference of their positions to lie in the selected convex set. For each body, a position motion variable is defined and a desired direction is assigned. The objective is then to maximize the sum, for all pieces, of the position motions in the desired directions subject to the position constraints over all pairs. The resulting LP solution provides positions representing the maximal motion in the desired directions. The process is then iterated, since positions have changed after motion, and convex regions may have also changed.

Not only can the compaction algorithm improve cutting plans generated by automated systems, it can also improve human-generated markers. So compacting algorithms developed by Dr. Milenkovic and his research group can be used within automated systems as well as in conjunction with manual systems.

The algorithms developed by the Harvard research team are currently being implemented in commercial garment automation systems.