Linear Optimization

linOpt: Linear Optimization

This subpackage contains solver for linear optimization problems e.g methods to solve

\[\text{max } c^T x\]

\[\text{s. t. } Ax \leq b\]

\[x \geq 0\]

where you can use the simplex() algorithm or, if in addition you need

\[x \in \mathbb{N}\]

you can use the b_and_b() method.

Documentation is available in the docstrings and online here.

Methods

oppy.linOpt.b_and_b module

Branch and Bound algorithm.

This Module contains the function b_and_b() and all helper functions to solve the problem of finding an integer solution to a linear program, e.g. solve:

\[\text{max } c^T x\]

\[\text{s. t. } Ax \leq b\]

\[x \geq 0\]

\[x \in \mathbb{N}\]

oppy.linOpt.b_and_b.b_and_b(c, N, b, options=None)

Branch and bound method to find the best integer solution.

Parameters:

c (numpy.ndarray, shape (n,)) – Vector from the costfunction \(c^T x\).
N (numpy.ndarray, shape (n,m)) – 2 dimensional and represent the matrix from the constraints.
b (numpy.ndarray, shape (m,)) – Is the vector of the inequalities.
options (Options, optional) –
Options for b_and_b(), represented as a Options object. The default is None. Possible options are:
- dispbool, optional
  
  Depending on disp, the algorithm shows some results during the process. If disp is False branch and bound doesn’t show any results. If disp is True branch and bound show some results. The default is disp = False.
- variable_searchint, optional
  
  if variable_search=0, choose the index which the variable is furthest away from integer; if =1 choose the first minimal index; if =2 choose the first maximal index; if =3 choose the first possible index; and if =4 choose with strong branching. The default is 0.
- initialstr, optional
  
  If initial is 'deepfirst' the algorithm tries to find an integer solution with deepfirst method. If intial is ‘bestsolution’, the algorithm try to find an integer solution with bestsolution method. The default is 'deepfirst'.
- nodesearchstr, optional
  
  If nodesearch = 'deepfirst' the algorithm tries to find an integer solution with deepfirst method; if nodesarch = 'bestsolution' the algorithm tries to find an integer solution with bestsolution method. The default is nodesearch = 'bestsolution'.
- maxiterint or float, optional
  
  Maximum number of iterations. The default is 1e3.

Returns:

res – Instance of the class Results. Represents the results of the solver. Attributes of the object are

boundint

Status of the bound. Bound=0 means, that the problem is bound, the algorithm has found a solution, bound=1 means, that the problem is primal unbound, that means, that the problem ist unbound, bound=2 means, that the problem is dual unbound, that means that the problem is infeasible and bound=3 means, that the maxiter is reached.

x_optnumpy.ndarray, shape (n,)

Is the vector of the optimal values.

f_optfloat

Is the maximum of \(c^T x\).

iterationsint

Is the number of iterations.

timefloat

Represent the the time the algorihtm needs for execution.

Return type:

Results

References

G. Sierksma, Linear and inger programming: theory and practice, see Sierksma [Sie01].

Robert J. Vanderbei, Linear programming, see Vanderbei [Van20].

Examples

Solve the problem

\[\max 1000 x_1 + 700 x_2\]

\[\text{s. t. } 100 x_1 + 50 x_2 \leq 2425\]

\[20 x_2 \leq 510\]

\[x_1, x_2 \geq 0\]

\[x_1, x_2 \in \mathbb{N}\]

Setting:

>>> from oppy.linOpt import b_and_b
>>> import numpy as np
>>> c = np.array([1000, 700])
>>> N = np.array([[100, 50], [0, 20]])
>>> b = np.array([2425, 510])

And solve with the branch and bound (b_and_b()) algorithm

>>> sol = b_and_b(c, N, b)

We get the expected solution

\[x_1= 12, x_2=24\]

via

>>> print(sol.x_opt)
>>> [12. 24.]

oppy.linOpt.b_and_b.isinteger(x)

Verify elementwise to an integer.

Parameters:	x (`numpy.ndarray`, shape (n,)) – Input array to check.
Returns:	ma – Where integers are saved.
Return type:	`numpy.ma`, shape (n,)

oppy.linOpt.b_and_b.strong_branching(P, ma, c)

