# solving multiple linear programming problems with the same set of constraints

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?

• The first phase of the simplex method is to find a feasible point in the polytope. This could be amortized across the different problem instances. Jun 2, 2011 at 18:16
• It would be really hard to benefit from having the same constraint set beyond choosing the common starting point because in high dimension relatively few planes may determine a multitude of edges and vertices, so any attempt to see the domain as a whole is doomed. Any decently fast method goes only over a tiny part of the entire space, so no knowledge acquired during the first 1000 runs can really help in the 1001st because, most likely, your 1001st extremum is in a totally uncharted territory. Jun 2, 2011 at 19:37
• There is not enough information in the question. How many variables? How many constraints? Any relationship between the objectives? As for @David Harris' comment, that is very true, but it is usually difficult to decouple the two phases in canned codes. Jun 2, 2011 at 19:53
• It seems to me that the OP told that quite explicitly: 100, 100, No. Jun 2, 2011 at 20:46
• @Igor Hmm... I thought that the phrase "don't see any obvious relation between the different ci's, so we can assume for example that they're drawn at random (each coordinate can be an i.i.d. standard Gaussian)" means exactly what it reads (in which case what I wrote is true, isn't it?). On the other hand, I agree that people almost always ask the wrong question (even mathematicians). So have it your way: I cannot add much to what I said anyway unless the real problem is totally different from what I perceived it to be. Jun 3, 2011 at 4:29