SCARF'S PROCEDURE FOR INTEGER PROGRAMMING AND A DUAL SIMPLEX ALGORITHM.

Philip M. White; Andrew S. Caplin; Ludo Van der Heyden

doi:10.1287/moor.10.3.439

SCARF'S PROCEDURE FOR INTEGER PROGRAMMING AND A DUAL SIMPLEX ALGORITHM.

Philip M. White, Andrew S. Caplin, Ludo Van der Heyden

Research output: Contribution to journal › Article › peer-review

Abstract

H. E. Scarf has recently introduced an algorithm for integer programs based on the combinatorial concept of primitive set. We show that as the decision variables of the integer program become continuous and the integer program reduces to a linear program, the Scarf algorithm converges to a dual simplex algorithm for the limit linear programming problem. This result is robust in the sense that even before the limit is reached, the dual simplex path is contained in the path of primitive sets generated by the Scarf algorithm.

Original language	English (US)
Pages (from-to)	439-449
Number of pages	11
Journal	Mathematics of Operations Research
Volume	10
Issue number	3
DOIs	https://doi.org/10.1287/moor.10.3.439
State	Published - 1985

ASJC Scopus subject areas

General Mathematics
Computer Science Applications
Management Science and Operations Research

Access to Document

10.1287/moor.10.3.439

Cite this

@article{56b2f3a229574f7cb5460a8dc572c35b,

title = "SCARF'S PROCEDURE FOR INTEGER PROGRAMMING AND A DUAL SIMPLEX ALGORITHM.",

abstract = "H. E. Scarf has recently introduced an algorithm for integer programs based on the combinatorial concept of primitive set. We show that as the decision variables of the integer program become continuous and the integer program reduces to a linear program, the Scarf algorithm converges to a dual simplex algorithm for the limit linear programming problem. This result is robust in the sense that even before the limit is reached, the dual simplex path is contained in the path of primitive sets generated by the Scarf algorithm.",

author = "White, {Philip M.} and Caplin, {Andrew S.} and {Van der Heyden}, Ludo",

year = "1985",

doi = "10.1287/moor.10.3.439",

language = "English (US)",

volume = "10",

pages = "439--449",

journal = "Mathematics of Operations Research",

issn = "0364-765X",

publisher = "INFORMS Institute for Operations Research and the Management Sciences",

number = "3",

}

TY - JOUR

T1 - SCARF'S PROCEDURE FOR INTEGER PROGRAMMING AND A DUAL SIMPLEX ALGORITHM.

AU - White, Philip M.

AU - Caplin, Andrew S.

AU - Van der Heyden, Ludo

PY - 1985

Y1 - 1985

N2 - H. E. Scarf has recently introduced an algorithm for integer programs based on the combinatorial concept of primitive set. We show that as the decision variables of the integer program become continuous and the integer program reduces to a linear program, the Scarf algorithm converges to a dual simplex algorithm for the limit linear programming problem. This result is robust in the sense that even before the limit is reached, the dual simplex path is contained in the path of primitive sets generated by the Scarf algorithm.

AB - H. E. Scarf has recently introduced an algorithm for integer programs based on the combinatorial concept of primitive set. We show that as the decision variables of the integer program become continuous and the integer program reduces to a linear program, the Scarf algorithm converges to a dual simplex algorithm for the limit linear programming problem. This result is robust in the sense that even before the limit is reached, the dual simplex path is contained in the path of primitive sets generated by the Scarf algorithm.

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

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

U2 - 10.1287/moor.10.3.439

DO - 10.1287/moor.10.3.439

M3 - Article

AN - SCOPUS:0022111330

SN - 0364-765X

VL - 10

SP - 439

EP - 449

JO - Mathematics of Operations Research

JF - Mathematics of Operations Research

IS - 3

ER -

SCARF'S PROCEDURE FOR INTEGER PROGRAMMING AND A DUAL SIMPLEX ALGORITHM.

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this