Electronic compendium of extreme functions for the 1-row Gomory–Johnson model

Index of Extreme Functions

cutgeneratingfunctionology.igp.extreme_functions.dg_2_step_mir = ParametricFamily_dg_2_step_mir(default_values=(('f', 4/5), ('alpha', 3/10), ('field', None), ('conditioncheck', True)), names=('f', 'alpha'))
_images/extreme_functions-1.svg
Summary:
  • Name: Dash-Gunluk’s 2-Step MIR;
  • Infinite (or Finite); Dim = 1; Slopes = 2; Continuous; Simple sets method;
  • Discovered [33] p.39 def.8, Fig.5;
  • Proven extreme (for infinite group) [60] p.377, thm.3.3.
  • dg_2_step_mir is a facet.
Parameters:
  • f (real) in (0,1);
  • alpha (real) in (0,f).
Function is known to be extreme under the conditions:
  • 0 < alpha < f < 1;
  • f / alpha < ceil(f / alpha) <= 1 / alpha.

Examples: [33] p.40, Fig.5

sage: from cutgeneratingfunctionology.igp import *
sage: logging.disable(logging.INFO)             # Suppress output in automatic tests.
sage: h = dg_2_step_mir(f=4/5, alpha=3/10)
sage: extremality_test(h, False)
True
Reference:
[33]: S. Dash and O. Gunluk, Valid inequalities based on simple mixed-integer sets.,
Proceedings 10th Conference on Integer Programming and Combinatorial Optimization (D. Bienstock and G. Nemhauser, eds.), Springer-Verlag, 2004, pp. 33-45.

[60]: R.E. Gomory and E.L. Johnson, Some continuous functions related to corner polyhedra, part II, Mathematical Programming 3 (1972) 359-389.

cutgeneratingfunctionology.igp.extreme_functions.dg_2_step_mir_limit = ParametricFamily_dg_2_step_mir_limit(default_values=(('f', 3/5), ('d', 3), ('field', None)), names=('f', 'd'))
_images/extreme_functions-2.svg
Summary:
  • Name: Dash-Gunluk 2-Step MIR Limit;
  • Infinite; Dim = 1; Slopes = 1; Discontinuous; Simple sets method;
  • Discovered [33] p.41, def.12;
  • Proven extreme [33] p.43, lemma 14.
  • dg_2_step_mir_limit is a facet.
Parameters:
  • f (real) \(\in (0,1)\);
  • d (positive integer): number of slopes on [0,f).
Function is known to be extreme under the conditions:
  • 0 < f < 1;
  • d >= ceil(1 / (1 - f)) - 1.
Note:

This is the limit function as alpha in dg_2_step_mir() tends (from left) to f/d, where d is integer; cf. [33] p.42, lemma 13.

It’s a special case of drlm_2_slope_limit():

dg_2_step_mir_limit(f, d) = multiplicative_homomorphism(drlm_2_slope_limit(f=1-f, nb_pieces_left=1, nb_pieces_right=d), -1).

Examples: [33] p.42, Fig.6

sage: from cutgeneratingfunctionology.igp import *
sage: logging.disable(logging.WARN) # Suppress warning about experimental discontinuous code.
sage: h = dg_2_step_mir_limit(f=3/5, d=3)
sage: extremality_test(h, False)
True
Reference:
[33]: S. Dash and O. Gunluk, Valid inequalities based on simple mixed-integer sets.,
Proceedings 10th Conference on Integer Programming and Combinatorial Optimization (D. Bienstock and G. Nemhauser, eds.), Springer-Verlag, 2004, pp. 33-45.
cutgeneratingfunctionology.igp.extreme_functions.kf_n_step_mir = ParametricFamily_kf_n_step_mir(default_values=(('f', 4/5), ('a', (1, 3/10, 2/25)), ('field', None), ('conditioncheck', True)), names=('f', 'a'))
_images/extreme_functions-3.svg
Summary:
  • Name: Kianfar-Fathi’s n-Step MIR;
  • Infinite (or Finite); Dim = 1; Slopes = 2; Continuous; Simple sets method;
  • Discovered [74] p.328, def.3, thm.2;
  • Proven extreme (for infinite group) [60] p.377, thm.3.3.
  • (Although only extremality has been established in literature, the same proof shows that) kf_n_step_mir is a facet.
Parameters:
  • f (real) \(\in (0,1)\);
  • a (list of reals, with length = n) \(\in (0,f)\).
Function is known to be extreme under the conditions:
  • 0 < a[1] < f < 1 == a[0];
  • a[i] > 0, for i = 0, 1, … , n-1;
  • b[i - 1] / a[i] < ceil(b[i - 1] / a[i]) <= a[i - 1] / a[i], for i = 1, 2, … , n-1;
where,
  • b[0] = f;
  • b[i] = b[i - 1] - a[i] * floor(b[i - 1] / a[i]), for i = 1, 2, … , n-1.
Note:
if a[i] > b[i-1] for some i, then the kf_n_step_mir function degenerates, i.e. kf_n_step_mir(f, [a[0], .. , a[n - 1]]) = kf_n_step_mir(f, [a[0], .. a[i - 1], a[i + 1], … , a[n - 1]])

Examples: [74] p.333 - p.335, Fig.1 - Fig.6

sage: from cutgeneratingfunctionology.igp import *
sage: logging.disable(logging.INFO)             # Suppress output in automatic tests.
sage: h = kf_n_step_mir(f=4/5, a=[1])
sage: extremality_test(h, False)
True
sage: h = kf_n_step_mir(f=4/5, a=[1, 3/10])
sage: extremality_test(h, False)
True
sage: h = kf_n_step_mir(f=4/5, a=[1, 3/10, 8/100])
sage: extremality_test(h, False)
True
sage: h = kf_n_step_mir(f=4/5, a=[1, 3/10, 8/100, 3/100])
sage: extremality_test(h, False)
True
sage: h = kf_n_step_mir(f=4/5, a=[1, 45/100, 2/10, 558/10000, 11/1000])
sage: extremality_test(h, False)
True
sage: h = kf_n_step_mir(f=4/5, a=[1, 48/100, 19/100, 8/100, 32/1000, 12/1000])
sage: extremality_test(h, False)
True
Reference:

[60]: R.E. Gomory and E.L. Johnson, Some continuous functions related to corner polyhedra, part II, Mathematical Programming 3 (1972) 359-389.

[74]: K. Kianfar and Y. Fathi, Generalized mixed integer rounding valid inequalities:
Facets for infinite group polyhedra, Mathematical Programming 120 (2009) 313-346.
cutgeneratingfunctionology.igp.extreme_functions.ll_strong_fractional = ParametricFamily_ll_strong_fractional(default_values=(('f', 2/3), ('field', None), ('conditioncheck', True)), names=('f',))
_images/extreme_functions-4.svg

Letchford–Lodi’s strong fractional cut.

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: logging.disable(logging.INFO)             # Suppress output in automatic tests.
sage: h = ll_strong_fractional(f=2/3)
sage: extremality_test(h, False)
True
sage: h = ll_strong_fractional(f=2/7)
sage: minimality_test(h, False)
False
Reference:
[78] Letchford-Lodi (2002) Thm. 2, Fig. 3 (but note this figure shows the wrong function;
see ll_strong_fractional_bad_figure_3 and ll_strong_fractional_bad_figure_3_corrected)

