= A Roadmap for Optimization and Polyhedral Geometry softwares interactions =
== (around Sage, (PyQ)Normaliz, SCIP, e-antic, Polymake, and others) ==

This page is being moved to https://trac.sagemath.org/wiki/SagePolyhedralGeometry

== 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 [[https://trac.sagemath.org/ticket/27689|#27689]]
 * Implement wedge over a face of Polyhedron [[https://trac.sagemath.org/ticket/27973|#27973]]
 * Implement center of a HyperplaneArrangement [[https://trac.sagemath.org/ticket/28245|#28245]]
 * Normal cone of faces of polyhedra [[https://trac.sagemath.org/ticket/17215|#17215]]
 * Implement facets method for Polyhedron [[https://trac.sagemath.org/ticket/27974|#27974]]
 * ehrhart_polynomial should be made available for polytopes defined over QQ [[https://trac.sagemath.org/ticket/18957|#18957]]

 * Fixed: bug in polyhedron over RDF [[https://trac.sagemath.org/ticket/24877|#24877]]
 * Fixed: Make outer normal fans readily available [[https://trac.sagemath.org/ticket/27993|#27993]]
 * Fixed: py3: polyhedron folder with optional packages [[https://trac.sagemath.org/ticket/28235|#28235]]
 * Fixed: Move rational methods of the backend normaliz to the `_QQ` class [[https://trac.sagemath.org/ticket/28240|#28240]]
 * Fixed: add .is_self_dual method for polytopes [[https://trac.sagemath.org/ticket/28256|#28256]]
 * Fixed: Add .boundary_complex() method for simplicial polytopes [[https://trac.sagemath.org/ticket/28248|#28248]]
 * Fixed: repr of NumberFields (the parents) should indicate its embedding if there is one [[https://trac.sagemath.org/ticket/21161|#21161]]

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

 * Thematic Tutorial on algebraic polytopes in Sage using Normaliz [[https://trac.sagemath.org/ticket/28230|#28230]]
 * Add the 0/1-hypercube to the library of polytopes [[https://trac.sagemath.org/ticket/28247|#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 [[https://trac.sagemath.org/ticket/27731|#27731]]
 * Almost done with repr of NumberFields (the parents) should indicate its embedding if there is one [[https://trac.sagemath.org/ticket/21161|#21161]]
 * Adjust the new features of the normaliz backend to the latest version [[https://trac.sagemath.org/ticket/25091|#25091]]
 * Algebraic polytopes now under review [[https://trac.sagemath.org/ticket/25097|#25097]]
 * Add the H4 polytopes and generalized permutahedron to the library of polytopes [[https://trac.sagemath.org/ticket/27760|#27760]]
 * Create a variant of the polymake interface using polymake's callable library (polymake::Main) via JuPyMake [[https://trac.sagemath.org/ticket/22704|#22704]]
 * Add Perles and irrational polytopes to library [[https://trac.sagemath.org/ticket/27728|#27728]]

 * Fixed: Upgrade polymake to version 3.4 (current interface breaks) [[https://trac.sagemath.org/ticket/24905|#24905]]
 * Fixed: upgrade normaliz to 3.7.1, pynormaliz to 2.1 and package e-antic [[https://trac.sagemath.org/ticket/27682|#27682]]
 * Fixed: Refactor backend_normaliz [[https://trac.sagemath.org/ticket/27716|#27716]]
 * Fixed: Polytope snub_cube should allow exact coordinates [[https://trac.sagemath.org/ticket/26340|#26340]]
 * Fixed: number_field_elements_from_algebraics should create embedded number field elements [[https://trac.sagemath.org/ticket/20181|#20181]]
 * Fixed: The attribute _vector of H and V representation is exposed [[https://trac.sagemath.org/ticket/27709|#27709]]
 * Fixed: Remove old deprecation warning of Minkowski -> minkowski [[https://trac.sagemath.org/ticket/27722|#27722]]
 * Fixed: Upgrade LiDIA to v2.3.0+latte-patches-2019-05-01 [[https://trac.sagemath.org/ticket/27746|#27746]]
 * Fixed: PolymakeElement._sage_: Handle polymake type Polyhedron [[https://trac.sagemath.org/ticket/27742|#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 [[https://trac.sagemath.org/ticket/25091|#25091]]
 * `number_field_elements_from_algebraics` should create embedded number field elements [[https://trac.sagemath.org/ticket/20181|#20181]] [[https://groups.google.com/forum/#!topic/sage-devel/iy72Q_EKKFs|Sage-devel discussion]]
 * Helper functions and improvements in the normaliz backend [[https://trac.sagemath.org/ticket/25097|#25097]]
 * Improve the output of repr_pretty for Polyhedron [[https://trac.sagemath.org/ticket/24837|#24837]]
 * Construct RationalPolyhedralFan from possibly overlapping cones [[https://trac.sagemath.org/ticket/25122|#25122]]
 * polygon3d ignores the "alpha" (and equivalent "opacity") argument [[https://trac.sagemath.org/ticket/25095|#25095]]
 * PolyhedralComplex: preliminary implementation, see [[https://trac.sagemath.org/ticket/20877|#20877]]

 * Fixed: Change error message in construction of polyhedron object [[https://trac.sagemath.org/ticket/24835|#24835]]
 * Fixed: Update normaliz 3.5.3 and pynormaliz 1.12 in Sage. [[https://trac.sagemath.org/ticket/22984|#22984]]
 * Fixed: Thematic tutorial on polyhedron in Sage [[https://trac.sagemath.org/ticket/22572|#22572]]
 * Fixed: Implement stacking onto a face of a polyhedron [[https://trac.sagemath.org/ticket/24847|#24847]]
 * Fixed: Implement join of polytopes [[https://trac.sagemath.org/ticket/24848|#24848]]
 * Fixed: Implement one point suspension and face split of polyhedron [[https://trac.sagemath.org/ticket/24886|#24886]]
 * Fixed: The polar of a polyhedron should carry the backend used [[https://trac.sagemath.org/ticket/25081|#25081]]


==== (Q)Normaliz ====

http://normaliz.uni-osnabrueck.de

 * Upgrade normaliz to 3.5.4 and pynormaliz to 1.16 [[https://trac.sagemath.org/ticket/25090|#25090]]: Ehrhart series and triangulation of polytope also for inhomogeneous input
 * Algebraic polytopes in Qnormaliz using e-antic [[https://trac.sagemath.org/ticket/25097|#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 [[https://trac.sagemath.org/ticket/22984|#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 [[https://groups.google.com/forum/#!topic/sage-devel/QH_E14WHQ70|discussion]]

 * Upgrade scipoptsuite to 5.0.1 [[https://trac.sagemath.org/ticket/24662|#24662]]
 * Add SCIP backend using PySCIPOpt [[https://trac.sagemath.org/ticket/21003|#21003]]

==== Polymake ====

https://polymake.org/doku.php

 * Upgrade polymake to version 3.4 (current interface breaks) [[https://trac.sagemath.org/ticket/24905|#24905]]

== A list of other Polyhedral Geometry softwares ==

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

 * Bensolve:
   * http://bensolve.org/

 * 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

 * Visualizations
   * [[https://polyhedra.tessera.li/|Polyhedra Viewer]] by [[https://www.tessera.li/|Nat Alison]].
     Sage should have such a GUI with all the animations for the different operations, at least for the catalog.