# A Roadmap for Optimization and Polyhedral Geometry softwares interactions

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

This page is intended to describe the current status of development of Sage 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

## Meetings

Sage Days 84 on Polytopes in Olot

## Tickets

Here are some practical lists of tickets:

Tickets from the Sage Days 84 March 2017

Tickets from the IMA Coding Sprint - April 2018

Current tickets of the Geometry component

## Meta-tickets

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

Polytopes, lattice (integer) point counting / enumeration, and their applications

Improvements to MixedIntegerLinearProgram, its backends, and InteractiveLinearProgram

## To do

- Thematic Tutorial for Py(Q)Normaliz installation/Usage in Sage
- Increase documentation in Py(Q)Normaliz
Deprecate the opacity argument for plot3d and use alpha #21984

Make Pynormaliz a feature in the PythonModule framework

Polymake: Turn polymake applications into objects with directories #27736

Add Perles and irrational polytopes to library #27728

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

## Progress Report Timeline

### August 2019

Here are improvements realized up to the Sage Days 100 in Bonn

#### Sage

The following are quite advanced and many are under review:

Implement is_pyramid, is_bipyramid, is_prism for polytopes #27689

Implement wedge over a face of Polyhedron #27973

Implement center of a HyperplaneArrangement #28245

Normal cone of faces of polyhedra #17215

Implement facets method for Polyhedron #27974

ehrhart_polynomial should be made available for polytopes defined over QQ #18957

Fixed: bug in polyhedron over RDF #24877

Fixed: Make outer normal fans readily available #27993

Fixed: py3: polyhedron folder with optional packages #28235

Fixed: Move rational methods of the backend normaliz to the

`_QQ`class #28240Fixed: add .is_self_dual method for polytopes #28256

Fixed: Add .boundary_complex() method for simplicial polytopes #28248

Fixed: repr of NumberFields (the parents) should indicate its embedding if there is one #21161

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

Thematic Tutorial on algebraic polytopes in Sage using Normaliz #28230

Add the 0/1-hypercube to the library of polytopes #28247

### April/May 2019

Here are improvements realized during the Research in Pairs at MFO

#### Sage

The following are quite advanced and many are under review:

upgrade normaliz to 3.7.2, pynormaliz to 2.5 #27731

Almost done with repr of NumberFields (the parents) should indicate its embedding if there is one #21161

Adjust the new features of the normaliz backend to the latest version #25091

Algebraic polytopes now under review #25097

Add the H4 polytopes and generalized permutahedron to the library of polytopes #27760

Create a variant of the polymake interface using polymake's callable library (polymake::Main) via JuPyMake #22704

Add Perles and irrational polytopes to library #27728

Fixed: Upgrade polymake to version 3.4 (current interface breaks) #24905

Fixed: upgrade normaliz to 3.7.1, pynormaliz to 2.1 and package e-antic #27682

Fixed: Refactor backend_normaliz #27716

Fixed: Polytope snub_cube should allow exact coordinates #26340

Fixed: number_field_elements_from_algebraics should create embedded number field elements #20181

Fixed: The attribute _vector of H and V representation is exposed #27709

Fixed: Remove old deprecation warning of Minkowski -> minkowski #27722

Fixed: Upgrade LiDIA to v2.3.0+latte-patches-2019-05-01 #27746

Fixed: PolymakeElement._sage_: Handle polymake type Polyhedron #27742

#### PyNormaliz

- Update PyQNormaliz by adding lattice points, integer hull and volume
- Removal of instabilities (Memory corruption etc.)
- Added functions
- Added test framework
- Interfacing the new Normaliz features
- Adjustment for Sage signal handling
Several improvements to JuPyMake

- Test implementation of polymake interface for python in cython
- Alpha implementation of Normaliz.jl, a julia interface to Normaliz, to be used in OSCAR and GAP.

#### Normaliz

