In the most general form, the problem we analyze in the sequel can be stated as follows: Given is a number of rectangles by their respective area sizes. The goal is to find an arrangement of these areas, such that they are nonoverlapping and, by sharing common borders of adjacent rectangles, the total length of all inner and outer border lines is minimum. Without loss of generality we can assume that all rectangles are arranged in an axis-aligned way. We additionally demand that the outer border line, which is a polygon in general, must be a rectangle with given width and height, or a square.

Our interest in this problem was also application-driven, namely by the problem of designing a multi-channel conduit. Here cross-section areas of several channels are given, and the design goal is to find an arrangement and widths and heights for the channels using as little material as possible.

Partners

Herbert Birkhofer, TU Darmstadt,

Marzena Fügenschuh, TU Darmstadt,

Ute Günther, TU Darmstadt,

Wolfgang Hess, TU Darmstadt,

Daniel Junglas, TU Darmstadt,

Konstanty Junosza-Szaniawski, Politechnika Warszawska, Poland,

Zbigniew Lonc, Politechnika Warszawska, Poland,

Alexander Martin, TU Darmstadt,

Thorsten Sauer, TU Darmstadt,

Lars Schewe, TU Darmstadt,

Stefan Ulbrich, TU Darmstadt,

Martin Wäldele, TU Darmstadt,

Stephan Walter, TU Darmstadt.

Funding

Deutsche Forschungsgemeinschaft DFG, Collaborative Research Center SFB-666.

Deutscher Akademische Auslandsdienst DAAD, travel grant for German-Polish academic exchange.

Related Talks

1. 1.Mixed-Integer Nonlinear Programming - Linear Approximations & Applications, DMV-SIGOPT International Conference on Optimization, Lambrecht, Germany, 16.6.2011.
   

2. 2.Nonlinear Mixed-Integer Programming – The MILP Perspective, Combinatorial Optimization at Work, Berlin, Germany, 8.10.2009.
   

3. 3.Mixed Integer Programming for Topology Optimization in Sheet-Metal Design, SIOPT 2008, SIAM Conference on Optimization, Boston (MA), USA, 10.5.2008.
   

4. 4.Solving Discrete-Nonlinear Problems with Linear Mixed-Integer Programming Techniques, Seminar on Algebra and Graph Theory, Warsaw, Poland, 26.9.2007.
   

5. 5.Solving Discrete-Nonlinear Problems with Linear Mixed-Integer Programming Techniques, 13th Czech-French-German Conference 2007, Heidelberg, Germany, 21.9.2007.
   

6. 6.Mixed Integer Programming for Topology Optimization in Sheet-Metal Design, 13th Czech-French-German Conference 2007, Heidelberg, Germany, 18.9.2007.
   

7. 7.Mixed Integer Programming for Topology Optimization in Sheet-Metal Design, 6th International Congress on Industrial and Applied Mathematics ICIAM07, Zürich, Switzerland, 19.7.2007.
   

8. 8.Solving Discrete-Nonlinear Problems with Linear Mixed-Integer Programming Techniques, Sino-German Matheon-Workshop „Nonlinear Integer Programming and Structural Optimization“, Berlin, Germany, 10.7.2007.
   

9. 9.Branched Sheet Metal Products: Topology Optimization with Mixed-Integer Programming, EUROPT-OMS Conference, Prague, Czech Republic, 5.7.2007.
   

10. 10.Recent Progress in Topology Optimization for Sheet Metal Products, Seminar on Algebra and Graph Theory, Warsaw, Poland, 23.10.2006.
    

11. 11.Mixed-Integer Programming for Topology Optimization in Sheet Metal Design, ESI European Summer School, Wittenberg, Germany, 24.8.2006.
    

12. 12.Mixed-Integer Programming for Topology Optimization in Sheet Metal Design, 19th International Symposium on Mathematical Programming ISMP 2006, Rio de Janeiro, Brazil, 2.8.2006.
    

13. 13.Optimization of Sheet Metal Products with Branches of a Higher Order, Annual meeting of the GAMM, Berlin, Germany, 30.3.2006.
    

14. 14.Optimization of Sheet Metal Products with Branches of a Higher Order, Seminar on Numerics and Scientific Computing, Kaiserslautern, Germany, 14.2.2006.
    

15. 15.Optimization of Sheet Metal Products with Branches of a Higher Order, Seminar on Algebra and Graph Theory, Warsaw, Poland, 14.12.2005.
    

16. 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, Germany, 8.9.2005.
    

Related Publications

1. 1.Armin Fügenschuh, Konstanty Junosza-Szaniawski, Zbigniew Lonc, Exact and Approximation Algorithms for a Soft Rectangle Packing Problem, Optimization, in print.
   

2. 2.Armin Fügenschuh, Matheon Adventskalender 17. Dezember, Lösungsheft, pp. 109 – 115, 2009.
   

3. 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. 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. 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. 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. 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. 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.