Generating linear programming instances with controllable rank and condition number

Instance generation is crucial for linear programming algorithms, especially for the evaluation and verification of corresponding methods. 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, a bounded feasible linear programming instance is generated with the right-hand side and objective coefficients satisfying the primal feasibility and dual feasibility. In addition, we provide three neighborhood exchange operators and prove that instances generated under this method can fill the entire space of feasible bounded linear programming instances. We experimentally validate that the proposed schedule generates more controllable linear programming instances in rank and condition number, while neighborhood exchange operators construct more complex instances.

Automated summary

This study proposes a general framework for designing linear programming instances based on the preset optimal solution, and validates the effectiveness of the framework through experiments.