Constraint using xsum with empty list is not added to model

[kaibir]

Describe the bug I have a model building constraints from a dictionary of type dict[str, list[mip.Var]]. If I now have the case, that one of these lists is empty, the constraint is not added to the model. In such a case when I want to add a constraint 1<= xsum(list) this one should lead to infeasibility, but as it is not added to the model it does not fail.

Using Gurobi to build and solve the model I get the expected infeasibility.

To Reproduce With MIP and CBC

import mip

m = mip.Model("cbc", solver_name="CBC")

variables = {"one": [], "two": []}

for i in [1, 2, 3]:
    var = m.add_var(name=f"var_{i}", var_type=mip.BINARY)
    variables["one"].append(var)

for k, var_list in variables.items():
    m.add_constr(1 <= mip.xsum(var_list), name=f"Constr_{k}")

m.optimize()

Writing this model in a file, Constr_two is missing.

\Problem name: cbc

Minimize
OBJROW: var_1 + var_2 + var_3
Subject To
Constr_one:  var_1 + var_2 + var_3 >= 1
Bounds
 0 <= var_1 <= 1
 0 <= var_2 <= 1
 0 <= var_3 <= 1
Integers
var_1 var_2 var_3 
End

To Reproduce With Gurobi

from gurobipy import Model, GRB, LinExpr, quicksum

m=Model("grb")
grb_variables = {"one": [], "two": []}

for i in [1, 2, 3]:
    var = m.addVar(vtype=GRB.BINARY, name=f"var_{i}", obj=0)
    grb_variables["one"].append(var)

for k, grb_var_list in grb_variables.items():
    m.addConstr(1, GRB.LESS_EQUAL,quicksum(grb_var_list) , f"Constr_{k}")

m.optimize()

Writing model in file.

\ Model grb
\ LP format - for model browsing. Use MPS format to capture full model detail.
Minimize
  var_1 + var_2 + var_3
Subject To
 Constr_one: - var_1 - var_2 - var_3 <= -1
 Constr_two: <= -1
Bounds
Binaries
 var_1 var_2 var_3
End

Expected behavior I would expect a constraint with xsum([]) on lhs or rhs to be handled as something like zero, e.g. a <= xsum([]) should be equivalent to a <= 0.

Or in the descripted case: 1 <= xsum([]) ---> 1 <= 0 should lead to infeasibility.

Desktop (please complete the following information):

• Operating System, version: MacOS BigSur 11.2.3
• Python version: 3.9.0
• Python-MIP version: 1.13.0

Additional context xsum of an empty list returns an "empty" linear expression with const = 0.0, but I am moreover not allowed to add a constraint of form 1 <= 0 because "A boolean (true/false) cannot be used as a constraint."

[sebheger]

After some research, the problem is already stated in model.py, line 334-338

https://github.com/coin-or/python-mip/blob/master/mip/model.py#L334-L338

# TODO: some tests use empty linear constraints, which ideally should not happen
        # if len(lin_expr) == 0:
        #     raise mip.InvalidLinExpr(
        #         "An empty linear expression cannot be used as a constraint."
        #     )

In our applications, we often auto-generate different constraints based on the user's inputs and selections. Might happen, that some of the settings are contradictory, leading to something like 1 <= 0. Gurobipy supports this case well.

Would be fantastic, if mip supports this too.

[sebheger]

Finally,

import mip
m = mip.Model("Crash", solver_name="cbc")
x = m.add_var(name="x")
y = m.add_var(name="y")
m.add_constr(x + y <= 5, name="c1")
m.add_constr(2*x + y <= 6, name="c2")
m.add_constr(mip.xsum([]) <= 1, name="c_crash") # useless constraint
m.objective = mip.maximize(x + 2*y)
m.optimize()
for c in m.constrs:
    print(c.name)

not adding those leads to a crash of underlying CBC.

Thread 0 Crashed:: Dispatch queue: com.apple.main-thread 0 libsystem_kernel.dylib 0x7ff807648112 __pthread_kill + 10 1 libsystem_pthread.dylib 0x7ff80767e233 pthread_kill + 263 2 libsystem_c.dylib 0x7ff8075cad10 abort + 123 3 cbc-c-darwin-x86-64.dylib 0x113ef6f6d Cbc_getRowName + 189

[brmanuel]

I also just encountered this bug. I find the current behaviour of MIP very counter-intuitive. Also I find there are real usecases that rely on the intuitiv behaviour of xsum([]) = 0. E.g. In our application, we have a network flow and want to enforce that flow goes through certain vertices. In this scenario, a node which has no incoming-edges is a symptom of an infeasible input. But the behaviour of MIP leads to a solution where this node has no flow.

[amitainz]

@sebheger any idea when your fix might be deployed? I've just discovered this bug the hard way

[rschwarz]

On top of the behavior described above, there are more troubling cases.

If you add a constraint with 0.0 coefficients, they are added to the solver (CBC) at first, but removed during preprocessing, ie when you solve the model. So the number of constraints before/after solve might be different and accessing, eg shadow price, might then lead to a crash even if printing all constraint names prior to solve does not.

I think that this is solver-dependent, ie it might occur only with CBC.

Our current work-around is to add a wrapper add_constraint method that checks for empty constraints (no variables, or all-zero coefficients) to avoid this. It's also a nice opportunity to check for unique constraint names etc.

[sebheger]

@sebheger any idea when your fix might be deployed? I've just discovered this bug the hard way

I will see what I can do. Actually, my fix does not fully solve the problem. E.g. it will still crash when there is no variable added before. But maybe I will pragmatically release it, as it fixes 95%, which is better than 0%.