I've just started using the studio, modeling and solving an MIP problem derived from graph colouring. It is solved fast (within seconds) when reaching minimization objective of 0. However, when I change one of the bounds (reduce number of available colours) which causes the objective function be greater than 0, it poses problems and finding the minimum objective takes much longer (for problems with 5000 constraints it takes about a minute, not possible when dealing with 28000 of constraints, 24hours is not enough). A few feasible solutions are found after exploring 30000 nodes but there is no proof of optimality (the last feasible solution with the gap 100%), the solution does not improve and the node exploration continues for hours (the number of nodes to explore keeps increasing). I can only stop by setting a time or node exploration limit. I tried different MIP strategies, as well as probing level 3 and aggressive cuts generation but it didn't help. I did also some tuning, but it returned default as the best strategy. I did profiling and time values are
ROOT • CPLEX MIP Optimization 99%
ROOT • CPLEX MIP Optimization • CPLEX Branch and Bound 93%
The rest is not more than 10% in terms of time and memory.
Are there any other ways to explore and help CPLEX prove optimality? I would be grateful for any suggestions, thank you!