I think you will want to write your own optimizer that understands the discrete variable constraints (maybe doing enumeration like you said). find_MAP had a very specific goal in the context of PyMC, as an old way to initialize the NUTS sampler.
Optimization is not the real goal of PyMC so I don’t think there is anything off the shelve you can use instead. PyMC is very happy to provide you the model logp/gradients for your own optimizer though! Hope that helps