wiki:SagePolyhedralGeometry

Roadmap for Optimization and Polyhedral Geometry softwares interactions in Sage

(around Sage, (PyQ)Normaliz, SCIP, e-antic, Polymake, and others)

This page is intended to describe the current tickets related to optimization and polyhedral geometry.

Future & Current Projects

  • Extend the usage of Normaliz in Sage
  • Extend the polyhedral geometry component of Sage
  • Polyhedral arrangements and complexes

Tickets

Here are some practical search lists of tickets:

Tickets from the Sage Days 84 March 2017

Tickets from the IMA Coding Sprint - April 2018

Tickets with keyword polytope

Current tickets of the Geometry component

Meta-tickets

There are already a few meta-tickets related to this topic:

  • #22420: Polyhedron: new features and known bugs
  • #20875: Polytopes, lattice (integer) point counting / enumeration, and their applications
  • #20302: Improvements to MixedIntegerLinearProgram?, its backends, and InteractiveLinearProgram?
  • #20877: Piecewise functions, polyhedral complexes, piecewise functions of several variables, periodic piecewise functions
  • #22710: Polymake
  • #22827: Expose all normaliz features
  • #27063: Transition of combinatorial computations of Polyhedron to Combinatorial Type
  • #29799: Vector spaces and algebras of polyhedra

To do

  • Thematic Tutorial for Py(Q)Normaliz installation/Usage in Sage
  • Increase documentation in Py(Q)Normaliz
  • #21984: Deprecate the opacity argument for plot3d and use alpha
  • Make Pynormaliz a feature in the PythonModule? framework
  • #27736: Polymake: Turn polymake applications into objects with directories
  • #27728: Add Perles and irrational polytopes to library
  • Euclidean automorphisms group of polytopes in Normaliz
  • The integration of automorphisms into SageMath
  • The remaining main computation goal, Hilbert and Ehrhart series turned out to be a very difficult task since it would require the precise construction of a fundamental domain of the group action.
  • Once interactive H-representation in normaliz is possible ("redund-like") make it work with the "A & B" operation in Sage!

Current Tickets

The following tickets have been created and should be worked on:

  • #20877: PolyhedralComplex: preliminary implementation
  • #25122: Construct RationalPolyhedralFan from possibly overlapping cones
  • #27728: Add Perles and irrational polytopes to library
  • #28230: Thematic Tutorial on algebraic polytopes in Sage using Normaliz
  • #29169: Maximal and critical angles for cones
  • #29811: PolyhedronFace?: Add methods to compute cones of feasible directions andaffine tangent cones
  • #30015: Schlegel projection breaks convexity
  • #30040: Improve face iterator for simple/simplicial polytopes
  • #30198: Polyhedra in vector spaces without distinguished basis
  • #30319: wrong intersection of polytopes
  • #30438: Improve face iterator for almost simple/simplicial polytopes
  • #30445: Merge duplications in edges, ridges and f-vector of combinatorial polyhedron
  • #30458: Outsource some functions in bit_vector_operations.cc
  • #30524: Remove maybe_newfaces in combinatorial polyhedron
  • #30528: Remove basic access to bitsets in combinatorial polyhedron
  • #30529: Use reference instead of pointer to simplify code
  • #30531: Polyhedron_normaliz._triangulate_normaliz should not use NmzResult? directly
  • #30549: Remove all the bitset access from cython files in combinatorial polyhedron
  • Task #27063: Transition of combinatorial computations of Polyhedron to combinatorial type:
  • Task #28893: Parallel f-vector for polyhedra:
  • Task #29191: Polytopal constructions for combinatorial polyhedra:
    • #30469: Face as polyhedron, quotien by face as polyhedron
  • Task #29199: Set up polyhedra with both Vrep and Hrep:
  • Obtain the meet of facets and the join of vertices:
    • #29683: "look up" a face in the face lattice of a polyhedron
  • Task #29842: Run a more stable test suite on polyhedra:

Short Sage Release Notes

Sage 9.2

