1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – A.Omidi
    Nov 28, 2023 at 7:11
  • $\begingroup$ 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. $\endgroup$
    – A.Omidi
    Nov 28, 2023 at 7:15

1 Answer 1

1
$\begingroup$

Your idea to tighten lower/upper bounds after solving for the min/max of the corresponding variable is fine. It may or may not provide improvements in speed. Taking a bound off the list of things to tighten any time a feasible solution hits that bound is also a good idea.

One other thing you can do that might help speed things up is to assure that hot-starts are turned on for whatever solver you are using. The optimal basis to the last LP you solved will be a valid starting basis for the next LP.

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.

You might also want to see if using an interior point method helps, especially if the solver will hot start from the previous interior point.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – RobPratt
    Nov 28, 2023 at 22:12
  • $\begingroup$ 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. $\endgroup$
    – ConMan
    Nov 28, 2023 at 22:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.