[33] S. Dash and O. Gunluk (2004) Thm. 16

Remarks:

Discontinuous, 1-slope;

For f >= 1/2, this function is facet (extreme), and is identical to drlm_2_slope_limit(f=f, nb_pieces_left=1, nb_pieces_right=1).

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: logging.disable(logging.INFO)             # Suppress output in automatic tests.
sage: f=2/3
sage: l = ll_strong_fractional(f)
sage: d = drlm_2_slope_limit(f=f, nb_pieces_left=1, nb_pieces_right=ceil(1/f)-1)
sage: dg = automorphism(dg_2_step_mir_limit(f=1-f, d=ceil(1/f)-1))
sage: show(plot(l, color='red', legend_label='ll_strong_fractional')) # not tested
sage: show(plot(d, color='blue', legend_label='drlm_2_slope_limit')) # not tested
sage: show(plot(dg, color='green', legend_label='automorphism(dg_2_step_mir_limit)')) # not tested
sage: l == d == dg
True
Remarks:
The function is NOT minimal for 0 < f < 1/2. It equals drlm_2_slope_limit(f=f, nb_pieces_left=1, nb_pieces_right=ceil(1/f)-1), except for limits at breakpoints.

EXAMPLES:

sage: logging.disable(logging.INFO)             # Suppress output in automatic tests.
sage: f=1/3
sage: l = ll_strong_fractional(f)
sage: d = drlm_2_slope_limit(f=f, nb_pieces_left=1, nb_pieces_right=ceil(1/f)-1)
sage: dg = automorphism(dg_2_step_mir_limit(f=1-f, d=ceil(1/f)-1))
sage: show(plot(l, color='red', legend_label='ll_strong_fractional')) # not tested
sage: show(plot(d, color='blue', legend_label='drlm_2_slope_limit')) # not tested
sage: show(plot(dg, color='green', legend_label='automorphism(dg_2_step_mir_limit)')) # not tested
sage: d == dg
True
sage: l == d
False
class cutgeneratingfunctionology.igp.extreme_functions.bcds_discontinuous_everywhere
_images/extreme_functions-5.svg

An extreme function whose graph is dense in R times [0,1].

Reference:
[bcds_discontinous_everywhere] Amitabh Basu, Michele Conforti, Marco Di Summa, An extreme function which is nonnegative and discontinuous everywhere, arXiv:1802.01499 [math.OC]
plot(xmin=0, xmax=1, ymin=0, ymax=1, color=None, rgbcolor=None, aspect_ratio='automatic', thickness=None, **kwds)
cutgeneratingfunctionology.igp.extreme_functions.hildebrand_2_sided_discont_1_slope_1()
_images/extreme_functions-6.svg

The first known example of function that is discontinuous on both sides of the origin but is also extreme.

Constructed by Robert Hildebrand (2013, unpublished).

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: logging.disable(logging.INFO)             # Suppress output in automatic tests.
sage: h = hildebrand_2_sided_discont_1_slope_1()
sage: extremality_test(h, False)
True
cutgeneratingfunctionology.igp.extreme_functions.hildebrand_2_sided_discont_2_slope_1()
_images/extreme_functions-7.svg

The second known example of function that is discontinuous on both sides of the origin but is also extreme. This one has 2 slopes.

Constructed by Robert Hildebrand (2013, unpublished).

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: logging.disable(logging.INFO)             # Suppress output in automatic tests.
sage: h = hildebrand_2_sided_discont_2_slope_1()
sage: extremality_test(h, False)
True
cutgeneratingfunctionology.igp.extreme_functions.hildebrand_5_slope_22_1()
_images/extreme_functions-8.svg

One of Hildebrand’s 5-slope functions.

They held the world record regarding the number of slopes until functions with more slopes were discovered in 2014.

From Hildebrand (2013, unpublished).

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: logging.disable(logging.INFO)             # Suppress output in automatic tests.
sage: h = hildebrand_5_slope_22_1()
sage: extremality_test(h, False)
True
cutgeneratingfunctionology.igp.extreme_functions.hildebrand_5_slope_24_1()
_images/extreme_functions-9.svg

One of Hildebrand’s 5-slope functions.

They held the world record regarding the number of slopes until functions with more slopes were discovered in 2014.

From Hildebrand (2013, unpublished).

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: logging.disable(logging.INFO)             # Suppress output in automatic tests.
sage: h = hildebrand_5_slope_24_1()
sage: extremality_test(h, False)
True
cutgeneratingfunctionology.igp.extreme_functions.hildebrand_5_slope_28_1()
_images/extreme_functions-10.svg

One of Hildebrand’s 5-slope functions.

They held the world record regarding the number of slopes until functions with more slopes were discovered in 2014.

From Hildebrand (2013, unpublished).

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: logging.disable(logging.INFO)             # Suppress output in automatic tests.
sage: h = hildebrand_5_slope_28_1()
sage: extremality_test(h, False)
True
cutgeneratingfunctionology.igp.extreme_functions.hildebrand_discont_3_slope_1()
_images/extreme_functions-11.svg

This is a very new discontinuous 3-slope function that is extreme.

Constructed by Robert Hildebrand (2013, unpublished).

A detailed extremality proof appears as an example in [HKoppeZ18b].

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: logging.disable(logging.INFO)             # Suppress output in automatic tests.
sage: psi = hildebrand_discont_3_slope_1()
sage: extremality_test(psi, False)
True

In [KoppeZ17b], it is shown that this function (called \(\psi\)) is neither a weak facets nor a facet, by showing that the function ` psi’ = discontinuous_facets_paper_example_psi_prime() ` has a larger additivity domain \(E\) (sans limits):

sage: psi = hildebrand_discont_3_slope_1()
sage: E_psi = set(generate_additive_faces_sans_limits(psi))
sage: psi_prime = discontinuous_facets_paper_example_psi_prime(merge=False)
sage: E_psi_prime = set(generate_additive_faces_sans_limits(psi_prime))
sage: E_psi.issubset(E_psi_prime)
True
sage: sorted(E_psi_prime.difference(E_psi), key=lambda F: F.minimal_triple)
[<Face ([0, 1/8], [0, 1/8], [1/8])>, <Face ([0, 1/8], [0, 1/8], [1/8, 1/4])>, ...]

In fact, if one uses only the faces of \(\psi\) that are additive sans limits, then there is one covered component only; two intervals remain uncovered:

sage: show_plots=False
sage: show_plots=True      # not tested
sage: sorted(generate_covered_components_strategically(psi, show_plots=show_plots,
....:                                                  additive_faces=E_psi))
[[<Int(0, 1/8)>, <Int(3/8, 1/2)>],
 [<Int(1/8, 1/4)>, <Int(1/4, 3/8)>],
 [<Int(5/8, 3/4)>, <Int(3/4, 7/8)>]]
cutgeneratingfunctionology.igp.extreme_functions.kzh_10_slope_1()
_images/extreme_functions-12.svg

A 10-slope extreme function.

Its two-dimensional polyhedral complex includes special patterns.

This example was found by computer-based search described in Koeppe–Zhou [KZh2015a].

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: h = kzh_10_slope_1()
sage: extremality_test(h)
True

Reference:

[KZh2015a] M. Koeppe and Y. Zhou, New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem, 2015, e-print http://arxiv.org/abs/1506.00017 [math.OC].

cutgeneratingfunctionology.igp.extreme_functions.kzh_28_slope_1()
_images/extreme_functions-13.svg

