A method of encoding a sequence of video images is described. The method receives the sequence of video images. The method iteratively examines different encoding solutions for the sequence of video images to identify an encoding solution that optimizes image quality while meeting a target bit rate and satisfying a set of constraints regarding flow of encoded data through an input buffer of a hypothetical reference decoder for decoding the encoded video sequence. The iterative examining includes, for each encoding solution, determining whether the hypothetical reference decoder underflows while processing the encoding solution for any set of images within the video sequence.