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
— TypeLinearProgram(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.
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
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
— Methodfeasible_region(lp::LinearProgram)
Return the feasible region of the linear program lp
, which is a Polyhedron
.
objective_function
— Methodobjective_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.
solve_lp
— Methodsolve_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
.
optimal_value
— Methodoptimal_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
optimal_vertex
— Methodoptimal_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
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.