• Linear Programs
• • Introduction
  • Constructions
  • Solving a linear program - an example
  • Functions
  • Saving and loading

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(P, c; k = 0, convention = :max)

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> c, k = objective_function(LP)(fmpq[3, -2, 4], 2)
julia> P == feasible_region(LP)true
julia> ℓ = objective_function(LP; as = :function)#1749 (generic function with 1 method)

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> m, v = solve_lp(LP)(-7, fmpq[-1, 1, -1])
julia> ℓ(v) == mfalse

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

julia> M = optimal_value(LP)-7
julia> V = optimal_vertex(LP)3-element PointVector{fmpq}:
 -1
 1
 -1
julia> ℓ(V) == Mfalse

Functions

After constructing a linear program, it is straightforward to extract the feasible region and objective function

feasible_region(lp::LinearProgram)

objective_function(LP::LinearProgram; as = :pair)

Calling solve_lp on a linear program outputs a pair: the optimal value and the vertex at which the optimum is obtained

solve_lp(LP::LinearProgram)

One can obtain the optimal value of the objective function over the feasible region, if it exists.

optimal_value(LP::LinearProgram)

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

One can also obtain an optimal vertex at which the objective function attains its optimal value (respectively).

optimal_vertex(LP::LinearProgram)

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

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)1180
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.