Why is there not a feasible solution for a MIP?

Question

Is there a way to see why a solver (OR-Tools, CPLEX, Gurobi) cannot find a feasible solution when solving a MIP?

By that I mean, is there a possibility to show at which constraint and exact indices the solver stoped?

Example:

• $x_i$ a binary variable

• $a_j$ a parameter

• $ i \in I:|I| =3$

• constraint: $\sum \limits_i x_i > a_j \ \ \forall j$

no solution found because for index $j=2$ not able to fulfill this constraint:

---> $a_2= 100$ and $\sum \limits_i x_i =3$

Answer 1

Yes - such a question can be answered by looking at the irreducible inconsistent subsystem (IIS).

From the Gurobi documentation:

An IIS is a subset of the constraints and variable bounds with the following properties: the subsystem represented by the IIS is infeasible, and if any of the constraints or bounds of the IIS is removed, the subsystem becomes feasible.

Answer 2

There exist various reasons why a solver could not find the optimal solution. You must always check why a solver terminated. Typical reasons are:

1. optimal solution was found
2. termination criteria was reached, e.g. time limit or a limit on the optimality gap
3. solver proved that problem is infeasible

Popular solvers such as cplex/gurobi can report their status through a getStatus function. When a solver terminates due to some termination criteria, you can end up in any of the following situations:

1. Some solution was found. The optimality gap gives you insight into the quality of this solution. However, there might exist better solutions, i.e. it is unknown whether this solution is optimal or not.
2. No solution was found. There might however exist feasible solutions. This status is usually indicated as 'undefined/unknown', as it is unknown whether the solution space is empty or not.

Frequently, the solver is quickly able to determine feasibility of a problem. This can already happen in the pre-solve status. Modern solvers can search for a Minimal irreducible inconsistent subsystem. This is a subset of constraints which collectively render your problem infeasible. Deleting any constraint of this set would render the subproblem defined by these constraints feasible. Note that there may exist multiple causes of infeasibility in your model, i.e. multiple different IISs.

If you want to know more about this subject, I recommend the following papers: - Finding the minimum weight IIS cover of an infeasible system of linear inequalities by Parker and Ryan, 1996 - Minimal Infeasible Subsystems and Benders cuts by Fischetti, Salvagnin, Zanette, 2008

Finding a minimum IIS, i.e. the smallest IIS is an NP-hard problem. Therefore, many solvers use heuristics to find a minimal, but not necessarily minimum IIS. I my experience, trying to find an IIS using CPLEX or Gurobi is a game of hit and miss: finding an IIS might take quite some time, especially in large models. Also, the IIS returned can be big, so interpreting the source of infeasibility might not be trivial. In practice I often use the following approach:

1. Compute a feasible solution to your problem using for instance a simple heuristic.
2. Fix all variables in your model to their corresponding values in the solution found in the previous step.
3. Solve the model and search for an IIS. Gurobi: Model.computeIIS(). Cplex: Cplex.getIIS.
4. Since all variables are fixed, the IIS returned by the solvers is typically very small.

Answer 3

As an alternative to finding irreducible infeasible subsets (smaller subproblems that are still infeasible) would be to introduce slack variables into your constraints. Then you would replace your original objective with the minimization of these (non-negative) slack variables, penalizing their use. This way, you can also get some insight into which constraints are difficult to satisfy (simultaneously).

Answer 4

Another possibility not mentioned in the other answers is that an optimal solution exists, but the solver is not able to find it, or perhaps confirm its optimality, due to numerical difficulties, which might in turn be due to poor scaling or ill-conditioning of the original problem. Double precision floating point computation can be a cruel mistress.