Editing videos calls for satisfying two fundamentally different kinds of requirements simultaneously. Editors often need to meet hard constraints, such as hitting a precise target duration, while also considering semantic objectives, such as preferring engaging content. These two requirements lend themselves to different computational tools, and combining them is non-trivial. Using video editing as a case study, we present a hybrid approach that combines using LLMs to provide semantically relevant labels for video clips with using mixed-integer linear programming to enforce hard constraints and select content. Our approach guarantees millisecond-precise output durations while optimizing for user-specified semantic objectives, such as informativity and topic relevance. Feedback from editors indicates that our tool supports interactive exploration across several video editing goals, including creating interview rough cuts and shortening edited videos for sharing across different platforms.