Solving Mixed Integer Problems: A Recipe for Success

Unlike solving LPs with all-continuous variables, solving mixed integer problems usually involves some experimentation with algorithm and parameter options, and potentially problem formulation. While research activity in integer programming algorithms is promising, current state-of-the-art solvers still require the application of judgement and experimentation.

The CPLEX 2.0 documentation includes a thorough discussion of options for improving performance when solving integer programming problems. We recommend all users solving mixed integer programming problems study this section carefully.

Be mindful of the nature of integer programming solution strategies, and the process by which your problem will be solved. Consider a small problem with 20 binary integer variables. The search tree for this problem could theoretically be over 1 million nodes in size! You must formulate your problem or select an algorithm which reduces the number of nodes to be explored.

Here are a few practical suggestions:

1. Before you start, always set some termination criteria--number of nodes, iterations, or time. You can usually tell if a strategy change is beneficial without running the entire problem. If you don't set a stopping criteria, you can waste time watching an ineffective strategy flounder.

2. Apply shortcuts. Often, a solution within a 1% or so of the theoretically possible will be found very quickly...but then the search for better solutions will continue for some time (often without finding any!). If an answer within 1% would have been acceptable--or within the precision level of the data and problem formulation--this exhaustive search was wasted effort. Set a MIPGAP relative tolerance and UPPERCUTOFF (for minimization problems) or LOWERCUTOFF (for maximization problems).

3. Use priority orders if you can. Priority orders direct CPLEX to branch on variables with high priorities first. By assigning branching priorities to as many variables as possible, the size of the tree to be explored can be dramatically reduced. Priority orders can be assigned based on your specific knowledge of the problem; for example, the yes/no decision to add a night-shift to an operating schedule should be given higher priority than determining which machines should be on/off during that night schedule.

4. Try both a "breadth-first" (best bound) and a "depth-first" search (using the NODESELECT parameter), or perhaps both in succession. While best bound is often most effective at "pruning" the tree and proving optimality sooner, it also requires more memory. And if integer-feasible solutions are "deep" in the tree, as is quite common, it might take a while to find them using a best-bound approach. Depth-first search typically takes longer to solve to optimality, but conserves memory and often finds a good integer-feasible solution faster.

5. Experiment with branching direction and variable arbitration. Normally, CPLEX determines the branching direction (up versus down) automatically. But occasionally, manually setting the BRANCH parameter to branch up or down can have a significant impact on problem solution time. Similarly, adjusting the variable arbitration strategy can occasionally provide benefits.

6. Finally, but perhaps MOST IMPORTANTLY, review your problem formulation. This is often the simplest, yet most powerful way to improve solution efficiency. Even small changes to a formulation can greatly simplify solution. If you can more tightly constrain your model, you can eliminate whole "trunks" of the search tree. Unlike continuous LP problems, mixed integer problems usually get EASIER as constraints are added and bounds tightened, since the number of potential solutions to be enumerated decreases. Also, if you can add structure to your problem that allows you to apply branching priorities, DO SO--even if this means adding new variables. Often minor changes model reformulations reduce virtually unsolvable problems to simple problems that solve in seconds.

New Run-Time Program

Users have been asking us for a simplified, affordable "run-time" program for distributing applications they developed using the CPLEX Callable Library and Mixed Integer Library. The long-established CPLEX Value Added Reseller program still works well for most developers reselling CPLEX-based applications to third parties; but our new Run Time program addresses the needs of many users distributing a smaller number of CPLEX-based applications, either internally or to third parties. Run Time licenses are now available for a flat discount off our standard licensing fees. And Run Time licensing is simple. Call us for details on the new CPLEX Run Time program, and how it might benefit your application development plans.

CPLEX Library Applications: "Top Ten" Development Tips

Development of a CPLEX Library application involves interfacing the developer's application with the CPLEX Library Systems. Most users find that the CPLEX Library Systems are quite easy to integrate within their applications; the CPLEX Library Systems contain numerous warning and error messages to help identify integration problems. However, an improper interface between the developer's code and the Library Systems may cause an obscure "bug" which can be time-consuming to identify. Errors involving memory management can be particularly difficult to spot. The following list of debugging suggestions has been compiled from our experience working with developers over the past several years.

1. Make sure you are using the correct machine flag in the compile statement. You must always define the type of computer you are using when compiling a CPLEX Library application. Consult the installation notes provided with your CPLEX software for the specific flag for your particular computer.

