Differences between revisions 27 and 28
 ⇤ ← Revision 27 as of 2019-10-25 07:18:59 → Size: 20539 Editor: jipilab Comment: ← Revision 28 as of 2019-10-25 07:26:02 → ⇥ Size: 20388 Editor: jipilab Comment: Deletions are marked like this. Additions are marked like this. Line 44: Line 44: * Make Ehrhart (quasi)polynomial accessible through normaliz (and consistent with the current one) [[https://trac.sagemath.org/ticket/18957|#18957]]

# 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

## Tickets

Here are some practical lists of tickets:

## Meta-tickets

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

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

• Fixed: 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

• 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.)
• 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 discussion

• Helper 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

• 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: Normaliz 3.5.4 released

#### Py(Q)Normaliz

PyNormaliz (last version is 1.17):

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

#### PyScipOpt

Sage devel discussion

• Upgrade scipoptsuite to 5.0.1 #24662

• Add SCIP backend using PySCIPOpt #21003

#### Polymake

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

## Short Sage Release Notes

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

OptiPolyGeom (last edited 2020-09-13 16:43:51 by mathzeta2)