search

scipopt / scip

SCIP - Solving Constraint Integer Programs
Other
392 stars 63 forks source link

Check which constraints are unsatisfied when the optimization result is infeasible #69

Closed marios-stam closed 10 months ago

marios-stam commented 1 year ago

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 commented 1 year ago

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 commented 10 months ago

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.