Timeline for solving multiple linear programming problems with the same set of constraints
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 3, 2011 at 4:29 | comment | added | fedja | @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 2:18 | comment | added | Igor Rivin | @fedia: no, he said "hundreds", and "hundreds", and he did not say whether the problems had special structure. As for the objectives, he said they were "different", but not how different. Maybe his problem was really: find all the vertices of the polytope defined by these hyperplanes. And maybe it was not, in which case it would be nice to get some more background. I have done enough work with scientists and engineers to know that people almost always ask the wrong question. | |
| Jun 2, 2011 at 21:10 | answer | added | Brian Borchers | timeline score: 4 | |
| Jun 2, 2011 at 20:46 | comment | added | fedja | It seems to me that the OP told that quite explicitly: 100, 100, No. | |
| Jun 2, 2011 at 19:53 | comment | added | Igor Rivin | 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:37 | comment | added | fedja | 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 18:16 | comment | added | David Harris | 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:11 | history | asked | Or Zuk | CC BY-SA 3.0 |