You should recheck the variable bounds and check the equation formulations for the given constraint.

It may be that your formulation is "bad", in the sense that it leads to a weak relaxation. I recommend looking at a good textbook on mathematical programming, like this one:

https://www.wiley.com/en-gb/Model+Building+in+Mathematical+Programming%2C+5th+Edition-p-9781118443330

Can you perhaps start with the optimisation-like problem of finding a feasible solution? If you have some easy constraints, you may keep them, and penalise only those that are hard to comply with. If you find a feasible solution, then you have a point from which you can start solving the original problem.

You can relax some of the (difficult) constraints using Lagrangian Relaxation, which means sending your constraints to objective function with Lagrangian multipliers. Then you are able to exam the resultant solutions for Lagrangian multipliers to see which multipliers violate the complementary slackness conditions. Those are the constraints that cannot be satisfied by CPLEX. This approach is very effective when you dealing with large-scale problems for either Linear Programs or Mixed-Integer Problems. For binary integer problems, there are logical constraints (cuts or lifts can be developed) based on the problem-specific structures.

Hi Vineet,

The suggestion in the IBM Support page is in the following:

"CPLEX's default settings for integer programming emphasize finding an optimal solution. In cases where finding a good feasible solution quickly is most important, consider setting the mipemphasis parameter to 1 if the defaults don't find a good feasible solution quickly enough. . While this may increase the time required to find an optimal solution, it typically enables CPLEX to find more feasible solutions during the course of the optimization. This setting causes CPLEX to search nodes further down in the tree, where most of the good feasible solutions lie.

Also, CPLEX offers a feasibility pump heuristic that you can apply at the start of the MIP optimization. By default CPLEX does not use this heuristic because it is relatively expensive, and cheaper default heuristics often do well enough. But, if the default settings don't yield good feasible solutions quickly enough, consider turning on the feasibility pump heuristic parameter to invoke this heuristic.

Also, CPLEX's FeasOpt feature can help find good feasible solutions quickly when the MIP optimization (even with some of the non default settings mentioned above) struggles to do so. However, because FeasOpt solves a related problem with an objective designed to find feasible solution, the solution it finds typically may not have a very good objective function value relative to the original MIP. Therefore, you will probably want to follow the FeasOpt run with a regular MIP optimization with settings designed to improve upon existing feasible solutions. Such settings including setting the MIP emphasis to 4 to find hidden feasible solutions, heavy application of the RINs heuristic by setting the RINs heuristic frequency parameter to a modest number of nodes (e.g. 20-100), or switching to CPLEX's solution polishing feature early in the MIP optimization.

Finally, if your application absolutely requires that you have a solution after a limited amount of time, consider using your own heuristic procedure to construct an initial feasible solution. Then, pass that solution, or specify its objective value as a cutoff, to CPLEX at the start of the MIP optimization. Set an appropriate time limit along with the previously discussed parameter settings, and optimize the MIP. CPLEX will either find a better solution before the time limit, or you can use your original solution. In either case, your application has a feasible solution to the MIP."

I hope it is helpful for you.

Best regards.

First of all, check the feasibility of your model. If the model is right and you cannot solve a medium or large scale test, I suggest using Benders Decomposition and Lagrangian Relaxation reformulations to reduce the complexity of your model. Then, you are able to achieve an optimum solution but may be not feasible.

Read relevant works. I have used these techniques in a number of my published works.

I think, by now the problem would be solved. But if not, the following steps can be tried :

A

First try relaxing all the integers to continuous variables (from 0 to 1, assuming you have binary variables). If it converges, then possibly MIP should converge too.

B :

(1). Fix the decision variables (to known feasible values so that the problem will get at least converged).

(2). Once converged, check if the upper/lower bounds have bigger gaps? (a sign of weak formulation). Reduce the range.

(3). Same goes to the bounds as in above (2) , if BigM is being used.

Maybe, there exist some conflicts between the constraints in the MIP model.

https://community.ibm.com/community/user/datascience/discussion/root-relaxation-time-is-long-for-mip-problem