FortMP is a state of the art optimization system designed to solve a wide range of well-known optimization problems. FortMP has been widely deployed to solve many management science and operational research problems. In its basic configuration, FortMP is suitable for Linear, and (Mixed) Integer Programming, but it is also available in extended configurations for (Integer) Quadratic Programming.
FortMP optimizer incorporates a suite of well known solution algorithms that have been carefully designed taking into consideration underlying data structures and modular processing components such that different features can interact well with each other. Research and development of the underlying algorithms started in the mid eighties. However, the computational algorithms and the software system have been constantly kept up to date with the developments that continue to take place in this field.
Linear programming problems are processed by sparse simplex (SSX) with both PRIMAL and DUAL variants. An interior point method (IPM) algorithm is also included which uses the PRIMAL-DUAL Logarithmic barrier method with predictor-corrector extensions. A powerful basis recovery (cross over) algorithm combines the speed of the IPM solution with the warm restart property of the SSX.
Mixed integer programs are solved by applying branch and bound tree search methods. Incorporating up to date cutting plane methods and integer preprocessing techniques the MIP solver engine is kept highly competitive and effective in solving discrete optimisation problems. The mixed integer programming feature can run under a single or multiple distributed memory parallel processors and performance can be tuned for both these platforms.
The MIP provides a very rich tree search procedure. It can represent binary, integer and semi-continuous variables, and special ordered sets. The MIP processing can be controlled using advanced cutting-plane strategies to automatically improve the quality of bounds and reduce the size of the global search.
FortMP incorporates a convex quadratic programming (QP) capability and processes the QP problems using a primal/dual QP simplex algorithm. Through a branch and bound harness, the system is extended to solve quadratic mixed integer programs (MIQPs). FortMP incorporates a branch-fix-and-relax heuristic enhancing the performance in solving large MIQPs.
FortMP's default setting usually performs well, though there may be instances whereby one needs to improve FortMP's performance on certain optimization problems. One can suggest a few pointers depending on the problem type:
The vast majority of LPs can be sufficiently solved using FortMP's default options. There are occasions where one needs to alter the parameter settings, these are usually a result of bad performance or numerical instability issues. Performance issues with the simplex method typically result due to degeneracy. If one is experiencing these issues it may be preferential to use the interior-point solver, which is better suited when solving large sparse LPs or problems that may be highly degenerate.
MIP problems can be extremely difficult to solve to optimality. There is no fixed rule that works on every MIP, certain settings work best on some models and may be disadvantageous in improving the performance on other problems. Preprocessing MIPs can greatly enhance the "tightness" of the problem formulation whereby coefficients and RHS values are modified, redundant constraints and variables are removed. This ultimately makes the problem smaller and more manageable. The default setting for the MIP preprocessor ("MIPpreprocess") is turned off, for more difficult MIPs one should always enable this option. Cutting plane algorithms are a keen area of research interest, addition of cuts can dramatically increase the performance of MIPs generally by reducing the size of the convex hull of the LP relaxed problem leading to improved best bounds and removing otherwise sub-optimal branches in the branch and bound tree. The default setting ("CutGenerate") is not to generate cuts, however for difficult MIP problems it is always advised to enable the cut generation option, this can lead to substantial performance gains.
MPL shows the progress of a FortMP solve by relaying information to the message window which in turn can also be printed to a log file. The log initially displays information about the which algorithm is being used along with the licensing information., the message log has the following appearance:
FORTMP: SPEC RECEIVED: *DLL*C:\mplwin4\fortmp.dll FORTMP: FORTMP(LP) SOLVER HAS BEEN CALLED FORTMP: FORTMP release version 3.02j, Jan 2004 FORTMP: License expires on (y)2050:(m)01:(d)01. FORTMP: BEGIN FORTMP: MAXIMUM MIP INTSOL = 100 FORTMP: ASGNFM: MREQ= 346608(Byte), OFFset= 174522432(Byte) FORTMP: TIME TAKEN FOR INPUT/SETUP = 0.17 SECS, TOTAL SO FAR = 0.17 SECS FORTMP: SCALING IN PROGRESS ... FORTMP: SCALING COMPLETE FORTMP: TIME TAKEN FOR SCALE/PRSLVE= 0.00 SECS, TOTAL SO FAR = 0.17 SECS FORTMP: CRASH(LTSF) ENDED. VARIABLE TYPES:- PLUS BNDD FIX FREE FORTMP: LOGICALS REMOVED FROM BASIS:- 116 0 192 0 FORTMP: STRUCTURALS ENTERED IN BASIS:- 308 0 0 0 FORTMP: CRASH(ART) ENDED: 1 PASSES: 12 ARTIFICIALS, 0 PIVOTED OUT FORTMP: TIME TAKEN FOR CRASHING = 0.03 SECS, TOTAL SO FAR = 0.20 SECS FORTMP: Invert demand: Obj =-.185030E+08 Suminf =-114750. ITER# 51 FORTMP: Invert demand: Obj =-.195792E+08 Suminf =-62040.8 ITER# 102 FORTMP: Invert demand: Obj =-.129458E+08 Suminf =-33010.8 ITER# 153 FORTMP: Invert demand: Obj =-.254514E+07 Suminf =-1836.46 ITER# 204 FORTMP: FEASIBLE BASIS REACHED AFTER ITERATION 208 FORTMP: Invert demand: Obj =0.601134E+07 Suminf = 0.00000 ITER# 255 FORTMP: Invert demand: Obj =0.149615E+08 Suminf = 0.00000 ITER# 306 FORTMP: FORREST-TOMLIN ACTIVATED FORTMP: Invert demand: Obj =0.231360E+08 Suminf = 0.00000 ITER# 382 FORTMP: Invert demand: Obj =0.252802E+08 Suminf = 0.00000 ITER# 436 FORTMP: STATUS = 3 -- OPTIMUM SOLUTION FOUND. 0.252802E+08 ITER# 436 FORTMP: TIME TAKEN FOR PRIMAL = 0.06 SECS, TOTAL SO FAR = 0.26 SECS FORTMP: TIME TAKEN FOR OUTPUT = 0.00 SECS, TOTAL SO FAR = 0.26 SECS Solver Statistics Solver name: FortMP Objective value: 25280162.3429924 Iterations: 436 Solution time: 0.29 sec Result code: 3
The log displays information regarding the crash procedure before relaying the objective, sum of infeasibilities of the iterations. For MIPs FortMP will simply display objective and node count when an integer solution is found, like below:
FORTMP: ---------- IN THIS SEARCH ------------- FORTMP: NODE CHOICE STRATEGY = ( 1, 7) FORTMP: VARIABLE CHOICE STRATEGY = 1 FORTMP: PRIORITY UP IS OFF, PREP IS OFF FORTMP: --------------------------------------- FORTMP: $$$$ INTEGER SOLUTION: 0.230000E+03, FOUND AT NODE# 14 FORTMP: Time since B&B start: 0.16 secs, Iter# = 334 FORTMP: $$$$ INTEGER SOLUTION: 0.187000E+03, FOUND AT NODE# 27 FORTMP: Time since B&B start: 0.25 secs, Iter# = 464 FORTMP: $$$$ INTEGER SOLUTION: 0.177000E+03, FOUND AT NODE# 53 FORTMP: Time since B&B start: 0.31 secs, Iter# = 631 FORTMP: ********** Search completed ************** FORTMP: Integer solutions 3 FORTMP: The IP optimum is 177.00000 FORTMP: Total nodes: opened = 133 processed = 122 FORTMP: Final iteration count = 786 FORTMP: TIME TAKEN FOR INTEGER = 0.56 SECS, TOTAL SO FAR = 0.70 SECS FORTMP: TIME TAKEN FOR OUTPUT = 0.03 SECS, TOTAL SO FAR = 0.74 SECS Solver Statistics Solver name: FortMP Objective value: 177.000000000000 Integer Nodes: 0 Iterations: 786 Solution time: 0.79 sec Result code: 5
For full description of all the FortMP Parameters that are supported in MPL, please go to the FortMP Option Parameters page.