Fast approximate solution of linear programming problems

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

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.