Differences between revisions 1 and 10 (spanning 9 versions)
Revision 1 as of 2018-04-12 19:04:18
Size: 75
Editor: jipilab
Comment:
Revision 10 as of 2018-04-13 16:30:35
Size: 8165
Editor: Winfried
Comment: Small additions by Winfried
Deletions are marked like this. Additions are marked like this.
Line 1: Line 1:
A Roadmap for Optimization and Polyhedral Geometry softwares interactions = 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 ==

[[https://wiki.sagemath.org/days84|Sage Days 84 on Polytopes in Olot]]

== Tickets ==

Here are some practical lists of tickets:

[[https://trac.sagemath.org/query?status=closed&status=needs_info&status=needs_review&status=needs_work&status=new&status=positive_review&keywords=~days84&col=id&col=summary&col=status&col=time&col=changetime&col=author&col=reviewer&order=status|Tickets from the Sage Days 84 March 2017]]

[[https://trac.sagemath.org/query?status=closed&status=needs_info&status=needs_review&status=needs_work&status=new&status=positive_review&keywords=~IMA-PolyGeom&col=id&col=summary&col=keywords&col=status&col=author&col=reviewer&order=status|Tickets from the IMA Coding Sprint - April 2018]]

[[https://trac.sagemath.org/query?status=needs_info&status=needs_review&status=needs_work&status=new&status=positive_review&keywords=~polytopes&keywords=~polytope&order=status|Tickets with keyword polytope]]

[[https://trac.sagemath.org/query?status=needs_info&status=needs_review&status=needs_work&status=new&component=geometry&col=id&col=summary&col=status&col=owner&col=type&col=priority&col=keywords&order=status|Current tickets of the Geometry component]]

== Meta-tickets ==

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

 * [[https://trac.sagemath.org/ticket/22420|Polyhedron: new features and known bugs]]
 * [[https://trac.sagemath.org/ticket/20875|Polytopes, lattice (integer) point counting / enumeration, and their applications]]
 * [[https://trac.sagemath.org/ticket/20302|Improvements to MixedIntegerLinearProgram, its backends, and InteractiveLinearProgram]]
 * [[https://trac.sagemath.org/ticket/20877|Piecewise functions, polyhedral complexes, piecewise functions of several variables, periodic piecewise functions]]
 * [[https://trac.sagemath.org/ticket/22710|Polymake]]
 * [[https://trac.sagemath.org/ticket/22827|Expose all normaliz features]]

== To do ==

 * Test the algebraic polytopes [[https://trac.sagemath.org/ticket/25097|#25097]]
 * Make Polyhedron_normaliz accept algebraic stuff, related to [[https://trac.sagemath.org/ticket/25097|#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 [[https://trac.sagemath.org/ticket/21161|#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 [[https://trac.sagemath.org/ticket/21984|#21984]]
 * Make Ehrhart (quasi)polynomial accessible through normaliz (and consisten with the current one) [[https://trac.sagemath.org/ticket/18957|#18957]]
 * Adjust the new features of the normaliz backend to the latest version [[https://trac.sagemath.org/ticket/25091|#25091]] [[https://trac.sagemath.org/ticket/25090|#25090]]

== Progress Report Timeline ==

=== April 2018 ===

==== Sage ====

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

 * Thematic tutorial on polyhedron in Sage [[https://trac.sagemath.org/ticket/22572|#22572]]
 * 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]]
 * Change error message in construction of polyhedron object [[https://trac.sagemath.org/ticket/24835|#24835]]
 * Improve the output of repr_pretty for Polyhedron [[https://trac.sagemath.org/ticket/24837|#24837]]
 * Implement stacking onto a face of a polyhedron [[https://trac.sagemath.org/ticket/24847|#24847]]
 * Implement join of polytopes [[https://trac.sagemath.org/ticket/24848|#24848]]
 * Implement one point suspension and face split of polyhedron [[https://trac.sagemath.org/ticket/24886|#24886]]
 * The polar of a polyhedron should carry the backend used [[https://trac.sagemath.org/ticket/25081|#25081]]
 * 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]]
 * Update normaliz 3.5.3 and pynormaliz 1.12 in Sage. Now Positive review. [[https://trac.sagemath.org/ticket/22984|#22984]]
 * PolyhedralComplex: preliminary implementation, see [[https://trac.sagemath.org/ticket/20877|#20877]]

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

http://normaliz.uni-osnabrueck.de

 * Upgrade normaliz to 3.5.3 and pynormaliz to 1.12 [[https://trac.sagemath.org/ticket/22984|#22984]]
 * 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 polytope using e-antic [[https://trac.sagemath.org/ticket/25097|#25097]]: convex hull computation completed
 * fixed: getProjectionCone might segfault [[https://github.com/Normaliz/Normaliz/issues/180]]
 * fixed: BadInputException for ProjectCone [[https://github.com/Normaliz/Normaliz/issues/181]]
 * Unified getter [[https://github.com/Normaliz/Normaliz/pull/182]]available for interfaces (return of results by type instead of computation goal)

==== 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 [[https://trac.sagemath.org/ticket/22984|#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

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.2r2 (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.

 * 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

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:

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

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

Progress Report Timeline

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 Sage-devel discussion

  • Helper functions and improvements in the normaliz backend #25097

  • 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

  • Update normaliz 3.5.3 and pynormaliz 1.12 in Sage. Now Positive review. #22984

  • PolyhedralComplex: preliminary implementation, see #20877

(Q)Normaliz

http://normaliz.uni-osnabrueck.de

Py(Q)Normaliz

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

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

A list of other Polyhedral Geometry softwares

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

OptiPolyGeom (last edited 2022-04-18 03:44:30 by mkoeppe)