一种用于线性规划问题的冗余约束检测的方法、设备和系统

摘要

本公开涉及一种用于线性规划LP问题的冗余约束检测的方法、设备和系统。所述方法包括：选择在所述LP问题的解空间内的一个内点；确定所述LP问题的约束集中在经过所述内点的直线的两个方向上与所述直线最先相交的约束，其中所述直线沿着一个坐标方向经过所述内点延伸；以及将找到的与该直线最先相交的所述约束作为非冗余约束，来执行冗余约束检测。根据本公开，提供了一种改进的用于冗余约束检测的方法，其中基于坐标搜索来确定非冗余约束，并基于确定的非冗余约束来执行冗余约束检测。利用该方法，可以找到更多的非冗余约束，而且基于找到的这些非冗余约束而执行冗余约束检测可以显著提高冗余约束的检出率，这特别在高维特征的情况下尤其有益。