# 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:

- #31748:
`PolyhedralComplex`

: preliminary implementation - #25114: Cannot plot Cone that is a halfplane in 2d
- #25122: Construct
`RationalPolyhedralFan`

from possibly overlapping cones - #27728: Add Perles and irrational polytopes to library
- #27744: Make pynormaliz a Feature
- #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
- #30198: Polyhedra in vector spaces without distinguished basis
- #30438: Improve face iterator for almost simple/simplicial polytopes
- #30699: Improve triangulate and volume methods for polytopes over inexact rings
- #30749: Characteristic polynomial of central Hyperplane arrangement results wrong result?
- #30772: induced volume for polytopes defined over algebraic fields

- Task #27063: Transition of combinatorial computations of Polyhedron to combinatorial type:

- 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.3

Bug fixes:

- #30015: Schlegel projection breaks convexity
- #30319: wrong intersection of polytopes
- #30545: A 1-dimensional polytope has no edge
- #30891: Normaliz cone from precomputed data has lattice messed up
- #31253: Put equations in stable position for backend cdd

Improvements:

- #30040: Improve face iterator for 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
- #30549: Remove all the bitset access from cython files in combinatorial polyhedron
- #30587: Remove import of 'ppl' at startup using lazy_import with feature
- #30878: some flake8 details in backend normaliz
- #31262: Implement non zero chunks for sparse bitsets

New features:

- #30704: Upgrade to Normaliz 3.8.9 and PyNormaliz? 2.13
- #30946: Add "minimal=True" option to affine_hull_projection
- #30954: Implement a proper equality check for polyhedron representation objects
- #31038: Improve the zonotope construction

### 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
- #30328: Need to convert values before passing them to
`cdd`

- #30330:
`cdd`

backend fails to initialize empty polyhedron from double description - #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`

- #30531: Polyhedron_normaliz._triangulate_normaliz should not use NmzResult? directly
- #30571: Remove doctests in
`combinatorial_polyhedron/conversions.pyx`

that depend on implementation details - #30605: improve cone containment tests

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:

- #28280: Task: CombinatorialPolyhedron?: replace attributes by methods, make names more consistent with Polyhedron

### 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:

- #18957: ehrhart_polynomial should be made available for polytopes defined over QQ
- #28621: Add CombinatorialPolyhedron? method to Polyhedron objects
- #28245: Implement center of a HyperplaneArrangement?
- #28248: Add .boundary_complex() method for simplicial polytopes
- #28429: Add the classical construction of the 120-cell
- #28743: Lattice Polytopes: Implement incidence matrix
- #28766: Implement incidence matrix for cones

### 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:

- #24451: get_integral_point

### 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