Check which constraints are unsatisfied when the optimization result is infeasible

[marios-stam]

Since scipopt/PySCIPOpt#486 was closed but never solved I am making the same issue here.

is there a way to check what conditions are failing when the optimization result is infeasible or get the latest (infeasible) solution from the solver?

[Joao-Dionisio]

Hello @marios-stam, sorry for the late reply.

I still don't have a proper answer for you, so I just paste the SCIP page on conflict analysis: link

Here it says: "Once a node is declared infeasible, SCIP automatically tries to infer a constraint that explains the reason for the infeasibility". Assuming this is true, we could just apply this analysis to the root node. However, as I understand it, we would only get the first constraint that results in an infeasiblity, not all. But this could be worked around with more or less work, I think.

The biggest problem seems to be that some of these things are not present in PySCIPOpt. Sorry for not being able to help.

[ambros-gleixner]

I am not 100% sure what the actual question is. If SCIP returns the status infeasible, then it has proven that the entire problem is infeasible and no solution can exist. So there is no solution to return, also no infeasible solution.

If you would like to know an explanation for the infeasibility, then there are several options. E.g. computing a minimum or minimal set of constraints that are unsatisfiable. SCIP has an extension to do so, see folder applications/MinIISC, but this is not interfaced to PySCIPOpt (and we have no plans to do so).

A manual alternative would be that you formulate an auxiliary MIP yourself that introduces continuous or binary slack variables for each constraint (all or the ones that you suspect to be problematic). And minimize their sum.

With that I would suggest to close the issue, but please reopen if you have further questions or create a new one if you have a more specific question.

[wangyexiang]

Any solution for this problem now?

[Joao-Dionisio]

hey @wangyexiang! SCIP can now compute an IIS (irreducible infeasible set) out of the box. However, it is not yet part of the latest release. If need be, you can compile the master version here from the GitHub repository and look in the iisfinder_greedy.c file, or you can add your own IIS-finder algorithm by editing the iisfinder_xyz.c file. You can compute a IIS directly from the command line with the iis command. You can take a look at the more detailed answer given by the author here: link

Please let me know if this answers your question!