mkoeppe / cutgeneratingfunctionology Goto Github PK

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

License: GNU General Public License v2.0

Makefile 0.37% Python 23.56% TeX 3.02% Shell 0.17% Jupyter Notebook 0.87% Emacs Lisp 0.01% Sage 71.99%

integer-programming mixed-integer-programming python sagemath cutting-planes

cutgeneratingfunctionology's Introduction

Most of the code is for the 1-dimensional Gomory-Johnson infinite group problem, including an electronic compendium of extreme functions.

See http://www.sagemath.org/doc/tutorial/ for information on how to use Sage.

Authors

See https://github.com/mkoeppe/cutgeneratingfunctionology/blob/master/AUTHORS.rst and also https://github.com/mkoeppe/cutgeneratingfunctionology/blob/master/THANKS.rst

License

The code is released under the GNU General Public License, version 2, or any later version as published by the Free Software Foundation.

Documentation

http://mkoeppe.github.io/cutgeneratingfunctionology/doc/html/

Using the cutgeneratingfunctionology package

There are many ways to run this package.

A. Run it online on mybinder.org

B. Install released version from PyPI and run it within conda

Install Miniconda from https://docs.conda.io/en/latest/miniconda.html
Set up the conda environment described in https://github.com/mkoeppe/cutgeneratingfunctionology/blob/master/environment.yml:
```
e=environment.yml; curl -o $e https://raw.githubusercontent.com/mkoeppe/cutgeneratingfunctionology/master/$e
conda env create -n sage-cgf -f $e
conda activate sage-cgf
```
This takes a while; it installs SageMath, which has many dependencies.
Install PyPI package:
```
pip install cutgeneratingfunctionology
```
Start Sage. You can either use the terminal (IPython):
```
sage
```
or a Jupyter notebook:
```
sage -n jupyter
```

At the Sage prompt, type:

import cutgeneratingfunctionology.igp as igp; from cutgeneratingfunctionology.igp import *

Follow the instructions and examples in https://github.com/mkoeppe/cutgeneratingfunctionology/blob/master/demo.rst or https://github.com/mkoeppe/cutgeneratingfunctionology/blob/master/demo.ipynb .

C. Clone from GitHub and run it within conda

Install Miniconda from https://docs.conda.io/en/latest/miniconda.html

Clone the GitHub repository https://github.com/mkoeppe/cutgeneratingfunctionology.git:

git clone https://github.com/mkoeppe/cutgeneratingfunctionology.git
cd cutgeneratingfunctionology

Set up the conda environment described in https://github.com/mkoeppe/cutgeneratingfunctionology/blob/master/environment.yml:
```
conda env create -n sage-cgf -f environment.yml
conda activate sage-cgf
```
This takes a while; it installs SageMath which has many dependencies.
(Optional:) Install the cutgeneratingfunctionology package using pip:
```
pip install .
```
Start Sage. You can either use the terminal (IPython):
```
sage
```
or a Jupyter notebook:
```
sage -n jupyter
```

At the Sage prompt, type:

import cutgeneratingfunctionology.igp as igp; from cutgeneratingfunctionology.igp import *

Follow the instructions and examples in https://github.com/mkoeppe/cutgeneratingfunctionology/blob/master/demo.rst or https://github.com/mkoeppe/cutgeneratingfunctionology/blob/master/demo.ipynb .

D. Run in a standalone installation of the SageMath distribution (no conda)

Install the SageMath distribution:
1. Either from source from http://www.sagemath.org/
2. or with a binary from http://www.sagemath.org/
The SageMath distribution brings its own installation of Python and many packages.

Clone the GitHub repository https://github.com/mkoeppe/cutgeneratingfunctionology.git:

git clone https://github.com/mkoeppe/cutgeneratingfunctionology.git
cd cutgeneratingfunctionology

(Optional:) Install optional SageMath distribution packages:
```
sage -i lrslib pynormaliz
```
Install the cutgeneratingfunctionology package using pip:
```
sage -pip install .
```
Start SageMath. You can either use the terminal (IPython):
```
sage
```
or a Jupyter notebook:
```
sage -n jupyter
```

At the Sage prompt, type:

import cutgeneratingfunctionology.igp as igp; from cutgeneratingfunctionology.igp import *

Follow the instructions and examples in https://github.com/mkoeppe/cutgeneratingfunctionology/blob/master/demo.rst or https://github.com/mkoeppe/cutgeneratingfunctionology/blob/master/demo.ipynb .

cutgeneratingfunctionology's People

Contributors

Stargazers

Watchers

Forkers

uduse robertopt weaver-viii jiawei-wang-ucd afiaramen drkwang ucd4ids jwg4 nicoleyueqili comboproblem roberthildebrand

cutgeneratingfunctionology's Issues

parametric.sage rich comparisons

http://doc.sagemath.org/html/en/reference/structure/sage/structure/richcmp.html
https://trac.sagemath.org/ticket/16537
http://python3porting.com/preparing.html
https://regebro.wordpress.com/2010/12/13/python-implementing-rich-comparison-the-correct-way/

