The large-scale performance conjecture for linear superiorization

Let LinSup denote the linear superiorization method, and let linear minimization algorithms denote algorithms for solving linear optimization problems. The conjecture concerns the performance of these methods as the size of the problem grows.

Large-scale performance conjecture. There exists a size level of huge problems above which LinSup will perform better than linear minimization algorithms.

The claim is motivated by the reported experiments, in which LinSup found superior feasible points and its execution time appeared to increase more moderately with problem size than that of the Simplex algorithm. The source further suggests, without asserting it as part of the conjecture, that this may call for parallelizable feasibility-seeking projection methods such as block-iterative projections or string-averaging projections.