I you have optimality requirements (aka from the feasible solutions find the absolutely best) then optimization is the way to go
I you have optimality requirements (aka from the feasible solutions find the absolutely best) then optimization is the way to go
My advice is if you are on the clock, just use whatever works best out of the box.
Now if you plan to solve this problem thousands of times daily, then I would invest in writing custom callbacks in CPLEX to inject feasible solutions during the search since its heuristics are suffering in your problem case.
Also very permissive license with unlimited deployment and cores!
But your intuition is right, this is roughly how IP optimizers work. They relax the problem to a continuous one (aka convert the {0,1} to [0,1]), solve this super easy linear problem and try to find integral solutions close this linear optimum. If not, start branching on the integers and solve smaller and smaller linear problems until you prove optimality.