Once you have pre-specified some simplices $S$ that must be included in your triangulation
of the convex polytope $P$, what remains is the problem of triangulating a nonconvex region:
$P \setminus S$.
There are nonconvex polyhedra (in dimension 3) that cannot be triangulated.
And it is an NP-complete problem to decide if a given nonconvex polyhedron can be triangulated,
a 1992 result of Ruppert and Seidel.

If you want to nevertheless hope that your region can be triangulated, you might explore
[geometric bistellar flips][1] to underlie an approach.


  [1]: http://www.voronoi.com/wiki/index.php?title=Bistellar_flips