On the convex hull of feasible solutions to certain combinatorial problems (Q1198616)

This paper deals with the question: In which cases is the convex hull of a finite union of (unbounded) convex polyhedra closed and hence a convex polyhedron itself? First the authors present three examples of combinatorial problems (the Steiner graphical Travelling Salesman problem, a nonpreemptive single-machine scheduling problem with changeover times and a preemptive single-machine scheduling problem), where the convex hull of the feasible set is not closed, and therefore not a polyhedron. The most essential result: Assume that the convex hull of the union \(C\) of a finite collection \(C_ i\), \(i\in I\), of convex polyhedra contains no line. Then the convex hull of \(C\) is a convex polyhedron if and only if for all extreme rays \(\{x\}+\text{cone}\{d\}\) of \(\text{cl conv } C\), and for all scalars \(\mu\geq 0\), there exists \(\mu'\geq \mu\) such that \(x+\mu'd\in C\) (the corresponding formulation in the paper contains a mistake). This theorem is applied to certain combinatorial problems (Steiner graphical Travelling Salesman problems, Steiner Chinese Postman problems, nonpreemptive scheduling problems with changeover times, preemptive scheduling problems).