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.

Tip

For problems starting from medium size, it is suggested to use the solve_standard_form to solve linear problems.

The definition of an LPP is expected in General Form:

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

where \(c_i, b_i\), and \(a_{j,i}\) are the data of the problem. It can be shown, that all problems that admit the general form can be simplified to a Standard Form:

\begin{eqnarray} minimize \quad \mathbf{c}\mathbf{x} \quad under \quad \mathbf{A}\mathbf{x}=\mathbf{b}, \quad \mathbf{x} \, \geq \, \mathbf{0}. \end{eqnarray}

where \(\mathbf{b} \in \mathbf{R}^m, \mathbf{c} \in \mathbf{R}^n\) and \(\mathbf{A}\) is an \(m \times n\) matrix with \(n>m\) and typically \(n\) much greater than \(m\).

class sigmaepsilon.math.optimize.LinearProgrammingProblem(*args, constraints=None, variables=None, positive=None, standardform=False, **kwargs)[source]#

A lightweight class to handle general linear programming problems. It gaps the bridge between the general form and the standard form. The class accepts symbolic expressions, but this should not be expected to be too fast. For problems starting from medium size, it is suggested to use the solve_standard_form method of the class.

Parameters:

  • constraints (Iterable[Function]) – List of constraint functions.

  • variables (Iterable) – List of variables of the system.

  • positive (bool, Optional) – A True value indicated that all variables are expected to take only positive values. Default is True.

  • 'obj' (Function) – The objective function.

  • 'cost' (Function) – The objective function.

  • 'payoff' (Function) – The objective function.

  • 'fittness' (Function) – The objective function.

  • 'f' (Function) – The objective function.

Examples

The examples requires sympy to be installed.

  1. Example for unique solution.

\begin{eqnarray} & minimize& \quad 3 x_1 + x_2 + 9 x_3 + x_4 \\ & subject \, to& & \\ & & 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}
>>> from sigmaepsilon.math.optimize import LinearProgrammingProblem as LPP
>>> import sympy as sy
>>> variables = ['x1', 'x2', 'x3', 'x4']
>>> x1, x2, x3, x4 = syms = sy.symbols(variables, positive=True)
>>> obj1 = Function(3*x1 + 9*x3 + x2 + x4, variables=syms)
>>> eq11 = Equality(x1 + 2*x3 + x4 - 4, variables=syms)
>>> eq12 = Equality(x2 + x3 - x4 - 2, variables=syms)
>>> problem = LPP(cost=obj1, constraints=[eq11, eq12], variables=syms)
>>> problem.solve()['x']
array([0., 6., 0., 4.])

(2) Example for degenerate solution. The problem is on the edge of being ill posed, it may or may not raise an error, or return a solution.

>>> variables = ['x1', 'x2', 'x3', 'x4']
>>> x1, x2, x3, x4 = syms = sy.symbols(variables, positive=True)
>>> obj2 = Function(3*x1 + x2 + 9*x3 + x4, variables=syms)
>>> eq21 = Equality(x1 + 2*x3 + x4, variables=syms)
>>> eq22 = Equality(x2 + x3 - x4 - 2, variables=syms)
>>> P2 = LPP(cost=obj2, constraints=[eq21, eq22], variables=syms)
>>> # P2.solve()

(3) Example for no solution. Solution returns None and the error message can be inspected.

>>> variables = ['x1', 'x2', 'x3', 'x4']
>>> x1, x2, x3, x4 = syms = sy.symbols(variables, positive=True)
>>> obj3 = Function(-3*x1 + x2 + 9*x3 + x4, variables=syms)
>>> eq31 = Equality(x1 - 2*x3 - x4 + 2, variables=syms)
>>> eq32 = Equality(x2 + x3 - x4 - 2, variables=syms)
>>> P3 = LPP(cost=obj3, constraints=[eq31, eq32], variables=syms)
>>> P3.solve()['e']
[NoSolutionError('There is not solution to this problem!')]

If you want the actual error to be raised, call solve with the option raise_errors=True.

>>> P3.solve(raise_errors=True)
Traceback (most recent call last):
    ...
sigmaepsilon.math.optimize.errors.NoSolutionError: There is not solution to this problem!

(4) Example for multiple solutions. We can ask for all the results with the option return_all=True. Note that the order of the solutions in the result are not deterministic. If you rerun the solution multiple times, you will see the solutions in different order.

