search

mkoeppe / cutgeneratingfunctionology

Python code for computation and experimentation with cut-generating functions, in particular the Gomory-Johnson infinite group problem. By M. Köppe, Y. Zhou, C.Y. Hong, J. Wang with contributions by undergrad programmers
GNU General Public License v2.0
12 stars 11 forks source link

Add option SemialgebraicComplex to compute only minimal functions #80

Closed ComboProblem closed 11 months ago

ComboProblem commented 1 year ago

For problems in the Gomory Johnson Model, add an option to SemialgebraicComplex to enable testing for only minimal functions functions rather than assuming the default behavior of extremity testing.

mkoeppe commented 1 year ago

Example?

ComboProblem commented 1 year ago

In SemialgebraicComplex in the paragmetric.sage file, there is an option for find_region_type and the doc string states to set this to None for functions from the Gomory Johnson model. By default, SemialgebraicComplex uses the find_region_type_igp method which defaults to computing extreme functions when used in a method like bfs_completion (as far as I'm aware). It is unclear (to me) how to how to change this option for find_region_type so that find_region_types_igp finds minimal functions only rather than also searching for extreme functions.

As a particular improvement, it would be nice if the command could be something like clx = SemialgebraicComplex(family_of_gomory_johnson_functions, list_of_parameters, model="minimal_only") which would compute the proof complex for the parameters taking into consideration only minimal, not-minimal, and not-constructible regions. Or it would be nice to add documentation on how to change the behavior of find_region_type_igp as an argument to SemialgebraicComplex so the above could be accomplished.

ComboProblem commented 11 months ago

Fixed with updated documentation.