On the convex hull of feasible solutions to certain combinatorial problems
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).
- scientific article; zbMATH DE number 3365044 (Why is no real title available?)
- Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
- On the convex hull of the union of certain polyhedra
- On the facial structure of scheduling polyhedra
- On the Polyhedrality of the Convex Hull of the Feasible Set of an Integer Program
- Single-Machine Scheduling Polyhedra with Precedence Constraints
- Structure of a simple scheduling polyhedron
- The traveling salesman problem on a graph and some related integer polyhedra
This page was built for publication: On the convex hull of feasible solutions to certain combinatorial problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1198616)