- Inclusion of the computation of automorphism groups for general polytopes and cones, also for algebraic polytopes and cones.
- Various types of automorphism groups can be computed: combinatorial, rational, integral and (for algebraic data) algebraic.
- Efficient exploitation of the automorphism group in polyhedral computations has been realized for volumes, Hilbert bases and lattice points in polytopes.
- Three new releases of Normaliz, namely 3.7.1, 3.7.2 and 3,7.3, that have repared several small bugs and improved weak points.
- The API libnormaliz has been restructured and enriched by the accessibility of the output function.

### April 2018

#### Sage

Here are improvements realized during the Coding Sprints at the IMA in Minneapolis to objects related to polyhedron in Sage:

Make features of normaliz accessible #25091

`number_field_elements_from_algebraics`should create embedded number field elements #20181 Sage-devel discussionHelper functions and improvements in the normaliz backend #25097

Improve the output of repr_pretty for Polyhedron #24837

Construct RationalPolyhedralFan from possibly overlapping cones #25122

polygon3d ignores the "alpha" (and equivalent "opacity") argument #25095

PolyhedralComplex: preliminary implementation, see #20877

Fixed: Change error message in construction of polyhedron object #24835

Fixed: Update normaliz 3.5.3 and pynormaliz 1.12 in Sage. #22984

Fixed: Thematic tutorial on polyhedron in Sage #22572

Fixed: Implement stacking onto a face of a polyhedron #24847

Fixed: Implement join of polytopes #24848

Fixed: Implement one point suspension and face split of polyhedron #24886

Fixed: The polar of a polyhedron should carry the backend used #25081

#### (Q)Normaliz

http://normaliz.uni-osnabrueck.de

Upgrade normaliz to 3.5.4 and pynormaliz to 1.16 #25090: Ehrhart series and triangulation of polytope also for inhomogeneous input

Algebraic polytopes in Qnormaliz using e-antic #25097: convex hull computation completed, improvement of Qnormaliz input and output, control of interrupts and parallelization via libQnormaliz, lattice points, integer hull and volume added. Qnormaliz should be essentially complete now.

- General getters for cone properties. The getters can be used in future interfaces to make access to Normaliz cone properties easier
- resetGrading method for cone: Can be used to replace the grading and redo certain Normaliz computation without having to delete
- degree indepenent properties, such as hilbert bases.

- documentation of QNormaliz written
- extensive tests of QNormaliz
- link from libQnormaliz to libnormaliz in preparation for lattice point computation in algebraic polytopes
- further attempts to improve QNormaliz output (not yet complete)
- work on the C++ wrapper of e-antic
fixed: Upgrade normaliz to 3.5.3 and pynormaliz to 1.12 #22984: repair of performance loss

fixed: getProjectionCone might segfault https://github.com/Normaliz/Normaliz/issues/180

fixed: BadInputException for ProjectCone https://github.com/Normaliz/Normaliz/issues/181

- fixed: Normaliz 3.5.4 released

#### Py(Q)Normaliz

https://pypi.python.org/pypi/PyNormaliz https://github.com/Normaliz/PyNormaliz

PyNormaliz (last version is 1.17):

- All computation goals and output properties from Normaliz 3.5.4 are supported
It is possible to give functions RationalHandler, VectorHandler, and MatrixHandler to NmzResult to construct rationals, vectors, and matrices

Some documentation in the sources of NormalizModule.cpp

- Functionality to copy cone
Functionality to reset grading of a cone in PyNormaliz

PyQNormaliz (current beta is 0.2, not available on PIPy):

- All QNormaliz compute targets can be accessed
- Input of number_field data as string
- Input of number_field elements as list of 2-tuples, or as string
Ouput handlers RationalHandler, NumberfieldElementHandler, VectorHandler, and MatrixHandler

See example worksheet: https://nbviewer.jupyter.org/github/sebasguts/PyQNormaliz/blob/master/examples/Dodecahedron.ipynb

Upgraded pynormaliz to 1.16 https://github.com/Normaliz/PyNormaliz

Started PyQNormaliz. https://github.com/sebasguts/PyQNormaliz

#### PyScipOpt

https://github.com/SCIP-Interfaces/PySCIPOpt

