While quantum devices rely on interactions between constituent subsystems and with their environment to operate, native interactions alone often fail to deliver targeted performance. Coherent pulsed control provides the ability to tailor effective interactions, known as Hamiltonian engineering. We propose a Hamiltonian engineering method that maximizes desired interactions while mitigating deleterious ones by conducting a pulse sequence search using constrained optimization. The optimization formulation incorporates pulse sequence length and cardinality penalties consistent with linear or integer programming. We apply the general technique to magnetometry with solid state spin ensembles in which inhomogeneous interactions between sensing spins limit coherence. Defining figures of merit for broadband Ramsey magnetometry, we present novel pulse sequences which outperform known techniques for homonuclear spin decoupling in both spin-1/2 and spin-1 systems. When applied to nitrogen vacancy (NV) centers in diamond, this scheme partially preserves the Zeeman interaction while zeroing dipolar coupling between negatively charged NV- centers. Such a scheme is of interest for NV- magnetometers which have reached the NV--NV- coupling limit. We discuss experimental implementation in NV ensembles, as well as applicability of the current approach to more general spin bath decoupling and superconducting qubit control.