Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
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. –  David Harris Jun 2 '11 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. –  fedja Jun 2 '11 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. –  Igor Rivin Jun 2 '11 at 19:53
    
It seems to me that the OP told that quite explicitly: 100, 100, No. –  fedja Jun 2 '11 at 20:46
1  
@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. –  fedja Jun 3 '11 at 4:29
show 1 more comment

1 Answer

Where do the different objective functions come from? Perhaps if we knew more about your problem we could make a helpful suggestion about how to approach it.

If the objective functions are totally unreleated to each other, then other than having a feasible solution to the LP, solving one of your LP's isn't very useful for solving any of the other LP's.

The standard approach that you should be aware of is "warm starting" the simplex method with the optimal basis for problem i as the starting point for the solution of problem i+1. Note that although warm starting the simplex method can be very helpful for small changes in the objective function, it can actually slow things down if there are large changes to the objective function. Most modern solvers use a heuristic "crash basis" to start the simplex method and these usually work very well.

For interior point methods for linear programming there are no well developed methods for warm starting with a new objective function.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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