Hacktoberfest 2026: the issues maintainers tagged for October, open and beginner-friendly. Browse Hacktoberfest issues

Incorrect handling of constraints with identical variables causing infeasible models

Open
#396 0 comments 1 reaction 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
3/5
Estimated time
1-2 days
Newbie friendliness
55/100
Issue type
Bug
Clarity
Mostly clear
Activity status
Stale
Tech stack
python
Domain
tooling

Research direction

Start with the LinExpr constructor in mip/entities.py and the Var operator overrides linked in the issue, then reproduce the examples involving x + x, x - x, and x == x. Compare the resulting constraints and optimization status with the expected combined coefficients; done means identical-variable expressions no longer produce incorrect or infeasible models.

Written by the indexing model from the issue text.

Description

Describe the bug
There is a bug where the LinExpr constructor incorrectly handles expressions involving identical variables, leading to wrong/infeasible models. This happens when a constraint contains variables that are the same object, causing the coefficients to be overwritten during expression construction by the dict constructor itself.

Importantly, all Var.__add__, Var.__sub__, Var.__rsub__, Var.__eq__, Var.__le__, and Var.__ge__ can easily trigger this issue when both operands are Var.

>>> m = Model(); x = m.add_var('x')
>>> m += x - x >= 0; print(m.constrs[0])
constr(0): -1.0 x >= -0.0

For example, the substraction override calls the constructor with [1, -1]. If the variables are the same object, the dict(zip()) constructor will void the first coefficient!

Why are the variables the same object? This can easily happen in problems where you have to specify any variable as a fixed point, for example order-based problems. As soon as you build constraints in a loop and you forget to skip the case where the variables are the same, you have a faulty constraint.

For example, where I first encountered the bug:
Partial Ordering Graph Coloring uses a constraint like this: https://arxiv.org/pdf/1706.10191 (p. 6). Constraint (21) has exactly this situation where, if you are not careful and v == q, python-mip breaks.

Additional context
The issue arises after a change made in commit https://github.com/coin-or/python-mip/commit/f9e2046, which removed some variable cleanup by avoiding the self.add_var call. This cleanup was crucial to avoid the coefficients being overwritten when dealing with duplicate variables in a constraint.

To Reproduce
Minimal working example:

from mip import *
m = Model()
x = m.add_var()
m += x >= 1
m += x - x >= 0
m.optimize()
Welcome to the CBC MILP Solver 
Version: devel 
Build Date: Nov  8 2024
Starting solution of the Linear programming problem using Dual Simplex

Coin0507I Presolve determined that the problem was infeasible with tolerance of 1e-08
Clp3003W Analysis indicates model infeasible or unbounded
Clp0001I Primal infeasible - objective value 0
Clp0032I PrimalInfeasible objective 0 - 1 iterations time 0.002
<OptimizationStatus.INFEASIBLE: 1>

These will result in the model being reported as infeasible, even though the constraints are valid. This is because the second constraint got parsed as -x >= 0.

Basically, it can be triggered manually by constructing the expression, or with the faulty Var overrides, and any variable type:

'Python 3.13.0 (main, Oct  8 2024, 00:00:00) [GCC 14.2.1 20240912 (Red Hat 14.2.1-3)] on linux'
>>> from mip import *
>>> m = Model(); x = m.add_var('x')
>>> m += x + x <= 1
>>> m += x - x <= 1
>>> m += x == x
>>> m += x <= x
>>> m += x >= x
>>> list(map(str, m.constrs))
['constr(0): +1.0 x <= 1.0', 'constr(1): -1.0 x <= 1.0', 'constr(2): -1.0 x = -0.0', 'constr(3): -1.0 x <= -0.0', 'constr(4): -1.0 x >= -0.0']

Also, I have read #163, and it seems like the speed improvements did not come without side effects.

Python-MIP version: Since https://github.com/coin-or/python-mip/commit/f9e2046 (Sep. 2021) (>=1.14.0) (via git-bisect).

Dominant language
Linear Programming
Stars
601
Forks
108
PR merge metrics
No merged PRs in 30d

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from coin-or/python-mip

All issues in coin-or/python-mip

Similar issues

More DevTools issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.