LP for feasibility problem results in primal infeasibility at even moderate problem size

[AnanthHari]

OR-Tools Version: v9.6
Language: Python 3.9.16
Solver: GLOP
OS: macOS 13.4

Hi, I was looking for simplex implementations for linear programming and I came across OR-Tools. I'm trying to see how the runtime/no. of iterations scales as problem size increases for simple feasibility LP problems, i.e., objective is a constant.

In the following program, for all odd values of n such that n >= 3, the problem is feasible with the following solution: x[0] = 0 and x[i] = 1, for all other i.

To reproduce the result, name the following program to be glop.py and run it as python glop.py 2197 (the full run script is attached):

import sys
from ortools.linear_solver.pywraplp import Solver, MPSolverParameters

n = int(sys.argv[1])
solver = Solver('GLOP', Solver.GLOP_LINEAR_PROGRAMMING)

solver.EnableOutput()

x = [solver.NumVar(0, 1, f'x[{i}]') for i in range(n)]

solver.Add(1-x[0] == 1)
solver.Add(x[1] == 1)
solver.Add(x[2] == 1)
for i in range(3,n-1,2):
    solver.Add(-x[i] + x[i-1] + x[i-2] <= 1)
    solver.Add(-x[i+1] + x[i-1] + x[i-2] <= 1)

solver.Maximize(1)

# ----------- Method 1: Default parameters ----------- #
status = solver.Solve()

if status == solver.OPTIMAL or status == solver.FEASIBLE or status == solver.UNBOUNDED:
    print('Solution: Objective value =', solver.Objective().Value())
else:
    print('The problem does not have an optimal solution.')

print('Problem solved in %d iterations' % solver.iterations())

model = solver.ExportModelAsMpsFormat(False, True)
print(model, file=open(f'model_{n}.lp', 'w'))

We expect the solver to return a trivial feasible (and therefore, optimal) solution. The expected behavior is observed for every valid odd number n less than 2197, using the GLOP solver without dual simplex invoked.

At n = 2197, the solver returns a PRIMAL_INFEASIBLE status, with the status of the "unscaled solution" being IMPRECISE. This is with the default parameters.

The following table outlines the fate of running the script with various options.

• tolerance=1e-2 implies setting solution_feasibility_tolerance, primal_feasibility_tolerance, and dual_feasibility_tolerance to 1e-2.
• PRESOLVE_OFF implies resetting MPSolverParameters.PRESOLVE.

S.No.	tolerance=1e-2	PRESOLVE_OFF	use_dual_simplex:True	Comment(s)
1	No	No	No	Default params. Infeasible for n=2197
2	Yes	No	No	Infeasible for n=2197
3	No	Yes	No	Infeasible for n=2077
4	No	No	Yes	Hangs for n=2001 needing SIGKILL
5	Yes	No	Yes	Infeasible for n=2001

The full run script, all LP models, and all log files are attached. Simply uncomment the appropriate option in the script before running.
glop_infeasibility.tar.gz