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.
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.
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.
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.
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.
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:
Probing:Looks at the logical implications of fixing binary variables. CoinMP allows one to set the intensity of the probing it undertakes, there is a trade off factor, more intensive probing can derive good results it can also take some time to complete the probing. For large difficult problems, we suggest using a "MipProbeMaxPass" of greater than 10 though for models with large number of binary variables one may want to keep it under 20. The time overhead of probing is more likely to be paid back over long running time of branch and bound.
Cuts:CoinMP has a wide range of cutting plane algorithms in its arsenal. 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. Thus in some situations one may need to deactivate some cuts though for extremely difficult MIP problems we would suggest utilizing all available cutting plane procedures. The cuts can be activated by setting the value to 1 for its corresponding option (i.e. MipCutOddHole = 1).