Home > Research > Publications & Outputs > Primal separation algorithms
View graph of relations

Primal separation algorithms

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published

Standard

Primal separation algorithms. / Letchford, A. N.; Lodi, A.
In: 4OR: A Quarterly Journal of Operations Research, Vol. 1, No. 3, 10.2003, p. 209-224.

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Harvard

Letchford, AN & Lodi, A 2003, 'Primal separation algorithms', 4OR: A Quarterly Journal of Operations Research, vol. 1, no. 3, pp. 209-224. https://doi.org/10.1007/s10288-003-0012-8

APA

Letchford, A. N., & Lodi, A. (2003). Primal separation algorithms. 4OR: A Quarterly Journal of Operations Research, 1(3), 209-224. https://doi.org/10.1007/s10288-003-0012-8

Vancouver

Letchford AN, Lodi A. Primal separation algorithms. 4OR: A Quarterly Journal of Operations Research. 2003 Oct;1(3):209-224. doi: 10.1007/s10288-003-0012-8

Author

Letchford, A. N. ; Lodi, A. / Primal separation algorithms. In: 4OR: A Quarterly Journal of Operations Research. 2003 ; Vol. 1, No. 3. pp. 209-224.

Bibtex

@article{305b56ac13bb4fba97875dd40f78293f,
title = "Primal separation algorithms",
abstract = "Given an integer polyhedron P ⊂ R^n, an integer point x in P, and a point x* in R^n \ P, the primal separation problem is the problem of finding a linear inequality which is valid for P, violated by x*, and satisfied at equality by x. The primal separation problem plays a key role in the primal approach to integer programming. In this paper we examine the complexity of primal separation for several well known classes of inequalities for various important combinatorial optimization problems, including the knapsack, stable set and travelling salesman problems.",
keywords = "integer programming, cutting planes, separation, primal algorithms, knapsack problem, stable set problem, travelling salesman problem",
author = "Letchford, {A. N.} and A. Lodi",
year = "2003",
month = oct,
doi = "10.1007/s10288-003-0012-8",
language = "English",
volume = "1",
pages = "209--224",
journal = "4OR: A Quarterly Journal of Operations Research",
issn = "1619-4500",
publisher = "Springer Verlag",
number = "3",

}

RIS

TY - JOUR

T1 - Primal separation algorithms

AU - Letchford, A. N.

AU - Lodi, A.

PY - 2003/10

Y1 - 2003/10

N2 - Given an integer polyhedron P ⊂ R^n, an integer point x in P, and a point x* in R^n \ P, the primal separation problem is the problem of finding a linear inequality which is valid for P, violated by x*, and satisfied at equality by x. The primal separation problem plays a key role in the primal approach to integer programming. In this paper we examine the complexity of primal separation for several well known classes of inequalities for various important combinatorial optimization problems, including the knapsack, stable set and travelling salesman problems.

AB - Given an integer polyhedron P ⊂ R^n, an integer point x in P, and a point x* in R^n \ P, the primal separation problem is the problem of finding a linear inequality which is valid for P, violated by x*, and satisfied at equality by x. The primal separation problem plays a key role in the primal approach to integer programming. In this paper we examine the complexity of primal separation for several well known classes of inequalities for various important combinatorial optimization problems, including the knapsack, stable set and travelling salesman problems.

KW - integer programming

KW - cutting planes

KW - separation

KW - primal algorithms

KW - knapsack problem

KW - stable set problem

KW - travelling salesman problem

U2 - 10.1007/s10288-003-0012-8

DO - 10.1007/s10288-003-0012-8

M3 - Journal article

VL - 1

SP - 209

EP - 224

JO - 4OR: A Quarterly Journal of Operations Research

JF - 4OR: A Quarterly Journal of Operations Research

SN - 1619-4500

IS - 3

ER -