Primal separation algorithms

摘要: Given an integer polyhedron \(P_I \subset \mathbb{R}^n\), point \({\bar x} \in P_I\), and a \(x^* \mathbb{R}^n \setminus the primal separation problem is of finding linear inequality which valid for PI, violated by x*, satisfied at equality \(\bar x\). The plays key role in approach to programming. In this paper we examine complexity several well-known classes inequalities various important combinatorial optimization problems, including knapsack, stable set travelling salesman problems.