Name
Abstract | ||
|---|---|---|
We report on a project with a German car manufacturer. The task is to compute (approximate) solutions to a specific large-scale packing problem. Given a polyhedral model of a car trunk, the aim is to pack as many identical boxes of size 4 x 2 x 1 units as possible into the interior of the trunk. This measure is important for car manufacturers, because it is a standard in the European Union. First, we prove that a natural formal variant of this problem is NP-complete. Further, we use a combination of integer linear programming techniques and heuristics that exploit the geometric structure to attack this problem. Our experiments show that for all considered instances, we can get very close to the optimal solution in reasonable time. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1007/978-3-540-39658-1_56 | ALGORITHMS - ESA 2003, PROCEEDINGS |
Keywords | Field | DocType |
polyhedral model | Combinatorics,Packing problems,Polyhedron,Greedy algorithm,Integer programming,Linear programming,Polytope model,Mathematics,Trunk,European union | Conference |
Volume | ISSN | Citations |
2832 | 0302-9743 | 6 |
PageRank | References | Authors |
0.75 | 9 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Friedrich Eisenbrand | 1 | 726 | 53.74 |
| stefan funke | 2 | 706 | 57.45 |
| joachim reichel | 3 | 120 | 6.22 |
| Elmar Schömer | 4 | 379 | 37.50 |
| Giuseppe Di Battista | 5 | 2298 | 361.48 |
| Uri Zwick | 6 | 3586 | 257.02 |