Traditional backbone optical networks can take months to provision a wavelength connection. Future optical networking aims at reducing the provisioning time to a few minutes. In conjunction, new services that allow the customers to dynamically set up and take down their connections is emerging. In this paper, we introduce the problem of optimizing network resources on a reconfigurable optical backbone network that provides such dynamic optical services. The problem grows exponentially in network scale and customer's demands, thus solving the entire problem for a realistic network is impractical. We address this problem by developing a heuristic optimization procedure, combined with problem-size reduction techniques. We show that good results can be achieved using small amounts of computing power and that our solutions are within 11% of a lower bound.