Improve documentation by omitting many irrelevant special attributes and methods

... such as dict ....

Branch facet_test_more_complete

Complete the work on this branch:

In simple cases, facet_test should be able to construct the lifting.
A version of the moves diagrams should be used for facet_test.
extremality_test, presented with a 2-sided discontinuous function, should by default raise a NotImplementedError if crazy perturbations might exist instead of just issuing a warning.

Centralize references

... and add DOIs.

plot_limit_cone_of_vertex_in_face: Improve scaling of arrows when there's no space

... to make plot_2d_diagram_with_face_cones more useful for complicated functions like kzh_minimal_has_only_crazy_perturbation_1_perturbation.

Parameter flights with splines

http://doc.sagemath.org/html/en/reference/calculus/sage/calculus/interpolation.html

Make completion resume correctly after interruption

Currently we have the following when the extremality test is interrupted during the first moves diagram plot:

sage: h = bhk_irrational()
INFO: 2017-06-16 09:02:29,906 Coerced into real number field: Real Number Field in `a` as the root of the defining polynomial y^2 - 2 near 1.414213562373095?
INFO: 2017-06-16 09:02:29,909 Conditions for extremality are satisfied if it is a minimal function.
INFO: 2017-06-16 09:02:29,998 Coerced into real number field: Real Number Field in `a` as the root of the defining polynomial y^2 - 2 near 1.414213562373095?
sage: extremality_test(h, True)
INFO: 2017-06-16 09:02:34,933 pi(0) = 0
INFO: 2017-06-16 09:02:34,954 pi is subadditive.
INFO: 2017-06-16 09:02:34,955 pi is symmetric.
INFO: 2017-06-16 09:02:34,955 Thus pi is minimal.
INFO: 2017-06-16 09:02:34,955 Plotting 2d diagram...
INFO: 2017-06-16 09:02:34,955 Computing maximal additive faces...
INFO: 2017-06-16 09:02:35,110 Computing maximal additive faces... done
Launched png viewer for Graphics object consisting of 382 graphics primitives
INFO: 2017-06-16 09:02:38,268 Plotting 2d diagram... done
INFO: 2017-06-16 09:02:38,409 Plotting...
^C
KeyboardInterrupt
sage: extremality_test(h, True)
INFO: 2017-06-16 09:02:43,345 pi(0) = 0
INFO: 2017-06-16 09:02:43,345 pi is subadditive.
INFO: 2017-06-16 09:02:43,346 pi is symmetric.
INFO: 2017-06-16 09:02:43,346 Thus pi is minimal.
INFO: 2017-06-16 09:02:43,346 Plotting 2d diagram...
Launched png viewer for Graphics object consisting of 382 graphics primitives
INFO: 2017-06-16 09:02:46,514 Plotting 2d diagram... done
INFO: 2017-06-16 09:02:46,515 Plotting covered intervals...
Launched png viewer for Graphics object consisting of 38 graphics primitives
INFO: 2017-06-16 09:02:57,235 Plotting covered intervals... done
INFO: 2017-06-16 09:02:57,235 Uncovered intervals: ([<Int(0.3000000000000000?, 0.3500000000000000?)>, <Int(0.4500000000000000?, 0.50000000000000000?)>],)
INFO: 2017-06-16 09:02:57,362 Total: 9 stability orbits, lengths: ['8', '8', '8', '8', '8', '8', '8', '6', '2']
INFO: 2017-06-16 09:02:57,364 Plotting completion diagram with perturbation...
INFO: 2017-06-16 09:02:57,364 pi(0) = 0
INFO: 2017-06-16 09:02:57,364 pi is subadditive.
INFO: 2017-06-16 09:02:57,364 pi is symmetric.
INFO: 2017-06-16 09:02:57,364 Thus pi is minimal.
INFO: 2017-06-16 09:02:57,365 Uncovered intervals: ([<Int(0.3000000000000000?, 0.3500000000000000?)>, <Int(0.4500000000000000?, 0.50000000000000000?)>],)
INFO: 2017-06-16 09:02:57,367 Finding epsilon interval for perturbation...
INFO: 2017-06-16 09:02:57,371 Zero epsilon encountered for x = 0.1500000000000000?, y = 0.3250000000000000?
---------------------------------------------------------------------------
AssertionError: Epsilon should be positive, something is wrong

This is probably because any_change_moves is cleared too early.

Add more sha1 hash tests

nice_field_values: Maybe raise error if coercion fails

This could be an option.

Documentation deployment: Put key to separate branch

See sagemath/sage_sample@c26d81d

add facet_test

... mostly delegating to extremality_test, but raising NotImplementedError for cases in which we don't have an algorithm

Error on plot_2d_diagram(gomory_fractional())

Stable rainbow coloring class for components

plot_limit_cone_of_vertex (style = 'sectors')

Revise this plotting method by defining precise nonoverlapping polygons like this:

Add support for non-master corner polyhedra

Replace VERSION file by using setuptools_scm or versioneer

