Currently, helicopter operations according to Instrument Flight Rules (IFR) consist of high-altitude trajectories where the probability of collision with terrain is assumed to be very low. In such high altitudes, the risk of icing has to be considered, additionally, the flight time is unnecessarily long. Therefore, this paper elaborates on an optimization approach to find helicopter trajectories minimizing both flight time and height above terrain. To ensure safe operations, an iso-probability surface is calculated using collision probabilities, representing a surface above which the probability of collision with terrain is smaller than a chosen safety level. The optimization problem is solved using Mixed Integer Linear Programming (MILP). To evaluate the resulting trajectories the time until collision is evaluated for each waypoint, using a time-to-go approach based on Monte-Carlo simulations. The optimization with MILP yields feasible trajectories fulfilling a chosen safety level. Although the approach is computationally expensive, it serves as a basis for further research on these kinds of trajectory optimization applications.