Linear superiorization for infeasible linear programming

Linear superiorization (abbreviated: LinSup) considers linear programming (LP) problems wherein the constraints as well as the objective function are linear. It allows to steer the iterates of a feasibility-seeking iterative process toward feasible points that have lower (not necessarily minimal) values of the objective function than points that would have been reached by the same feasiblity-seeking iterative process without superiorization. Using a feasibility-seeking iterative process that converges even if the linear feasible set is empty, LinSup generates an iterative sequence that converges to a point that minimizes a proximity function which measures the linear constraints violation. In addition, due to LinSup's repeated objective function reduction steps such a point will most probably have a reduced objective function value. We present an exploratory experimental result that illustrates the behavior of LinSup on an infeasible LP problem.

Citation

In: Discrete Optimization and Operations Research, Editors: Y. Kochetov, M. Khachay, V. Beresnev, E. Nurminski and P. Pardalos, Lecture Notes in Computer Science (LNCS), Vol. 9869, 2016, Springer International Publishing, pp. 15-24. DOI:10.1007/978-3-319-44914-2_2.

Article

Download

View Linear superiorization for infeasible linear programming