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.
I believe one could make such an example from the [Schönhardt polyhedron][1],
by insisting on the inclusion of three tetrahedra ($S$) external to that polyhedron as 
part of a triangulation of the convex hull ($P$) of two twisted triangles in parallel planes,
so that $P \setminus S$ is the un-tetrahedralizable Schönhardt polyhedron
(see below).
And it is an NP-complete problem to decide if a given nonconvex polyhedron can be triangulated,
a 1992 result of Ruppert and Seidel.

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;![alt text][2]<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<sub>([Image from Wikipedia][1])</sub>

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


  [1]: http://en.wikipedia.org/wiki/Sch%C3%B6nhardt_polyhedron
  [2]: https://upload.wikimedia.org/wikipedia/commons/thumb/f/f3/Sch%C3%B6nhardt_polyhedron.svg/220px-Sch%C3%B6nhardt_polyhedron.svg.png
  [3]: http://www.voronoi.com/wiki/index.php?title=Bistellar_flips