>>> variables = ['x1', 'x2', 'x3', 'x4']
>>> x1, x2, x3, x4 = syms = sy.symbols(variables, positive=True)
>>> obj4 = Function(3*x1 + 2*x2 + 8*x3 + x4, variables=syms)
>>> eq41 = Equality(x1 - 2*x3 - x4 + 2, variables=syms)
>>> eq42 = Equality(x2 + x3 - x4 - 2, variables=syms)
>>> P4 = LPP(cost=obj4, constraints=[eq41, eq42], variables=syms)
>>> len(P4.solve(return_all=True)['x'])
2
add_constraint(*args, **kwargs)[source]#

Adds a new constraint to the system.

static basic_solution(A=None, b=None, order=None) → Tuple[ndarray][source]#

Returns a basic solution to a problem the form

\begin{eqnarray} minimize \quad \mathbf{c}\mathbf{x} \quad under \quad \mathbf{A}\mathbf{x}=\mathbf{b}, \quad \mathbf{x} \, \geq \, \mathbf{0}. \end{eqnarray}

where \(\mathbf{b} \in \mathbf{R}^m, \mathbf{c} \in \mathbf{R}^n\) and \(\mathbf{A}\) is an \(m \times n\) matrix with \(n>m\).

Parameters:

  • A (numpy.ndarray) – An \(m imes n\) matrix with \(n>m\)

  • b (numpy.ndarray) – Right-hand sides. \(\mathbf{b} \in \mathbf{R}^m\)

  • order (Iterable[int], Optional) – An arbitrary permutation of the indices.

Returns:

  • numpy.ndarray – Coefficient matrix \(\mathbf{B}\)

  • numpy.ndarray – Inverse of coefficient matrix \(\mathbf{B}^{-1}\)

  • numpy.ndarray – Coefficient matrix \(\mathbf{N}\)

  • numpy.ndarray – Basic solution \(\mathbf{x}_{B}\)

  • numpy.ndarray – Remaining solution \(\mathbf{x}_{N}\)

eval_constraints(x: Iterable) → Iterable[source]#

Evaluates the constraints at x.

static example_unique() → LinearProgrammingProblem[source]#

Returns the following LPP:

\begin{eqnarray} & minimize& \quad 3 x_1 + x_2 + 9 x_3 + x_4 \\ & subject \, to& & \\ & & 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}

The returned LPP has a unique solution:

\(\quad \mathbf{x} = (0., 6., 0., 4.), \quad f(\mathbf{x}) = 10.\)

Example

>>> from sigmaepsilon.math.optimize import LinearProgrammingProblem as LPP
>>> problem = LPP.example_unique()
>>> problem.solve()['x']
array([0., 6., 0., 4.])
feasible(x: Iterable | None = None) → bool[source]#

Returns True if x is a feasible candidate to the current problem, False othwerise.

get_slack_variables(template=None) → list[source]#

Returns the slack variables of the inequality constraints of the problem.

get_system_variables() → list[source]#

Returns all variables of the system.

has_standardform() → bool[source]#

Tells if the object admits the standard form of a linear program or not.

Notes

An LPP admits standard form if

  • only equality constraints are present

  • all variables are positive

Returns:

True if the problem admits the standard form of an LPP.

Return type:

bool

maximize(*args, **kwargs) → dict[source]#

Solves the LPP as a maximization. For the possible arguments, and return types see solve.

simplify(maximize=False, inplace=False) → LinearProgrammingProblem[source]#

Simplifies the problem so that it admits the standard form.

This is done in 3 steps:

  1. Decomposing variables not restricted in sign according to

    \(x = x^{+} - x^{-}, \quad \mid x \mid = x^{+} + x^{-}\),

    where

    \(x^{+} = max(0, x) \geq 0, \quad x^{-} = max(0, -x) \geq 0\).

    Then the variable \(x\) can be substituted by

    \(x = x^{+} - x^{-}\) and the conditions \(\quad x^{+}, x^{-} \geq 0\).

  2. Transforming inequalities into equalities using slack variables.

    We introduce new variables

    \(\mathbf{y} = \mathbf{b} - \mathbf{A} \mathbf{x} \geq \mathbf{0}\),

    and formulate the extended problem

    \(\hat{\mathbf{A}} \mathbf{X} = \mathbf{b}\),

    where

    \(\mathbf{X} = (\mathbf{x} \, \, \mathbf{y}), \quad \hat{\mathbf{A}} = (\mathbf{A} \, \, \mathbf{1})\).

  3. Transform to minimization problem if necessary using the simple rule

    \(max(f) = -min(-f)\).

