メインコンテンツへスキップ

IISConstrForce=1 not guaranteeing IISConstr=1 in computeIIS output

回答済み
Hendrik Bierlee
編集済み
  • First Comment
  • First Question

Dear reader,

I'm observing that a constraint with IISConstrForce=1 ends up with IISConstr=0 after computeIIS(), which seems to contradict the attribute docs stating that forced constraints are included in the IIS (even if it may lead to a reducible "IIS").

Minimal example on Gurobi 13.0.1, Python 3.13.2, Linux:

import gurobipy as gp

m = gp.Model()
m.setParam('OutputFlag', 0)

BV0 = m.addVar(vtype=gp.GRB.BINARY, name='BV0')
BV1 = m.addVar(vtype=gp.GRB.BINARY, name='BV1')
p = m.addVar(vtype=gp.GRB.BINARY, name='p')

R0 = m.addConstr(BV0 + p <= 1, name='R0')
R1 = m.addConstr(-p + BV1 <= 0, name='R1')
R2 = m.addConstr(p + BV1 <= 1, name='R2')
R3 = m.addConstr(BV0 >= 1, name='R3')
R4 = m.addConstr(BV1 >= 1, name='R4')

m.update()

# Force R0, R1, R2 into IIS
R0.IISConstrForce = 1
R1.IISConstrForce = 1
R2.IISConstrForce = 1

m.update()
m.computeIIS()

for c in m.getConstrs():
   print(f'{c.ConstrName}: IISConstr={c.IISConstr}, IISConstrForce={c.IISConstrForce}')

Output:

R0: IISConstr=1, IISConstrForce=1
R1: IISConstr=1, IISConstrForce=1
R2: IISConstr=0, IISConstrForce=1   <-- unexpected
R3: IISConstr=1, IISConstrForce=-1
R4: IISConstr=1, IISConstrForce=-1

As you can see, IISConstrForce does not imply IISConstr for R2, which is unexpected to me.

The context for this model may be of interest, I'm encoding a constraint problem p <= 0, (p >= 1) AND (p <= 0) (note it has two constraints) and then using Gurobi's IIS to find an Minimal Unsatisfiable Subset (MUS, an equivalent concept to IIS). The 2nd constraint takes two Gurobi constraints to encode, so we introduce two binary variables to imply/"reify" both constraints BV0 -> p <= 0, BV1 -> (p >= 1), BV1 -> (p <= 0), then compute the IIS only on BV0, BV1, to ensure each "group" of Gurobi constraints is enforced all together or not at all. Now, the IIS of R0, R1, R3, R4 falsely indicates that both groups are in the MUS, but actually only the 2nd constraint is, which would be clear if the IIS was R0, R1, R2, R4 as expected. I'm curious if there are better ways to do it as well (apart from the optimization that p <= 0 does not need to be reified, and that we should use indicator constraints rather than this big-M approach).

Kind regards,

Hendrik ‘Henk’ Bierlee

関連

1

コメント

5件のコメント

