CPLEX for MPL gives MPL users access to the world best known linear programming and mixed integer programming solver from within the user-friendly Windows environment of MPL. The CPLEX Callable Library, including the Mixed Integer Solver, is actually accessed from MPL for Windows as a Dynamic Link Library (DLL). This tight integration allows MPL users to transparently access CPLEX solution algorithms from their MPL application. Optimizing problems and setting CPLEX options is all done through convenient, intuitive pull-down menus and dialog boxes within MPL for Windows. CPLEX is the first choice for solving large difficult models in mission- critical applications where robustness and reliability are important. Few solvers can come close to match CPLEX's speed and reliability. CPLEX is currently used to solve many of the largest problems in the world, with up to millions of variables, constraints, and non-zeros.
CPLEX has a number of sophisticated features that drastically improve solving performance, these include: sophisticated problem preprocessing, efficient restarts form an advanced basis, sensitivity analysis, infeasibilty finder to mention a few.
CPLEX has an arsenal of methodologies to solve LP problems, typically the best approach is CPLEX's dual simplex algorithm for the majority of problems. There are certain types of problems that may benefit from CPLEX's primal simplex algorithm. CPLEX also encompasses an interior point method, its Barrier algorithm which provides an alternative to the simplex method for solving linear problems, it is based on a primal-dual predictor-corrector method. The barrier algorithm is generally considered when used to solve large problems or if the problems may have numerical instability issues. There is also an efficient network simplex method that is effective in solving network models.
CPLEX can solve models that have a quadratic objective function and linear constraints. If the objective function is positive semi-definite it can utilize any of the LP methods. To solve QPs in MPL by CPLEX one has to set in MPL the "ModelType" to Quadratic.
CPLEX Mixed Integer Optimizer provides the capability to solve problems with mixed-integer variables (general or binary). It utilizes state-of-the art algorithms and techniques. CPLEX principally uses a branch and cut algorithm that essentially solves a series of relaxed LP subproblems. Addition of cuts and sophisticated branching strategies can be employed at these subproblems to try to find the optimal solution more effectively. CPLEX also have heuristics that can aid in finding initial good solutions, it also includes a sophisticated mixed integer preprocessing system. One can even solve large and difficult integer problems quickly and efficiently.
CPLEX is tuned to solve the vast majority of LP problems using the default options. There are occasions where one may need to change the option settings, these are usually a result of bad performance or numerical instability issues. On the whole the dual simplex method is best for most LP problems, there are some instances where the primal simplex may work best. The barrier method typically should be used for very large sparse models or models that are experiencing numerical difficulties. The sifting algorithm is a simple form of column generation well suited for models where the number of variables dramatically exceeds the number of constraints. Bad performance on LPs is using a result of degeneracy, which can be identified by examining the iteration log, having long sequences of iterations where the objective value remains unchanged. Perturbations can help speed up performance on degenerate problems. Degeneracy is not an issue for the barrier method, thus highly degenerate problems one should use the barrier algorithm to solve the LP.
MIP problems can be extremely difficult to solve, though there are no steadfast rules on enhancing MIP performance, certain things may be advantageous in improving the performance on some models and be a hinderous on other problems. Below are some of the considerations one should look into when try to solve difficult MIP problems:
Priority orders:Assign higher priority to the integer variables that should be decided earlier, these tend to represent decisions that are strategic or activate processes. The order, the variables are defined in MPL indicates the MIP priority, earlier the definition the higher the priority.
Cutoffs: Setting cutoff values can greatly speedup the process, the cuttoff value (known value that is equal or worse than the true optimal value) maybe attained from some heuristic algorithms to the same problem or a previous uncompleted run of the MIP model. Use "MipUpperCutoff" to set upper cutoff value for minimization problems, and set "MipLowerCutoff" value for maximization problems.
Probing: This looks at the logical implications of fixing binary variables, which happens after presolve but before branch and bound. CPLEX has 3 levels of probing, there is a trade off factor here that though more intensive probing can derive good results it can also take some time to complete the probing. For large difficult problems, we suggest using level 3 or 2 since time overhead of probing is more likely to be paid back over long running time of branch and bound.
Variable Selection: Selecting which variable to branch on can have considerable benefits. In difficult models "Strong Branching" or "Pseudo reduced costs" may be helpful. Both methods especially strong branching invest considerable effort in analyzing potential branches in hope of drastically reducing the number of nodes that will be explored.
Cuts: Adding cuts are one of the principal reasons of recent dramatic increases in MIP performance. The cuts can dramatically increase the best bound and remove otherwise sub-optimal branches in the tree. The more cuts added, the larger the inherent matrix becomes which can increase the processing time at the nodes. However usually on difficult models an aggressive cut strategy is the best mode of practice.
MPL shows the progress of CPLEX during a solve run in the message window which also can be relayed to a log file. One can set various log file parameters in MPL, allowing one to display log information for LPs and MIPs. One can set the frequency based on the number of iterations or nodes. The log initially displays information about the model and any subsequent information from the various preprocessing done, the message log has the following appearance:
CPLEX: Tried aggregator 1 time. CPLEX: MIP Presolve eliminated 0 rows and 1 columns. CPLEX: MIP Presolve modified 36 coefficients. CPLEX: Reduced MIP has 362 rows, 360 columns, and 1638 nonzeros. CPLEX: Reduced MIP has 342 binaries, 0 generals, 0 SOSs, and 0 indicators. CPLEX: Presolve time = 0.02 sec. CPLEX: Clique table members: 191. CPLEX: MIP emphasis: balance optimality and feasibility. CPLEX: MIP search method: dynamic search. CPLEX: Parallel mode: none, using 1 thread. CPLEX: Root relaxation solution time = -0.00 sec.
For MIPs CPLEX will display cut information and how they affect the best bound at the root node:
CPLEX: Nodes Cuts/ CPLEX: Node Left Objective IInf Best Integer Best Node ItCnt Gap CPLEX: 0 0 469.1579 41 469.1579 60 CPLEX: 0 0 598.0000 26 Cuts: 81 108 CPLEX: 0 0 598.0000 29 Cuts: 41 129 CPLEX: 0 0 598.3421 39 Cuts: 25 161 CPLEX: 0 0 600.1667 39 Cuts: 28 176 CPLEX: 0 0 607.0000 40 Cuts: 16 199 CPLEX: 0 0 607.0000 40 Cuts: 51 218 CPLEX: * 0+ 0 1650.0000 607.0000 218 63.21% CPLEX: 0 2 607.0000 40 1650.0000 607.0000 218 63.21%
The subsequent log shows the progress per x nodes, first column stating the nodes examined the second stated how many of those are still left in the tree. It also displays the best objective found so far, best bound and the relative gap.
CPLEX: * 780+ 390 678.0000 611.8947 14535 9.75% CPLEX: 800 402 639.2895 13 678.0000 611.9474 14916 9.74% CPLEX: 900 467 634.1667 26 678.0000 613.3158 17084 9.54% CPLEX: 1000 393 668.2879 25 678.0000 613.3158 19010 9.54% CPLEX: Elapsed time = 1.00 sec. (tree size = 0.11 MB, solutions = 15) CPLEX: * 1061 289 integral 0 674.0000 613.3158 20069 9.00% CPLEX: 1100 281 614.0000 8 674.0000 613.3158 20795 9.00% CPLEX: * 1150 235 integral 0 665.0000 613.3158 21656 7.77% CPLEX: 1200 239 654.5667 25 665.0000 614.0000 22467 7.67% CPLEX: * 1250+ 193 656.0000 616.0000 23483 6.10% CPLEX: 1300 203 cutoff 656.0000 617.3056 24461 5.90% CPLEX: 1400 257 623.8333 7 656.0000 618.9405 26481 5.65% CPLEX: 1500 297 645.0000 22 656.0000 620.6667 28594 5.39% CPLEX: 1600 337 624.4167 28 656.0000 621.0000 30524 5.34% CPLEX: 1700 370 638.0000 26 656.0000 622.1000 32702 5.17%
The asterix shows a MIP feasible solution was found. Once the optimal solution is found for a MIP problem the log will show summary statistics and also the number and of what type of cuts were added during the solving process:
CPLEX: Elapsed time = 3.14 sec. (tree size = 0.04 MB, solutions = 18) CPLEX: 5100 40 654.3333 25 656.0000 653.2222 89527 0.42% CPLEX: Clique cuts applied: 7 CPLEX: Cover cuts applied: 82 CPLEX: Implied bound cuts applied: 8 CPLEX: Flow cuts applied: 19 CPLEX: Mixed integer rounding cuts applied: 21 CPLEX: Zero-half cuts applied: 4 CPLEX: Gomory fractional cuts applied: 8 STATUS: Writing MIP start values file 'tsp3.mst' CPLEX: Using devex. Solver Statistics Solver name: CPLEX (11.2.1) Objective value: 656.000000000000 Integer Nodes: 5153 Iterations: 89906 Solution time: 3.21 sec Result code: 101
CPLEX 11 runs under the control of the ILOG License Manager (ILM). Before you can run ILOG CPLEX, or any application that calls it, you must have established a valid license that ILM can read.
CPLEX requires the ihostid codes to generate a valid license, thus once the software has been installed, the following steps should be performed to the obtain the ihostid codes: Choose CPLEX IHostID from the Start menu:
Start | Programs | MPL for Windows 5.0 | CPLEX IHostID
You will need to copy the three codes displayed in the DOS window which you can do by clicking on the MSDOS icon in the upper left corner and choose
Edit | Mark from the menu.
Then select the three lines with the mouse and choose Edit | Copy from the same menu and paste this into the email you are sending us.
The license for CPLEX will be 2 or 3 lines of text that need to be placed in a file called Access.ilm. An example of a license is shown below:
---------------------------------------------------------------------- LICENSE Evaluation maximal software-arlington, va EVAL CPLEX 10.200 25-Aug-2007 C9520026GDA5 any , options: e m b q MaintenanceEnd=20070825 , license: 1260742 ----------------------------------------------------------------------
You can use the 'CPLEX 7+' tab in the Maximal License Manager to copy and paste the text between the lines and then activate the license.
For full description of all the CPLEX Parameters that are supported in MPL please go to the CPLEX Option Parameters page.