Verify the indices which have the minimal opt.

Parameters:	P (`dict`) – Solution dictionary of a solved LP. ma (`numpy.ma`, shape (n,)) – Represent the integer test. c (`numpy.ndarray`, shape (m,)) – Vector of the costfunction.
Returns:	z – The index which have the minimal opt.
Return type:	`int`

References

G. Sierksma, Linear and inger programming: theory and practice, see Sierksma [Sie01].

oppy.linOpt.b_and_b.initial_b_and_b(c, N, b, disp=False, variable_search=0, initial='deepfirst', maxiter=1000.0)

Branch and bound method to find a first feasible solution.

Parameters:

c (numpy.ndarray, shape (n,)) – Vector from the costfunction \(c^T x\).
N (numpy.ndarray, shape (n,m)) – 2 dimensional and represent the matrix from the constraints.
b (numpy.ndarray, shape (m,)) – Is the vector of the inequalities.
disp (bool, optional) – Depending on disp, the algorithm shows some results during the process. If disp is False branch and bound doesn’t show any results. If disp is True branch and bound show some results. The default is False.
variable_search (int, optional) – if variable_search=0, choose the index which the variable is furthest away from integer; if =1 choose the first minimal index; if =2 choose the first maximal index; if =3 choose the first possible index; and if =4 choose with strong branching. The default is 0.
initial (str, optional) – If initial is ‘deepfirst’ the algorithm tries to find an integer solution with deepfirst method. If initial is ‘bestsolution’, the algorithm tries to find an integer solution with bestsolution method. The default is ‘deepfirst’.
maxiter (int or float, optional) – Maximum number of iterations. The default is 1e3.

Returns:

res –

Dictionary, containing

boundint

Status of the bound. Bound=0 means, that the problem is bound, the algorithm has found a solution, bound=1 means, that the problem is primal unbound, that means, that the problem ist unbound, bound=2 means, that the problem is dual unbound, that means that the problem is infeasible and bound=3 means, that the maxiter is reached.
x_optnumpy.ndarray, shape (n,)

Is the vector of the optimal values.
f_optfloat

Is the maximum of \(c^T x\).
iterations: int

Is the number of iterations.
timefloat

Represent the the time the algorithm needed.

Return type:

dict

References

G. Sierksma, Linear and inger programming: theory and practice, see Sierksma [Sie01].

Robert J. Vanderbei, Linear programming, see Vanderbei [Van20].

oppy.linOpt.simplex module

Simplex Method.

This Module contains the function simplex() and all helper functions to solve the problem of finding a solution to a linear program, e.g. solve:

\[\text{max } c^T x\]

\[\text{s. t. } Ax \leq b\]

\[x \geq 0\]

oppy.linOpt.simplex.simplex(c, N, b, options=None)

Simplex Method.

Solve problems of the form

\[\max c^\top x\]

\[s.T. Nx \leq b\]

\[x \geq 0\]

Parameters:

c (numpy.ndarray, shape (n,)) – Vector from the costfunction :math`c^Tx`.
N (numpy.ndarray, shape (n,m)) – 2 dimensional and represent the matrix from the constraints.
b (numpy.ndarray, shape (m,)) – Is the vector of the inequalities.
options (Options, optional) –
Options for simplex, represented as a Options object. The default is None. Possible options are:
- dispbool, optional
  
  Depending on dips, the algorithm shows some results during the process. If disp is False simplex doesn’t show any results. If disp is True simplex show some resutls. The default is False.
- maxiterint or float, optional
  
  Maximum number of iterations. The default is 1e4.

Returns:

res – Instance of the class Results. Represents the results of the solver. Attributes of the object are (depending on feasible and bound)

feasible int

Status which represent the feasible of the problem; feasible=1 means that the problem is primal feasible feasible=2 means that the problem is dual feasible feasible=3 means that the problem is wether primal nor dual feasible.

boundint

Status of the bound. Bound=0 means, that the problem is bound, the algorithm has found a solution, bound=1 means, that the problem is primal unbound, that means, that the problem ist unbound, bound=2 means, that the problem is dual unbound, that means that the problem is infeasible and bound=3 means, that the maxiter is reached.

x_optnumpy.ndarray, shape (n,)

