The formation of persistent contrails has been recognized as a potential threat to the global climate. This paper presents a methodology to optimally reroute aircraft trajectories to mitigate the formation of persistent contrails with the use of mixed integer linear programming (MILP). The path planning algorithm was developed so that flights through areas conducive to persistent contrail formation are assessed a penalty which can be adjusted by the user before the flight. The tradeoff between persistent contrail formation and increased fuel burn was analyzed for flights of different contrail formation penalty weighting. It was found that fuel burn increased 1.48% when approximately 50% of persistent contrails were avoided and 6.19% when 100% of persistent contrails were avoided.