Hi,

I need to solve a set of linear programs of the form:

Problem $i$: $\quad \max c_i \cdot x$ s.t. $ A x \leq b$.

The $c_i$'s are different vectors so each problem has a different objective function. I currently solve them one by one using the simplex algorithm. (In my particular problem there are a few thousands such problems, each with a few hundreds variables and constrains).

Is there any way to use the fact that all problems share the same constrains in order to speed-up their solution? (my guess is that the simplex algorithm may not be a good candidate for this problem since it simply traverses the solution space and for different objective functions it will need explore different parts of the space)

I don't see any obvious relation between the different $c_i$'s, so we can assume for example that they're drawn at random (each coordinate can be an i.i.d. standard Gaussian). I've considered looking at the dual case - then you get the same objective function but each problem has its own constrains, but don't have a concrete plan exploiting this fact.

Googling found some stuff on 'linear programs with multiple objective functions' but it seems like they try to achieve one solution which is 'reasoanble' with respect to each objective function. I want to find the exact (different) solution for each objective, and couldn't find a reference for that. Is the computational complexity simply linear in the number of problems, or can we do better?

1more comment