Minimal constraints needed to prove the contradiction
Answered
I need the minimal constraints needed to prove the contradiction.
The problem is binary but maybe its easier to explain like this:
a > 20
a > 40
a < 60
asking the model a = 70 should return a < 60 as the only constraint needed to prove invalid.
My idea:
Adding an extra var to the constraints as fallback
.AddTerm(1.0, model.AddVar(0.0, 1.0, 0.0, GRB.BINARY, "Extra var"))
.AddConstr(constraint, GRB.EQUAL, 1.0,
And then SetObjective(Maximize all fallback vars)
did not work
It this even possible with Gurobi?
How to set the objectives for this problem? (in .net syntax if possible)
(Then I can enumerate each possible var a to scan for the minimal constraints needed.
Enumerating if var is impossible is done by scenarios)
-
Hi Saška,
You could try an approach like you suggesting, perhaps using indicator constraints would be best, but are you aware that Gurobi offers this functionality already?
The knowledge base article How do I determine why my model is infeasible? will be useful for you.- Riley
0 -
Even with
model.Parameters.Presolve = 0
model.Parameters.IISMethod = 1
model.ComputeIIS()
and writing the .ilp to file
The result is not the smallest irreducible subsystem. For example I get 8 constraints instead of 5.I found:
https://support.gurobi.com/hc/en-us/articles/360041448572-How-does-Gurobi-compute-the-IIS-for-infeasible-models-
Note that there are different approaches to compute an IIS, and, since Gurobi does not compute the IIS with minimal cardinality, there may exist an irreducible infeasible system smaller than what Gurobi reports.And there not any updates after Gurobi 9.5 that can find the smallest IIS?
I don't know how indicators constraints is going to help me with this.
0 -
Hi Saška,
Currently the latest version of Gurobi is v10, and it also cannot guarantee finding a minimum IIS. I'm not aware of any solvers which do guarantee the minimum IIS.
The suggestion of the indicator constraints was proposing as a method of "turning constraints on or off". This can be used to naively implement a brute force approach to calculate a minimum IIS like the example below. Don't forget the IIS includes variable bounds, which is why the variable in the example (which are essentially binary variables) are defined as integer and bounds are provided as constraints.
import gurobipy as gp
from gurobipy import GRB
import itertools
import numpy as np
m = gp.Model()
x = m.addVar(vtype=GRB.INTEGER)
y = m.addVar(vtype=GRB.INTEGER)
z = m.addVar(vtype=GRB.INTEGER)
potential_constraints = [
x >= 0,
x <= 1,
y >= 0,
y <= 1,
z >= 0,
z <= 1,
x + y >= 2,
x + z >= 2,
z + y >= 2,
x + y + z <= 2,
x + 2*z <= 3,
x + y + z >= 0,
]
# an auxiliary variable for each constraint
aux = m.addMVar(len(potential_constraints), vtype=GRB.BINARY)
for a, c in zip(aux.tolist(),potential_constraints):
m.addConstr((a == 1) >> (c)) # indicator constraints
m.update()
# loop through all subsets of constraints, from smaller subsets to larger
for arr in sorted(itertools.product([0, 1], repeat=len(potential_constraints)), key=lambda x:sum(x)):
m2 = m.copy()
m2.params.OutputFlag = 0
m2.addConstr(aux == np.array(arr)) # "turn the constraints on" that correspond to 1s in arr
m2.optimize()
if m2.Status == GRB.INFEASIBLE:
print("found minimal", np.nonzero(arr)[0])
breakYou could perhaps use this approach in a smarter way. For example if Gurobi computes an IIS of size 8, then start with looking for an IIS of size 7 by ensuring sum(arr) == 7. If you don't find one of size 7 then you know the IIS of size 8 is the smallest. If you find one of size 7 then repeat for sum(arr) == 6.
This approach is only practical for toy models though. You will find the time taken for the above approach will grow exponentially as the model size grows. I think the approach you first suggested will work for finding the maximum set of feasible constraints, but not the minimum set of constraints in an IIS. If we could formulate the problem as a MILP then we would, but solving it is much harder than this.
- Riley
0 -
Removing constraints but staying infeasible, this won't result in minimal IIS.
Trying all combinations outside Gurobi is indeed a slow choice. Speed impact 2^n.Is there any chance that this will be implemented and optimized in the near future?
It would then be an unique selling point.0 -
Thank you for the feedback, Saska. One thing I could potentially add is that right now we deliver a small IIS with high probability, due to the nature of how things are implemented. That is, if you have say 2 disjoint IIS, one of size 10 and the other 1,000, it is ~100 times more likely you will see the one of size 10 at the end. However, no deterministic guarantees can be made.
Hope this helps.0
Please sign in to leave a comment.
Comments
5 comments