A constraint generation algorithm for large scale linear programs using multiple-points separation (Q2492707)

The authors study a scheme of constraint generation algorithms that consists in separating several points from the feasible set \(S\) of large scale linear programming (P): \(\max c^Tx \text{ s.t. } x \in S\) where \(S \subseteq\mathbb R^n\) is a polyhedron. They show that many problems involving multiple-points separation are NP-complete. A generic algorithmic scheme for multiple-points separation is introduced and it is claimed that its efficiency has been tested computationally on random linear programs and other problems and the experiments show that such procedures may substantially decrease the total number of iterations needed to solve the original problem (P). The authors also suggest the need for further studies that use different multiple-points separation schemes taking advantage of the particular problem structures or interior point algorithms.