HiGHS

HiGHS is the world's best open-source linear optimization software, with industry standard benchmarks demonstrating that its interior point solver (IPX) for large scale linear programming (LP) problems offers significantly better performance than other popular open-source software. This has been acclaimed by users who had, previously, been unable to solve problems of interest without expensive licensed commercial software. However, for certain classes of practical LP problems, HiGHS still lags well behind the leading commercial solvers. The aim of this project is to close this gap by enhancing IPX in two stages. The first stage will see IPX adapted to use the existing, more efficient, sparse numerical linear algebra system in HiGHS, rather than the system written when IPX was first developed. This will require several weeks of work by an expert developer at a cost of approximately $27k. In cases where IPX has identified inefficiencies, it is anticipated that this will improve its performance by a factor of 2-4. The second stage will develop an entirely new alternative sparse numerical linear algebra option to solve practical LPs where IPX is currently prohibitively inefficient. This is a considerable undertaking, requiring 12 months’ work by a skilled developer and consultancy input, at a cost of approximately $114k. In the case of such LP problems, it is anticipated that the performance of IPX will be enhanced by one or two orders of magnitude.