https://packaging.python.org/guides/single-sourcing-package-version/
https://pypi.org/project/setuptools_scm/
https://gitlab.com/BuildStream/buildstream/commit/4be462d3a43e2d32c1d2115737acefe632c48ccc
https://github.com/warner/python-versioneer
branch: setuptools_scm

Subquadratic minimality test and enumeration of additive faces

extremality_test: New option use_two_slope_theorem=True

Profile parametric.sage with polynomial rings with many variables

It seems to get very slow

Finite group problem: minimality_test, extremality_test should interpolate

... this should usually be faster than doing the computation naively!

PiecewiseCrazyFunction needs eq

Param: Add debug mode, storing backtrace with each inequality

Spaces of valid functions

Replace our RealNumberFields with embedded number fields available in current SageMath

... but we still like some of our print (and latex?) methods (but see https://trac.sagemath.org/ticket/25210 - Add option to make QQbar / AA print using radicals)
... and this certainly needs benchmarking.

Modularization

e.g. FastPiecewise should go to a separate file

Fix deployment of github documentation

problem with limiting_slopes

Hi
There seems to be a bug in limiting_slopes:

sage: limiting_slopes(gmic(f=0.66666666))
INFO: 2016-08-01 16:20:58,542 Rational case.
(50000000/33333333, -Infinity)
sage: limiting_slopes(gmic(f=0.666666666))
INFO: 2016-08-01 16:22:48,343 Rational case.
(499999997/333333331, -499999973/166666658)

Selective ticks labels

The ticks labels often overlap. Should select or make it easy to move the labels.

Random matplotlib links:

axis and tick API — Matplotlib 2.2.2 documentation
https://matplotlib.org/api/axis_api.html

python - Matplotlib showing x-tick labels overlapping despite best efforts - Stack Overflow
https://stackoverflow.com/questions/26700598/matplotlib-showing-x-tick-labels-overlapping-despite-best-efforts

python - How to move a tick's label in matplotlib? - Stack Overflow
https://stackoverflow.com/questions/28615887/how-to-move-a-ticks-label-in-matplotlib

Ticks, tick labels, and grid lines — Astropy v3.0.3
http://docs.astropy.org/en/stable/visualization/wcsaxes/ticks_labels_grid.html

Customizing Ticks | Python Data Science Handbook
https://jakevdp.github.io/PythonDataScienceHandbook/04.10-customizing-ticks.html

Overlapping tick labels on x axis · Issue #258 · aplpy/aplpy
aplpy/aplpy#258

matplotlib - Aligning rotated xticklabels with their respective xticks - Stack Overflow
https://stackoverflow.com/questions/14852821/aligning-rotated-xticklabels-with-their-respective-xticks

matplotlib - LogFormatter tickmarks scientific format limits - Stack Overflow
https://stackoverflow.com/questions/43923966/logformatter-tickmarks-scientific-format-limits

Controlling tick marks in plots - ASKSAGE: Sage Q&A Forum
https://ask.sagemath.org/question/7855/controlling-tick-marks-in-plots/

ticker — Matplotlib 2.2.2 documentation
https://matplotlib.org/api/ticker_api.html

find_epsilon should call crazy perturbation code if appropriate

Add separate doctests for all functions that are shown with examples in survey etc.

kf_n_step_mir (factory instance) missing from documentation

Add plots to extreme functions documentation

... but the .. PLOT:: directive does not work -- : (ERROR/3) Unknown directive type "PLOT".

Fix coercion in ParametricRealField and make it pass TestSuite

... do this on top of branch sage_embedded_number_fields.

Replace our coho intervals with RealSet in current sage

Add Travis builds using conda

https://docs.conda.io/projects/conda/en/latest/user-guide/tasks/use-conda-with-travis-ci.html

https://groups.google.com/d/msg/sage-devel/H9E307IWBMA/I9rXtiK7AwAJ

Implement Basu et al. "Optimal cutting planes from the group relaxations"

Optimal cutting planes from the group relaxations, (A. Basu, M. Conforti, M. Di Summa and G. Zambelli), to appear in Mathematics of Operations Research. https://arxiv.org/abs/1710.07672

multirow: which_function

example from the docstring to test which function and kept everything else the same.
hsquare.which_function(Polyhedron(vertices=[(5,1),(5,3/2),(11/2,3/2)]))
I took out the vertex argument x here and it threw an error on mod_Zk(x).
This function works when Polyhedron=None, but x cant be None.

mkoeppe / cutgeneratingfunctionology Goto Github PK

cutgeneratingfunctionology's Introduction

Authors

License

Documentation

Using the cutgeneratingfunctionology package

A. Run it online on mybinder.org

B. Install released version from PyPI and run it within conda

C. Clone from GitHub and run it within conda

D. Run in a standalone installation of the SageMath distribution (no conda)

cutgeneratingfunctionology's People

Contributors

Stargazers

Watchers

Forkers

cutgeneratingfunctionology's Issues

Recommend Projects

Recommend Topics

Recommend Org