A 28-slope extreme function.

This example was found by computer-based search described in Koeppe–Zhou [KZh2015a].

This was briefly the world record, until Basu, Conforti, Di Summa, and Paat gave a construction of a family of functions with an arbitrary number of slopes (see bcdsp_arbitrary_slope).

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: h = kzh_28_slope_1()
sage: number_of_slopes(h)
28
sage: extremality_test(h) # long time
True

Reference:

[KZh2015a] M. Koeppe and Y. Zhou, New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem, 2015, e-print http://arxiv.org/abs/1506.00017 [math.OC].

cutgeneratingfunctionology.igp.extreme_functions.kzh_28_slope_2()
_images/extreme_functions-14.svg

A 28-slope extreme function.

This example was found by computer-based search described in Koeppe–Zhou [KZh2015a].

This was briefly the world record, until Basu, Conforti, Di Summa, and Paat gave a construction of a family of functions with an arbitrary number of slopes (see bcdsp_arbitrary_slope).

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: h = kzh_28_slope_2()
sage: number_of_slopes(h)
28
sage: extremality_test(h) # long time
True

Reference:

[KZh2015a] M. Koeppe and Y. Zhou, New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem, 2015, e-print http://arxiv.org/abs/1506.00017 [math.OC].

cutgeneratingfunctionology.igp.extreme_functions.kzh_5_slope_fulldim_1()
_images/extreme_functions-15.svg

A continuous 5-slope extreme function without any 0-d or 1-d maximal additive faces except for the symmetry reflection or x=0 or y=0.

This example was found by computer-based search described in Koeppe–Zhou [KZh2015a].

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: h = kzh_5_slope_fulldim_1()
sage: extremality_test(h)
True
sage: uncovered_intervals_from_covered_intervals(generate_directly_covered_intervals(h))
[]

Reference:

[KZh2015a] M. Koeppe and Y. Zhou, New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem, 2015, e-print http://arxiv.org/abs/1506.00017 [math.OC].

cutgeneratingfunctionology.igp.extreme_functions.kzh_5_slope_fulldim_2()
_images/extreme_functions-16.svg

A continuous 5-slope extreme function without any 0-d or 1-d maximal additive faces except for the symmetry reflection or x=0 or y=0.

This example was found by computer-based search described in Koeppe–Zhou [KZh2015a].

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: h = kzh_5_slope_fulldim_2()
sage: extremality_test(h)
True
sage: uncovered_intervals_from_covered_intervals(generate_directly_covered_intervals(h))
[]

Reference:

[KZh2015a] M. Koeppe and Y. Zhou, New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem, 2015, e-print http://arxiv.org/abs/1506.00017 [math.OC].

cutgeneratingfunctionology.igp.extreme_functions.kzh_5_slope_fulldim_3()
_images/extreme_functions-17.svg

A continuous 5-slope extreme function without any 0-d or 1-d maximal additive faces except for the symmetry reflection or x=0 or y=0.

This example was found by computer-based search described in Koeppe–Zhou [KZh2015a].

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: h = kzh_5_slope_fulldim_3()
sage: extremality_test(h)
True
sage: uncovered_intervals_from_covered_intervals(generate_directly_covered_intervals(h))
[]

Reference:

[KZh2015a] M. Koeppe and Y. Zhou, New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem, 2015, e-print http://arxiv.org/abs/1506.00017 [math.OC].

cutgeneratingfunctionology.igp.extreme_functions.kzh_5_slope_fulldim_4()
_images/extreme_functions-18.svg

5-slope extreme function without any 0-d or 1-d maximal additive faces except for the symmetry reflection or x=0 or y=0.

This example was found by computer-based search described in Koeppe–Zhou [KZh2015a].

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: h = kzh_5_slope_fulldim_4()
sage: extremality_test(h)
True
sage: uncovered_intervals_from_covered_intervals(generate_directly_covered_intervals(h))
[]

Reference:

[KZh2015a] M. Koeppe and Y. Zhou, New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem, 2015, e-print http://arxiv.org/abs/1506.00017 [math.OC].

cutgeneratingfunctionology.igp.extreme_functions.kzh_5_slope_fulldim_5()
_images/extreme_functions-19.svg

5-slope extreme function without any 0-d or 1-d maximal additive faces except for the symmetry reflection or x=0 or y=0.

This example was found by computer-based search described in Koeppe–Zhou [KZh2015a].

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: h = kzh_5_slope_fulldim_5()
sage: extremality_test(h)
True
sage: uncovered_intervals_from_covered_intervals(generate_directly_covered_intervals(h))
[]

Reference:

[KZh2015a] M. Koeppe and Y. Zhou, New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem, 2015, e-print http://arxiv.org/abs/1506.00017 [math.OC].

cutgeneratingfunctionology.igp.extreme_functions.kzh_5_slope_fulldim_covers_1()
_images/extreme_functions-20.svg

5-slope extreme function whose extremality proof does not depend on lower-dimensional additive faces. All intervals are directly covered.

This is in contrast to hildebrand_5_slope_22_1 etc., whose extremality proof requires to translate and reflect covered intervals.

This example was found by computer-based search described in Koeppe–Zhou [KZh2015a].

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: h = kzh_5_slope_fulldim_covers_1()
sage: extremality_test(h)
True
sage: uncovered_intervals_from_covered_intervals(generate_directly_covered_intervals(h))
[]

Reference:

[KZh2015a] M. Koeppe and Y. Zhou, New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem, 2015, e-print http://arxiv.org/abs/1506.00017 [math.OC].

cutgeneratingfunctionology.igp.extreme_functions.kzh_5_slope_fulldim_covers_2()
_images/extreme_functions-21.svg

5-slope extreme function whose extremality proof does not depend on lower-dimensional additive faces. All intervals are directly covered. This is in contrast to hildebrand_5_slope_22_1 etc., whose extremality proof requires to translate and reflect covered intervals.

This example was found by computer-based search described in Koeppe–Zhou [KZh2015a].

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: h = kzh_5_slope_fulldim_covers_2()
sage: extremality_test(h)
True
sage: uncovered_intervals_from_covered_intervals(generate_directly_covered_intervals(h))
[]

Reference:

[KZh2015a] M. Koeppe and Y. Zhou, New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem, 2015, e-print http://arxiv.org/abs/1506.00017 [math.OC].

cutgeneratingfunctionology.igp.extreme_functions.kzh_5_slope_fulldim_covers_3()
_images/extreme_functions-22.svg

5-slope extreme function whose extremality proof does not depend on lower-dimensional additive faces. All intervals are directly covered. This is in contrast to hildebrand_5_slope_22_1 etc., whose extremality proof requires to translate and reflect covered intervals. This example was found by computer-based search described in Koeppe–Zhou [KZh2015a].

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: h = kzh_5_slope_fulldim_covers_3()
sage: extremality_test(h)
True
sage: uncovered_intervals_from_covered_intervals(generate_directly_covered_intervals(h))
[]

Reference:

[KZh2015a] M. Koeppe and Y. Zhou, New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem, 2015, e-print http://arxiv.org/abs/1506.00017 [math.OC].

cutgeneratingfunctionology.igp.extreme_functions.kzh_5_slope_fulldim_covers_4()
_images/extreme_functions-23.svg

