Skip to content

[BUG] Rotated second order cone detection assumes symmetrized inputs #1435

@mlubin

Description

@mlubin

This is a bug in the C++-level detection of rotated second order cones, but it's easy to demonstrate in python:

from cuopt.linear_programming.problem import Problem, MAXIMIZE, CONTINUOUS

INF = float("inf")

def solve(label, build_constraint):
    p = Problem("rsoc")
    t  = p.addVariable(lb=0.5, ub=0.5, vtype=CONTINUOUS, name="t")
    u  = p.addVariable(lb=1.0, ub=1.0, vtype=CONTINUOUS, name="u")
    v0 = p.addVariable(lb=-INF, ub=INF, vtype=CONTINUOUS, name="v0")
    v1 = p.addVariable(lb=-INF, ub=INF, vtype=CONTINUOUS, name="v1")
    p.addConstraint(t + u + v0 + v1 <= 100.0, name="slack")
    p.addConstraint(build_constraint(t, u, v0, v1), name="rsoc")
    p.setObjective(v0 + v1, sense=MAXIMIZE)
    sol = p.solve()
    lhs = (v0.getValue()**2 + v1.getValue()**2
           - 2 * t.getValue() * u.getValue())
    print(f"\n[{label}]")
    print(f"  Status:    {sol.get_termination_reason()}")
    print(f"  Objective: {sol.get_primal_objective():.10g}   "
          f"(expected sqrt(2) ~ 1.41421)")
    print(f"  v0 = {v0.getValue():.6g},  v1 = {v1.getValue():.6g}")
    print(f"  v0^2 + v1^2 - 2*t*u = {lhs:.6g}   (should be <= 0)")


solve("A: v0*v0 + v1*v1 - 2*t*u <= 0  (natural idiom)",
      lambda t, u, v0, v1: v0*v0 + v1*v1 - 2*t*u <= 0.0)

solve("B: v0*v0 + v1*v1 - t*u - u*t <= 0  (manually symmetrized)",
      lambda t, u, v0, v1: v0*v0 + v1*v1 - t*u - u*t <= 0.0)

Yields:

[A: v0*v0 + v1*v1 - 2*t*u <= 0  (natural idiom)]
  Status:    Optimal
  Objective: 0.0001276033875   (expected sqrt(2) ~ 1.41421)
  v0 = 6.38017e-05,  v1 = 6.38017e-05
  v0^2 + v1^2 - 2*t*u = -1   (should be <= 0)
[B: v0*v0 + v1*v1 - t*u - u*t <= 0  (manually symmetrized)]
  Status:    Optimal
  Objective: 1.414213562   (expected sqrt(2) ~ 1.41421)
  v0 = 0.707107,  v1 = 0.707107
  v0^2 + v1^2 - 2*t*u = -4.58143e-10   (should be <= 0)

The C API is similarly affected (confirmed) and potentially the MPS reader too (not confirmed).

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
No fields configured for issues without a type.

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions