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
|
# Copyright (c) 1997-2024
# Ewgenij Gawrilow, Michael Joswig, and the polymake team
# Technische Universität Berlin, Germany
# https://polymake.org
#
# This program is free software; you can redistribute it and/or modify it
# under the terms of the GNU General Public License as published by the
# Free Software Foundation; either version 2, or (at your option) any
# later version: http://www.gnu.org/licenses/gpl.txt.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#-------------------------------------------------------------------------------
# @category Optimization
# A linear program specified by a linear or abstract objective function
# @relates objects/Polytope
# @tparam Scalar numeric type of variables and objective function
declare object LinearProgram<Scalar=Rational> {
# Linear objective function. In d-space a linear objective function is given by a (d+1)-vector.
# The first coordinate specifies a constant that is added to the resulting value.
# @example The following creates a new LinearProgram object and assigns a linear objective to it:
# > $l = cube(2)->LP(LINEAR_OBJECTIVE=>[0,1,1]);
# > print $l->LINEAR_OBJECTIVE;
# | 0 1 1
property LINEAR_OBJECTIVE : Vector<Scalar>;
# Abstract objective function. Defines a direction for each edge such that each non-empty
# face has a unique source and a unique sink.
# The i-th element is the value of the objective function at vertex number i.
# Only defined for bounded polytopes.
# @example The following creates a new LinearProgram object and assigns an abstract objective to it:
# > $l = cube(2)->LP(ABSTRACT_OBJECTIVE=>[1,2,3,4]);
# > print $l->ABSTRACT_OBJECTIVE;
# | 1 2 3 4
property ABSTRACT_OBJECTIVE : Vector<Scalar>;
# Indices of vertices at which the maximum of the objective function is attained.
# @example The following defines a LinearProgram together with a linear objective for the centered square with side length 2 and asks
# for the maximal face:
# > $c = new Vector([0, 1, 0]);
# > $p = cube(2);
# > $p->LP(LINEAR_OBJECTIVE=>$c);
# > print $p->LP->MAXIMAL_FACE;
# | {1 3}
property MAXIMAL_FACE : Set;
# Similar to [[MAXIMAL_FACE]].
# @example The following defines a LinearProgram together with a linear objective for the centered square with side length 2 and asks
# for the minimal face:
# > $c = new Vector([0, 1, 0]);
# > $p = cube(2);
# > $p->LP(LINEAR_OBJECTIVE=>$c);
# > print $p->LP->MINIMAL_FACE;
# | {0 2}
property MINIMAL_FACE : Set;
# Coordinates of a (possibly not unique) affine vertex at which the maximum of the objective function is attained.
# @example The following defines a LinearProgram together with a linear objective for the centered square with
# side length 2 and asks for a maximal vertex:
# > $c = new Vector([0, 1, -1/2]);
# > $p = cube(2);
# > $p->LP(LINEAR_OBJECTIVE=>$c);
# > print $p->LP->MAXIMAL_VERTEX;
# | 1 1 -1
property MAXIMAL_VERTEX : Vector<Scalar>;
# Similar to [[MAXIMAL_VERTEX]].
# @example The following defines a LinearProgram together with a linear objective for the centered square with side length 2 and asks
# for a minimal vertex:
# > $c = new Vector([0, 1, 0]);
# > $p = cube(2);
# > $p->LP(LINEAR_OBJECTIVE=>$c);
# > print $p->LP->MINIMAL_VERTEX;
# | 1 -1 -1
property MINIMAL_VERTEX : Vector<Scalar>;
# Maximum value of the objective function. Negated if linear problem is unbounded.
# @example The following defines a LinearProgram together with a linear objective for the centered square with side length 2 and asks
# for the maximal value:
# > $c = new Vector([0, 1, 0]);
# > $p = cube(2);
# > $p->LP(LINEAR_OBJECTIVE=>$c);
# > print $p->LP->MAXIMAL_VALUE;
# | 1
# @example The following defines a LinearProgram together with a linear objective with bias 3 for the centered square with side length 4 and asks
# for the maximal value:
# > $c = new Vector([3, 1, 0]);
# > $p = cube(2,2);
# > $p->LP(LINEAR_OBJECTIVE=>$c);
# > print $p->LP->MAXIMAL_VALUE;
# | 5
# @example The following defines a LinearProgram together with a linear objective for the positive quadrant (unbounded) and asks
# for the maximal value:
# > $c = new Vector([0, 1, 1]);
# > $p = facet_to_infinity(simplex(2),0);
# > $p->LP(LINEAR_OBJECTIVE=>$c);
# > print $p->LP->MAXIMAL_VALUE;
# | inf
property MAXIMAL_VALUE : Scalar;
# Similar to [[MAXIMAL_VALUE]].
# @example The following defines a LinearProgram together with a linear objective for the centered square with side length 2 and asks
# for the minimal value:
# > $c = new Vector([0, 1, 0]);
# > $p = cube(2);
# > $p->LP(LINEAR_OBJECTIVE=>$c);
# > print $p->LP->MINIMAL_VALUE;
# | -1
# @example The following defines a LinearProgram together with a linear objective with bias 3 for the centered square with side length 4 and asks
# for the minimal value:
# > $c = new Vector([3, 1, 0]);
# > $p = cube(2,2);
# > $p->LP(LINEAR_OBJECTIVE=>$c);
# > print $p->LP->MINIMAL_VALUE;
# | 1
property MINIMAL_VALUE : Scalar;
# Subgraph of [[Polytope::GRAPH]]. Consists only of directed arcs along which the value of the objective function increases.
# @example The following defines a LinearProgram together with a linear objective for the centered square with side length 2. The directed
# graph according to the linear objective is stored in a new variable and the corresponding edges are printend.
# > $c = new Vector([0, 1, 0]);
# > $p = cube(2);
# > $p->LP(LINEAR_OBJECTIVE=>$c);
# > $g = $p->LP->DIRECTED_GRAPH;
# > print $g->EDGES;
# | {0 1}
# | {2 3}
property DIRECTED_GRAPH : Graph<Directed>;
# methods for backward compatibility
# Array of out-degrees for all nodes of [[DIRECTED_GRAPH]]
# or numbers of objective increasing edges at each vertex
# @return Array<Int>
user_method VERTEX_OUT_DEGREES = DIRECTED_GRAPH.NODE_OUT_DEGREES;
# Array of in-degrees for all nodes of [[DIRECTED_GRAPH]]
# or numbers of objective decreasing edges at each vertex
# @return Array<Int>
user_method VERTEX_IN_DEGREES = DIRECTED_GRAPH.NODE_IN_DEGREES;
# Expected average path length for a simplex algorithm employing "random edge" pivoting strategy.
property RANDOM_EDGE_EPL : Vector<Rational>;
}
package Visual::Color;
# distinguished color for MAX_FACE: red
custom $max="255 0 0";
# distinguished color for MIN_FACE: yellow
custom $min="255 255 0";
# Local Variables:
# mode: perl
# c-basic-offset:3
# End:
|
