In search and rescue operations, optimization-based decision support systems can assist search mission coordinators in planning searches with higher probabilities of success, potentially resulting in more lives saved. However, traditional model-and-solve techniques, such as integer programming, are not easily applicable in maritime searches where there is a need to conduct simulations to compute the value of the objective function. In this paper, we show how we can still use mathematical programming to propose maritime search and rescue plans, even when simulations are used. In addition, we take into account operational constraints such as airspace deconfliction for security reasons. Our model, implemented for a suitable solver using a surrogate to estimate search simulation results on scenarios with two helicopters, proved flexible and fast—we implemented operational constraints in a problem-specific model, solved by a general solver, which provided quality solutions in a short time frame.