GitHub

Mixed Integer Linear Programs

Introduction

The purpose of a mixed integer linear program is to optimize a linear function over a polyhedron, where we require a given subset of the variables to be integers.

Constructions

Mixed integer 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. Furthermore one can optionally specify integer_variables, a subset of variables that are required to be integral, given as a set of integers, their respective indices.

mixed_integer_linear_program — Function
mixed_integer_linear_program(P, c; integer_variables = [], k = 0, convention = :max)

The mixed integer linear program on the feasible set P (a Polyhedron) with respect to the function x ↦ dot(c,x)+k, where $x_i\in\mathbb{Z}$ for all $i$ in integer_variables. If integer_variables is empty, or not specified, all entries of x are required to be integral. If this is not intended, consider using a linear_program instead.

source

Functions

feasible_region — Method
feasible_region(milp::MixedIntegerLinearProgram)

Return the feasible region of the mixed integer linear program milp, which is a Polyhedron.

source
ambient_dim — Method
ambient_dim(MILP::MixedIntegerLinearProgram)

Return the ambient dimension of the feasible reagion of MILP.

source
optimal_value — Method
optimal_value(MILP::MixedIntegerLinearProgram)

Return, if it exists, the optimal value of the objective function of MILP over the feasible region of MILP. Otherwise, return -inf or inf depending on convention.

Examples

Take the square $[-1/2,3/2]^2$ and optimize $[1,1]$ in different settings.

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> optimal_value(milp)
5/2

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

julia> optimal_value(milp)
2
source
optimal_solution — Function
optimal_solution(MILP::MixedIntegerLinearProgram)

Return either a point of the feasible region of MILP which optimizes the objective function of MILP, or nothing if no such point exists.

Examples

Take the square $[-1/2,3/2]^2$ and optimize $[1,1]$ in different settings.

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> optimal_solution(milp)
2-element PointVector{QQFieldElem}:
 1
 3//2

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

julia> optimal_solution(milp)
2-element PointVector{QQFieldElem}:
 1
 1
source
solve_milp — Function
solve_milp(MILP::MixedIntegerLinearProgram)

Return a pair (m,v) where the optimal value m of the objective function of MILP 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.

Examples

Take the square $[-1/2,3/2]^2$ and optimize $[1,1]$ in different settings.

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> solve_milp(milp)
(5/2, QQFieldElem[1, 3//2])

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

julia> solve_milp(milp)
(2, QQFieldElem[1, 1])
source
integer_hull — Function
integer_hull(P::Polyhedron)

Return the convex hull of the lattice points in P. Works even for nonrational polytopes.

Examples

julia> vertices(integer_hull(dodecahedron()))
6-element SubObjectIterator{PointVector{QQFieldElem}}:
 [-1, 0, 0]
 [0, -1, 0]
 [0, 0, -1]
 [0, 0, 1]
 [0, 1, 0]
 [1, 0, 0]
source
gomory_chvatal_closure — Function
gomory_chvatal_closure(P::Polyhedron{QQFieldElem})

Return the Gomory-Chvátal closure of a rational polyhedron; sometimes also called "elementary closure".

Applying this function iteratively to any rational polytope yields the integer hull after finitely many steps. [Sch86].

Examples

julia> vertices(gomory_chvatal_closure(cube(2, -1//2, 3//2)))
4-element SubObjectIterator{PointVector{QQFieldElem}}:
 [1, 0]
 [1, 1]
 [0, 1]
 [0, 0]
source