Sage 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
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
docs
multirow
old_examples
survey_graphics
.check-long-timings.json
.gitignore
.travis-deploy-doc.sh
.travis-install.sh
.travis-test.sh
.travis.yml
.travis_ci_gh_pages_deploy_key.enc
2q_mip.sage
AUTHORS.rst
Gomory_conversion.sage
Makefile
README.rst
THANKS.rst
VERSION
animation_2d_diagram.sage
attach_all.sage
bug_examples.sage
compendium_procedures.sage
computer_based_search_naive_dff.sage
continuous_case.sage
crazy_perturbation.sage
crazy_perturbation_examples.sage
demo.sage
dff_functions.sage
dff_graphics.sage
dff_test_plot.sage
discontinuous_case.sage
discontinuous_dff.sage
discrete_case.sage
extreme_functions.py
extreme_functions_in_literature.sage
extreme_functions_mlr_cpl3.sage
extreme_functions_sporadic.sage
fast_linear.sage
functions.sage
gdff_linear_test.sage
igp.py
intervals.sage
kslope_mip.sage
kslope_pattern.sage
kslope_ppl_mip.py
lifting_project.sage
lifting_project_debug.sage
lifting_region.sage
logging.sage
old_walk_and_stability_interval_code.sage
param_icms_abstract_examples.sage
parametric.sage
parametric_cpl.sage
parametric_linear_independence.sage
piecewise_functions.sage
plot_options.sage
procedures.py
quasi_periodic.sage
real_number_field.sage
sage_version.py
semialgebraic_mathematica.sage
show_plot_zoom.sage
simple_extremality_test.sage
survey_examples.sage
vertex_enumeration.py

README.rst

cutgeneratingfunctionology

This is Sage code for computation and experimentation with cut-generating functions.

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

See the survey "Light on the Infinite Group Relaxation" (http://www.optimization-online.org/DB_HTML/2014/10/4620.html) for the mathematical background and a table of functions in the electronic compendium. See also the paper "An electronic compendium of extreme functions for the Gomory--Johnson infinite group problem" (http://www.optimization-online.org/DB_HTML/2014/11/4646.html) for a discussion of several functions in the compendium.

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

Authors

See file AUTHORS.rst and also 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.

How to run the code in a local copy of Sage

  1. Install Sage from http://www.sagemath.org/

  2. Download the code from https://github.com/mkoeppe/cutgeneratingfunctionology.git

  3. From the directory cutgeneratingfunctionology, start Sage. You can either use the terminal or the worksheet.

  4. At the Sage prompt, type:

    import igp; from igp import *
    
  5. Follow the instructions and examples in demo.sage.

How to run the code online via cloud.sagemath.com

  1. Create a user account at https://cloud.sagemath.com

  2. Log in at https://cloud.sagemath.com

  3. Create a new project "Group relaxation" (or any name)

  4. Open the project

  5. Create a directory: Paste in the weblink: https://github.com/mkoeppe/cutgeneratingfunctionology.git and hit enter

  6. Enter that directory

  7. Click "+ New", select "Sage worksheet"

  8. Type:

    import igp; from igp import *
    

    and hit shift+enter

  9. Follow the instructions and examples in demo.sage.

To update the code to the latest version:

  1. In the project "Group relaxation", open the directory "cutgeneratingfunctionology".

  2. In the line "Terminal command...", enter:

    git pull