‣ PolyhedronByInequalities( L ) | ( operation ) |
Returns: a Polyhedron Object
The function takes a list of lists L:=[L_1, L_2, ...] where each L_j represents an inequality and returns the polyhedron defined by them. For example the j'th entry L_j = [c_j,a_{j1},a_{j2},...,a_{jn}] corresponds to the inequality c_j+\sum_{i=1}^n a_{ji}x_i \geq 0.
‣ Polyhedron( P, C ) | ( operation ) |
Returns: a Polyhedron Object
The input is a polytope P and a cone C. The output is the polyhedron defined by the Minkowski sum P+C.
‣ Polyhedron( L, C ) | ( operation ) |
Returns: a Polyhedron Object
The input is a list L and a cone C. The output is the polyhedron defined by the Minkowski sum P+C where P is the polytope, i.e., the convex hull, defined by the points L.
‣ Polyhedron( P, L ) | ( operation ) |
Returns: a Polyhedron Object
The input is a polytope P and a list L. The output is the polyhedron defined by the Minkowski sum P+C where C is the cone defined by the rays L.
‣ Polyhedron( P, C ) | ( operation ) |
Returns: a Polyhedron Object
The input is a list P and a list C. The output is the polyhedron defined by the Minkowski sum of the polytope defined by P and the cone defined by C.
‣ ExternalCddPolyhedron( P ) | ( attribute ) |
Returns: cdd Object
Converts the polyhedron to a cdd object. The operations of CddInterface can then be applied on this convex object.
‣ ExternalNmzPolyhedron( P ) | ( attribute ) |
Returns: normaliz Object
Converts the polyhedron to an normaliz object. The operations of NormalizInterface can then be applied on this convex object.
‣ DefiningInequalities( P ) | ( attribute ) |
Returns: a list
Returns the Defining inequalities of the given polyhedron.
‣ MainRatPolytope( P ) | ( attribute ) |
Returns: a Polytope Object
Returns the main rational polytope of the polyhedron.
‣ MainPolytope( P ) | ( attribute ) |
Returns: a Polytope Object
Returns the main integral polytope of the given polyhedron.
‣ VerticesOfMainRatPolytope( P ) | ( attribute ) |
Returns: a list
Returns the vertices of the main rational polytope of the polyhedron.
‣ VerticesOfMainPolytope( P ) | ( attribute ) |
Returns: a list
Returns the vertices of the main integral polytope of the given polyhedron.
‣ TailCone( P ) | ( attribute ) |
Returns: a Cone Object
Returns the tail cone of the polyhedron.
‣ RayGeneratorsOfTailCone( P ) | ( attribute ) |
Returns: a list
Returns the Ray Generators of the tail cone.
‣ LatticePointsGenerators( P ) | ( attribute ) |
Returns: a list
Returns the integral lattice generators of the polyhedron. The output is a list L of length 3. Any integral point in polyhedron can be written as a+mb+nc, where a\in L[1],b\in L[2],c\in L[3], m\geq 0.
‣ BasisOfLinealitySpace( P ) | ( attribute ) |
Returns: a list
Returns a basis to the lineality space of the polyhedron. I.e., a basis to the vector space that is contained in P.
‣ FVector( P ) | ( attribute ) |
Returns: a list
Returns a list whose i'th entry is the number of faces of dimension i-1.
‣ IsBounded( P ) | ( property ) |
Returns: true or false
The input is a polyhedron P and the output is whether it is bounded or not.
‣ IsPointed( P ) | ( property ) |
Returns: true or false
The input is a polyhedron P and the output is whether its tail cone is pointed or not.
gap> P := Polyhedron( [ [ 1, 1 ], [ 4, 7 ] ], [ [ 1, -1 ], [ 1, 1 ] ] ); <A polyhedron in |R^2> gap> VerticesOfMainRatPolytope( P ); [ [ 1, 1 ], [ 4, 7 ] ] gap> VerticesOfMainPolytope( P ); [ [ 1, 1 ], [ 4, 7 ] ] gap> P := Polyhedron( [ [ 1/2, 1/2 ] ], [ [ 1, 1 ] ] ); <A polyhedron in |R^2> gap> VerticesOfMainRatPolytope( P ); [ [ 1/2, 1/2 ] ] gap> VerticesOfMainPolytope( P ); [ [ 1, 1 ] ] gap> LatticePointsGenerators( P ); [ [ [ 1, 1 ] ], [ [ 1, 1 ] ], [ ] ] gap> Dimension( P ); 1 gap> Q := Polyhedron( [ [ 5, 0 ], [ 0, 6 ] ], [ [ 1, 2 ] , [ -1, -2 ] ] ); <A polyhedron in |R^2> gap> VerticesOfMainRatPolytope( Q ); [ [ 0, 6 ], [ 5, 0 ] ] gap> V := VerticesOfMainPolytope( Q ); [ [ 0, 6 ], [ 5, 0 ] ] gap> L := LatticePointsGenerators( Q ); [ [ [ 0, -10 ], [ 0, -9 ], [ 0, -8 ], [ 0, -7 ], [ 0, -6 ], [ 0, -5 ], [ 0, -4 ], [ 0, -3 ], [ 0, -2 ], [ 0, -1 ], [ 0, 0 ], [ 0, 1 ], [ 0, 2 ], [ 0, 3 ], [ 0, 4 ], [ 0, 5 ], [ 0, 6 ] ], [ ], [ [ 1, 2 ] ] ] gap> Dimension( Q ); 2 gap> RayGeneratorsOfTailCone( Q ); [ [ -1, -2 ], [ 1, 2 ] ] gap> BasisOfLinealitySpace( Q ); [ [ 1, 2 ] ] gap> DefiningInequalities( Q ); [ [ 6, 2, -1 ], [ 10, -2, 1 ] ] gap> Q; <A polyhedron in |R^2 of dimension 2>
gap> P := PolyhedronByInequalities( [ [ -2, 3, 4, -7 ], -[ -2, 3, 4, -7 ] ] ); <A polyhedron in |R^3 > gap> L := LatticePointsGenerators( P ); [ [ [ -4, 0, -2 ] ], [ ], [ [ 0, 7, 4 ], [ 1, 1, 1 ] ] ]
gap> Q := PolyhedronByInequalities( [ [-3, 4, 6 ], [ 3, -4, -6 ] ] ); <A polyhedron in |R^2 > gap> LatticePointsGenerators( Q ); [ [ ], [ ], [ [ 3, -2 ] ] ]
gap> P := PolyhedronByInequalities( [ [ -1, 2, 3, 2, 0 ], [ -3, 7, 1, 0, 5 ], > [ 1, -2, -3, -2, 0 ], [ 3, -7, -1, 0, -5 ] ] ); <A polyhedron in |R^4 > gap> L := LatticePointsGenerators( P ); [ [ [ -19, 1, 18, 27 ] ], [ ], [ [ 0, 10, -15, -2 ], [ 1, -2, 2, -1 ] ] ]
The problem of solving linear programs can be solved in the gap package CddInterface, which is required by NConvex.
‣ SolveLinearProgram( P, max_or_min, target_func ) | ( operation ) |
Returns: a list or fail
The input is a polyhedron P, a string max_or_min \in {"max", "min"} and an objective function target_func, which we want to maximize or minimize. If the linear program has an optimal solution, the operation returns a list of two entries, the solution vector and the optimal value of the objective function, otherwise it returns fail.
‣ SolveLinearProgram( P, max_or_min, target_func ) | ( operation ) |
Returns: a list or fail
The input is a polytope P, a string max_or_min \in {"max","min"} and an objective function target_func, which we want to maximize or minimize. If the linear program has an optimal solution, the operation returns a list of two entries, the solution vector and the optimal value of the objective function, otherwise it returns fail.
\newline To illustrate the using of this operation, let us solve the linear program: \\P(x,y)= 1-2x+5y, with \newline 100\leq x \leq 200 \newline 80\leq y\leq 170 \newline y \geq -x+200\newline\newline We bring the inequalities to the form b+AX\geq 0, we get: \newline -100+x\geq 0 \newline 200-x \geq 0 \newline -80+y \geq 0 \newline 170 -y \geq 0 \newline -200 +x+y \geq 0 \newline
gap> P := PolyhedronByInequalities( [ [ -100, 1, 0 ], [ 200, -1, 0 ], > [ -80, 0, 1 ], [ 170, 0, -1 ], [ -200, 1, 1 ] ] );; gap> max := SolveLinearProgram( P, "max", [ 1, -2, 5 ] ); [ [ 100, 170 ], 651 ] gap> min := SolveLinearProgram( P, "min", [ 1, -2, 5 ] ); [ [ 200, 80 ], 1 ] gap> VerticesOfMainRatPolytope( P ); [ [ 100, 100 ], [ 100, 170 ], [ 120, 80 ], [ 200, 80 ], [ 200, 170 ] ]
So the optimal solutions are (x=100,y=170) with maximal value p=1-2(100)+5(170)=651 and (x=200,y=80) with minimal value p=1-2(200)+5(80)=1.
‣ SolveEqualitiesAndInequalitiesOverIntergers( eqs, eqs_rhs, ineqs, ineqs_rhs[, signs] ) | ( function ) |
Returns: a list of three matrices
This function produces a basis of the system eqs = eqs_rhs and ineqs >= ineqs_rhs. It outputs a list containing three matrices. The first one is a list of points in a polytope, the second is the hilbert basis of a cone. The set of solutions is then the minkowski sum of the polytope generated by the points in the first list and the cone generated by the hilbert basis in the second matrix. The third one is the free part of the solution polyhedron. The optional argument signs must be a list of zeros and ones which length is the number of variables. If the ith entry is one, the ith variable must be >= 0. If the entry is 0, the number is arbitraty. Default is all zero.
\newline To illustrate the using of this function, let us compute the integers solutions of the system: \newline3x+5y=8\newline 4x-2y\geq 2\newline 3x+y\geq 3\newline
gap> SolveEqualitiesAndInequalitiesOverIntergers( [ [ 3, 5 ] ], [ 8 ], > [ [ 4, -2 ], [ 3, 1 ] ], [ 2, 3 ] ); [ [ [ 1, 1 ] ], [ [ 5, -3 ] ], [ ] ] gap> SolveEqualitiesAndInequalitiesOverIntergers( [ [ 3, 5 ] ], [ 8 ], > [ [ 4, -2 ], [ 3, 1 ] ], [ 2, 3 ], [ 1, 1 ] ); [ [ [ 1, 1 ] ], [ ], [ ] ]
So the set of all solutions is given by \{(1,1)+y*(5,-3),y\geq 0\} and it has only one positive solution (1,1).
generated by GAPDoc2HTML