# Making a batch of related linear problems more efficient

I have a linear system that is of the form

$$My = b \\ L \leq y \leq U$$

i.e. all of the $$y_i$$ are potentially bounded, and there are various linear relationships between them.

I want to find the tightest possible upper and lower bounds for each $$y_i$$, meaning that I am running $$n$$ maximisation and $$n$$ minimisation problems with the same constraints but changing the objective each time. Obviously, these values are often going to be related to each other.

Is there a way of making this process more efficient? My first thought is to keep track of the generated solutions and use them to update the lower and upper bounds, i.e. something like:

for i in [1..n]
Find min(y_i) for the system
set L[i] = min(y_i)
Find max(y_i) for the system
set U[i] = max(y_i)


My other thought is that if $$y[j] = L[j]$$ in any given solution, then since we know a solution exists in which it reaches its lower bound then we don't need to minimise, and similarly if $$y[j] = U[j]$$, so I can set some flags to avoid running any unnecessary LPs.

Are these reasonable ideas? Is there another way of improving the efficiency?

In case it's relevant, I am likely to be setting these problems up in either R or python, using cvxr/cvxpy, and either a free solver or Gurobi.

• As you want to find the tightest possible upper and lower bounds, why not try adding LB and UB as the decision variables and adding them to the objective function to optimize them? Nov 28, 2023 at 7:11
• Also, it might be a complicated task if you want to know the possible range of these LB and UB. As actually there are lots of possible ranges. Nov 28, 2023 at 7:15

Another thought: since the basis that maximizes $$y_i$$ is likely much different from the one that minimizes $$y_i,$$ you might want to do all the mins, then all the maxes rather than go variable by variable. Combined with hot starts, it might (or might not) save you a few pivots.
• Before maximizing or minimizing individual $y_i$ variables, it is worth trying to maximize or minimize $\sum_i y_i$ in an attempt to deduce the bounds of multiple variables with one solve. Nov 28, 2023 at 22:12
• Because of the way the $y_i$ are related, it will often be the case that the minimiser of one is the maximiser of another, so I'm not sure whether doing all minimisations first will necessarily help, but I will experiment with it. Your other suggestions are definitely something I will look into further. Nov 28, 2023 at 22:24