This paper presents a discretize-then-relax method to construct convex/concave bounds for the solutions of a wide class of parametric nonlinear ODEs. The algorithm builds upon Taylor model methods recently developed for verified solution of parametric ODEs. To enable the propagation of convex/concave state bounds, a new type of Taylor model is introduced, in which convex/concave bounds for the remainder term are computed in addition to the usual interval bounds. At each time step, a two-phase procedure is applied: a priori convex/concave bounds that are valid over the entire time step are calculated in the first phase; then, pointwise-in-time convex/concave bounds at the end of the time step are obtained in the second phase. This algorithm is implemented in an object-oriented manner using templates and operator overloading. It is demonstrated and compared to other available approaches on a selection of problems from the literature. (C) 2011 Elsevier Ltd. All rights reserved.