A penalty approach to linear programs with many two-sided constraints

Research output: Contribution to book/Conference proceedings/Anthology/ReportConference contributionContributedpeer-review

Contributors

Abstract

The paper focuses on linear programming problems with two-sided constraints whose number is much larger than the number of variables. The solution approach is based on a non-smooth convex penalty function. An appropriate penalty parameter ensures the equivalence between the original problem and the problem of minimizing the penalty function. The latter problem is tackled by means of a modification of the r-algorithm, i.e., of an iterative subgradient method with an adaptive step adjustment and a constant coefficient of space dilation in the direction of the difference of two successive subgradients. Based on an implementation of this LPralg algorithm with GNU Octave, computational results on randomly generated instances with 20.000 to 1.500.000 two-sided constraints and up to 300 variables are presented. The results turn out to be very promising compared to well-known linear programming software, such as the GLPK package as well as CPLEX and Gurobi solvers. Among other problems, the new approach can be applied to robust linear programs with a finite uncertainty set.

Details

Original languageEnglish
Title of host publicationMathematical Optimization Theory and Operations Research - 20th International Conference, MOTOR 2021, Proceedings
EditorsPanos Pardalos, Michael Khachay, Alexander Kazakov
Place of PublicationCham
PublisherSpringer Nature Switzerland, Dortrecht [u. a.]
Pages206-217
Number of pages12
Volume12755
ISBN (electronic)978-3-030-77876-7
ISBN (print)978-3-030-77875-0
Publication statusPublished - 2021
Peer-reviewedYes

External IDs

Scopus 85111379789

Keywords

DFG Classification of Subject Areas according to Review Boards

Subject groups, research areas, subject areas according to Destatis