# 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.

## 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`

— Method`feasible_region(lp::LinearProgram)`

Return the feasible region of the linear program `lp`

, which is a `Polyhedron`

.

`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.

`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`

.

`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
```

`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
```

## 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.