This message appears if (i) the Dual Simplex method (or the Default method, which is Dual Simplex) is selected for the Algorithm to Use option in the Task Pane Engine tab General group, and (ii) you entered an inappropriate value in the Integer Cutoff option in the Integer group (i.e. a value larger than the optimal objective if maximizing, or smaller than the optimal objective if minimizing).

This message appears only if the LP relaxation of the mixed-integer problem yields an objective worse than the value entered for the Integer Cutoff option.  On mixed-integer programming problems, if the objective of the relaxation is better than the Integer Cutoff value, then the Branch & Bound method will proceed with the search for integer solutions, cutting off the search on any node of the B&B tree whose objective is worse than the Integer Cutoff.  So, if the Integer Cutoff value does not “cut off” the solution of the relaxation, but it does “cut off” the search that would have yielded the optimal integer solution, you will instead receive the message “Solver could not find a feasible solution.”

Also bear in mind that this message will appear only if the Dual Simplex method is used; if the Primal Simplex or Newton Barrier method is used, and the Integer Cutoff value is inappropriate, you will always receive the message “Solver could not find a feasible solution.”  Hence, you should take care to ensure that the value you enter for the Integer Cutoff option is no better than the objective of a known integer solution to the current problem.