5-slope extreme function whose extremality proof does not depend on lower-dimensional additive faces. All intervals are directly covered. This is in contrast to hildebrand_5_slope_22_1 etc., whose extremality proof requires to translate and reflect covered intervals. This example was found by computer-based search described in Koeppe–Zhou [KZh2015a].

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: h = kzh_5_slope_fulldim_covers_4()
sage: extremality_test(h)
True
sage: uncovered_intervals_from_covered_intervals(generate_directly_covered_intervals(h))
[]

Reference:

[KZh2015a] M. Koeppe and Y. Zhou, New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem, 2015, e-print http://arxiv.org/abs/1506.00017 [math.OC].

cutgeneratingfunctionology.igp.extreme_functions.kzh_5_slope_fulldim_covers_5()
_images/extreme_functions-24.svg

5-slope extreme function whose extremality proof does not depend on lower-dimensional additive faces. All intervals are directly covered. This is in contrast to hildebrand_5_slope_22_1 etc., whose extremality proof requires to translate and reflect covered intervals. This example was found by computer-based search described in Koeppe–Zhou [KZh2015a].

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: h = kzh_5_slope_fulldim_covers_5()
sage: extremality_test(h)
True
sage: uncovered_intervals_from_covered_intervals(generate_directly_covered_intervals(h))
[]

Reference:

[KZh2015a] M. Koeppe and Y. Zhou, New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem, 2015, e-print http://arxiv.org/abs/1506.00017 [math.OC].

cutgeneratingfunctionology.igp.extreme_functions.kzh_5_slope_fulldim_covers_6()
_images/extreme_functions-25.svg

5-slope extreme function whose extremality proof does not depend on lower-dimensional additive faces. All intervals are directly covered. This is in contrast to hildebrand_5_slope_22_1 etc., whose extremality proof requires to translate and reflect covered intervals. This example was found by computer-based search described in Koeppe–Zhou [KZh2015a].

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: h = kzh_5_slope_fulldim_covers_6()
sage: extremality_test(h)
True
sage: uncovered_intervals_from_covered_intervals(generate_directly_covered_intervals(h))
[]
cutgeneratingfunctionology.igp.extreme_functions.kzh_5_slope_q22_f10_1()
_images/extreme_functions-26.svg
cutgeneratingfunctionology.igp.extreme_functions.kzh_5_slope_q22_f10_2()
_images/extreme_functions-27.svg
cutgeneratingfunctionology.igp.extreme_functions.kzh_5_slope_q22_f10_3()
_images/extreme_functions-28.svg
cutgeneratingfunctionology.igp.extreme_functions.kzh_5_slope_q22_f10_4()
_images/extreme_functions-29.svg
cutgeneratingfunctionology.igp.extreme_functions.kzh_5_slope_q22_f2_1()
_images/extreme_functions-30.svg
cutgeneratingfunctionology.igp.extreme_functions.kzh_6_slope_1()
_images/extreme_functions-31.svg

A 6-slope extreme function.

Its two-dimensional polyhedral complex includes special patterns.

This example was found by computer-based search described in Koeppe–Zhou [KZh2015a].

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: h = kzh_6_slope_1()
sage: extremality_test(h)
True

Reference:

[KZh2015a] M. Koeppe and Y. Zhou, New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem, 2015, e-print http://arxiv.org/abs/1506.00017 [math.OC].

cutgeneratingfunctionology.igp.extreme_functions.kzh_6_slope_fulldim_covers_1()
_images/extreme_functions-32.svg

6-slope extreme function whose extremality proof does not depend on lower-dimensional additive faces. All intervals are directly covered. This is in contrast to hildebrand_5_slope_22_1 etc., whose extremality proof requires to translate and reflect covered intervals. This example was found by computer-based search described in Koeppe–Zhou [KZh2015a].

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: h = kzh_6_slope_fulldim_covers_1()
sage: extremality_test(h)
True
sage: uncovered_intervals_from_covered_intervals(generate_directly_covered_intervals(h))
[]

Reference:

[KZh2015a] M. Koeppe and Y. Zhou, New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem, 2015, e-print http://arxiv.org/abs/1506.00017 [math.OC].

cutgeneratingfunctionology.igp.extreme_functions.kzh_6_slope_fulldim_covers_2()
_images/extreme_functions-33.svg

6-slope extreme function whose extremality proof does not depend on lower-dimensional additive faces. All intervals are directly covered. This is in contrast to hildebrand_5_slope_22_1 etc., whose extremality proof requires to translate and reflect covered intervals. This example was found by computer-based search described in Koeppe–Zhou [KZh2015a].

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: h = kzh_6_slope_fulldim_covers_2()
sage: extremality_test(h)
True
sage: uncovered_intervals_from_covered_intervals(generate_directly_covered_intervals(h))
[]

Reference:

[KZh2015a] M. Koeppe and Y. Zhou, New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem, 2015, e-print http://arxiv.org/abs/1506.00017 [math.OC].

cutgeneratingfunctionology.igp.extreme_functions.kzh_6_slope_fulldim_covers_3()
_images/extreme_functions-34.svg

6-slope extreme function whose extremality proof does not depend on lower-dimensional additive faces. All intervals are directly covered. This is in contrast to hildebrand_5_slope_22_1 etc., whose extremality proof requires to translate and reflect covered intervals. This example has a similar 2d-diagram as that of kzh_6_slope_fulldim_covers_2() This example was found by computer-based search described in Koeppe–Zhou [KZh2015a].

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: h = kzh_6_slope_fulldim_covers_3()
sage: extremality_test(h)
True
sage: uncovered_intervals_from_covered_intervals(generate_directly_covered_intervals(h))
[]

Reference:

[KZh2015a] M. Koeppe and Y. Zhou, New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem, 2015, e-print http://arxiv.org/abs/1506.00017 [math.OC].

cutgeneratingfunctionology.igp.extreme_functions.kzh_6_slope_fulldim_covers_4()
_images/extreme_functions-35.svg
_images/extreme_functions-36.svg

6-slope extreme function whose extremality proof does not depend on lower-dimensional additive faces. All intervals are directly covered. This is in contrast to hildebrand_5_slope_22_1 etc., whose extremality proof requires to translate and reflect covered intervals. This example has a similar 2d-diagram as that of kzh_6_slope_fulldim_covers_2() This example was found by computer-based search described in Koeppe–Zhou [KZh2015a].

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: h = kzh_6_slope_fulldim_covers_4()
sage: extremality_test(h)
True
sage: uncovered_intervals_from_covered_intervals(generate_directly_covered_intervals(h))
[]

Reference:

[KZh2015a] M. Koeppe and Y. Zhou, New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem, 2015, e-print http://arxiv.org/abs/1506.00017 [math.OC].

cutgeneratingfunctionology.igp.extreme_functions.kzh_6_slope_fulldim_covers_5()
_images/extreme_functions-37.svg
_images/extreme_functions-38.svg

6-slope extreme function whose extremality proof does not depend on lower-dimensional additive faces. All intervals are directly covered. This is in contrast to hildebrand_5_slope_22_1 etc., whose extremality proof requires to translate and reflect covered intervals. This example has a similar 2d-diagram as that of kzh_6_slope_fulldim_covers_2() This example was found by computer-based search described in Koeppe–Zhou [KZh2015a].

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: h = kzh_6_slope_fulldim_covers_5()
sage: extremality_test(h)
True
sage: uncovered_intervals_from_covered_intervals(generate_directly_covered_intervals(h))
[]

