Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

BUG: removevredundancy! removes wrong row #52

Open
oyamad opened this issue Jan 17, 2025 · 3 comments · May be fixed by #53
Open

BUG: removevredundancy! removes wrong row #52

oyamad opened this issue Jan 17, 2025 · 3 comments · May be fixed by #53
Labels
bug

Comments

@oyamad
Copy link
Member

oyamad commented Jan 17, 2025

Related to #51

A = [0 1 0; -1 0 0; 0 -1 0; 0 0 -1; 1 0 0]
b = [2, -1, -1, -1, 2]
linset = BitSet(5)
hr = hrep(A, b, linset)
p = polyhedron(hr, LRSLib.Library())
removevredundancy!(p)
p
Polyhedron LRSLib.Polyhedron:
1-element iterator of HyperPlane{Rational{BigInt}, Vector{Rational{BigInt}}}:
 HyperPlane(Rational{BigInt}[1, 0, 0], 2//1),
4-element iterator of HalfSpace{Rational{BigInt}, Vector{Rational{BigInt}}}:
 HalfSpace(Rational{BigInt}[0, 1, 0], 2//1)
 HalfSpace(Rational{BigInt}[-1, 0, 0], -1//1)
 HalfSpace(Rational{BigInt}[0, -1, 0], -1//1)
 HalfSpace(Rational{BigInt}[0, 0, -1], -1//1):
1-element iterator of Vector{Rational{BigInt}}:
 Rational{BigInt}[2, 1, 1],
2-element iterator of Ray{Rational{BigInt}, Vector{Rational{BigInt}}}:
 Ray(Rational{BigInt}[0, 0, 1])
 Ray(Rational{BigInt}[0, 0, 1])

p.ext.R
3×4 Matrix{Rational{BigInt}}:
 1  2  1  1
 0  0  0  1
 0  0  0  1

In

LRSLib.jl/src/polyhedron.jl

Lines 183 to 196 in 22915a1

function Polyhedra.removevredundancy!(p::Polyhedron)
if !p.noredundantgenerator
detectvlinearity!(p)
ext = getext(p)
extm = getextm(p, :AlmostFresh) # FIXME does it need to be fresh ?
redset = redund(extm)
nonred = setdiff(BitSet(1:size(ext.R, 1)), redset)
nonred = collect(setdiff(nonred, ext.linset))
lin = collect(ext.linset)
ext.R = [ext.R[lin,:]; ext.R[nonred,:]]
ext.linset = BitSet(1:length(ext.linset))
p.noredundantgenerator = true
end
end
redund(extm) returns 0-based indices (output from a C program!). That should be modified to be consistent with Julia's 1-based indexing.
@oyamad oyamad added the bug label Jan 17, 2025
@blegat
Copy link
Member

blegat commented Jan 17, 2025

Is that the root cause of #51?

@oyamad
Copy link
Member Author

oyamad commented Jan 17, 2025

Is that the root cause of #51?

No I don't think so. I guess that behavior is a bug/feature of lrslib.

I guess it is the root cause of the error in #50:

nonfulldimensional: Test Failed at /home/runner/.julia/packages/Polyhedra/Dm3Ap/test/utils.jl:74
  Expression: nrays(vr) == nrays(exp)
   Evaluated: 2 == 1

What do you think?

@oyamad
Copy link
Member Author

oyamad commented Jan 18, 2025

If detectvlinearity! is called before removevredundancy!, removevredundancy! does not do anything:

A = [0 1 0; -1 0 0; 0 -1 0; 0 0 -1; 1 0 0]
b = [2, -1, -1, -1, 2]
linset = BitSet(5)
hr = hrep(A, b, linset)
p = polyhedron(hr, LRSLib.Library())
detectvlinearity!(p)
removevredundancy!(p)
p
Polyhedron LRSLib.Polyhedron:
1-element iterator of HyperPlane{Rational{BigInt}, Vector{Rational{BigInt}}}:
 HyperPlane(Rational{BigInt}[1, 0, 0], 2//1),
4-element iterator of HalfSpace{Rational{BigInt}, Vector{Rational{BigInt}}}:
 HalfSpace(Rational{BigInt}[0, 1, 0], 2//1)
 HalfSpace(Rational{BigInt}[-1, 0, 0], -1//1)
 HalfSpace(Rational{BigInt}[0, -1, 0], -1//1)
 HalfSpace(Rational{BigInt}[0, 0, -1], -1//1):
2-element iterator of Vector{Rational{BigInt}}:
 Rational{BigInt}[2, 1, 1]
 Rational{BigInt}[2, 2, 1],
2-element iterator of Ray{Rational{BigInt}, Vector{Rational{BigInt}}}:
 Ray(Rational{BigInt}[0, 0, 1])
 Ray(Rational{BigInt}[0, 0, 1])

p.ext.R
4×4 Matrix{Rational{BigInt}}:
 1  2  1  1
 0  0  0  1
 1  2  2  1
 0  0  0  1

p.noredundantgenerator should not be set true in getext (and possibly also in getine):

LRSLib.jl/src/polyhedron.jl

Lines 70 to 82 in 22915a1

function getext(p::Polyhedron)
if p.ext === nothing
if p.extm !== nothing && checkfreshness(p.extm, :Fresh)
p.ext = p.extm
else
p.ext = LiftedVRepresentation(getinem(p, :Fresh))
p.extm = nothing
p.vlinearitydetected = true
p.noredundantgenerator = true
end
end
return p.ext
end

@oyamad oyamad linked a pull request Jan 18, 2025 that will close this issue
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Fix removevredundancy! JuliaPolyhedra/LRSLib.jl
2 participants
@blegat @oyamad