Is the vector of the optimal values.

f_optfloat

Is the maximum of :math`c^Tx`.

iterationsint

Is the number of iterations.

timefloat

Represent the the time the algorihtm need.

Anumpy.ndarray, shape (n,n)

Is the initial matrix.

CB, CNnumpy.ndarray, shape (n,)

Are die basic and nonbasic sets from the old one.

x_bnumpy.ndarray, shape (n,)

Is the x_b from the old one.

z_nnumpy.ndarray, shape (n,)

Is the z_n from the old one.

cnumpy.ndarray, shape (n,)

Is the vector which represent the cost function.

bnumpy.ndarray, shape (n,)

Is the whole vector which represent all constraint.

Bnumpy.ndarray, shape (n,n)

Represent the last basic matrix.

Return type:

Results

References

Robert J. Vanderbei, Linear programming. Vol. 3, see Vanderbei [Van20].

Examples

Solve the problem

\[\max c^\top x\]

\[s.T. Nx \leq b\]

with random inputs.

>>> import numpy as np
>>> from oppy.linOpt import simplex
>>> c = np.random.rand(10)
>>> b = np.random.rand(8)
>>> N = np.random.rand(8, 10)

And solve it with the simplex() algorithm.

>>> P = simplex(c, N, b)
>>> print(P.f_opt)
>>> 0.15551

Notice, that this value varies because of the random input.

oppy.linOpt.simplex.division(a, b)

Ignore divide by zero.

Parameters:	a (`numpy.ndarray`, shape (n,)) – Array of numerator(s). b (`numpy.ndarray`, shape (n,)) – Array of divisor(s).
Returns:	c – Solution of numerator(s)/divisor/(s) ignoring zeros.
Return type:	`numpy.ndarray`, shape (n,)

Examples

Ignore divsion over zero(s). Define two arrays, e.g.

>>> a = np.array([-1, 0, 1])
>>> b = np.array([0, 0, 0])

The function division will now ignore zero division which means, 0/0=0.

>>> c = division(a, b)
>>> print(c)
>>> [-inf, 0., inf]

oppy.linOpt.simplex.dsimplex(P, v, b, disp=False, maxiter=10000)

Dual simplex method.

Dual simplex method to solve Problems after adding a new constraint. This method is special made for branch and bound algorithm.

Parameters:

P (dict) – The dict with the return of the old problem.
v (numpy.ndarray, shape (n,)) – Represent the vector which represent the new constraint.
b (float) – The new constraint.
disp (bool, optional) – Depending on dips, the algorithm shows some results during the process. If disp is False simplex doesn’t show any results. If disp is True simplex show some results. The default is False.
maxiter (int or float, optional) – Maximum number of iterations. The default is 10000.

Returns:

res –

Dictionary, containing

boundint

Status of the bound. Bound=0 means, that the problem is bound, the algorithm has found a solution, bound=1 means, that the problem is primal unbound, that means, that the problem ist unbound, bound=2 means, that the problem is dual unbound, that means that the problem is infeasible and bound=3 means, that the maxiter is reached.

x_optnumpy.ndarray, shape (n,)

Is the vector of the optimal values.

f_optfloat

Is the maximum of \(c^T x\).

iterationsint

Is the number of iterations.

timefloat

Represent the the time the algorithm need.

Anumpy.ndarray, shape (n,n)

Is the initial matrix.

CB, CNnumpy.ndarray, shape (n,)

Are die basic and nonbasic sets from the old one.

x_bnumpy.ndarray, shape (n,)

Is the x_b from the old one.

z_nnumpy.ndarray, shape (n,)

Is the z_n from the old one.

cnumpy.ndarray, shape (n,)

Is the vector which represent the cost function.

bnumpy.ndarray, shape (n,)

Is the whole vector which represent all constraint.

Bnumpy.ndarray, shape (n,n)

Represent the last basic matrix.

Return type:

dict

References

Robert J. Vanderbei, Linear programming. Vol. 3, see Vanderbei [Van20].

oppy.linOpt.simplex.solve_primal(C, n, m, B, A, x_b, z_n, CB, CN, count, x_opt, bound, maxiter)

Primal solver for the simplex method.

