BUG: Linprog reports failure despite success convergence, given a problem involving semi-continuous variables

[boschmic]

Describe your issue.

Given the following problem involving a semi-continuous variable, linprog(method='highs') reports a failure despite successful convergence to a solution.

The problem is the following:

maximize x
s.t
    x <= 0.5
    x is semi-continuous, bounds=[1;5]

Linprog reports the correct solution: x=[0.] and slack=[0.5], but the success flag is False and there is an error message.

Reproducing Code Example

import numpy as np
from scipy.optimize import linprog

c = np.array([-1.])
A_ub = np.array([[1.]])
b_ub = np.array([0.5])
A_eq = np.zeros((0, 1), dtype=float)
b_eq = np.array([], dtype=float)
bounds = np.array([[1., 5.]])
integrality = np.array([2])

ans = linprog(
    c,
    A_ub,
    b_ub,
    A_eq,
    b_eq,
    bounds,
    integrality=integrality,
    method='highs'
)
print(f'ans.success: {ans.success}')
print(f'ans.x: {ans.x}')
print(f'ans.slack: {ans.slack}')
print(f'ans.message: {ans.message}')

Error message

ans.success: False
ans.x: [0.]
ans.slack: [0.5]
ans.message: The solution does not satisfy the constraints within the required tolerance of 3.16E-04, yet no errors were raised and there is no certificate of infeasibility or unboundedness. Check whether the slack and constraint residuals are acceptable; if not, consider enabling presolve, adjusting the tolerance option(s), and/or using a different method. Please consider submitting a bug report.

SciPy/NumPy/Python version and system information

1.10.1 1.24.2 sys.version_info(major=3, minor=10, micro=6, releaselevel='final', serial=0)
{
  "Compilers": {
    "c": {
      "name": "gcc",
      "linker": "ld.bfd",
      "version": "10.2.1",
      "commands": "cc"
    },
    "cython": {
      "name": "cython",
      "linker": "cython",
      "version": "0.29.33",
      "commands": "cython"
    },
    "c++": {
      "name": "gcc",
      "linker": "ld.bfd",
      "version": "10.2.1",
      "commands": "c++"
    },
    "fortran": {
      "name": "gcc",
      "linker": "ld.bfd",
      "version": "10.2.1",
      "commands": "gfortran"
    },
    "pythran": {
      "version": "0.12.1",
      "include directory": "/tmp/pip-build-env-xob7rtip/overlay/lib/python3.10/site-packages/pythran"
    }
  },
  "Machine Information": {
    "host": {
      "cpu": "x86_64",
      "family": "x86_64",
      "endian": "little",
      "system": "linux"
    },
    "build": {
      "cpu": "x86_64",
      "family": "x86_64",
      "endian": "little",
      "system": "linux"
    },
    "cross-compiled": false
  },
  "Build Dependencies": {
    "blas": {
      "name": "OpenBLAS",
      "found": true,
      "version": "0.3.18",
      "detection method": "cmake",
      "include directory": "unknown",
      "lib directory": "unknown",
      "openblas configuration": "unknown",
      "pc file directory": "unknown"
    },
    "lapack": {
      "name": "OpenBLAS",
      "found": true,
      "version": "0.3.18",
      "detection method": "cmake",
      "include directory": "unknown",
      "lib directory": "unknown",
      "openblas configuration": "unknown",
      "pc file directory": "unknown"
    }
  },
  "Python Information": {
    "path": "/opt/python/cp310-cp310/bin/python",
    "version": "3.10"
  }
}

[boschmic]

I looked into the implementation of linprog. The bounds checking in _check_results doesn't make sense for semi-continuous variables:

scipy/scipy/optimize/_linprog_util.py

Line 1491 in 4a6f2d1

invalid_bounds = (x < bounds[:, 0] - tol).any() or (x > bounds[:, 1] + tol).any()

Semi-continuous variables can always take value 0 (same for semi-integer variables), regardless of the bounds. At least that's what the documentation of linprog is saying for the integrality flag:

2 : Semi-continuous variable; decision variable must be within bounds or take value 0.
3 : Semi-integer variable; decision variable must be an integer within bounds or take value 0.

[mdhaber]

Thanks. Those checks were probably written before the semi-continuous bounds were added. We'll adjust that.