22765
Comment: Added tickets to Sage9.1

23712
Added v9.1 tickets

Deletions are marked like this.  Additions are marked like this. 
Line 219:  Line 219: 
* #28880: Prepare setting up polyhedron from both Vrep and Hrep for different backends  
Line 221:  Line 222: 
* #29074: Better error message for polar of nonfull dimensional polyhedra * #29116: affine_basis does not always work when used with orthogonal or orthonormal * #29125: `is_inscribed` depends on order of vertices * #29155: Fulldimensional face of Polyhedron should have equations * #29223: Pickle cached value of volume and fvector 

Line 223:  Line 229: 
* #17215: Normal cone of faces of polyhedra  
Line 224:  Line 231: 
* #26623: Constructions for common polyhedral cones  
Line 226:  Line 234: 
* #28413: Add .h_star_vector to compact rational polytopes * #28724: Polyhedron._acted_upon_ should handle left multiplication by matrices, linear transformations 

Line 227:  Line 237: 
* #29112: Implement incidence matrix for combinatorial polyhedron * #29117: Implement a maximal chain for combinatorial polyhedron * #29127: Implement an affine basis for polytopes * #29224: `flag_f_vector` for polyhedra 
A Roadmap for Optimization and Polyhedral Geometry softwares interactions
(around Sage, (PyQ)Normaliz, SCIP, eantic, 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
Metatickets
There are already a few metatickets 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 Hrepresentation in normaliz is possible ("redundlike") 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/1hypercube 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 eantic #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+lattepatches20190501 #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 Sagedevel 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.uniosnabrueck.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 eantic #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 eantic
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 2tuples, 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/SCIPInterfaces/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
 #28880: Prepare setting up polyhedron from both Vrep and Hrep for different backends
 #29057: make stack method of Polyhedron use fraction_field
#29073: gale_transform does not work for RDF
 #29074: Better error message for polar of nonfull dimensional polyhedra
 #29116: affine_basis does not always work when used with orthogonal or orthonormal
#29125: is_inscribed depends on order of vertices
 #29155: Fulldimensional face of Polyhedron should have equations
 #29223: Pickle cached value of volume and fvector
New features:
 #17215: Normal cone of faces of polyhedra
 #26363: Polyhedron_normaliz.save
 #26623: Constructions for common polyhedral cones
#27086: Simplicity and simpliciality for CombinatorialPolyhedron
 #28247: Parametrize the cube/hypercube functions in the library of polytopes
 #28413: Add .h_star_vector to compact rational polytopes
 #28724: Polyhedron._acted_upon_ should handle left multiplication by matrices, linear transformations
#29085: CombinatorialPolyhedron: Expose is_bounded
 #29112: Implement incidence matrix for combinatorial polyhedron
 #29117: Implement a maximal chain for combinatorial polyhedron
 #29127: Implement an affine basis for polytopes
#29224: flag_f_vector for polyhedra
Sage 9.0
Improvements:
 #17339: Polyhedron class mistreats empty inputs
 #18861: Three apparently useless polyhedron methods
 #25183: Bug in the associahedron object
 #26922: Wrong fvector 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 fulldimensional
 #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 120cell
 #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 / eantic (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 4uniform 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 eantic
 #27700: Fix is_simplicial for nonfulldimensional 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=... (followup)
 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
 onepoint 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 nonfulldim. 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 nonexhaustive 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: