Creating Integer Range from multiple string math expressions in python

Question

I have a problem in a project and I've searched the internet high and low with no clear answer. How can i convert math expressions As 3x + 5y >= 100 And x,y < 500 Into a range of x and range of y to be used as ristriction in a math problem, Ex: f = x^2+4y The end result is to find the largest answer using genetic algorithms where x and y are ristricted in value.

Tried sympy and eval with no luck Searched every and found only a few helpful but not enough resources I need just to translate the user input to the code for the genetic algorithm to use.

Note that systems of linear inequations like 3x+5y>=100 tend to correspond to polygons, not to squares necessarily. In other words, they usually cannot be decomposed into a separate range for x and range for y. — Stef, Dec 21 '22 at 14:25
For instance, the region described by 3x+5y>=100, x<=500, y<=500 is this one: https://i.imgur.com/yIImlLP.png . It's not an axis-aligned rectangle, but a triangle. The three vertices of the triangle are: (x=-800, y=500), (x=500, y=500), (x=500, y=-280) — Stef, Dec 21 '22 at 14:33
Perhaps this can be a better answer to your question: [How to find all vertices of a polyhedron given by a set of linear inequalities?](https://or.stackexchange.com/questions/4540/how-to-find-all-vertices-of-a-polyhedron) — Stef, Dec 21 '22 at 14:34
*" f = x^2+4y The end result is to find the largest answer"* This is new, I didn't see this before. So you're actually not interested in the polygon at all, only on maximising this objective function?? That's a lot easier! — Stef, Dec 25 '22 at 22:49
How Can I do that but by using multiple deferent x,y,z parameters, my goal here is to generate n number of x,y,z params without taking minutes of looping and random generating — Bashar, Dec 26 '22 at 08:05
I recommend taking a look at [scipy.optimize: Optimisation and root-finding](https://docs.scipy.org/doc/scipy/reference/optimize.html). Note that if objective function f is linear or quadratic, it's a lot easier than if it isn't. Searching for "quadratic programming python" can also give you specialised modules, for instance [qpsolvers](https://pypi.org/project/qpsolvers/) or [cvxopt](https://pypi.org/project/qpsolvers/), but I recommend only going for a specialised quadratic programming module if you haven't found what you want with scipy, numpy or sympy. — Stef, Dec 26 '22 at 10:21
See also this related question: [Quadratic programming: QP solvers that only depend on numpy/scipy?](https://stackoverflow.com/questions/17009774/quadratic-program-qp-solver-that-only-depends-on-numpy-scipy) — Stef, Dec 26 '22 at 10:22
Note that "quadratic programming" means "linear constraints and quadratic objective function", which is exactly your situation. — Stef, Dec 26 '22 at 10:22
There might be more results on the Operations Research stackexchange than on stackoverflow: https://or.stackexchange.com/search?q=quadratic+programming+python — Stef, Dec 26 '22 at 10:25

score 1 · Answer 1 · answered Dec 21 '22 at 15:11

Your set of linear inequations define a polygon in the plane.

The edges of this polygon are the lines defined by each equality that you get by replacing the inequal sign by an equal sign in an inequality.

The vertices of this polygon are the intersections of two adjacent edges; equivalently, they are the intersections of two edges that satisfy the system of (large) inequalities.

So, one way to find all the vertices of the polygon is to find every intersection point by solving every subsystem of two equalities, then filtering out the points that are outside of the polygon.

import numpy as np
from numpy.linalg import solve, LinAlgError
from itertools import combinations
import matplotlib.pyplot as plt

A = np.array([[-3, -5],[1,0],[0,1]])
b = np.array([-100,500,500])

# find polygon for system of linear inequations
# expects input in "less than" form:
# A X <= b
def get_polygon(A, b, tol = 1e-5):
    polygon = []
    for subsystem in map(list, combinations(range(len(A)), 2)):
        try:
            polygon.append(solve(A[subsystem], b[subsystem])) # solve subsystem of 2 equalities
        except LinAlgError:
            pass
    polygon = np.array(polygon)
    polygon = polygon[(polygon @ A.T <= b + tol).all(axis=1)] # filter out points outside of polygon
    return polygon

polygon = get_polygon(A, b)
polygon = np.vstack((polygon, polygon[0])) # duplicate first point of polygon to "close the loop" before plotting
plt.plot(polygon[:,0], polygon[:,1])
plt.show()

Note that get_polygon will find all vertices of the polygon, but if there are more than 3, they might not be ordered in clockwise order.

If you want to sort the vertices in clockwise order before plotting the polygon, I refer you to this question:

How to sort a list of points in clockwise/anticlockwise in python?

Sorry for taking a long time to answer, while this approach functions I'm aware of it and I'm actually looking for a more dynamic approach without looping for seconds wjust to generate a population of 20 — Bashar, Dec 25 '22 at 20:48

score 1 · Answer 2 · answered Dec 21 '22 at 18:27

Using @Stef's approach in SymPy would give the triangular region of interest like this:

>>> from sympy.abc import x, y
>>> from sympy import intersection, Triangle, Line
>>> eqs = Eq(3*x+5*y,100), Eq(x,500), Eq(y,500)
>>> Triangle(*intersection(*[Line(eq) for eq in eqs], pairwise=True))
Triangle(Point2D(-800, 500), Point2D(500, -280), Point2D(500, 500))

So x is in range [-800, 500] and y is in range [m, 500] where m is the y value calculated from the equation of the diagonal:

m = solve(eqs[0], y)[0]  # m(x)
def yval(xi):
    if xi <-800 or xi > 500:
        return
    return m.subs(x,xi)
yval(300) # -> -160

Sorry for taking a long time to answer, i need a more dynamic and fast approach to get x,y,z values without looping for one minute, i've tried pulp but could not randomise the x,y z combinations — Bashar, Dec 25 '22 at 20:51

Creating Integer Range from multiple string math expressions in python

2 Answers2