Available versions of this document: latest release, release 3.5, nightly master

Reference documentation for older polymake versions: release 3.4, release 3.3, release 3.2

BigObject LinearProgram<Scalar>

from application polytope

A linear program specified by a linear or abstract objective function

Type Parameters:

Scalar: numeric type of variables and objective function

no category

ABSTRACT_OBJECTIVE

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.

Type:
Vector<Scalar>
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

DIRECTED_BOUNDED_GRAPH

Subgraph of BOUNDED_GRAPH. Consists only of directed arcs along which the value of the objective function increases.

Type:

DIRECTED_GRAPH

Subgraph of GRAPH. Consists only of directed arcs along which the value of the objective function increases.

Type:
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} LINEAR_OBJECTIVE 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. Type: Vector<Scalar> 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 MAXIMAL_FACE Indices of vertices at which the maximum of the objective function is attained. Type: Set<Int> 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}

MAXIMAL_VALUE

Maximum value of the objective function. Negated if linear problem is unbounded.

Type:
Scalar
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 MAXIMAL_VERTEX Coordinates of a (possibly not unique) affine vertex at which the maximum of the objective function is attained. Type: Vector<Scalar> 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

MINIMAL_FACE

Similar to MAXIMAL_FACE.

Type:
Set<Int>
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} MINIMAL_VALUE Similar to MAXIMAL_VALUE. Type: Scalar 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 MINIMAL_VERTEX Similar to MAXIMAL_VERTEX. Type: Vector<Scalar> 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

RANDOM_EDGE_EPL

Expected average path length for a simplex algorithm employing “random edge” pivoting strategy.

Type:

no category

VERTEX_IN_DEGREES()

Array of in-degrees for all nodes of DIRECTED_GRAPH or numbers of objective decreasing edges at each vertex

Returns:

VERTEX_OUT_DEGREES()

Array of out-degrees for all nodes of DIRECTED_GRAPH or numbers of objective increasing edges at each vertex

Returns:

• documentation/latest/polytope/linearprogram.txt