Skip to content

[BUG] unbounded problem solved at presolve wrongly reported infeasible #923

@mtanneau

Description

@mtanneau

Describe the bug

A problem found by PSLP to be "infeasible or unbounded" is wrongly reported to be infeasible.

I encountered this issue on v26.02 via the Julia and python APIs.

Steps/Code to reproduce bug

In python:

from cuopt.linear_programming.problem import Problem, CONTINUOUS, MINIMIZE
from cuopt.linear_programming.solver_settings import SolverSettings

problem = Problem(name="unbounded")
x = problem.addVariable(lb=0.0, vtype=CONTINUOUS, name="x")
y = problem.addVariable(lb=0.0, vtype=CONTINUOUS, name="y")

problem.addConstraint(-1*x + 2*y <= 0, name="c1")

problem.setObjective(-1*x - 1*y, sense=MINIMIZE)

settings = SolverSettings()

problem.solve(settings)

problem.Status.name  # 'PrimalInfeasible'

This problem corresponds to the MPS file below:

NAME
ROWS
 N  OBJ
 L  c1
COLUMNS
    x        OBJ       -1
    x        c1        -1
    y        c1        2
    y        OBJ       -1
RHS
    rhs       c1        0
RANGES
BOUNDS
 LO bounds    x        0
 LO bounds    y        0
ENDATA

Here is the log I obtain from cuOpt:

cuOpt version: 26.2.0, git hash: f73da24d, host arch: aarch64, device archs: 75-real,80-real,86-real,90a-real,100f-real,120a-real,120
CPU: Unknown, threads (physical/logical): 1/20, RAM: 107.53 GiB
CUDA 13.1, device: NVIDIA GB10 (ID 0), VRAM: 119.70 GiB
CUDA device UUID: 43bce240-d7d6-65e5-ca7a-e351bab5de7a

Solving a problem with 2 constraints, 4 variables (0 integers), and 4 nonzeros
Problem scaling:
Objective coefficents range:          [1e+00, 1e+00]
Constraint matrix coefficients range: [1e+00, 2e+00]
Constraint rhs / bounds range:        [0e+00, 0e+00]
Variable bounds range:                [0e+00, 0e+00]

Using PSLP presolver
PSLP declares problem as infeasible or unbounded.
PSLP Presolved problem: 0 constraints, 0 variables, 0 non-zeros

Note that PSLP correctly reports the problem as "infeasible or unbounded", but cuOpt returns only the "infeasible" part.

Expected behavior

The problem is unbounded: (x, y) = (0, 0) is feasible, and the ray (x, y) = (1, 0) is feasible and has negative objective value. cuOpt should return that the problem is unbounded / dual infeasible.

Environment details (please complete the following information):

  • Environment location: DGX Spark with GB10
  • Method of cuOpt install: in a python virtual environment using uv.

Additional context

cuOpt does not have a "dual infeasible" termination status, which would be appropriate here.

Metadata

Metadata

Assignees

Labels

awaiting responseThis expects a response from maintainer or contributor depending on who requested in last comment.bugSomething isn't working

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions