-
Notifications
You must be signed in to change notification settings - Fork 0
/
demo.sage
199 lines (153 loc) · 6.01 KB
/
demo.sage
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
## Demonstration of how to use infinite-group-relaxation-code.
##
## We interact with Sage using commands that basically follow standard
## Python syntax.
##
## See http://www.sagemath.org/doc/tutorial/ for information on how to use Sage.
##
## Copy these commands into your Sage terminal session or notebook session.
## First load the code.
import igp; from igp import *
## First we load a function and store it in variable h.
##
## The functions are defined in the file
## extreme_functions_in_literature.sage
##
## Additional functions are defined in the file
## survey_examples.sage
##
## We start with the easiest function, the GMIC.
h = gmic()
## Plot the function.
plot_with_colored_slopes(h)
## Test its extremality; this will create informative output and
## plots.
extremality_test(h, show_plots=True)
## The documentation string of each function reveals its optional
## arguments, usage examples, and bibliographic information.
gmic?
## The docstring tells us that we can set the `f' value using an
## optional argument.
h = gmic(1/5)
## Of course, we know it will still be extreme; but let's test it to
## see all the informative graphs.
extremality_test(h, show_plots=True)
## Let's learn about a different function.
## It's from Dey--Richard--Li--Milller -- hence the prefix of the function.
drlm_backward_3_slope?
## Let's change the parameters a little bit, so that they do NOT
## satisfy the known sufficient conditions from the literature about
## this class of functions.
h = drlm_backward_3_slope(f=1/12, bkpt=4/12)
## Let's run the extremality test.
extremality_test(h, show_plots=True)
## Indeed, it's not extreme. We see a perturbation in magenta and the
## two perturbed functions in blue and red, whose average is the
## original function (black).
## The extremality test stops when it has found one perturbation. To
## see more perturbations, we use the following:
extremality_test(h, show_plots=True, show_all_perturbations=True)
## Here's the Gomory fractional cut.
gomory_fractional?
h = gomory_fractional()
plot_with_colored_slopes(h)
## It is not even minimal:
minimality_test(h, True)
## Let's consider an interesting discontinuous function.
## It was defined by Letchford and Lodi.
ll_strong_fractional?
## The docstring suggests a few things to try with this function.
## In particular it tells us that it fails to be minimal if 0 < f < 1/2.
## Let's verify that.
h = ll_strong_fractional(1/3)
extremality_test(h, True)
## There's many more functions to explore. Try some of the following
## to get more information.
##
## Also consult the survey, which shows the graphs
## of these functions for default parameters next to their names.
gj_2_slope?
gj_2_slope_repeat?
dg_2_step_mir?
kf_n_step_mir?
gj_forward_3_slope?
drlm_backward_3_slope?
dg_2_step_mir_limit?
drlm_2_slope_limit?
drlm_3_slope_limit?
bccz_counterexample?
bhk_irrational?
chen_4_slope?
rlm_dpl1_extreme_3a?
mlr_cpl3_g_3_slope?
# Many more mlr_cpl3_... functions.
not_extreme_1?
drlm_not_extreme_2?
hildebrand_5_slope_28_1?
hildebrand_2_sided_discont_1_slope_1?
hildebrand_2_sided_discont_2_slope_1?
hildebrand_discont_3_slope_1?
gomory_fractional?
## There are also "procedures" operations that can be applied to
## extreme functions. They are defined in compendium_procedures.sage.
## First, the multiplicative homomorphism.
multiplicative_homomorphism?
h = multiplicative_homomorphism(gmic(f=4/5), 3)
## Note, this function has several points where it takes value 1,
## and hence several candidates for "f". If we don't provide the f value
## that we mean, it will warn and pick the first one from the left.
## So let's provide the f value.
extremality_test(h, True, f=4/15)
## A special case of the above.
automorphism?
h = automorphism(gmic(f=4/5))
extremality_test(h, True)
## We can restrict to a finite group problem.
restrict_to_finite_group?
hr = restrict_to_finite_group(gmic(f=4/5))
extremality_test(hr, True)
## For the finite group problems, automorphisms are more interesting!
ha = automorphism(hr, 2)
extremality_test(ha, True)
## We can interpolate to get a function for the infinite group
## problem.
hi = interpolate_to_infinite_group(ha)
extremality_test(hi, True)
## The docstring has more interesting examples.
interpolate_to_infinite_group?
## There's also this:
projected_sequential_merge?
## Sometimes, for complicated functions, the graphics do not show
## enough detail.
h = bhk_irrational(delta=[1/200, 3/200])
extremality_test(h, True)
## :-(
## There are two ways to see more.
##
## Approach 1: Use specific plotting functions to zoom in to some
## areas of interest.
## The 2d diagram, showing non-subadditive vertices and additive faces.
plot_2d_diagram(h).show(xmin=0.15, xmax=0.35, ymin=0.15, ymax=0.35)
## The diagram of covered intervals.
plot_covered_intervals(h).show(xmin=0.15, xmax=0.35, ymin=0.22, ymax=0.55)
## The completion diagram (to be explained in a forthcoming paper).
plot_completion_diagram(h).show(xmin=0.28, xmax=0.52, ymin=0.25, ymax=0.35)
## The perturbation diagram. 1 is the index of the perturbation shown.
plot_perturbation_diagram(h, 1).show(xmin=0.28, xmax=0.35, ymin=0.33, ymax=0.4)
## Approach 2: Increase the plotting figure size (the default is 10).
igp.show_plots_figsize = 40
h = bhk_irrational(delta=[1/200, 3/200])
extremality_test(h, True)
## Of course, we can define functions from scratch.
h = piecewise_function_from_breakpoints_and_values([0, 1/5, 2/5, 4/5, 1], [0, 1/5, 3/5, 1, 0]);
extremality_test(h, True)
## Here's another way.
slopes = [10/3,0,10/3,0,10/3,-10/3,0,-10/3,0,-10/3]
interval_lengths = [1/10,1/10,1/10,1/10,1/10,1/10,1/10,1/10,1/10,1/10]
h = piecewise_function_from_interval_lengths_and_slopes(interval_lengths, slopes)
extremality_test(h, True, show_all_perturbations=True)
## See the extreme function with the world-record number of different slopes.
extreme_function_with_world_record_number_of_slopes?
h = extreme_function_with_world_record_number_of_slopes()
plot_with_colored_slopes(h).show(figsize=70)
## See extreme_functions_in_literature.sage and survey_examples.sage for many more examples.