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.

linear_program — Function
linear_program(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)
Polyhedron in ambient dimension 3

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

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

julia> P = cube(3);

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

julia> c, k = objective_function(LP)
(QQFieldElem[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 = linear_program(P,[3,-2,4];k=2,convention = :min);

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

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

julia> ℓ(v) == convert(QQFieldElem, 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 QQFieldElem 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 = linear_program(P,[3,-2,4];k=2,convention = :min);

julia> M = optimal_value(LP)
-7

julia> V = optimal_vertex(LP)
3-element PointVector{QQFieldElem}:
 -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)
Polyhedron in ambient dimension 3

julia> LP=linear_program(C,[1,2,-3]; convention = :min)
Linear program
   min{c⋅x + k | x ∈ P}
where P is a Polyhedron{QQFieldElem} and
   c=Polymake.LibPolymake.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)
Polyhedron in ambient dimension 3

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

julia> optimal_vertex(LP)
3-element PointVector{QQFieldElem}:
 1
 1
 -1
source
load_lp — Method
load_lp(file::String)

Load a (mixed integer) linear program from an .lp file using the LP file format.

source
save_lp — Method
save_lp(target::Union{String, IO}, lp::Union{MixedIntegerLinearProgram,LinearProgram})

Save a (mixed integer) linear program to an .lp file using the LP file format.

Examples

Take the square $[-1/2,3/2]^2$ with objective $[1,1]$ and one integer variable. Print the object in LP format to stdout:

julia> c = cube(2, -1//2, 3//2)
Polyhedron in ambient dimension 2

julia> milp = mixed_integer_linear_program(c, [1,1], integer_variables=[1])
Mixed integer linear program

julia> save_lp(stdout, milp)
MAXIMIZE
  obj: +1 x1 +1 x2
Subject To
  ie0: +2 x1 >= -1
  ie1: -2 x1 >= -3
  ie2: +2 x2 >= -1
  ie3: -2 x2 >= -3
BOUNDS
  x1 free
  x2 free
GENERAL
  x1
END
source
load_mps — Method
load_mps(file::String)

Load a (mixed integer) linear program from an .mps file using the MPS file format.

source
save_mps — Method
save_mps(target::String, lp::Union{MixedIntegerLinearProgram,LinearProgram})

Save a (mixed integer) linear program to an .mps file using the MPS file format.

Examples

Create the square $[-1/2,3/2]^2$ with objective $[1,1]$ and one integer variable. Print the object in MPS format to stdout:

julia> c = cube(2, -1//2, 3//2)
Polyhedron in ambient dimension 2

julia> milp = mixed_integer_linear_program(c, [1,1], integer_variables=[1])
Mixed integer linear program

julia> save_mps(stdout, milp)
* Class:	MIP
* Rows:		5
* Columns:	2
* Format:	MPS
*
NAME          unnamed#0
ROWS
 N  C0000000
 G  R0000000
 G  R0000001
 G  R0000002
 G  R0000003
COLUMNS
    M0000000  'MARKER'                 'INTORG'
    x1        C0000000  1                        R0000000  1
    x1        R0000001  -1                       
    M0000000  'MARKER'                 'INTEND'
    x2        C0000000  1                        R0000002  1
    x2        R0000003  -1                       
RHS
    B         R0000000  -0.5                     R0000001  -1.5
    B         R0000002  -0.5                     R0000003  -1.5
BOUNDS
 FR BND       x1  
 FR BND       x2  
ENDATA
source