documentation:latest:polytope:linearprogram

Available versions of this document: latest release, release 4.12, release 4.11, release 4.10, release 4.9, release 4.8, release 4.7, release 4.6, release 4.5, release 4.4, release 4.3, release 4.2, release 4.1, release 4.0, release 3.6, 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

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:
Graph<Directed>

DIRECTED_GRAPH

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

Type:
Graph<Directed>
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:
Vector<Rational>

VERTEX_IN_DEGREES()

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

Returns:
Array<Int>

VERTEX_OUT_DEGREES()

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

Returns:
Array<Int>

• documentation/latest/polytope/linearprogram.txt