Efficient LP warmstarting for linear modifications of the constraint matrix

2025/01/07 by Guillaume Derval, Derval, Guillaume, Bardhyl Miftari +5
Engineering · #Manufacturing Process and Optimization #Advanced Numerical Analysis Techniques #Optimization and Packing Problems

paper · pdf · doi:10.48550/arxiv.2501.04151

Abstract

We consider the problem of computing the optimal solution and objective of a linear program under linearly changing linear constraints. The problem studied is given by min c^t x s.t Ax + λDx ≤ b where λ belongs to a set of predefined values Λ. Based on the information given by a precomputed basis, we present three efficient LP warm-starting algorithms. Each algorithm is either based on the eigenvalue decomposition, the Schur decomposition, or a tweaked eigenvalue decomposition to evaluate the optimal solution and optimal objective of these problems. The three algorithms have an overall complexity O(pm²+pmn) where m (resp. n) is the number of constraints (resp. variables) of the original problem and p the number of values in Λ after an initial preprocessing step. We also provide theorems related to the optimality conditions to verify when a basis is still optimal and a local bound on the objective.

Related

• Sensitivity analysis for linear changes of the constraint matrix of a linear program
• Reducing Linear Programs into Min-max Problems
• Warm-starting constraint generation for mixed-integer optimization: A Machine Learning approach
• Solving a linear program via a single unconstrained minimization
• Nearly Linear-Time Packing and Covering LP Solvers