Sage devel discussion

#### Polymake

Upgrade polymake to version 3.4 (current interface breaks) #24905

## Short Sage Release Notes

### Sage 9.1

Improvements:

- #19803: difference of behavior in polyhedra with different backends
- #29057: make stack method of Polyhedron use fraction_field
#29073:

`gale_transform`does not work for`RDF`

New features:

- #26363: Polyhedron_normaliz.save
#27086: Simplicity and simpliciality for CombinatorialPolyhedron

- #28247: Parametrize the cube/hypercube functions in the library of polytopes
#29085: CombinatorialPolyhedron: Expose

`is_bounded`

### 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
- #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
- #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:
- #27071: Make indices of V_representation of faces of polyhedron accessible through a new method
- #27533: Improve Polyhedron.is_simple()
- #26340: polytopes.snub_cube should be set up with base_ring=QQ
#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

- #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:
- Upgrade scipoptsuite to 5.0.1
- #24152: Bug when converting a Sage polyhedron into Polymake pexpect
#22984: Upgrade normaliz to 3.5.3 and pynormaliz to 1.12 #22984

- #22572: Add a thematic tutorial on the polyhedron class
- #25081: The polar of a polyhedron should carry the backend used.
- #24846: Make the face lattice of a polyhedron a lattice
- #24835: Change error message in construction of polyhedron object
- #25081: The polar of a polyhedron should carry the backend used

- New methods for polyhedron:
- join of polytopes
- one-point suspension and face split of polyhedron
- (sub)direct sums of polytopes

### Sage 8.2

- Improvements:
- Library of polytopes accepts a backend parameter
- Fixed _facet_adjacency_matrix of non-full-dim. polyhedron
- Optimize count lattice points of polytopes
Fixed Polyhedron.affine_hull() raises AssertionError

- Bounding box bug in Polyhedron plots
Minkowski -> minkowski

- New methods for polyhedron:
- get_integral_point

### Sage 8.1

- Improvements:
- Fixed equation handling in .to_linear_program and integral_points_count
- Fixed sage_input to include the backend used
- Improved the polyhedron constructor
- Fixed .affine_hull() raising an assertion error
- Volume function handling better the different measures depending on the engine used
- Always use PPL for facet normals of lattice polytopes
- Fixed: Volume of polyhedron does not handle unbounded polyhedron properly
- Fixed: affine hull of one point polyhedron

### Sage 8.0

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

- Highlights:
- Integration with Latte (function .integrate() )
- New class for Voronoi Diagrams
- Backend polymake for polyhedron

- Improvements:
Fixed CartesianProduct with distinct dimensions

- Fixed an error in .is_lattice_polytope()
- Fixed overflow in integral_points()
- Fixed normaliz backend with empty polyhedron

- New methods for Polyhedron:
- integral_points_count()

### Sage 7.6

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

- Improvements:
- documentation of Combinatorial and Discrete Geometry
- combinatorial_automorphism_group
- Fixes on .volume()
- Fixes in integral_points()

- New methods for Polyhedron:
- .is_inscribed()
- .neighborliness()
- .is_neighborly()
- .normal_fan()
- .face_fan()
- .is_combinatorially_isomorphic()
- .face_truncation()

New methods for SimplicialComplexes:

- star of a face
- stellar subdivision

- Generic interface to latte integrale:
- count points

## A list of other Polyhedral Geometry softwares

What are other softwares dealing with polyhedral geometry? Here is a non-exhaustive list.

- Bensolve:
- Maple:
https://www.maplesoft.com/support/help/Maple/view.aspx?path=PolyhedralSets%2fPolyhedralSet (seems to be only rational and implemented in 2015).

http://qhull.org/ (seems old?)

https://www.maplesoft.com/products/maple/new_features/Maple2018/ComputationalGeometry.aspx

https://www.maplesoft.com/support/help/Maple/view.aspx?path=PolyhedralSets

- CGAL:
- A paper:
Jing & Maza https://dl.acm.org/citation.cfm?id=3177798

- Matlab:
- Matematica: