A Roadmap for Optimization and Polyhedral Geometry softwares interactions

(around Sage, (PyQ)Normaliz, SCIP, e-antic, 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

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

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

Progress Reports

April 2018

Sage

Here are improvements realized to objects related to polyhedron in Sage:

• Thematic tutorial on polyhedron in Sage #22572

• Make features of normaliz accessible #25091

• number_field_elements_from_algebraics should create embedded number field elements #20181

• Helper functions in the normaliz backend

• Change error message in construction of polyhedron object #24835

• Improve the output of repr_pretty for Polyhedron #24837

• Implement stacking onto a face of a polyhedron #24847

• Implement join of polytopes #24848

• Implement one point suspension and face split of polyhedron #24886

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

• Construct RationalPolyhedralFan from possibly overlapping cones #25122

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

(Q)Normaliz

http://normaliz.uni-osnabrueck.de

• Upgrade normaliz to 3.5.3 and pynormaliz to 1.12 #22984

• Algebraic polytope using e-antic #25097

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

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

• Unified getter https://github.com/Normaliz/Normaliz/pull/182

Py(Q)Normaliz

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

• Upgrade normaliz to 3.5.3 and pynormaliz to 1.12 #22984

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

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

PyScipOpt

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

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

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