Fast approximate solution of linear programming problems

这个项目的目的是开发和实施新的技术，在应用单纯形法之前对线性规划(LP)问题进行预处理。学生将研究现有的通过消除变量和约束来减少LP问题的“预解”规则，并开发有效的技术来实施它们，以及可能地识别新的预解规则。在开源单纯形求解器CLP中，存在一种未记录和未发表的技术，用于获得LP问题的近似解。这被称为“白痴崩溃”，众所周知，它对有限类别的LP问题是有效的。在学习和传播这项技术之后，学生将开发新的算法来解决Idiot Crash的局限性，以便将其适用于更广泛类别的LP问题。学生的工作将在开源求解器High的背景下开发，并有望对商业线性优化软件产生影响。

The aim of this project is to develop and implement novel techniques preprocessing linear programming (LP) problems prior to application of the simplex method. The student will study existing "presolve" rules for the reduction of LP problems via the elimination of variables and constraints and develop efficient techniques for implementing them, as well as possibly identifying new presolve rules. Within the open source simplex solver Clp, there exists an undocumented and unpublished technique for obtaining an approximate solution of LP problems. This is known as the "Idiot crash", and is known to be effective for a limited class of LP problems. After studying and disseminating this technique, the student will develop novel algorithms that address the limitations of the Idiot crash in order to extend its applicability to a wider class of LP problems. The student's work will be developed in the context of the open source solver HiGHS, and can be expected to have an impact on commercial linear optimization software.