Edit on GitHub

Linear Programs

Introduction

The purpose of a linear program is to optimize a linear function over a polyhedron.

Constructions

Linear programs are constructed from a polyhedron and a linear objective function which is described by a vector and (optionally) a translation. One can select whether the optimization problem is to maximize or to minimize the objective function.

LinearProgram — Type
LinearProgram(P, c; k = 0, convention = :max)

The linear program on the feasible set P (a Polyhedron) with respect to the function x ↦ dot(c,x)+k.

source

Solving a linear program - an example

Let $P=[-1,1]^3$ be the $3$-dimensional cube in $\mathbb{R}^3$, and consider the linear function $\ell$, given by $\ell(x,y,z) = 3x-2y+4z+2$. Minimizing $\ell$ over $P$ can be done by solving the corresponding linear program. Computationally, this means first defining a linear program:

julia> P = cube(3)
A polyhedron in ambient dimension 3

julia> LP = LinearProgram(P,[3,-2,4];k=2,convention = :min)
The linear program
   min{c⋅x + k | x ∈ P}
where P is a Polyhedron{fmpq} and
   c=Polymake.Rational[3 -2 4]
   k=2

The information about the linear program LP can be easily extracted.

julia> P = cube(3);

julia> LP = LinearProgram(P,[3,-2,4];k=2,convention = :min);

julia> c, k = objective_function(LP)
(fmpq[3, -2, 4], 2)

julia> P == feasible_region(LP)
true

To solve the optimization problem call solve_lp, which returns a pair m, v where the optimal value is m, and that value is attained at v.

julia> P = cube(3);

julia> LP = LinearProgram(P,[3,-2,4];k=2,convention = :min);

julia> m, v = solve_lp(LP)
(-7, fmpq[-1, 1, -1])

julia> ℓ = objective_function(LP; as = :function);

julia> ℓ(v) == convert(fmpq, m)
true
Infinite solutions

Note that the optimal value may be $\pm\infty$ which currently is well-defined by Polymake.jl, but not with the fmpq number type. Hence manual conversion is necessary, until this issue has been resolved.

The optimal value and an optimal vertex may be obtained individually as well.

julia> P = cube(3);

julia> LP = LinearProgram(P,[3,-2,4];k=2,convention = :min);

julia> M = optimal_value(LP)
-7

julia> V = optimal_vertex(LP)
3-element PointVector{fmpq}:
 -1
 1
 -1

Functions

feasible_region — Method
feasible_region(lp::LinearProgram)

Return the feasible region of the linear program lp, which is a Polyhedron.

source
objective_function — Method
objective_function(LP::LinearProgram; as = :pair)

Return the objective function x ↦ dot(c,x)+k of the linear program LP. The allowed values for as are

  • pair: Return the pair (c,k)
  • function: Return the objective function as a function.
source
solve_lp — Method
solve_lp(LP::LinearProgram)

Return a pair (m,v) where the optimal value m of the objective function of LP is attained at v (if m exists). If the optimum is not attained, m may be inf or -inf in which case v is nothing.

source
optimal_value — Method
optimal_value(LP::LinearProgram)

Return, if it exists, the optimal value of the objective function of LP over the feasible region of LP. Otherwise, return -inf or inf depending on convention.

Examples

The following example constructs a linear program over the three dimensional cube, and obtains the minimal value of the function (x,y,z) ↦ x+2y-3z over that cube.

julia> C=cube(3)
A polyhedron in ambient dimension 3

julia> LP=LinearProgram(C,[1,2,-3]; convention = :min)
The linear program
   min{c⋅x + k | x ∈ P}
where P is a Polyhedron{fmpq} and
   c=Polymake.Rational[1 2 -3]
   k=0

julia> optimal_value(LP)
-6
source
optimal_vertex — Method
optimal_vertex(LP::LinearProgram)

Return either a point of the feasible region of LP which optimizes the objective function of LP, or nothing if no such point exists.

Examples

The following example constructs a linear program over the three dimensional cube, and obtains the vertex of the cube which maximizes the function (x,y,z) ↦ x+2y-3z.

julia> C=cube(3)
A polyhedron in ambient dimension 3

julia> LP=LinearProgram(C,[1,2,-3])
The linear program
   max{c⋅x + k | x ∈ P}
where P is a Polyhedron{fmpq} and
   c=Polymake.Rational[1 2 -3]
   k=0

julia> optimal_vertex(LP)
3-element PointVector{fmpq}:
 1
 1
 -1
source

Saving and loading

Objects of type LinearProgram can be saved to a file and loaded from a file in the following way:

julia> C = cube(3)
A polyhedron in ambient dimension 3

julia> LP=LinearProgram(C, [1,2,-3], convention=:min)
The linear program
   min{c⋅x + k | x ∈ P}
where P is a Polyhedron{fmpq} and
   c=Polymake.Rational[1 2 -3]
   k=0

julia> save("lp.poly", LP)

julia> LP0 = load("lp.poly")
The linear program
   min{c⋅x + k | x ∈ P}
where P is a Polyhedron{fmpq} and
   c=Polymake.Rational[1 2 -3]
   k=0

julia> solve_lp(LP0)
(-6, fmpq[-1, -1, 1])

julia> solve_lp(LP)
(-6, fmpq[-1, -1, 1])

The file is in JSON format and contains all previously gathered data belonging to the underlying polymake object. In particular, this file can now be read by both polymake and OSCAR.