Finding Irreducible Infeasible Subsets for Linear Optimization Problems? #3020
Replies: 2 comments 5 replies
-
|
Hello @lperron and @Mizux, I see that issue #3019 has been marked as closed, that the issue was added to milestone v9.2, and that milestone v9.2 is 100% complete. I assume that this means that the feature I'm asking about already exists. Is that correct? |
Beta Was this translation helpful? Give feedback.
-
|
No, it was moved to discussion as a feature request. |
Beta Was this translation helpful? Give feedback.
-
|
OK, thanks for the clarification. |
Beta Was this translation helpful? Give feedback.
-
|
I am also trying to solve a Mixed Integer Programming problem using SCIP solver (using .Net wrapper for Google OR) and would appreciate if we can get an option to identify which constraints are causing infeasibilities. |
Beta Was this translation helpful? Give feedback.
-
|
@GhayourAli, people at SCIP are currently working on adding an IIS feature. It might be released by the time SCIP 10 comes out, which shouldn't take tooo long. |
Beta Was this translation helpful? Give feedback.
-
|
@Joao-Dionisio Am i right, that there is no official branch available allowing to track (and get a grasp of) that work? |
Beta Was this translation helpful? Give feedback.
-
|
@sschnug Yes, this is currently on the private research repo of SCIP. |
Beta Was this translation helpful? Give feedback.
-
What language and solver does this apply to?
Python
Describe the problem you are trying to solve.
Suppose you have an instance of
ortools.linear_solver.pywraplp.Solverwhich you've populated with decision variables and constraints, and you've found that the optimization model is unexpectedly infeasible. The natural question is: "Why is it infeasible? Which constraints cause it to be infeasible?" In other words, can we identify an irreducible infeasible subset of constraints?This question is analogous to Issue #973. However, I'm asking about the linear optimization solver, not the CP-SAT solver.
Describe the solution you'd like
I'm interested in a method of the solver object that would return an irreducible infeasible subset of constraints for the infeasible optimization problem. Specifically, it should return the indices of the constraints belonging to the irreducible infeasible subset. The method should be independent of the solver available (provided the solver is sufficiently powerful to correctly ascertain the feasibility/infeasibility of the problem).
Describe alternatives you've considered
I've coded up my own solution in python.
Additional context
It's not clear to me that this method does not already exist. However, if it does exist, I have not yet found it. Does it, in fact, already exist?
Beta Was this translation helpful? Give feedback.
All reactions