Reference:

[KZh2015a] M. Koeppe and Y. Zhou, New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem, 2015, e-print http://arxiv.org/abs/1506.00017 [math.OC].

cutgeneratingfunctionology.igp.extreme_functions.kzh_7_slope_1()
_images/extreme_functions-39.svg

A 7-slope extreme function.

This example was found by computer-based search described in Koeppe–Zhou [KZh2015a].

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: h = kzh_7_slope_1()
sage: extremality_test(h)
True

Reference:

[KZh2015a] M. Koeppe and Y. Zhou, New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem, 2015, e-print http://arxiv.org/abs/1506.00017 [math.OC].

cutgeneratingfunctionology.igp.extreme_functions.kzh_7_slope_2()
_images/extreme_functions-40.svg

A 7-slope extreme function.

This example was found by computer-based search described in Koeppe–Zhou [KZh2015a].

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: h = kzh_7_slope_2()
sage: extremality_test(h)
True

Reference:

[KZh2015a] M. Koeppe and Y. Zhou, New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem, 2015, e-print http://arxiv.org/abs/1506.00017 [math.OC].

cutgeneratingfunctionology.igp.extreme_functions.kzh_7_slope_3()
_images/extreme_functions-41.svg

A 7-slope extreme function.

This example was found by computer-based search described in Koeppe–Zhou [KZh2015a].

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: h = kzh_7_slope_3()
sage: extremality_test(h)
True

Reference:

[KZh2015a] M. Koeppe and Y. Zhou, New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem, 2015, e-print http://arxiv.org/abs/1506.00017 [math.OC].

cutgeneratingfunctionology.igp.extreme_functions.kzh_7_slope_4()
_images/extreme_functions-42.svg

A 7-slope extreme function.

This example was found by computer-based search described in Koeppe–Zhou [KZh2015a].

EXAMPLES:

sage: from cutgeneratingfunctionology.igp import *
sage: h = kzh_7_slope_4()
sage: extremality_test(h)
True

Reference:

[KZh2015a] M. Koeppe and Y. Zhou, New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem, 2015, e-print http://arxiv.org/abs/1506.00017 [math.OC].

class cutgeneratingfunctionology.igp.extreme_functions.kzh_extreme_and_weak_facet_but_not_facet(pi=None)
_images/extreme_functions-43.svg

An extreme function and weak facet that is not a facet.

This factory class generates a fresh function from an infinite family. The function depends on the sequence of its evaluations.

TESTS:

sage: from cutgeneratingfunctionology.igp import *
sage: logging.disable(logging.INFO)
sage: h = kzh_extreme_and_weak_facet_but_not_facet()
sage: hm = kzh_minimal_has_only_crazy_perturbation_1()+1/1000000*kzh_minimal_has_only_crazy_perturbation_1_perturbation()
sage: minimality_test_randomized(h, kzh_minimal_has_only_crazy_perturbation_1(), hm,
....:                            limits=False, extra_cosets=[sqrt(3), -sqrt(3)],
....:                            max_iterations=10)
True
Reference:
Matthias Koeppe, Yuan Zhou. On the notions of facets, weak facets, and extreme functions of the Gomory-Johnson infinite group problem.
is_in_C(x)
is_in_Cplus(x)
is_in_T(x)
plot(*args, **kwds)
cutgeneratingfunctionology.igp.extreme_functions.mlr_cpl3_a_2_slope(r0=3/13, z1=3/26, field=None, conditioncheck=True)
_images/extreme_functions-44.svg
Summary:
  • The group representation of the continuous piecewise linear lifting (CPL) function.
  • Infinity; Dim = 1; Slopes = 2 ; Continuous.
  • Discovered [1] p.179, Table 3, Ext. pnt a.
  • Proven extreme p.188, thm.19.
Parameters:
  • 0 < r0 (real) < 1,
  • 0 < z1 (real) <= (1-r0)/4
Function is known to be extreme under the conditions:
  • 0 < r0 < 1,
  • 0 <= z1 < 1
Note:
Parameter z1 is not actually used. Same as gmic(f=r0).
Examples:

page 183, Fig 2, point a:

sage: from cutgeneratingfunctionology.igp import *
sage: logging.disable(logging.INFO) # Suppress output in automatic tests.
sage: h = mlr_cpl3_a_2_slope(r0=3/13, z1=3/26)
sage: extremality_test(h)
True
sage: phi = cpl3_function(r0=3/13, z1=3/26, o1=3/20, o2=3/20)
sage: fn = group_function_from_superadditive_lifting_function(phi)
sage: h == fn
True
sage: h == gmic(f=3/13)
True
Reference:
  • [1] L. A. Miller, Y. Li, and J.-P. P. Richard, New Inequalities for Finite and Infinite Group Problems from Approximate Lifting, Naval Research Logistics 55 (2008), no.2, 172-191, doi:10.1002/nav.20275
cutgeneratingfunctionology.igp.extreme_functions.mlr_cpl3_b_3_slope(r0=3/26, z1=1/13, field=None, conditioncheck=True)
_images/extreme_functions-45.svg
Summary:
  • The group representation of the continuous piecewise linear lifting (CPL) function.
  • Infinity; Dim = 1; Slopes = 3 ; Continuous.
  • Discovered [1] p.179, Table 3, Ext. pnt b.
  • Proven extreme p.188, thm.19.
Parameters:
  • 0 < r0 (real) < 1,
  • 0 < z1 (real) <= (1-r0)/4.
Function is known to be extreme under the conditions:
  • 3*r0 + 8*z1 <= 1
Note:
  • When z1 = (1-r0)/4, the function is the same as gmic(f=r0).
  • mlr_cpl3_b_3_slope(r0,z1) is the same as drlm_backward_3_slope(f=r0,bkpt=r0+2*z1).
Examples:

page 183, Fig 2, point b:

sage: from cutgeneratingfunctionology.igp import *
sage: logging.disable(logging.INFO) # Suppress output in automatic tests.
sage: h1 = mlr_cpl3_b_3_slope(r0=3/26, z1=1/13)
sage: extremality_test(h1)
True
sage: phi = cpl3_function(r0=3/26, z1=1/13, o1=7/58, o2=7/58)
sage: fn = group_function_from_superadditive_lifting_function(phi)
sage: h1 == fn
True
sage: h2 = drlm_backward_3_slope(f=3/26,bkpt=7/26)
sage: extremality_test(h2)
True
sage: h1 == h2
True
sage: h3 = mlr_cpl3_b_3_slope(r0=3/26, z1=23/104, conditioncheck=False)
sage: h3 == gmic(f=3/26)
True
Reference:
  • [1] L. A. Miller, Y. Li, and J.-P. P. Richard, New Inequalities for Finite and Infinite Group Problems from Approximate Lifting, Naval Research Logistics 55 (2008), no.2, 172-191, doi:10.1002/nav.20275
cutgeneratingfunctionology.igp.extreme_functions.mlr_cpl3_c_3_slope(r0=5/24, z1=1/12, field=None, conditioncheck=True)
_images/extreme_functions-46.svg
Summary:
  • The group representation of the continuous piecewise linear lifting (CPL) function.
  • Infinity; Dim = 1; Slopes = 3 ; Continuous.
  • Discovered [1] p.179, Table 3, Ext. pnt c.
  • Proven extreme p.188, thm.19.
