Skip to content

Unexpected behaviour of removehredundancy #350

@ma-b

Description

@ma-b

I'm getting some unexpected errors when removing redundancy from a polyhedron as opposed to removing it from its H-representation.
Here is an example (using Julia v1.11.3, Polyhedra v0.8.1, and GLPK v1.2.1):

A = [1 1; 1 1; -1 0; 0 -1]
b = [1, 1, 0, 0]
h = hrep(A, b, BitSet([1,2]))
lib = DefaultLibrary{Rational{Int}}(GLPK.Optimizer)
p = polyhedron(h, lib)

This produces the following (the H-representation of p contains a duplicate hyperplane):

Polyhedron DefaultPolyhedron{Rational{Int64}, MixedMatHRep{Rational{Int64}, Matrix{Rational{Int64}}}, MixedMatVRep{Rational{Int64}, Matrix{Rational{Int64}}}}:
2-element iterator of HyperPlane{Rational{Int64}, Vector{Rational{Int64}}}:
 HyperPlane(Rational{Int64}[1, 1], 1//1)
 HyperPlane(Rational{Int64}[1, 1], 1//1),
2-element iterator of HalfSpace{Rational{Int64}, Vector{Rational{Int64}}}:
 HalfSpace(Rational{Int64}[-1, 0], 0//1)
 HalfSpace(Rational{Int64}[0, -1], 0//1)

When I do

removehredundancy!(p)

all works fine and the duplicate hyperplane is removed (probably in the process of implicitly calling detecthlinearity!(p)). But when I just do

removehredundancy(h, GLPK.Optimizer)

then I get ERROR: The index MOI.VariableIndex(1) is invalid. Note that an index becomes invalid after it has been deleted.

(The same error occurs if I add a redundant halfspace, so that there actually is some redundancy in the halfspace part of the H-representation.)

Interestingly, if I lift p to one dimension higher and add a (non-redundant) hyperplane at index 1, as in the following code, then the variable index in the error message above becomes MOI.VariableIndex(2).

A2 = [0 0 1; A zeros(Int, size(A,1))]
b2 = [0; b]
h2 = hrep(A2, b2, BitSet([1,2,3]))
p2 = polyhedron(h2, lib)
removehredundancy(h2, GLPK.Optimizer)  # fails
removehredundancy!(p2)  # works fine

Could this have something to do with a dual variable for the redundant hyperplane that is being deleted too early?

Thanks!

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions