Empty solution set with a known-feasible MPLP

[gdinh]

Hi! I'm trying to solve the following toy MPLP: maximize i + j + k, subject to:

i + j <= m i + k <= m k + j <= m i, j, k all fall within [0,n].

The parameters m and n are only required to be nonnegative.

Following the documentation here, I've set up the problem as follows:

A=np.array([
   [1,1,0],
   [1,0,1],
   [0,1,1],
   [-1,0,0],
   [0,-1,0],
   [0,0,-1],
   [1,0,0],
   [0,1,0],
   [0,0,1]])
b=np.array([0,0,0,0,0,0,0,0,0]).reshape(-1,1)
c = np.array([-1,-1,-1]).reshape(-1,1)
F = np.array([
 [1, 0],
 [1, 0],
 [1, 0],
 [0, 0],
 [0, 0],
 [0, 0],
 [0, 1],
 [0, 1],
 [0, 1]])
CRa = -np.eye(2)
CRb = np.array([[0],[0]])
H = np.zeros((A.shape[1],F.shape[1]))
prog = MPLP_Program(A, b, c, H, CRa, CRb, F)

This generates the warning:

/Users/grace/projects/mplp/.venv/lib/python3.13/site-packages/ppopt/mplp_program.py:104:
UserWarning: The chebychev ball has either a radius of zero, or the problem is not feasible!
  warnings.warn(warning, UserWarning)

and an attempt to solve it gives an empty solution.

This is clearly incorrect: the LP is definitely feasible, and the objective should be either -3n (if m<=2n) or -3m/2 (otherwise).

Interestingly, removing n entirely works: the following code:

A=np.array([
   [1,1,0],
   [1,0,1],
   [0,1,1],
   [-1,0,0],
   [0,-1,0],
   [0,0,-1]])
b=np.array([0,0,0,0,0,0]).reshape(-1,1)
c = np.array([-1,-1,-1]).reshape(-1,1)
F = np.array([ [1], [1], [1], [0], [0], [0]])
CRa = -np.eye(1)
CRb = np.array([[0]])
H = np.zeros((A.shape[1],F.shape[1]))
prog = MPLP_Program(A, b, c, H, CRa, CRb, F)
prog.process_constraints()
solve_mpqp(prog, mpqp_algorithm.combinatorial)

produces the same "The chebychev ball has either a radius of zero" warning, but does produce the correct solution with the combinatorial solver:

Solution(program=<ppopt.mplp_program.MPLP_Program object at 0x108be4490>, critical_regions=[Critical region with active set [0, 1, 2]
The Omega Constraint indices are [0]
The Lagrange multipliers Constraint indices are []
The Regular Constraint indices are [[0, 1, 2], [3, 4, 5]]
  x(θ) = Aθ + b 
 λ(θ) = Cθ + d 
  Eθ <= f
 A = [[0.5]
 [0.5]
 [0.5]] 
 b = [[0.]
 [0.]
 [0.]] 
 C = [[0.]
 [0.]
 [0.]] 
 d = [[0.8660254]
 [0.8660254]
 [0.8660254]] 
 E = [[ 1]
 [-1]] 
 f = [[inf]
 [ 0.]]])

(The graph and geometric solvers fail with both LPs).

Do you have any insight on what the underlying issue might be?

Thanks!