Improvements:

  • #28894: Parallel f-vector for polyhedra: Move most important attributes of FaceIterator to a structure
  • #28982: Use CombinatorialPolyhedron to obtain faces lattice of polyhedra
  • #29196: Make Ehrhart series related function cached
  • #29325: precomputed double description for permutahedron
  • #29565: Transition of combinatorial computations of Polyhedron to combinatorial type: Migrate neighborly to combinatorial polyhedron
  • #29566: CombinatorialPolyhedron?: Store incidence matrix on initialization
  • #29568: Initialize polyhedra with backend cdd with both Vrepresentation and Hrepresentation
  • #29654: Improve face generator of polyhedra by exposing FaceIterator class
  • #29661: Some optimizations for method regions of hyperplane arrangements
  • #29676: Make a nogil version of the most important methods of FaceIterator?
  • #29679: Cleanup of 28757
  • #29681: Small improvements for FaceIterator_base
  • #29800: Make categories of Polyhedra parent more precise
  • #29836: normaliz backend isn't ready for generators
  • #29837: Improvement for incidence matrix of polyhedra
  • #29840: Document choice of base ring of incidence matrix and adjacency matrices
  • #29841: Improve obtaining combinatorial polyhedron
  • #29843: Set up linear transformation with precomputed data if injective
  • #29898: vertex facet graph for trivial polyhedra fails
  • #29899: Two bugs with dilation
  • #29904: Broken double description of hypercube
  • #30146: #29843 introduces a bug in Polyhedron().linear_transformation
  • #30204: Prepare Polyhedra parent factory to handle more general ambient spaces
  • #30248: Normaliz backend is broken with double description input
  • #30292: is_pyramid returns a wrong certificate
  • #30293: bug in lawrence_extension
  • #30321: Improve tikz picture methods of Polyhedron
  • #30428: More direct check for simple/simplicial polytopes
  • #30429: Standardize intersection in combinatorial_polyhedron/bit_vector_operations.cc
  • #30435: Improve count vertices of combinatorial faces
  • #30443: Simplify setting and getting "edges" of edges, ridges, incidences in CombinatorialPolyhedron

New features:

  • #29506: Backend for Hyperplane Arrangements
  • #29838: Implement slack matrix for polyhedra
  • #29843: Set up polyhedra with both Vrep and Hrep: linear transformation
  • #29569: Set up polyhedra with both Vrep and Hrep: Obtain polar with both Vrep and Hrep (if backend supports it)
  • #29583: Set up polyhedra with both Vrep and Hrep: product
  • #30440: Pyramid for combinatorial polyhedra

Testing Framework:

  • #29903: Run many test suite examples for polyhedra
  • #29905: test basic properties of polyhedra
  • #29906: Run tests for an_affine_basis
  • #29907: Run test suite to check method dilation
  • #29908: Test method is_combinatorially_isomorphic
  • #29918: Run test suite for gale transform

Finished Task:

Sage 9.1

Improvements:

  • #19803: difference of behavior in polyhedra with different backends
  • #28626: Compute graph of polyhedron with CombinatorialPolyhedron
  • #28757: CombinatorialPolyhedron: Remove empty folder
  • #28873: Implement ambient volume of polyhedron with normaliz
  • #28866: doctest killed due to abort in geometry/polyhedron/base.py
  • #28880: Prepare setting up polyhedron from both Vrep and Hrep for different backends
  • #29057: make stack method of Polyhedron use fraction_field
  • #29073: gale_transform does not work for RDF
  • #29074: Better error message for polar of non-full dimensional polyhedra
  • #29078: Move is_simple and is_simplicial to CombinatorialPolyhedron
  • #29116: affine_basis does not always work when used with orthogonal or orthonormal
  • #29125: is_inscribed depends on order of vertices
  • #29155: Full-dimensional face of Polyhedron should have equations
  • #29176: Bug in Voronoi Diagram
  • #29186: Add simplicity and simpliciality to polyhedra
  • #29188: Move vertex facet graph to combinatorial polyhedron
  • #29189: Migrate is_lawrence_polytope and is_pyramid to combinatorial polyhedron
  • #29198: Set up hypercube with both Vrep and Hrep (if backend supports it)
  • #29200: Dilation of polyhedron with both Vrep and Hrep (if backend supports it)
  • #29223: Pickle cached value of volume and f-vector
  • #29229: Improvements for is_reflexive for polyhedra over the integers
  • #29242: CombinatorialPolyhedron: bit_repr_ -> bit_rep_
  • #29323: Set up cross polytope with both Vrep and Hrep (if backend supports it)
  • #29324: Translation with both Vrep and Hrep
  • #29326: Improvements for projection into affine hull
  • #29382: Compute the centroid of a polytope
  • #29455: Bug in incidence_matrix of CombinatorialPolyhedron?

New features:

  • #17215: Normal cone of faces of polyhedra
  • #26363: Polyhedron_normaliz.save
  • #26623: Constructions for common polyhedral cones
  • #27086: Simplicity and simpliciality for CombinatorialPolyhedron?
  • #28247: Parametrize the cube/hypercube functions in the library of polytopes
  • #28413: Add .h_star_vector to compact rational polytopes
  • #28646: A face generator for polyhedra (using CombinatorialPolyhedron?)
  • #28724: Polyhedron._acted_upon_ should handle left multiplication by matrices, linear transformations
  • #28960: Initialize CombinatorialPolyhedron?? from incidence matrix of cone or lattice polytope
  • #29065: Inverse function for gale_transform
  • #29085: CombinatorialPolyhedron?: Expose is_bounded
  • #29112: Implement incidence matrix for combinatorial polyhedron
  • #29117: Implement a maximal chain for combinatorial polyhedron
  • #29127: Implement an affine basis for polytopes
  • #29382: Compute the centroid of a polytope
  • #29190: polar/dual for combinatorial polyhedra
  • #29224: flag_f_vector for polyhedra

