The optimization problem isn't, but neither are the optimization problems for a bunch of other NP-complete problems. The decision problem (where you specify an upper bound cost) is indeed NP-complete.