Polynomial traffic demand polytope partitioning

We consider the problem of partitioning of a traffic demand polytope using a hyper-plane. The polytope is divided into parts, and different routing schemes are applied while dealing with traffic matrices from different parts of the polytope. Different demands cannot share resources, and reservation vectors on opposite sides of the hyperplane have to be identical. We provide a polynomial time algorithm solving the presented problem when a traffic demand polytope is defined as a convex hull of a known set of traffic demand matrices.