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

Tickets with keyword polytope

Current tickets of the Geometry component

Meta-tickets

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

• Polyhedron: new features and known bugs

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

• Improvements to MixedIntegerLinearProgram, its backends, and InteractiveLinearProgram

• Piecewise functions, polyhedral complexes, piecewise functions of several variables, periodic piecewise functions

• Polymake

• Expose all normaliz features

To do

• Test the algebraic polytopes #25097

• Make Polyhedron_normaliz accept algebraic stuff, related to #25097 (adapt _init_from_Hrepresentation)

• Add known irrational polytope to the library of polytopes

• repr of NumberFields (the parents) should indicate its embedding if there is one #21161 (this ticket will help in debugging and have good feedback)

• Thematic Tutorial for Py(Q)Normaliz installation/Usage in Sage
• Increase documentation in Py(Q)Normaliz
• Update PyQNormaliz by adding lattice points, integer hull and volume

• Deprecate the opacity argument for plot3d and use alpha #21984

• Make Ehrhart (quasi)polynomial accessible through normaliz (and consisten with the current one) #18957

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

Progress Report Timeline

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

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

• Upgrade scipoptsuite to 5.0.1 #24662

• Add SCIP backend using PySCIPOpt #21003

Polymake

https://polymake.org/doku.php

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

Short Sage Release Notes

Sage 8.8

• Improvements:
  • #27071: Make indices of V_representation of faces of polyhedron accessible through a new method
  • #27533: Improve Polyhedron.is_simple()
• 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.

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

  • https://doc.cgal.org/latest/Triangulation/index.html#Chapter_Triangulations

• A paper:

  • Jing & Maza https://dl.acm.org/citation.cfm?id=3177798

• Matlab:

  • https://www.mathworks.com/help/matlab/ref/convhulln.html

  • https://www.mathworks.com/matlabcentral/fileexchange/48509-computational-geometry-toolbox

  • https://www.mathworks.com/help/optim/ug/linprog.html

  • https://www.mathworks.com/discovery/linear-programming.html

  • https://www.mathworks.com/help/optim/ug/example-linear-programming.html

• Matematica:

  • http://reference.wolfram.com/language/MultivariateStatistics/ref/Polytope.html

  • http://reference.wolfram.com/language/PolyhedronOperations/tutorial/PolyhedronOperations.html