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
  • Last modified: 2019/08/13 10:31
  • (external edit)