2. Use the setscr_ind and setlogfile functions so that all CPLEX messages are visible. In V2.0 no output is produced unless you specifically ask for it.

3. Make sure you are not directly altering problem data that has been loaded but not freed. You must always use Library routines to change a loaded problem rather than alter loaded problem data directly.

4. Always check return codes from the Library functions. If the return code indicates failure, be sure to check if sufficient memory is available.

5. Write out an MPS or LP file and run it using the interactive CPLEX executable provided with every Library license. When you run the problem does the problem persist? Examine the problem file. Is it the problem you thought you defined? Examining the MPS or LP problem file will usually reveal the problem.

6. Check for changes in your application that increase problem size. If any exist, make sure that any memory allocations are big enough to accommodate the increase in problem dimensions.

7. When calling mpsread or lpread, make sure macsz, marsz, matsz, and other parameters that control memory allocation are initialized. Failure to do so can result in inconsistent behavior, since the uninitialized variables may take different values during different runs.

8. When calling mpsread, do not set pointers to arrays to be NULL even if the arrays themselves will not be allocated; mpsread will still set the arrays to NULL, so the double pointers must be available. This applies in particular to the pointers to arrays that are not allocated when pmae is NULL.

9. Do not access and use any of the data passed to CPLEX until after the problem has been unloaded or freed. CPLEX uses the space and may modify or move data. Use a query routine instead. This is similar to tip &##35; 3 but is worth repeating.

10. (Fortran only) Use the IMPLICIT NONE declaration at the start of the program. This will help detect any unintended type conversions that often lead to unpredicted behavior.

Q & A

Q: In my CPLEX 2.0 Callable Library application, I construct some ranged rows. After reading about the rngval and senx arrays in the loadprob function documentation, I wrote the code to construct the ranged rows. However, when I try to run the application, I get a message during the call to loadprob indicating insufficient space for the "range columns" is available. Why is this happening?

A: CPLEX handles ranged rows by adding one range variable for each ranged row. Each range variable requires an extra column in the constraint matrix which contains exactly one nonzero. The macsz and matsz parameters, as well as their associated arrays, must be large enough to account for these columns and their associated nonzeros when passed to the loadprob function. Otherwise, CPLEX will determine that insufficient memory exists to store these range columns.

Q: I plan to develop a CPLEX Callable Library Application using Microsoft Windows. How can I control the CPLEX stream of output so that it functions properly in my application?

A: Windows, and many other software development toolkits, will not display output generated by calls to the C printf function or by writing to the standard output. Fortunately, the CPLEX Message Channel capability, a new feature in Version 2.0, provides developers with complete control over the various types of CPLEX messages. Messages can go to any number of files, the screen, or a memory location in the application. For example, an application can suppress all CPLEX warning messages, write error messages to multiple files, and write results messages to a character string that can then be displayed in a window on the screen. Or you can use the addfuncdest function to send messages to a memory location.

Q: Will CPLEX be available on the new DEC Alpha systems?

A: Definitely. We have already begun the Alpha port and look forward to making CPLEX available on this exciting new high performance computer architecture.

Feature Application: GfAI Cash Management System

GfAI (Group for Applied Informatics Ltd.), a CPLEX Value Added Reseller in Switzerland, has developed an innovative application for business cash management which calls CPLEX for optimization. This application, GfAI CMS (Cash Management System), is a decision-support system designed to help treasurers manage liquid capital funds in short-term and medium-term time frames.

GfAI CMS considers all available information related to available liquid capital assets and alternative cash dispositions. CMS also incorporates the user's expectations related to future interest rates, exchange rates, and capital market conditions. GfAI CMS assists the treasurer in quantifying uncertainty and performing what/if analyses. From a potentially infinite number of possible alternatives, CMS quickly proposes optimal solutions. By providing better solutions in less time, CMS improves both the efficiency and effectiveness of cash management decision-makers.

Like many CPLEX Library application developers, GfAI has built a graphical user interface for the CMS application. The user interacts with the software through an easy-to-use and easy-to-learn environment; the mathematical modeling and application complexity are hidden from the user. The graphical interface also allows solutions and decision-making information to be presented in a clear and useful manner.

GfAI CMS is marketed as an application kit. This flexible system can therefore be adapted to the specific needs of each customer. An open architecture allows GfAI CMS to be readily integrated into existing systems, allowing communication with external data sources and corporate data systems.

For additional information regarding this application, you may contact Rolf Widmer at GfAI in Switzerland, phone 41/1/835 8118 or fax 41/1/833 5853.