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)
Polytope in ambient dimension 3

julia> LP = linear_program(P,[3,-2,4];k=2,convention = :min)
Linear program
   min{c*x + k | x in P}
where P is a Polyhedron{QQFieldElem} and
   c=QQFieldElem[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

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
ambient_dim — Method
ambient_dim(LP::LinearProgram)

Return the ambient dimension of the feasible reagion of LP.

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 or the feasible region is empty, m may be infinity, -infinity, or nothing 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 -infinity or infinity depending on convention, or nothing if the feasible region is empty.

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)
Polytope in ambient dimension 3

julia> LP=linear_program(C,[1,2,-3]; convention = :min)
Linear program
   min{c*x + k | x in P}
where P is a Polyhedron{QQFieldElem} and
   c=QQFieldElem[1, 2, -3]
   k=0

julia> optimal_value(LP)
-6

Optimizing in an unbounded direction yields infinity.

julia> lp = linear_program(convex_hull([0 0], [1 0; 0 1]), [1, 1])
Linear program
   max{c*x + k | x in P}
where P is a Polyhedron{QQFieldElem} and
   c=QQFieldElem[1, 1]
   k=0

julia> optimal_value(lp)
infinity
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)
Polytope in ambient dimension 3

julia> LP=linear_program(C,[1,2,-3])
Linear program
   max{c*x + k | x in P}
where P is a Polyhedron{QQFieldElem} and
   c=QQFieldElem[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)
Polytope 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)
Polytope 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