Persistent contrails have been recognized as a potential threat to the global climate. This paper presents a methodology to optimally reroute aircraft trajectories to avoid the formation of persistent contrails with the use of mixed integer programming (MIP). The main contributions of this paper are the introduction of a more realistic fuel burn model, and the implementation of a quadratic cost function. Existing MIP path planning literature has used a 1-norm approximation of the vehicle acceleration for fuel burn. The fuel burn model created for this paper is based on aircraft data and engine performance software, and the fuel burn cost was approximated with piecewise linear, and quadratic functions for implementation into the MIP. Fuel optimal trajectories for contrail avoidance were created for each cost function and the results were compared. In addition, differences between the linear and quadratic cost were investigated with a pathological obstacle field, and the sensitivity of the trajectory to changes in the planning horizon length and time step size are presented. For a specific scenario, it was found that persistent contrails could be avoided with a 2.76% increase in fuel burn.