Linear Programming (LP)#

The main feature of a linear programming problem (LPP) is that all functions involved, the objective function and those expressing the constraints, must be linear. The appereance of a single nonlinear function anywhere, suffices to reject the problem as an LPP.

The definition of an LPP is expected in General Form:

\begin{eqnarray} & minimize \quad &cx = \, \sum_i c_i x_i \\ & subject \, to \quad & \nonumber \\ && \sum_i a_{ji} \,x_i \,\leq\, b_j, \qquad j = 1, \ldots, p, \\ && \sum_i a_{ji} \,x_i \,\geq\, b_j, \qquad j = p+1, \ldots, q, \\ && \sum_i a_{ji} \,x_i \,=\, b_j, \qquad j = q+1, \ldots, m, \end{eqnarray}

where \(c_i, b_i\), and \(a_{ji}\) are the data of the problem.

A class to solve linear programming problems [1]. It uses the scipy.optimize.linprog() function as a solver [2], which eventually calls into the HIGHS solver [3].

To define the objective and the constraints, you can use the Function, Relation, Equality and InEquality classes. These are able to understand SymPy expressions and strings, giving you the flexibility in defining the problem.

Parameters:

obj (Function) – The objective function.
constraints (Sequence[Relation]) – The constraints.
variables (Sequence[Symbol], Optional) – The variables of the problem. The variables must be provided for symbolic functions to guarantee that the order of the variables is consistent with the symbolic functions that make up the problem.
bounds (BoundsLike, Optional) – See the bounds parameter in scipy.optimize.linprog for more details.
integrality (Iterable[int] | int, Optional) – See the integrality parameter in scipy.optimize.linprog for more details.
sparsify (bool, Optional) – If True, the constraint matrices will be converted to sparse format before passing them to the solver. This can improve performance for large problems with many zero coefficients. Default is True.

Examples

The following example solves a problem with a unique solution.

\[\begin{split}\begin{eqnarray} & minimize& \quad 3 x_1 + x_2 + 9 x_3 + x_4 \\ & subject \, to& & \nonumber\\ & & x_1 + 2 x_3 + x_4 \,=\, 4, \\ & & x_2 + x_3 - x_4 \,=\, 2, \\ & & x_i \,\geq\, \, 0, \qquad i=1, \ldots, 4. \end{eqnarray}\end{split}\]

>>> from sigmaepsilon.math.optimize import LinearProgrammingProblem as LPP
>>> from sigmaepsilon.math.function import Function, Relation
>>> import sympy as sy
>>>
>>> x1, x2, x3, x4 = variables = sy.symbols('x1:5')
>>> obj = Function(3*x1 + 9*x3 + x2 + x4, variables=variables)
>>> eq1 = Relation(x1 + 2*x3 + x4 - 4, variables=variables)
>>> eq2 = Relation(x2 + x3 - x4 - 2, variables=variables)
>>>
>>> bounds = [(0, None), (0, None), (0, None), (0, None)]
>>> problem = LPP(obj, [eq1, eq2], variables=variables, bounds=bounds)
>>> problem.solve().x
array([0., 6., 0., 4.])

In this example, bounds could have been specified as bounds=(0, None) as well, since all variables have the same bound.

Now let see how to solve the following mixed integer linear programming problem.

\[\begin{split}\begin{eqnarray} & minimize& \quad 3 x_2 + 2 x_3 \\ & subject \, to& & \nonumber\\ & & 2 x_1 + 2 x_2 - 4 x_3 \,=\, 5, \\ & & x_i \,\geq\, \, 0, \qquad i=1, \ldots, 4. \\ & & x_1, x_3 \,\in\, \mathbb{Z}. \end{eqnarray}\end{split}\]

>>> variables = x1, x2, x3 = sy.symbols(["x1", "x2", "x3"])
>>> f = Function(3 * x2 + 2 * x3, variables=variables)
>>> eq = Relation(2 * x1 + 2 * x2 - 4 * x3 - 5, op="=", variables=variables)
>>> bounds = (0, None)
>>> integrality = [1, 0, 1]
>>> problem = LPP(f, [eq], variables=variables, bounds=bounds, integrality=integrality)

These integrality constraints can also be specified using assumptions on the symbolic variables.

>>> x1, x3 = sy.symbols(["x1", "x3"], integer=True)
>>> x2 = sy.symbols("x2")
>>> variables = x1, x2, x3
>>> f = Function(3 * x2 + 2 * x3, variables=variables)
>>> eq = Relation("2 * x1 + 2 * x2 - 4 * x3 = 5", variables=variables)
>>> problem = LPP(f, [eq], variables=variables, bounds=(0, None))

References

solve(*, maximize: bool = False, method: str = 'highs', **kwargs) → OptimizeResult[source]#

Solves the linear programming problem using scipy.optimize.linprog and returns an instance of scipy.optimize.OptimizeResult.

Parameters:

maximize (bool, Optional) – If True, the problem is a maximization problem.
method (str, Optional) – The solver to use. The default is “highs”. For more options see the method parameter in scipy.optimize.linprog.
**kwargs – Additional keyword arguments to pass to scipy.optimize.linprog.

Returns:

The result of the optimization.

Return type:

scipy.optimize.OptimizeResult

property variables: Iterable[Symbol]#: Returns the variables of the problem.