Sage 9.0

Improvements:

  • #17339: Polyhedron class mistreats empty inputs
  • #18861: Three apparently useless polyhedron methods
  • #25183: Bug in the associahedron object
  • #26922: Wrong f-vector for unbounded polyhedra
  • #28311: Random failure in combinatorial_polyhedron/base.pyx
  • #28463: .neighbors() error in polyhedron.representation
  • #28464: .is_inscribed() makes a bad assumption in Polyhedron
  • #28506: Direct sum of polyhedron is broken, so is minkowski difference and face truncation
  • #28625: Let CombinatorialPolyhedron? handle f_vector of polyhedra
  • #28643: Speed up incidence matrix of polyhedra
  • #28650: Fix the dimension of PolyhedronFace?
  • #28654: A Bug in the backend field
  • #28655: Fix typos in the method 'is_combinatorially_isomorphic' of Polyhedron
  • #28662: Missing edges when visualizing Polyhedra with threejs
  • #28668: fix the base_ring of face_split
  • #28678: Bug in CombinatorialPolyhedron? of empty Lattice polytope
  • #28725: fix lawrence_extension and lawrence_polytope for backend field
  • #28741: Lattice Polytopes: compute_facets does not check dimension when setting is_reflexive
  • #28770: Polyhedra coercion of base rings fails for number fields
  • #28828: Attributes of polyhedra are exposed
  • #28850: Polar of polytopes does not check if polytope is full-dimensional
  • #28851: Polar of integer polytopes does not respect backend
  • #28872: Wrong usage of normaliz/pynormaliz makes sage crash hard
  • #28876: Polyhedron: Let affine hull fully respect backend

New features:

Sage 8.9

The polyhedron folder is now py3 compatible with all optional packages!

Improvements:

  • #24877: bug in polyhedron over RDF
  • #27798: Add backend option to associahedron and flow polytope
  • #27926: Preserve backend for polytopal constructions
  • #27987: CombinatorialPolyhedron?? improve initialization, remove bug for unbounded polyhedra
  • #27993: NormalFan??: issue with inner and outer normal vectors
  • #28235: py3: polyhedron folder with optional packages
  • #28240: Move rational methods of the backend normaliz to the _QQ class
  • #28430: Polyhedron: Preserve backend for barycentric subdivision

New features:

  • #25091: Expose some normaliz features
  • #25097: Algebraic polyhedra with QNormaliz / e-antic (in the normaliz backend)
  • #26887: Implement the class CombinatorialPolyhedron?
  • #27689: Implement is_pyramid, is_bipyramid, is_prism for polytopes
  • #27760: Generalized Permutohedra and type H4 4-uniform polytopes
  • #27973: Implement wedge over a face of Polyhedron
  • #27974: Implement facets method for Polyhedron
  • #28256: Add .is_self_dual method for polytopes

Sage 8.8

Improvements:

  • #20181: number_field_elements_from_algebraics should create embedded number field elements Sage-devel discussion
  • #21161: repr of NumberFields? (the parents) should indicate its embedding if there is one
  • #22704: Create a variant of the polymake interface using polymake's callable library (polymake::Main) via JuPyMake?
  • #26340: polytopes.snub_cube should be set up with base_ring=QQ
  • #27071: Make indices of V_representation of faces of polyhedron accessible through a new method
  • #27533: Improve Polyhedron.is_simple()
  • #27673: AttributeError?? of Polyhedron.volume()
  • #27682: upgrade normaliz to 3.7.1, pynormaliz to 2.1 and package e-antic
  • #27700: Fix is_simplicial for non-full-dimensional polytopes
  • #27709: The attribute _vector of H and V representation is exposed
  • #27716: Refactor backend_normaliz
  • #27722: Remove old deprecation warning of Minkowski -> minkowski
  • #27731: upgrade normaliz to 3.7.2, pynormaliz to 2.5
  • #27840: Bug in the ppl backend of polyhedron

New methods for polyhedron:

  • #27534: Implement Lawrence extension for polytopes

Sage 8.7

Improvements:

  • #18214: Bug in volume computation of polyhedron

New methods for polyhedron:

  • #22574: Add .change_ring() method for polyhedra

Sage 8.4

Improvements:

  • #22701: Setting up a Polyhedron from both Vrep and Hrep
  • #24837: Improve the output of repr_pretty for Polyhedron
  • #25090: Upgrade pynormaliz to 1.15 or higher (2.0?)
  • #26077: Document and doctest constructing polyhedra over number fields
  • #26365: Library of polytopes should allow specifying backend=... (follow-up)

