FortMP for MPL

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.

Algorithmic Features

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

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 Programming

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.

Quadratic Programming

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.

Performance Tuning

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:

For LPs

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.

For MIPs

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.

FortMP Log Output

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     

FortMP Parameter Options

For full description of all the FortMP Parameters that are supported in MPL, please go to the FortMP Option Parameters page.


Back To Top | Maximal Home Page | List of Solvers | Previous Page | Next Page