Scarf's Procedure for Integer Programming and a Dual Simplex Algorithm | Zendy

Philip M. White | Zendy; Andrew Caplin | Zendy; Ludo Van der Heyden | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Scarf's Procedure for Integer Programming and a Dual Simplex Algorithm

Author(s) -

Philip M. White,

Andrew Caplin,

Ludo Van der Heyden

Publication year - 1985

Publication title -

mathematics of operations research

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.619

H-Index - 83

eISSN - 1526-5471

pISSN - 0364-765X

DOI - 10.1287/moor.10.3.439

Subject(s) - simplex algorithm , mathematics , integer programming , linear programming , simplex , path (computing) , integer (computer science) , mathematical optimization , limit (mathematics) , branch and cut , criss cross algorithm , algorithm , linear fractional programming , set (abstract data type) , dual (grammatical number) , branch and price , combinatorics , computer science , art , mathematical analysis , literature , programming language

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research