Parameters:
  • 0 < r0 (real) < 1,
  • 0 < z1 (real) <= (1-r0)/4
Function is known to be extreme under the conditions:
  • 3*r0 + 4*z1 <= 1
Note:
  • mlr_cpl3_c_3_slope(r0,z1) is the same as drlm_backward_3_slope(f=r0,bkpt=r0+z1).
Examples:

page 183, Fig 2, point c:

sage: from cutgeneratingfunctionology.igp import *
sage: logging.disable(logging.INFO) # Suppress output in automatic tests.
sage: h1 = mlr_cpl3_c_3_slope(r0=5/24, z1=1/12)
sage: extremality_test(h1)
True
sage: phi = cpl3_function(r0=5/24, z1=1/12, o1=7/29, o2=2/29)
sage: fn = group_function_from_superadditive_lifting_function(phi)
sage: h1 == fn
True
sage: h2 = drlm_backward_3_slope(f=5/24,bkpt=7/24)
sage: extremality_test(h2)
True
sage: h1 == h2
True
Reference:
  • [1] L. A. Miller, Y. Li, and J.-P. P. Richard, New Inequalities for Finite and Infinite Group Problems from Approximate Lifting, Naval Research Logistics 55 (2008), no.2, 172-191, doi:10.1002/nav.20275
cutgeneratingfunctionology.igp.extreme_functions.mlr_cpl3_d_3_slope(r0=1/6, z1=None, field=None, conditioncheck=True)
_images/extreme_functions-47.svg
Summary:
  • The group representation of the continuous piecewise linear lifting (CPL) function.
  • Infinity; Dim = 1; Slopes = 3 ; Continuous.
  • Discovered [1] p.179, Table 3, Ext. pnt d.
  • Proven extreme p.188, thm.19.
Parameters:
  • 0 < r0 (real) < 1,
  • 0 < z1 (real) <= (1-r0)/4
Function is known to be extreme under the conditions:
  • r0 = 2*z1,
  • r0 + 8*z1 <= 1
Note:
  • multiplicative_homomorphism(mlr_cpl3_d_3_slope(r0, z1=2*r0), -1) is the same as gj_forward_3_slope(f=1-r0, lambda_1=2*z1/(1-r0), lambda_2=z1/r0);
  • gj_forward_3_slope being extreme only requires: r0 >= z1, r0 + 4*z1 <= 1.
Examples:

p.183, Fig 2, point d1:

sage: from cutgeneratingfunctionology.igp import *
sage: logging.disable(logging.INFO) # Suppress output in automatic tests.
sage: h1 = mlr_cpl3_d_3_slope(r0=1/6, z1=1/12)
sage: extremality_test(h1)
True
sage: phi = cpl3_function(r0=1/6, z1=1/12, o1=1/5, o2=0) 
sage: fn1 = group_function_from_superadditive_lifting_function(phi)
sage: h1 == fn1
True
sage: h2 = mlr_cpl3_d_3_slope(r0=1/6, z1=5/24, conditioncheck=False)
sage: extremality_test(h2)
False
sage: phi = cpl3_function(r0=1/6, z1=5/24, o1=7/20, o2=3/20)
sage: fn2 = group_function_from_superadditive_lifting_function(phi)
sage: h2 == fn2
True
Reference:
  • [1] L. A. Miller, Y. Li, and J.-P. P. Richard, New Inequalities for Finite and Infinite Group Problems from Approximate Lifting, Naval Research Logistics 55 (2008), no.2, 172-191, doi:10.1002/nav.20275
cutgeneratingfunctionology.igp.extreme_functions.mlr_cpl3_f_2_or_3_slope(r0=1/6, z1=None, field=None, conditioncheck=True)
_images/extreme_functions-48.svg
Summary:
  • The group representation of the continuous piecewise linear lifting (CPL) function.
  • Infinity; Dim = 1; Slopes = 2 or 3; Continuous.
  • Discovered [1] p.179, Table 3, Ext. pnt f.
  • Proven extreme p.188, thm.19.
Parameters:
  • 0 < r0 (real) < 1,
  • 0 < z1 (real) <= (1-r0)/4
Function is known to be extreme under the conditions:
  • r0 <= z1,
  • r0 + 5*z1 = 1
Note:
When z1 = (1-r0)/4, the function is the same as gmic(f=r0).
Examples:

page 184, Fig 3, point f1 and f2:

sage: from cutgeneratingfunctionology.igp import *
sage: logging.disable(logging.INFO) # Suppress output in automatic tests.
sage: h1 = mlr_cpl3_f_2_or_3_slope(r0=1/6, z1=1/6)
sage: extremality_test(h1, f=1/6)
True
sage: phi = cpl3_function(r0=1/6, z1=1/6, o1=1/3, o2=0) 
sage: fn = group_function_from_superadditive_lifting_function(phi, f=1/6)
sage: h1 == fn
True
sage: h2 = mlr_cpl3_f_2_or_3_slope(r0=3/23, z1=4/23)
sage: extremality_test(h2)
True
sage: h3 = mlr_cpl3_f_2_or_3_slope(r0=3/23, z1=5/23, conditioncheck=False)
sage: h3 == gmic(f=3/23)
True
Reference:
  • [1] L. A. Miller, Y. Li, and J.-P. P. Richard, New Inequalities for Finite and Infinite Group Problems from Approximate Lifting, Naval Research Logistics 55 (2008), no.2, 172-191, doi:10.1002/nav.20275
cutgeneratingfunctionology.igp.extreme_functions.mlr_cpl3_g_3_slope(r0=1/12, z1=None, field=None, conditioncheck=True)
_images/extreme_functions-49.svg
Summary:
  • The group representation of the continuous piecewise linear lifting (CPL) function.
  • Infinity; Dim = 1; Slopes = 3 ; Continuous.
  • Discovered [1] p.179, Table 3, Ext. pnt g.
  • Proven extreme p.188, thm.19.
Parameters:
  • 0 < r0 (real) < 1,
  • 0 < z1 (real) <= (1-r0)/4
Function is known to be extreme under the conditions:
  • r0 < z1,
  • 2*r0 + 4*z1 = 1
Examples:

page 184, Fig 3, point g:

sage: from cutgeneratingfunctionology.igp import *
sage: logging.disable(logging.INFO) # Suppress output in automatic tests.
sage: h1 = mlr_cpl3_g_3_slope(r0=1/12, z1=5/24)
sage: extremality_test(h1)
True
sage: phi = cpl3_function(r0=1/12, z1=5/24, o1=5/18, o2=1/6)
sage: fn1 = group_function_from_superadditive_lifting_function(phi)
sage: h1 == fn1
True
sage: h2 = mlr_cpl3_g_3_slope(r0=1/12, z1=11/48, conditioncheck=False)
sage: extremality_test(h2)
False
sage: phi = cpl3_function(r0=1/12, z1=11/48, o1=11/36, o2=7/36)
sage: fn2 = group_function_from_superadditive_lifting_function(phi)
sage: h2 == fn2
True
Reference:
  • [1] L. A. Miller, Y. Li, and J.-P. P. Richard, New Inequalities for Finite and Infinite Group Problems from Approximate Lifting, Naval Research Logistics 55 (2008), no.2, 172-191, doi:10.1002/nav.20275
