Many promising computing substrates, including quantum computers, oscillator-based computers, and p computers solve constrained combinatorial optimization problems by minimizing energy functions called Ising models. Because Ising solvers explore an unconstrained search space, Ising models for many popular optimization problems must include penalty terms to raise the energy of infeasible solutions that would appear optimal otherwise. We observe that for some problems, Ising solvers spend the majority of computation time exploring this invalid state and often never find a feasible solution. We introduce the encoded Ising model (E-I model), an extension to the Ising model that uses a digital encoding circuit to vastly reduce the proportion of time a solver spends exploring invalid states. We present Fuse, a software framework that enables the description of such functions and automatically lowers them to a p-computer. Our formulation reduces the number of iterations to a solution by a factor of $7.2-52000 \mathrm{x}$ and achieves up to $\mathbf{1 0 0. 0 \%}$ higher estimated success probability over baseline formulations.