论文标题
生成具有可控等级和条件编号的线性编程实例
Generating Linear programming Instances with Controllable Rank and Condition Number
论文作者
论文摘要
实例生成对于线性编程算法至关重要，这对于通过训练学习方法找到最佳枢轴规则或评估和验证相应的算法是必要的。这项研究提出了一个一般框架，用于设计基于预设最佳解决方案的线性编程实例。首先，我们从矩阵分解的角度给出了具有可控条件编号的约束矩阵生成方法。基于预设的最佳解决方案，有界的可行线性编程实例是用右侧和客观系数生成的，可满足原始和双重可行性。此外，我们还提供了三种邻里交换运算符，并证明在这种方法下生成的实例可以填充线性编程的整个可行且有限的案例空间。我们通过实验验证提出的时间表可以生成更可控制的线性编程实例，而邻居交换运算符可以构建更复杂的实例。
Instances generation is crucial for linear programming algorithms, which is necessary either to find the optimal pivot rules by training learning method or to evaluate and verify corresponding algorithms. This study proposes a general framework for designing linear programming instances based on the preset optimal solution. First, we give a constraint matrix generation method with controllable condition number and rank from the perspective of matrix decomposition. Based on the preset optimal solution, the bounded feasible linear programming instance is generated with the right-hand side and objective coefficient satisfying the original and dual feasibility. In addition, we provide three kind of neighborhood exchange operators and prove that instances generated under this method can fill the whole feasible and bounded case space of linear programming. We experimentally validate that the proposed schedule can generate more controllable linear programming instances, while neighborhood exchange operator can construct more complex instances.
