CoinMP for MPL

The Coin-MP optimizer is an open source solver, it is part of the COIN-OR project which is an initiative to spur the development of open-source software for the operations research community. CoinMP amalgamates the projects: CLP (linear programming), CBC (Branch and Cut library) and the CGL (Cut Generation library) together in one dynamic linked library. CoinMP at present is a linear and integer programming optimizer. MPL links direct through memory to the CoinMP, allowing users full functionality of the powerful optimization routines encompassed by the associated 3 COIN-OR libraries.

Algorithmic Features

COIN-OR is a large group of projects ranging from linear to nonlinear programming right through to heuristic and modelling interfaces, CoinMP is solely about the integration of the COIN's CLP, CBC and CGL libraries into one easy to use tool. Thus CoinMP can solve linear programming problems accessing the functionality embedded in the CLP library, solve integer and mixed integer programming problems utilising the algorithmic features of both the CBC and CGL libraries.

Linear Programming

CoinMP has a complete set of algorithms to handle LP problems, encompassing the dual simplex, primal simplex and barrier methods. It has an integrated presolve algorithm, that removes redundant constraints and variables whilst also tightening the constraint formulations. CoinMP's barrier algorithm provides an alternative to the simplex algorithms and uses interior point methods to solve linear programming problems. The barrier algorithm employs a number of cutting edge Cholesky factorization techniques allowing for fast dense factorization, which is especially useful for large problems.

Mixed Integer Programming

CoinMP uses the branch and bound algorithm to solve MIP problems, coupled with numerous branching and cutting plane strategies, this generally results in reasonable performance even on fairly difficult MIP problems. Synopses of its features are:

Has access to the CGL of pre-defined cutting planes, these advanced cutting-plane strategies automatically improve the quality of bounds and ultimately will reduce the size of the global search. CoinMP implements a series of cutting planes which include:

Having these components in the optimizer allows often fairly large and difficult MIP problems to be solved effectively.

Performance Tuning

For LPs

The vast majority of LPs can be solved using CoinMP's default setting. There are on occasions one may need to tinker with the settings, typically as a result of degeneracy or bad performance. The default algorithm in solving LPs is the primal simplex method, the dual simplex method on average performs much better in larger LPs, for very large sparse problems the barrier method should be considered. To change the LP algorithm one needs to set the option "SolveMethod" to a setting of 0 for the dual and 4 for the barrier method. The pricing mechanism can also play a vital role in the effectiveness of the simplex methods, for both methodologies the steepest edge pricing is set as the default. This will always result in fewer iterations reaching the optimal solution but the computation required per iteration can be expensive thus faster pricing policies can be chosen that will result in a greater number of fast iterations. Steepest edge works very well in the dual simplex, though in the primal one may find partial devex (setting option "PrimalColPivotAlg" = 2) may work better than the default.

For MIPs

Solving MIPs can be a difficult and exhaustive task, difficulty is dependent on the actual formulation along with the number of discrete variables in the problem. There is no universal rule on enhancing the performance on MIPs, certain setting may work well on one problem and be impediment in other problems. Though there are some considerations that should be looked into when solving difficult MIP problems using CoinMP:

Back To Top | Maximal Home Page | Table of Contents | Previous Page | Next Page