cutgeneratingfunctionology.igp.extreme_functions.mlr_cpl3_h_2_slope(r0=1/4, z1=1/6, field=None, conditioncheck=True)
_images/extreme_functions-50.svg
Summary:
  • The group representation of the continuous piecewise linear lifting (CPL) function.
  • Infinity; Dim = 1; Slopes = 2 ; Continuous.
  • Discovered [1] p.179, Table 3, Ext. pnt h.
  • Proven extreme p.188, thm.19.
Parameters:
  • 0 < r0 (real) < 1,
  • 0 < z1 (real) <= (1-r0)/4
Function is known to be extreme under the conditions:
  • r0 + 4*z1 <= 1 < 2*r0 + 4*z1
Note:
When z1 = (1-r0)/4, the function is the same as gmic(f=r0).
Examples:

page 183, Fig 2, point h:

sage: from cutgeneratingfunctionology.igp import *
sage: logging.disable(logging.INFO) # Suppress output in automatic tests.
sage: h1 = mlr_cpl3_h_2_slope(r0=1/4, z1=1/6)
sage: extremality_test(h1)
True
sage: phi = cpl3_function(r0=1/4, z1=1/6, o1=1/4, o2=1/4) 
sage: fn = group_function_from_superadditive_lifting_function(phi)
sage: h1 == fn
True
sage: h2 = mlr_cpl3_h_2_slope(r0=1/4, z1=3/16)
sage: h2 == gmic(f=1/4)
True
Reference:
  • [1] L. A. Miller, Y. Li, and J.-P. P. Richard, New Inequalities for Finite and Infinite Group Problems from Approximate Lifting, Naval Research Logistics 55 (2008), no.2, 172-191, doi:10.1002/nav.20275
cutgeneratingfunctionology.igp.extreme_functions.mlr_cpl3_k_2_slope(r0=7/27, z1=4/27, field=None, conditioncheck=True)
_images/extreme_functions-51.svg
Summary:
  • The group representation of the continuous piecewise linear lifting (CPL) function.
  • Infinity; Dim = 1; Slopes = 2 ; Continuous.
  • Discovered [1] p.179, Table 3, Ext. pnt k.
  • Proven extreme p.188, thm.19.
Parameters:
  • 0 < r0 (real) < 1,
  • 0 < z1 (real) <= (1-r0)/4
Function is known to be extreme under the conditions:
  • r0 <= 2*z1,
  • r0 + 5*z1 = 1
Examples:

page 185, Fig 4, point k1:

sage: from cutgeneratingfunctionology.igp import *
sage: logging.disable(logging.INFO) # Suppress output in automatic tests.
sage: h = mlr_cpl3_k_2_slope(r0=7/27, z1=4/27)
sage: extremality_test(h)
True
sage: phi = cpl3_function(r0=7/27, z1=4/27, o1=1/3, o2=0) 
sage: fn = group_function_from_superadditive_lifting_function(phi)
sage: h == fn
True
Reference:
  • [1] L. A. Miller, Y. Li, and J.-P. P. Richard, New Inequalities for Finite and Infinite Group Problems from Approximate Lifting, Naval Research Logistics 55 (2008), no.2, 172-191, doi:10.1002/nav.20275
cutgeneratingfunctionology.igp.extreme_functions.mlr_cpl3_l_2_slope(r0=8/25, z1=None, field=None, conditioncheck=True)
_images/extreme_functions-52.svg
Summary:
  • The group representation of the continuous piecewise linear lifting (CPL) function.
  • Infinity; Dim = 1; Slopes = 2 ; Continuous.
  • Discovered [1] p.179, Table 3, Ext. pnt l.
  • Proven extreme p.188, thm.19.
Parameters:
  • 0 < r0 (real) < 1,
  • 0 < z1 (real) <= (1-r0)/4
Function is known to be extreme under the conditions:
  • r0 = 2*z1,
  • 6*z1 <= 1 < 7*z1
Note:
There is a typo in one of the given slopes [1] p.179, Table 3, Ext. pnt l, s3. The given slope is -4*z1/(2*z1-4*z1*r0) while the correct slope is (1-4*z1)/(2*z1-4*z1*r0).
Examples:

page 185, Fig 4, point l:

sage: from cutgeneratingfunctionology.igp import *
sage: logging.disable(logging.INFO) # Suppress output in automatic tests.
sage: h1 = mlr_cpl3_l_2_slope(r0=8/25, z1=4/25)
sage: extremality_test(h1)
True 
sage: phi = cpl3_function(8/25,4/25,4/9,0)
sage: fn1 = group_function_from_superadditive_lifting_function(phi)
sage: h1 == fn1
True
sage: h2 = mlr_cpl3_l_2_slope(r0=8/25, z1=17/100, conditioncheck=False)
sage: extremality_test(h2)
False
sage: phi = cpl3_function(r0=8/25, z1=17/100, o1=17/36, o2=1/36)
sage: fn2 = group_function_from_superadditive_lifting_function(phi)
sage: h2 == fn2
True
Reference:
  • [1] L. A. Miller, Y. Li, and J.-P. P. Richard, New Inequalities for Finite and Infinite Group Problems from Approximate Lifting, Naval Research Logistics 55 (2008), no.2, 172-191, doi:10.1002/nav.20275
cutgeneratingfunctionology.igp.extreme_functions.mlr_cpl3_n_3_slope(r0=9/25, z1=2/25, field=None, conditioncheck=True)
_images/extreme_functions-53.svg
Summary:
  • The group representation of the continuous piecewise linear lifting (CPL) function.
  • Infinity; Dim = 1; Slopes = 3 ; Continuous.
  • Discovered [1] p.179, Table 3, Ext. pnt n.
  • Proven extreme p.188, thm.19.
Parameters:
  • 0 < r0 (real) < 1,
  • 0 < z1 (real) <= (1-r0)/4
Function is known to be extreme under the conditions:
  • r0 > 2*z1,
  • r0 + 8*z1 <= 1
Note:
  • multiplicative_homomorphism( mlr_cpl3_n_3_slope(r0, z1), -1) == gj_forward_3_slope(f=1-r0, lambda_1=4*z1/(1-r0), lambda_2=2*z1/r0);
  • gj_forward_3_slope being extreme only requires: r0 >= z1, r0 + 4*z1 <= 1.
Examples:

page 185, Fig 4, point n2:

sage: from cutgeneratingfunctionology.igp import *
sage: logging.disable(logging.INFO) # Suppress output in automatic tests.
sage: h1 = mlr_cpl3_n_3_slope(r0=9/25, z1=2/25)
sage: extremality_test(h1)
True
sage: phi = cpl3_function(r0=9/25, z1=2/25, o1=1/4, o2=0) 
sage: fn1 = group_function_from_superadditive_lifting_function(phi)
sage: h1 == fn1
True
sage: h2 = mlr_cpl3_n_3_slope(r0=9/25, z1=4/25, conditioncheck=False)
sage: extremality_test(h2)
True
sage: phi = cpl3_function(r0=9/25, z1=4/25, o1=1/2, o2=0)
sage: fn2 = group_function_from_superadditive_lifting_function(phi)
sage: h2 == fn2
True
Reference:
  • [1] L. A. Miller, Y. Li, and J.-P. P. Richard, New Inequalities for Finite and Infinite Group Problems from Approximate Lifting, Naval Research Logistics 55 (2008), no.2, 172-191, doi:10.1002/nav.20275
