12,000

We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK

93%

93% of Lancaster students go into work or further study within six months of graduating

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

« Back

Primal separation algorithms

Research output: Contribution to journalJournal article

Published

<mark>Journal publication date</mark>10/2003
<mark>Journal</mark>4OR: A Quarterly Journal of Operations Research
Issue3
Volume1
Number of pages16
Pages209-224
<mark>Original language</mark>English

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.

Related projects