Specifying greater than inequality in scipy

Question

I've solved a simple LP problem where all constraints are "less than or equal to".

I used scipy.optimize.linprog for those.

The problem is when one or more of the constraints equation is "greater than or equal to". How do I specify that? I need to use the two-phase approach provided by scipy.optimize.linprog

An example of such is:

    7X1 + 4X2 + 9X3 ≥ 750                                                                              
    4X1 + 6X2 + 7X3 ≤ 40
    17X1 + 9X2 + 2.5X3 ≥ 3540                                                                              
    56X1 + 3X2 + 27X3 ≤ 6450

Answer 1

Here is a wrapper that incorporates lower bound rows in the lingprog formulation. Note that more error trapping is necessary (for example, the number of columns of each A matrix need to be equal), this is not meant to be a robust implementation. For proper error trapping, I suggest you skim through the linprog source code.

from scipy.optimize import linprog
import numpy as np

def linprog_lb_wrapper(c, A_ub=None, b_ub=None, A_lb=None, b_lb=None, A_eq=None, b_eq=None, \
    bounds=None, method='simplex', callback=None, options=None):

    if A_lb is None:
        res = linprog(c, A_ub, b_ub, A_eq, b_eq, bounds, method, callback, options)
        return res
    elif (b_lb is None) or (len(b_lb) != len(A_lb)):
        # catch the error here
        print('Error')

    A_ub_new, b_ub_new = np.array(A_ub), np.array(b_ub)
    A_lb_new, b_lb_new = np.array(A_lb), np.array(b_lb)
    A_lb_new *= -1.
    b_lb_new *= -1.
    A_ub_new = np.vstack((A_ub_new, A_lb_new))
    b_ub_new = np.vstack((b_ub_new, b_lb_new))

    res = linprog(c=c, A_ub=A_ub_new, b_ub=b_ub_new, A_eq=A_eq, b_eq=b_eq, bounds=bounds, \ 
        method=method, callback=callback, options=options)

    return res

def test():
    c = [0, 0, 0]
    A_ub = [[4, 6, 7], [56, 3, 27]]
    b_ub = [40, 6450]
    A_lb = [[7, 4, 9], [17, 9, 2.5]]
    b_lb = [750, 3540]
    bounds = ((None, None), (None, None), (None, None))

    res = linprog_lb_wrapper(c=c, A_ub=A_ub, b_ub=b_ub, A_lb=A_lb, b_lb=b_lb, bounds=bounds)
    print(res)

test()

Note that for the instance that you presented, there is no feasible solution (I checked this with another solver as well and got an infeasibility proof).

I hope this helps.

This code can be tested here.

Answer 2

To express a "greater than or equal to" constraint in scipy.optimize.linprog, you can multiply each side of the constraint by -1 to convert the constraint into the expected format of "less than or equal to".

For instance, in the example provided, the constraint matrix with mixed inequalities would have been

A = [[7, 4, 9], [4, 6, 7], [17, 9, 2.5], [56, 3, 27]]

with right-hand side

b = [750, 40, 3540, 6450]

and we want to express the constraints as Ax <= b. So, in order to flip the necessary inequalities, the constraint matrix becomes

A = [[-7, -4, -9], [4, 6, 7], [-17, -9, -2.5], [56, 3, 27]]

and the right-hand side becomes

b = [-750, 40, -3540, 6450]

Then we can pass the arguments A_ub=A and b_ub=b to linprog.