Linear programming with special ordered sets

Research output: Contribution to journalArticleResearchpeer-review

6 Citations (Scopus)

Abstract

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
Volume35
Issue number1
DOIs
Publication statusPublished - 1 Jan 1984

Keywords

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

Cite this

@article{e08a3ce2e44d4f6cb193d60416707953,
title = "Linear programming with special ordered sets",
abstract = "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.",
keywords = "Linear programming, Non-linear programming, Production planning, Statistics",
author = "Snyder, {R. D.}",
year = "1984",
month = "1",
day = "1",
doi = "10.1057/jors.1984.8",
language = "English",
volume = "35",
pages = "69--74",
journal = "Journal of the Operational Research Society",
issn = "0160-5682",
publisher = "Palgrave Macmillan",
number = "1",

}

Linear programming with special ordered sets. / Snyder, R. D.

In: Journal of the Operational Research Society, Vol. 35, No. 1, 01.01.1984, p. 69-74.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Linear programming with special ordered sets

AU - Snyder, R. D.

PY - 1984/1/1

Y1 - 1984/1/1

N2 - 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.

AB - 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.

KW - Linear programming

KW - Non-linear programming

KW - Production planning

KW - Statistics

UR - http://www.scopus.com/inward/record.url?scp=0021155372&partnerID=8YFLogxK

U2 - 10.1057/jors.1984.8

DO - 10.1057/jors.1984.8

M3 - Article

VL - 35

SP - 69

EP - 74

JO - Journal of the Operational Research Society

JF - Journal of the Operational Research Society

SN - 0160-5682

IS - 1

ER -