Comparison of two mixed integer solvers with real world data from combinatorial auctions

Abstract: Coupa is a software company specialising in Business Spending Management, BSM. In the Uppsala office they utilise MIP solvers to help their clients lower sourcing outlays by translating sourcing auc- tions into MIP problems [1] [2]. MIP, or Mixed-Integer Programming, is a mathematical optimization technique used to solve optimization problems where some of the variables can only take on integer values [3] [4]. MIP solvers are specialized software tools that employ algorithms to find the optimal solution. As Coupa utilise MIP solvers it is in the best interest to see how different MIP solvers fare against each other. A good solver employs efficient solving large scale problems as well as handle increasingly complex problems without a significant decline in efficiency. For Coupa, a good solver should present some sort of determinism in the sense that given the same prerequisite a solver should return the same solution every time. The test suite examined two solvers, the open source solver HiGHS and a commercial solver called Xpress [5] [6]. The test suite is divided into four categories, Primal Dual Gap, Ratio, Memory Usage, and Determinism. Primal Dual Gap is the gap between the primal and dual problem of a MIP problem, Ratio are intermediate objective values divided by a precalculated run at Coupa with the Xpress solver, Memory Usage is how much memory each solver used and Determinism is as explained before. Although the method used to extract memory usage has flaws HiGHS showed better results than Xpress. In the categories Primal Dial Gap and Ratio Xpress showed to be the superior solver, but HiGHS was not too far behind, while determinism showed equal re- sults.