cutgeneratingfunctionology.igp.extreme_functions.mlr_cpl3_o_2_slope(r0=3/8, z1=None, field=None, conditioncheck=True)
_images/extreme_functions-54.svg
Summary:
  • The group representation of the continuous piecewise linear lifting (CPL) function.
  • Infinity; Dim = 1; Slopes = 2 ; Continuous.
  • Discovered [1] p.179, Table 3, Ext. pnt o.
  • Proven extreme p.188, thm.19.
Parameters:
  • 0 < r0 (real) < 1,
  • 0 < z1 (real) <= (1-r0)/4
Function is known to be extreme under the conditions:
  • r0 >= 2*z1,
  • 2*r0 + 2*z1 = 1
Examples:

page 186, Fig 5, point o:

sage: from cutgeneratingfunctionology.igp import *
sage: logging.disable(logging.INFO) # Suppress output in automatic tests.
sage: h1 = mlr_cpl3_o_2_slope(r0=3/8, z1=1/8)
sage: extremality_test(h1, f=3/8)
True
sage: phi = cpl3_function(r0=3/8, z1=1/8, o1=1/2, o2=0) 
sage: fn1 = group_function_from_superadditive_lifting_function(phi)
sage: h1 == fn1
True
sage: h2 = mlr_cpl3_o_2_slope(r0=2/8, z1=3/16,conditioncheck=False)
sage: extremality_test(h2)
False
sage: phi = cpl3_function(r0=2/8, z1=3/16, o1=3/8, o2=1/8)
sage: fn2 = group_function_from_superadditive_lifting_function(phi)
sage: h2 == fn2
True
Reference:
  • [1] L. A. Miller, Y. Li, and J.-P. P. Richard, New Inequalities for Finite and Infinite Group Problems from Approximate Lifting, Naval Research Logistics 55 (2008), no.2, 172-191, doi:10.1002/nav.20275
cutgeneratingfunctionology.igp.extreme_functions.mlr_cpl3_p_2_slope(r0=5/12, z1=None, field=None, conditioncheck=True)
_images/extreme_functions-55.svg
Summary:
  • The group representation of the continuous piecewise linear lifting (CPL) function.
  • Infinity; Dim = 1; Slopes = 2 ; Continuous.
  • Discovered [1] p.179, Table 3, Ext. pnt p.
  • Proven extreme p.188, thm.19.
Parameters:
  • 0 < r0 (real) < 1,
  • 0 < z1 (real) <= (1-r0)/4
Function is known to be extreme under the conditions:
  • r0 > 2*z1,
  • 2*r0 + 2*z1 = 1
Note:
There is a typo in one of the given slopes [1] p.179, Table 3, Ext. pnt p, s4. The given slope is (2*z1-10*z1*r0+r0)/(r0*(1-2*r0)*(4*z1-1+r0)) while the correct slope is (-r0+2*r0^2-2*z1+8*z1*r0)/(r0*(1-2*r0)*(1-r0-4*z1)).
Examples:

page 186, Fig 5, point p1 and p2:

sage: from cutgeneratingfunctionology.igp import *
sage: logging.disable(logging.INFO) # Suppress output in automatic tests.
sage: h1 = mlr_cpl3_p_2_slope(r0=5/12, z1=1/12)
sage: extremality_test(h1, f=5/12)
True
sage: phi = cpl3_function(r0=5/12, z1=1/12, o1=1/2, o2=0)
sage: fn = group_function_from_superadditive_lifting_function(phi)
sage: h1 == fn
True
sage: h2 = mlr_cpl3_p_2_slope(r0=7/21, z1=1/6, conditioncheck=False)
sage: extremality_test(h2, f=1/3)
True
sage: phi = cpl3_function(r0=7/21, z1=1/6, o1=1/2, o2=0)
sage: fn2 = group_function_from_superadditive_lifting_function(phi)
sage: h2 == fn2
True
Reference:
  • [1] L. A. Miller, Y. Li, and J.-P. P. Richard, New Inequalities for Finite and Infinite Group Problems from Approximate Lifting, Naval Research Logistics 55 (2008), no.2, 172-191, doi:10.1002/nav.20275
cutgeneratingfunctionology.igp.extreme_functions.mlr_cpl3_q_2_slope(r0=5/12, z1=1/8, field=None, conditioncheck=True)
_images/extreme_functions-56.svg
Summary:
  • The group representation of the continuous piecewise linear lifting (CPL) function.
  • Infinity; Dim = 1; Slopes = 2 ; Continuous.
  • Discovered [1] p.179, Table 3, Ext. pnt q.
  • Proven extreme p.188, thm.19.
Parameters:
  • 0 < r0 (real) < 1,
  • 0 < z1 (real) <= (1-r0)/4
Function is known to be extreme under the conditions:
  • r0 > 2*z1,
  • r0+4*z1 <= 1 < r0+5*z1
Examples:

page 186, Fig 5, point q:

sage: from cutgeneratingfunctionology.igp import *
sage: logging.disable(logging.INFO) # Suppress output in automatic tests.
sage: h1 = mlr_cpl3_q_2_slope(r0=5/12, z1=3/24)
sage: extremality_test(h1)
True
sage: phi = cpl3_function(r0=5/12, z1=3/24, o1=3/8, o2=0) 
sage: fn1 = group_function_from_superadditive_lifting_function(phi)
sage: h1 == fn1
True
sage: h2 = mlr_cpl3_q_2_slope(r0=5/12, z1=7/48,conditioncheck=False)
sage: extremality_test(h2)
True
sage: phi = cpl3_function(r0=5/12, z1=7/48, o1=1/2, o2=0)
sage: fn2 = group_function_from_superadditive_lifting_function(phi)
sage: h2 == fn2
True
Reference:
  • [1] L. A. Miller, Y. Li, and J.-P. P. Richard, New Inequalities for Finite and Infinite Group Problems from Approximate Lifting, Naval Research Logistics 55 (2008), no.2, 172-191, doi:10.1002/nav.20275
cutgeneratingfunctionology.igp.extreme_functions.mlr_cpl3_r_2_slope(r0=3/7, z1=1/7, field=None, conditioncheck=True)
_images/extreme_functions-57.svg
Summary:
  • The group representation of the continuous piecewise linear lifting (CPL) function.
  • Infinity; Dim = 1; Slopes = 2 ; Continuous.
  • Discovered [1] p.179, Table 3, Ext. pnt r.
  • Proven extreme p.188, thm.19.
Parameters:
  • 0 < r0 (real) < 1,
  • 0 < z1 (real) <= (1-r0)/4
Function is known to be extreme under the conditions:
  • r0 > 2*z1,
  • r0+4*z1 <= 1 <= 2*r0+2*z1
Examples:

page 185, Fig , point r:

sage: from cutgeneratingfunctionology.igp import *
sage: logging.disable(logging.INFO) # Suppress output in automatic tests.
sage: h = mlr_cpl3_r_2_slope(r0=3/7, z1=1/7)
sage: extremality_test(h)
True 
sage: phi = cpl3_function(r0=3/7, z1=1/7, o1=1/2, o2=0) 
sage: fn = group_function_from_superadditive_lifting_function(phi)
sage: h == fn
True
Reference:
  • [1] L. A. Miller, Y. Li, and J.-P. P. Richard, New Inequalities for Finite and Infinite Group Problems from Approximate Lifting, Naval Research Logistics 55 (2008), no.2, 172-191, doi:10.1002/nav.20275