[wenc]

Makes sense. MIPs are good for getting to rigorous optimality, but right now they have limits to their scaling (every binary variable and every inequality constraint you add increases the complexity of the problem).

Your experiences track those of the folks working in airline fare pricing (e.g. ITA software, now Google Flights).

If you are willing to give up strict optimality (or small MIP gap), any number of greedy and / or embarassingly parallel algorithms will likely get you reasonable (maybe not optimal, but good enough) results in a shorter amount of time. Plus, you can do much more massive scale out.