A new optimization-based approach to kinetic model reduction is presented. The reaction-elimination problem is formulated as a linear integer program which can be solved to guaranteed global optimality. This formulation ensures that the solution to the integer program is the smallest possible reduced model consistent with the user-set tolerances. The method is applied to generate optimally-reduced models for isobaric, adiabatic homogeneous combustion. The computational cost and accuracy of the reduced models are compared to those of the full mechanism. Results are shown for GRImech 3.0 and the Lawrence Livermore n-heptane combustion mechanism. The accuracy of the integer programming approach is compared to existing reaction elimination methods. The method is also applied to generate a library of reduced kinetic models for an adaptive chemistry simulation of a 2-D laminar, partially-premixed methane burner flame. Preliminary results are presented comparing the computational cost of the full GRImech 3.0 chemistry to that of the reduced model library.