Linear programming with special ordered sets

Research output: Contribution to journalArticleResearchpeer-review

4 Citations (Scopus)


Concave objective functions which are both piecewise linear and separable are often encountered in a wide variety of management science problems. Provided the constraints are linear, problems of this kind are normally forced into a linear programming mould and solved using the simplex method. This paper takes another look at the associated linear programs and shows that they have special structural features which are not exploited by the simplex algorithm. It suggests that their variables can be divided into special ordered sets which can then be used to guide the pivoting strategies of the simplex algorithm with a resultant reduction in basis changes.

Original languageEnglish
Pages (from-to)69-74
Number of pages6
JournalJournal of the Operational Research Society
Issue number1
Publication statusPublished - 1 Jan 1984


  • Linear programming
  • Non-linear programming
  • Production planning
  • Statistics

Cite this