4
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – David Harris
    Commented Jun 2, 2011 at 18:16
  • $\begingroup$ 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. $\endgroup$
    – fedja
    Commented Jun 2, 2011 at 19:37
  • $\begingroup$ 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. $\endgroup$
    – Igor Rivin
    Commented Jun 2, 2011 at 19:53
  • $\begingroup$ It seems to me that the OP told that quite explicitly: 100, 100, No. $\endgroup$
    – fedja
    Commented Jun 2, 2011 at 20:46
  • 1
    $\begingroup$ @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. $\endgroup$
    – fedja
    Commented Jun 3, 2011 at 4:29

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Do you know about heuristic methods for integer linear programming? $\endgroup$
    – Nick
    Commented Oct 18, 2016 at 6:30
  • $\begingroup$ @Nick, your comment doesn't have anything to do with the original question or my answer. Perhaps you should ask a new question. $\endgroup$
    – Brian Borchers
    Commented Oct 18, 2016 at 14:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .