Abstract Over-constrained temporal problems are commonly encountered while operating autonomous and decision support systems. An intelligent system must learn a human’s preference over a problem in order to generate preferred resolutions that minimize perturbation. We present the Best-first Conflict-Directed Relaxation (BCDR) algorithm for enumerating the best continuous relaxation for an over-constrained conditional temporal problem with controllable choices. BCDR reformulates such a problem by making its temporal constraints relaxable and solves the problem using a conflictdirected approach. It extends the Conflict-Directed A* (CD-A*) algorithm to conditional temporal problems, by first generalizing the conflict learning process to include all discrete variable assignments and continuous temporal constraints, and then by guiding the forward search away from known infeasible regions using conflict resolution. When evaluated empirically on a range of coordinated car sharing network problems, BCDR demonstrates a substantial improvement in performance and solution quality compared to previous conflict-directed approaches.