Infeasibility Issue in Python-MIP When Incrementing an Integer Constant

[uuuutsu]

Describe the bug I'm encountering an issue with the Python-MIP library where incrementing a certain variable (large_sufficient_ub) causes the model to become infeasible. While new to Mixed-Integer Programming, I am unable to find a logical explanation for it.

To Reproduce Here's a simplified version of the code to reproduce the issue:

import mip

model = mip.Model()

x = model.add_var(var_type=mip.INTEGER, lb=0, ub=mip.INT_MAX)
y = model.add_var(var_type=mip.INTEGER, lb=0, ub=mip.INT_MAX)

large_sufficient_ub = 999_999

# Express: abs(x - y) >= 1
binary_flag = model.add_var(var_type=mip.BINARY)
model.add_constr(x - y - (binary_flag * large_sufficient_ub) <= -1)
model.add_constr((x - y + ((1 - binary_flag) * large_sufficient_ub)) >= 1)

model.objective = mip.xsum([x, y])

model.optimize()
print(model.status)

Increasing large_sufficient_ub by one results in OptimizationStatus.INFEASIBLE. This issue only arises when the objective function mip.xsum([x, y]) is set. If this line is omitted, the model converges correctly regardless of the large_sufficient_ub value.

Expected behavior I expected the model to find an optimal solution with any reasonable value of large_sufficient_ub, regardless of the presence of the objective function.

Desktop (please complete the following information):

• Operating System, version: macOS 14.1.2 (23B92)
• Python version: 3.11.5
• Python-MIP version: 1.15.0

[christian2022]

Using "big M" formulations without tight upper bounds is in general a bad idea as it will lead to numerical issues sooner or later. Would recommend to use

#express abs(x - y)
abs_pos = model.add_var(lb=0)
abs_neg = model.add_var(lb=0)
# divide expression into positive and negative part
model += (x - y == abs_pos - abs_neg)
# only one part may be non zero
model.add_sos([abs_pos, abs_neg], 1)
# now abs(.) = abs_pos + abs_neg
model += (abs_pos + abs_neg >= 1)

[uuuutsu]

Thanks a lot! It fixed everything and is very insightful. Happy New Year!