New methods for polyhedron

  • #22575: Add .change_backend() method for polyhedra
  • #24847: Implement stacking onto a face of a polyhedron

Sage 8.3

Improvements:

  • #22572: Add a thematic tutorial on the polyhedron class
  • #22984: Upgrade normaliz to 3.5.3 and pynormaliz to 1.12
  • #24152: Bug when converting a Sage polyhedron into Polymake pexpect
  • #24662: Upgrade scipoptsuite to 5.0.1
  • #24835: Change error message in construction of polyhedron object
  • #24846: Make the face lattice of a polyhedron a lattice
  • #25081: The polar of a polyhedron should carry the backend used
  • #25095: polygon3d ignores the "alpha" (and equivalent "opacity") argument

New methods for polyhedron:

  • #24848: join of polytopes
  • #24849: (sub)direct sums of polytopes
  • #24886: one-point suspension and face split of polyhedron

Sage 8.2

Improvements:

  • #21937: Library of polytopes accepts a backend parameter
  • #22455: Fixed _facet_adjacency_matrix of non-full-dim. polyhedron
  • #22524: Optimize computing points of lattice polytopes
  • #23555: Bounding box bug in Polyhedron plots
  • #23685: Minkowski -> minkowski
  • #24047: Fixed Polyhedron.affine_hull() raises AssertionError?

New methods for polyhedron:

Sage 8.1

Improvements:

  • #16045: Polytope volume function engines produce different results
  • #22391: Always use PPL for facet normals of lattice polytopes
  • #22400: Transpose text databases of reflexive polytopes for PALP
  • #22552: 2 bugs creating a simple 2-point Polytope
  • #22558: Fixed: Volume of polyhedron does not handle unbounded polyhedron properly
  • #22565: Fixed sage_input to include the backend used
  • #22605: Improved the polyhedron constructor
  • #23355: Fixed: affine hull of one point polyhedron
  • #24154: Fixed equation handling in .to_linear_program and integral_points_count

Sage 8.0

Here is a sample of changes related to Polyhedral Geometry in this release.

Highlights:

  • #13517: New class for Voronoi Diagrams
  • #22522: Integration with Latte (function .integrate() )
  • #22683: Backend polymake for polyhedron
  • #22824: Add see also section to integrate over a polytope

Improvements:

  • #11759: octahedron() and icosahedron() produce "non-enclosed" polyhedra
  • #15253: Cartesian product of polyhedra with different dimension fails
  • #20887: Integration of polynomials over polytopes with LattE
  • #21270: Polyhedron RDF face lattice bug / intersection of polyhedra
  • #21993: Fixed overflow in integral_points()
  • #22310: Use PPL for facet normals of full-dimensional polytopes
  • #22498: Add .normal_fan() and .face_fan() methods for rational bounded polyhedra
  • #22562: Lattice point count with preprocessing
  • #22578: Polyhedron.bounding_box: New keyword argument integral_hull, use it in .integral_points
  • #22568: Polyhedron_ZZ should inherit from Polyhedron_QQ, not Polyhedron_base
  • #22622: Inconsistency in the .is_lattice_polytope() method
  • #22804: Add isometry feature to affine_hull of polyhedra
  • #22824: Add see also section to integrate over a polytope
  • #22938: Fixed normaliz backend with empty polyhedron

Sage 7.6

Improvements:

  • #17264: Polyhedron function broken with floats in sage-6.3 (worked in sage-6.2)
  • #18220: disallow non exact fields for the 'field' backend
  • #22122: Remove deprecated code in geometry
  • #22275: Implement duality of faces for reflexive polytopes
  • #22309: Use PPL for computing vertices of LatticePolytope?
  • #22469: Deprecate/remove sage/geometry/polytope.py
  • #22496: documentation of Combinatorial and Discrete Geometry
  • #22497: generic latte_int interface to count
  • #22505: perl_term_readline_gnu fails to install
  • #22534: Add "long time" to doctests in the geometry component
  • #22546: Improve combinatorial_automorphism_group in polyhedra class
  • #22551: Deprecate the old .field() method from polyhedron class
  • #22578: Polyhedron.bounding_box: New keyword argument integral_hull, use it in .integral_points

New methods for Polyhedron:

  • #18128: Add a face truncation method to Polyhedron class
  • #20887: Integration of polynomials over polytopes with LattE
  • #22416: Add .is_inscribed() method to polytopes
  • #22417: .neighborliness() and .is_neighborly(): Add neighborly methods for polyhedra
  • #22500: Add .is_combinatorially_isomorphic() method to polyhedra

New methods for SimplicialComplexes?:

  • #22466: Implement star and stellar subdivision of a face of simplicial complex
Last modified 3 weeks ago Last modified on 09/10/20 19:32:41