The GLPK optimizer is an open source solver under the banner of the GNU project. GLPK is a linear and mixed integer programming optimizer and is currently developed and maintained by Andrew Makhorin, of the Moscow Aviation Institute. GLPK for MPL gives MPL users access to this renowned free solver from within the user-friendly Windows environment of MPL. As with other solvers, the GLPK optimizer is accessed from MPL for Windows as a Dynamic Link Library (DLL). This tight and robust integration allows MPL users to access various GLPK solution algorithms and options from their MPL application.
GLPK incorporates a number routines and procedures used solving linear and mixed integer programming problems, making it one of the most popular open source solver out in the market place.
GLPK does have a complete set of algorithms to handle LP problems, encompassing the dual simplex, primal simplex and barrier methods. The simplex solver has its own presolver, which transform the original LP problem in to a more manageable form. Undertaking various procedures to remove redundant variables and constraints, fixing some non-basic variables and improving the numeric properties of the model. The GLPK implementation of the interior-point method is reasonable and generally can handle most LP problems. Though users should note that currently the interior point solver does not include many important features especially: processing of dense columns, no features that stabilize numerical instability thus many LPs can terminate prematurely.
GLPK naturally implements the branch and bound algorithm to solve MIP problems. Recent enhancements have been added to the Integer optimizer, making it possible to solve reasonably large and difficult models, a synopsis of its features are:
The default settings generally work well for a large set of problems, though especially in very large LPs or solving MIPs one often will need to tune the solver parameters in order to achieve the best results.
The vast majority of LPs can be solved using GLPK default settings. The primal simplex method is the default setting, though in many cases especially when the model is large it may be more appropriate to utilize the dual simplex method. The option "Dual" can be set to one. If one still experiences performance issues for both the simplex methods one can try the interior point method though as mentioned it can be unstable. Other strategies would be suggesting to modify the pricing strategies employed in the simplex method, the default is set to steepest edge pricing ("price" = 1). This works best in the dual simplex instance, steepest edge pricing can be computationally more expensive, GLPK offers an alternative (Dual = 0) where it implements a simple basic pricing strategy which may work well especially for the primal simplex method. Generally a reduced and more numerically sound model will result in better performance, thus one should as a standard rule implement GLPK's linear presolver, which by default is not used, to activate it set the option "Presolve" to one
GLPK has encompassed many features in its MIP solver, implementing an effective MIP presolver that removes free, singleton and redundant constraints, improves the bounds on variables, eliminating fixed variables and reducing constraint coefficients. This essentially tightens the model formulation making subsequent branch and bound process likely to be more efficient.
One of the most important factors in recent advances in MIP optimizers is the development and implementation of cutting plane algorithms. These add constraints that cutoff regions of the LP relaxed convex hull that do not contain integer feasible solutions. This can lead to drastic speed ups in performance. For difficult MIP problems employing cuts is recommended, GLPK incorporates:
A setting of 256 for the option "UseCuts" initiates all the above cuts, this setting should be used for large or difficult MIPs.
Traversing the branch and bound tree and exploring new branches can ultimately determine how quick one finds good solutions and ultimately prove optimality. GLPK default settings uses a heuristical approach based on the work by Driebeck and Tomlin in regards to the variable selection. It also uses a projection heuristic as its default setting in backtracking. For difficult set of MIP problems the breadth first approach should be used as the de facto backtracking method this is set using the option "Backtrack" to one. The best branching strategy can be problem specific, thus for the more difficult MIP problems it is best to try all three strategies.
MPL displays the progress of GLPK during an optimization run in the message window that also can be relayed to a log file. The log has the following appearance:
STATUS: Optimizing 'Stiglers_nutrition_model' with Glpk 4.16 Solver GLPK: 0: objval = 0 infeas = 1 (0) GLPK: 10: objval = 0.134944748 infeas = 0 (0) GLPK: * 10: objval = 0.134944748 infeas = 0 (0) GLPK: * 15: objval = 0.108662278 infeas = 0 (0) GLPK: OPTIMAL SOLUTION FOUND Solver Statistics Solver name: GLPK Objective value: 0.108662278206757 Iterations: 15 Solution time: 0.00 sec Result code: 180 STATUS: Optimal solution found
For LPs GLPK will relay the iteration number the corresponding objective value and the status of the infeasiblities during the two-phase simplex search. Upon completion of the solve, MPL will relay a summary of the solver statistics.
For MIPs GLPK relays the same type of information in regards to the initial LP relaxation and whilst in the branch and bound search displays the node count, the second columns states the best integer feasible solution found thus far . The third column states the best bound along with the relative gap at the specific stage of the search. An example of a MIP log is displayed below:
GLPK: 0: objval = 0 infeas = 1 (0) GLPK: 26: objval = 690.083333 infeas = 9.25185854e-018 (1) GLPK: * 26: objval = 690.083333 infeas = 2.22044605e-016 (1) GLPK: * 82: objval = 141 infeas = 6.66133815e-016 (1) GLPK: OPTIMAL SOLUTION FOUND GLPK: Integer optimization begins... GLPK: Objective function is integral GLPK: 82: mip = not found yet >= -inf (1; 0) GLPK: * 244: mip = 305 >= 141 53.8% (20; 0) GLPK: * 296: mip = 234 >= 141 39.7% (25; 1) GLPK: * 375: mip = 177 >= 141 20.3% (29; 12) GLPK: 606: mip = 177 >= tree is empty 0.0% (0; 127) GLPK: INTEGER OPTIMAL SOLUTION FOUND Solver Statistics Solver name: GLPK Objective value: 177.000000000000 Integer Nodes: 0 Iterations: 606 Solution time: 0.25 sec Result code: 171 STATUS: Optimal integer solution found
For full description of all the GLPK Parameters that are supported in MPL, please go to the GLPK Option Parameters page.