Simplex method to solve a primal feasible problem like

\[\max c^\top x\]

\[s.T. Ax = b\]

Parameters:

C (numpy.ndarray, shape (n,n)) – Copy from N, the matrix from the constraints.
n (int) – m and n are the integers which represent the size from A.
m (int) – m and n are the integers which represent the size from A.
B (numpy.ndarray, shape (m,m)) – Represent the basic matrix.
A (numpy.ndarray) – Represent the whole matrix A = [N,B].
x_b (numpy.ndarray, shape (n,)) – Vector of x_b from the algorithm, usually x_b = b.
z_n (numpy.ndarray, shape (n,)) – Vector of z_n from the algorithm, usually z_n = -c.
CB (numpy.ndarray, shape (n,)) – CB represent the set of basic indices.
CN (numpy.ndarray, shape (n,)) – CN represent the set of nonbasic indices.
count (int) – An integer number which counts the number of iterations.
x_opt (numpy.ndarray, shape (n,)) – normally at the beginning it is a zero-vector.
bound (bool) – the initial bound.
maxiter (int or float) – maximum number of iterations.

Returns:

res – if the problem is bound than it returns the optimum, if not, then it returns the status that the problem is unbound.

boundint

Status of the bound. Bound=0 means, that the problem is bound, the algorithm has found a solution, bound=1 means, that the problem is primal unbound, that means, that the problem ist unbound, bound=2 means, that the problem is dual unbound, that means that the problem is infeasible and bound=3 means, that the maxiter is reached.

x_optnumpy.ndarray, shape (n,)

Is the vector of the optimal values.

iterationsint

Is the number of iterations.

CB, CNnumpy.ndarray, shape (n,)

Are die basic and nonbasic sets from the old one.

x_bnumpy.ndarray, shape (n,)

Is the x_b from the old one.

z_nnumpy.ndarray, shape (n,)

Is the z_n from the old one.

Return type:

dict

References

Robert J. Vanderbei, Linear programming. Vol. 3, see Vanderbei [Van20].

oppy.linOpt.simplex.solve_dual(C, n, m, B, A, x_b, z_n, CB, CN, count, x_opt, bound, maxiter)

Dual solver for the simplex method.

Simplex method to solve a dual feasible problem like

\[\max c^\top x\]

\[s.T. Ax = b\]

Parameters:

C (numpy.ndarray, shape (n,n)) – Copy from N, the matrix from the constraints.
n (int) – m and n are the integers which represent the size from A.
m (int) – m and n are the integers which represent the size from A.
B (numpy.ndarray, shape (n,n)) – Represent the basic matrix.
A (numpy.ndarray, shape (n,n)) – Represent the whole matrix A = [N,B].
x_b (numpy.ndarray, shape (n,)) – Vector of x_b from the algorithm, usually x_b = b.
z_n (numpy.ndarray, shape (n,)) – Vector of z_n from the algorithm, usually z_n = -c.
CB (numpy.ndarray, shape (n,)) – CB represent the set of basic indices.
CN (numpy.ndarray, shape (n,)) – CN represent the set of nonbasic indices.
count (int) – An integer number which counts the number of iterations.
x_opt (numpy.ndarray, shape (n,)) – normally at the beginning it is a zero-vector.
bound (bool) – the initial bound.
maxiter (int or float) – maximum number of iterations.

Returns:

res – if the problem is bound than it returns the optimum, if not, then it returns the status that the problem is unbound.

boundint

Status of the bound. Bound=0 means, that the problem is bound, the algorithm has found a solution, bound=1 means, that the problem is primal unbound, that means, that the problem ist unbound, bound=2 means, that the problem is dual unbound, that means that the problem is infeasible and bound=3 means, that the maxiter is reached.

x_optnumpy.ndarray, shape (n,)

Is the vector of the optimal values.

iterationsint

Is the number of iterations.

CB, CNnumpy.ndarray, shape (n,)

Are die basic and nonbasic sets from the old one.

x_bnumpy.ndarray, shape (n,)

Is the x_b from the old one.

z_nnumpy.ndarray, shape (n,)

Is the z_n from the old one.

Return type:

dict

References

Robert J. Vanderbei, Linear programming. Vol. 3, see Vanderbei [Van20].