Timeline for Model for shipping widgets in an optimal way
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 11, 2011 at 4:03 | comment | added | TerryB | Thanks for the comments so far and the answer below. The locations for each distributor is fixed. I am ultimately trying to figure out the best way to pack the boxes that go to the distributors. I will look into the "bin packing problem" mentioned by Brian Borchers. | |
| May 11, 2011 at 3:53 | vote | accept | TerryB | ||
| May 11, 2011 at 0:28 | answer | added | Brian Borchers | timeline score: 2 | |
| May 11, 2011 at 0:25 | comment | added | Robert Israel | It's not clear to me what the variables and constraints are. Is the map from locations to distributors fixed, or is it variable? If it's fixed, you have separate (and fairly small) problems for each distributor. If it's variable, what are the constraints? You say "Each of those 2000 distributors service on average 10 locations", but that could mean one distributor services all 20000 locations and the others service 0. | |
| May 11, 2011 at 0:06 | comment | added | David E Speyer | As I said, I don't understand this question, but I'd like to leave it open until users like David Eppstein take a look at it. | |
| May 11, 2011 at 0:04 | comment | added | David E Speyer | NP-complete isn't the end of the story. I don't understand the set up well enough to think about it, but this sounds similar to the sort of questions that people who think about transportation polytopes study. win.tue.nl/diamant/symposium0705/slides/loera.pdf In that field, when the things you are shipping are infinitely divisible (like oil), there are usually good theoretical results. When your shipping input is discrete (widgets) then the problem is often NP-complete in theory, but you can get good approximations in practice by solving the continuous problem and rounding. | |
| May 10, 2011 at 23:09 | comment | added | user5810 | I'm going to go ahead and say there's no way in ... this problem isn't NP-complete. | |
| May 10, 2011 at 22:54 | history | asked | TerryB | CC BY-SA 3.0 |