Rechteckpackungen mit weichen Rändern

In der allgemeinsten Form kann das Problem wie folgt beschrieben werden: Gegeben ist eine Anzahl von Rechtecken, die durch ihre jeweiligen Flächeninhalte gekennzeichnet sind, aber nicht ihre Breiten oder Höhen. Das Ziel ist es, eine Anordnung von diesen Bereichen zu finden, so dass sie sich gegenseitig nicht überlappen und deren Begrenzung minimale Gesamtlänge aufweist. Wenn zwei Rechtecke aneinander grenzen, so wird die gemeinsame Grenze nur einmal zur Gesamtlänge gezählt. Ohne Beschränkung der Allgemeinheit können wir annehmen, dass alle Rechtecke an den Koordinatenachsen ausgerichtet sind. Wir verlangen zudem, dass die äußere Grenze, welche im Allgemeinen ein Polygon ist, entweder ein Rechteck mit gegebener Breite und Höhe oder ein Quadrat sein soll.

Unser Interesse an diesem Problem war anfänglich anwendungsorientiert: Das Problem der topologischen und geometrischen Gestaltung eines Mehr-Kanal-Kabelträgers. Hier ist die Querschnittsflächen von mehreren Kanälen gegeben, und das Designziel ist es, eine Anordnung und die Breiten und Höhen der Kanäle zu finden, die möglichst wenig Material verbraucht (Leichtbau).

Partner

  • Technische Universität Darmstadt
  • Politechnika Warszawska, Poland

Finanzierung

  • Deutsche Forschungsgemeinschaft DFG, Sonderforschungsbereich SFB-666.
  • Deutscher Akademische Auslandsdienst DAAD, Reisemittel für den deutsch-polnischen akademischen Austausch.

Vorträge

  1. Mixed-Integer Nonlinear Programming - Linear Approximations & Applications, DMV-SIGOPT International Conference on Optimization, Lambrecht, 16.6.2011.
  2. Nonlinear Mixed-Integer Programming – The MILP Perspective, Combinatorial Optimization at Work, Berlin, 8.10.2009.
  3. Mixed Integer Programming for Topology Optimization in Sheet-Metal Design, SIOPT 2008, SIAM Conference on Optimization, Boston (MA), USA, 10.5.2008.
  4. Solving Discrete-Nonlinear Problems with Linear Mixed-Integer Programming Techniques, Seminar on Algebra and Graph Theory, Warschau, Polen, 26.9.2007.
  5. Solving Discrete-Nonlinear Problems with Linear Mixed-Integer Programming Techniques, 13th Czech-French-German Conference 2007, Heidelberg, 21.9.2007.
  6. Mixed Integer Programming for Topology Optimization in Sheet-Metal Design, 13th Czech-French-German Conference 2007, Heidelberg, 18.9.2007.
  7. Mixed Integer Programming for Topology Optimization in Sheet-Metal Design, 6th International Congress on Industrial and Applied Mathematics ICIAM07, Zürich, Schweiz 19.7.2007.
  8. Solving Discrete-Nonlinear Problems with Linear Mixed-Integer Programming Techniques, Sino-German Matheon-Workshop „Nonlinear Integer Programming and Structural Optimization“, Berlin, 10.7.2007.
  9. Branched Sheet Metal Products: Topology Optimization with Mixed-Integer Programming, EUROPT-OMS Conference, Prag, Tschechische Republik, 5.7.2007.
  10. Recent Progress in Topology Optimization for Sheet Metal Products, Seminar on Algebra and Graph Theory, Warschau, Polen, 23.10.2006.
  11. Mixed-Integer Programming for Topology Optimization in Sheet Metal Design, ESI European Summer School, Wittenberg, 24.8.2006.
  12. Mixed-Integer Programming for Topology Optimization in Sheet Metal Design, 19th International Symposium on Mathematical Programming ISMP 2006, Rio de Janeiro, Brasilien, 2.8.2006.
  13. Optimization of Sheet Metal Products with Branches of a Higher Order, Annual meeting of the GAMM, Berlin, 30.3.2006.
  14. Optimization of Sheet Metal Products with Branches of a Higher Order, Seminar on Numerics and Scientific Computing, Kaiserslautern, 14.2.2006.
  15. Optimization of Sheet Metal Products with Branches of a Higher Order, Seminar on Algebra and Graph Theory, Warschau, Polen, 14.12.2005.
  16. Topology- and shape-optimization of branched sheet metal products, Conf. on Oper. Res. OR, Bremen. Integrated Optimization in Public Transport, International Conference on Operations Research OR 2005, Bremen, 8.9.2005.

Veröffentlichungen

  1. Armin Fügenschuh, Konstanty Junosza-Szaniawski, Zbigniew Lonc, Exact and Approximation Algorithms for a Soft Rectangle Packing Problem , Optimization, Vol. 63, No. 11, pp. 1637 – 1663, 2014.
  2. Armin Fügenschuh, Matheon Adventskalender 17. Dezember , Lösungsheft, pp. 109 – 115, 2009.
  3. Armin Fügenschuh, Marzena Fügenschuh, Integer Linear Programming Models for Topology Optimization in Sheet Metal Design , Mathematical Methods of Operations Research, Vol. 68, No. 2, pp. 313 – 331, 2008.
  4. Martin Wäldele, Herbert Birkhofer, Armin Fügenschuh, Alexander Martin, Modeling Properties for the Design of Branched Sheet Metal Products, Amaresh Chakrabarti (Ed.), Research into Design: Supporting Multiple Facets of Product Development, Research Publishing Services, pp. 287 – 294, 2009.
  5. Armin Fügenschuh, Wolfgang Hess, Lars Schewe, Alexander Martin, Stefan Ulbrich, Verfeinerte Modelle zur Topologie- und Geometrie-Optimierung von Blechprofilen mit Kammern, Peter Groche (Ed.), Sonderforschungsbereich 666: Integrale Blechbauweisen höherer Verzweigungsordnung – Entwicklung, Fertigung, Bewertung, Meisenbach Verlag, Bamberg, pp. 17 – 28, 2008.
  6. Armin Fügenschuh, Alexander Martin, Mixed-Integer Models for Topology Optimization in Sheet Metal Design , 6th International Congress on Industrial Applied Mathematics (ICIAM07) and GAMM Annual Meeting, Zürich 2007, PAMM Proceedings in Applied Mathematics and Mechanics, Band 7, Nr. 1, pp. 2060049 – 2060050, 2007.
  7. Armin Fügenschuh, Wolfgang Hess, Alexander Martin, Stefan Ulbrich, Diskrete und kontinuierliche Modelle zur Topologie- und Geometrie-Optimierung von Blechprofilen, Peter Groche (Ed.), Sonderforschungsbereich 666: Integrale Blechbauweisen höherer Verzweigungsordnung – Entwicklung, Fertigung, Bewertung, Meisenbach Verlag, Bamberg, pp. 37 – 47, 2007.
  8. Herbert Birkhofer, Armin Fügenschuh, Ute Günther, Daniel Junglas, Alexander Martin, Thorsten Sauer, Stefan Ulbrich, Martin Wäldele, Stephan Walter, Topology- and shape-optimization of branched sheet metal products , Hans-D. Haasis, Herbert Kopfer, Jörn Schönberger (Eds.), Operations Research Proceedings 2005, Springer Verlag, Berlin, pp. 327 – 336, 2006.