Parameters:

  • maximize (bool) – Set this true if the problem is a maximization. Default is False.

  • inplace (bool) – If True, transformation happend in place, changing the internal structure ob the instance it is invoked by. In this case, self gets returned for possible continuation.

Notes

Steps 1) and 2) both increase the number of variables of the standard system.

Returns:

  • LinearProgrammingProblem – An LPP that admits a standard form.

  • dict, Optional – A mapping between variables of the standard and the general form. Only if return_inverse is True.

Raises:

NotImplementedError – On invalid input.

solve(order=None, return_all: bool = True, maximize: bool = False, as_dict: bool = False, raise_errors: bool = False, tol: float = 1e-10)[source]#

Solves the problem and returns the solution(s) if there are any.

Parameters:

  • order (Iterable, Optional) – The order of the variables. This might speed up finding the basic solution. Default is None.

  • as_dict (bool) – If True, the results are returned as a dictionary, where the keys are sympy symbols of the variables of the problem.

  • raise_errors (bool) – If True, the solution raises the actual errors on exception events, otherwise they get returned within the result, under key e.

  • tol (float, Optional) – Floating point tolerance. Default is 1e-10.

Notes

It is assumed that this function gets invoked on relatively small problems. For large-scale situations, we suggest to use solve_standard_form function of this class instead. Contrary to this one, it rases errors, while the more high-level solve method of the instance catches those errors, and returns them as part of the returned dictionary.

Returns:

A dictionary with the following items: x : numpy.ndarray or dict

The solution as an array or a dictionary, depending on your input.

eIterable

A list of errors that occured during solution.

timedict

A dictionary with information of execution times of the main stages of the calculation.

Return type:

dict

static solve_standard_form(A: ndarray, b: ndarray, c: ndarray, order=None, tol: float = 1e-10)[source]#

Solves a linear problem in standard form:

\(minimize \quad \mathbf{c} \mathbf{x} \quad under \quad \mathbf{A}\mathbf{x} = \mathbf{b}\).

See the notes section for the behaviour and the possible gotchas.

Parameters:

  • A (numpy.ndarray) – 2d float array.

  • b (numpy.ndarray) – 1d float array.

  • c (numpy.ndarray) – 1d float array.

  • order (Iterable, Optional) – The order of the variables.

  • tol (float, Optional) – Floating point tolerance. Default is 1e-10.

Returns:

Results as a 1d (unique solution) or a 2d (multiple solutions) numpy array.

Return type:

numpy.ndarray

Notes

1) The value of the parameter tol is used to make judgements on the vanishing ratios of entering variables, therfore effects the detection of degenerate situations. The higher the value, the more tolerant the system is to violations.

2) The line between the unique, the degenerate situation and having no solution at all may be very thin in some settings. In such a scenario, repeated solutions might return a a solution, a NoSolutionError or a DegenerateProblemError as well. Problems with this behaviour are all considered degenerate, and suggest an ill-posed setup.

Raises:
to_numpy(maximize: bool = False, return_coeffs: bool = False)[source]#

Returns the complete numerical representation of the standard form of the problem:

\(minimize \quad \mathbf{c} \mathbf{x} \quad under \quad \mathbf{A}\mathbf{x} = \mathbf{b}\).

Parameters:

  • maximize (bool) – Set this true if the problem is a maximization. Default is False.

  • return_coeffs (bool) – If True, linear coefficients of the design variables are returned as a sequence of SymPy symbols.

Returns:

  • numpy.ndarray – 2d NumPy array ‘A’

  • numpy.ndarray – 1d NumPy array ‘b’

  • list, Optional – A list of SymPy symbols. Only if return_coeffs is True.

class sigmaepsilon.math.optimize.DegenerateProblemError[source]#

The problem is degenerate.

The objective could be decreased, but only on the expense of violating positivity of the standard variables.

class sigmaepsilon.math.optimize.NoSolutionError[source]#

There is no solution to this problem.

Step size could be indefinitely increased in a direction without violating feasibility.