日付 投票
  • Riley Clement
    • Gurobi Staff

    HI Hendrik,

    I agree, the omission of R2 from the IIS this looks like a bug to me.  I will open up a ticket through the Gurobi Help Center to address this, so please keep an eye out for a corresponding email.

    Now, the IIS of R0, R1, R3, R4 falsely indicates that both groups are in the MUS

    I might be missing something but this looks like a valid IIS to me.  R3 and R4 force BV0 and BV1 to be 1, then R0 forces p to be 0, but R1 forces p to be 1, which is inconsistent.

    indicator constraints rather than this big-M

    No real need for indicator constraints here.  Your “big M" values are in fact tiny Ms :). There is a discussion on this topic here on or.stackexchange which you might find useful.

    - Riley

     

    0
  • Hendrik Bierlee
    編集済み
    • First Comment
    • First Question

    Hi Riley,

    Thanks for the reply and creating a ticket.

    Indeed, if you ignore the force attributes, then `R0, R1, R3, R4` is an IIS. If your IIS is forced to contain `R0, R1, R3`, you will not get this IIS. This is important for my use-case, which is to create an IIS/MUS for a “high-level” constraint model in CPMpy (https://github.com/CPMpy/cpmpy, and the IIS-MUS PR with too much discussion on this here: https://github.com/CPMpy/cpmpy/pull/880). High-level constraints are comparable to General constraints, but since Gurobi does not support all of them, we need to represent them with multiple Gurobi constraints.

    The example high-level CPMpy model has two high-level constraints, but requires three Gurobi constraints.

    C0: p <= 0
C1: (p >= 1) AND (p <= 0)

    Note that `C1` is a conjunction, which will require two Gurobi linear constraints, namely `p≥1, p≤0`, to represent. We'd get this Gurobi model:

    C0_0: p <= 0
C1_0: p >= 1
C1_1: p <= 0

    We have other constraint types, e.g. `AllDifferent(x, y, z)`, which may require thousands of Gurobi constraints to represent, even if we use Gurobi's General constraints. We usually call these “groups”, with each group of Gurobi constraints representing a single high-level constraint. The goal is to extract an IIS of these high-level constraints, in this case, there's only one “high-level IIS”, namely `{C1}`. However, there are two IIS's on Gurobi's model namely `{C1_0, C1_1}` and `{C0_0, C1_0}`. If you get the 2nd one, I believe there is no way to map it to `{C1}`.

    We fix this a similar way to other solvers (e.g. SAT solvers), by creating this model instead:

    C0_0: BV0 -> p <= 0
C1_0: BV1 -> p >= 1
C1_1: BV1 -> p <= 0
R0: BV0 >= 1
R1: BV1 >= 1

    Essentially, `C1` is in the high-level IIS only if its whole group `R1` is in the Gurobi IIS. The first three constraints are hard constraints (forced to be in the IIS), while `R0, R1` are soft. Now, Gurobi has to enforce the whole group for `R1` to be in the IIS, meaning there is now again only one ISS `{R1}` which maps to high-level IIS `{C1}`.

    I hope that makes it more clear. We are thinking about alternative approaches (e.g. which would require fewer indicator constraints). As I said, `C0` is represented by a singleton group, so we can do with the same effect:

    C1_0: BV1 -> p >= 1
C1_1: BV1 -> p <= 0
R0: p <= 0
R1: BV1 >= 1

    If there are other ideas, please let me know! :)

    Also thanks for the extra resources on big-M and indicators, I didn't know there were cases of “implied linear constraints” where you'd want to use big-M instead of indicators, as I thought Gurobi would be able to make better decisions than me when to reformulate as big-M and when to keep as indicator. It's a good idea to check the pre-solved model.

    Kind regards,

    Hendrik ‘Henk’ Bierlee

    Post-doc @ KU Leuven

    0
  • Hendrik Bierlee
    • First Comment
    • First Question

    The bug has been resolved in 13.0.2, my thanks to Riley for the quick fix.

    0
  • Riley Clement
    • Gurobi Staff

    Hi Hendrik,

    I think you're on the right track.  I'm not sure I see a motivation to use less indicator constraints.  The only think I would do is make fix the binaries by the lower bounds.  It might make the analysis simpler.

    m = gp.Model()

BV0 = m.addVar(vtype="B", name='BV0', lb=1)
BV1 = m.addVar(vtype="B", name='BV1', lb=1)
p = m.addVar(vtype="B", name='p')

R0 = m.addConstr((BV0 == 1) >> (p <= 0), name="R0")
R1 = m.addConstr((BV1 == 1) >> (p >= 1), name="R1")
R2 = m.addConstr((BV1 == 1) >> (p <= 0), name="R2")

m.update()

bin_map = {}
for gencon in m.getGenConstrs():
    if gencon.GenConstrType == gp.GRB.GENCONSTR_INDICATOR:
        gencon.IISGenConstrForce=1
        binvar, *_ = m.getGenConstrIndicator(gencon)
        if binvar not in bin_map:
            bin_map[binvar] = []
        bin_map[binvar].append(gencon)

m.computeIIS()

cons = []

for v in (v for v in m.getVars() if v.VType == "B"):
    if v in bin_map and v.IISLB==1:
        cons.extend(bin_map[v])

print("high level IS:", [con.GenConstrName for con in cons])

    Cheers,
    Riley

    0
  • Hendrik Bierlee
    • First Comment
    • First Question

    Thanks Riley, that's a great idea. We'll definitely try that out.

    0

サインインしてコメントを残してください。

お探しのものを見つけられませんでしたか？

新規投稿