A new branch and bound method for a discrete truss topology design problem. (English) Zbl 1267.90175
Summary: Our paper considers a classic problem in the field of truss topology design, the goal of which is to determine the stiffest truss, under a given load, with a bound on the total volume and discrete requirements in the cross-sectional areas of the bars. To solve this problem, we propose a new two-stage branch and bound algorithm.
In the first stage, we perform a branch and bound algorithm on the nodes of the structure. This is based on the following dichotomy study: either a node is in the final structure or not. In the second stage, a branch and bound on the bar areas is conducted. The existence or otherwise of a node in this structure is ensured by adding constraints on the cross-sectional areas of its incident bars. In practice, for reasons of stability, free bars linked at free nodes should be avoided. Therefore, if a node exists in the structure, then there must be at least two incident bars on it, unless it is a supported node. Thus, a new constraint is added, which lower bounds the sum of the cross-sectional areas of bars incident to the node. Otherwise, if a free node does not belong to the final structure, then all the bar area variables corresponding to bars incident to this node may be set to zero. These constraints are added during the first stage and lead to a tight model. We report the computational experiments conducted to test the effectiveness of this two-stage approach, enhanced by the rule to prevent free bars, as compared to a classical branch and bound algorithm, where branching is only performed on the bar areas.
In the first stage, we perform a branch and bound algorithm on the nodes of the structure. This is based on the following dichotomy study: either a node is in the final structure or not. In the second stage, a branch and bound on the bar areas is conducted. The existence or otherwise of a node in this structure is ensured by adding constraints on the cross-sectional areas of its incident bars. In practice, for reasons of stability, free bars linked at free nodes should be avoided. Therefore, if a node exists in the structure, then there must be at least two incident bars on it, unless it is a supported node. Thus, a new constraint is added, which lower bounds the sum of the cross-sectional areas of bars incident to the node. Otherwise, if a free node does not belong to the final structure, then all the bar area variables corresponding to bars incident to this node may be set to zero. These constraints are added during the first stage and lead to a tight model. We report the computational experiments conducted to test the effectiveness of this two-stage approach, enhanced by the rule to prevent free bars, as compared to a classical branch and bound algorithm, where branching is only performed on the bar areas.
MSC:
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 90C22 | Semidefinite programming |
| 90C10 | Integer programming |
Keywords:
truss topology design; stiffness; semi-definite programming; quadratic programming; global optimization; branch and boundReferences:
| [1] | Achterberg, T., Koch, T., Martin, A.: Branching rules revisited. Oper. Res. Lett. 33, 42–54 (2005) · Zbl 1076.90037 · doi:10.1016/j.orl.2004.04.002 |
| [2] | Achtziger, W.: Optimization with variable sets of constraints and an application to truss design. Comput. Optim. Appl. 15(1), 69–96 (2000) · Zbl 0942.90036 · doi:10.1023/A:1008775015126 |
| [3] | Achtziger, W., Stolpe, M.: Truss topology optimization with discrete design variables–guaranteed global optimality and benchmark examples. Struct. Multidiscip. Optim. 34, 1–20 (2007) · Zbl 1273.74396 · doi:10.1007/s00158-006-0074-2 |
| [4] | Achtziger, W., Stolpe, M.: Global optimization of truss topology with discrete bar areas. Part I. Theory of relaxed problems. Comput. Optim. Appl. 40(2), 247–280 (2008) · Zbl 1181.90202 · doi:10.1007/s10589-007-9138-5 |
| [5] | Achtziger, W., Stolpe, M.: Global optimization of truss topology with discrete bar areas. Part II. Implementation and numerical results. Comput. Optim. Appl. 44(2), 315–341 (2009) · Zbl 1184.90110 · doi:10.1007/s10589-007-9152-7 |
| [6] | Alvarez, F., López, J., Ramírez, H.: Interior proximal algorithm with variable metric for second-order cone programming: applications to structural optimization and support vector machines, Optimization Online, June (2009) · Zbl 1226.90041 |
| [7] | Bastos, F., Cerveira, A., Gromicho, J.: Using optimization to solve truss topology design problems. Investig. Oper. 22, 123–156 (2005) |
| [8] | Ben-Tal, A., Bendsøe, M.: A new method for optimal truss topology design. SIAM J. Optim. 3, 322–358 (1993) · Zbl 0780.90076 · doi:10.1137/0803015 |
| [9] | Ben-Tal, A., Nemirovski, A.: Robust truss topology design via semidefinite programming. SIAM J. Optim. 7, 991–1016 (1997) · Zbl 0899.90133 · doi:10.1137/S1052623495291951 |
| [10] | Ben-Tal, A., Nemirovski, A.: Potential reduction polynomial time method for truss topology design. SIAM J. Optim. 3, 596–612 (1994) · Zbl 0821.90137 · doi:10.1137/0804033 |
| [11] | Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. Society for Industrial and Applied Mathematics, Philadelphia (2001) · Zbl 0986.90032 |
| [12] | Bollapragada, S., Ghattas, O., Hoocker, J.: Optimal design of truss structures by logic-based branch and cut. Oper. Res. 49, 42–51 (2001) · Zbl 1163.90827 · doi:10.1287/opre.49.1.42.11196 |
| [13] | Borchers, B.: CSDP 3.2 User’s Guide. Optim. Methods Softw. 11, 597–611 (1999) · Zbl 0973.90523 · doi:10.1080/10556789908805764 |
| [14] | Calvel, S., Mongeau, M.: Topology optimization of a mechanical component subject to dynamical constraints. Optimization Online, August (2005) |
| [15] | Cerveira, A., Bastos, F.: Semidefinite relaxations and Lagrangian duality in truss topology design problem. Int. J. Math. Stat. 9, 12–25 (2011) |
| [16] | de Klerk, E., Roos, C., Terlaky, T.: Semi-definite problems in truss topology optimization. Tech. report Nr. 95–128, Faculty of Technical Mathematics and Informatics, Delft University of Technology, (1995) |
| [17] | Faustino, A., Júdice, J., Ribeiro, I., Neves, A.: An integer programming model for truss topology optimization. Investig. Oper. 26, 111–127 (2006) |
| [18] | Haslinger, J., Kočvara, M., Leugering, G., Stingl, M.: Multidisciplinary free material optimization. SIAM J. Appl. Math. 70, 2709–2728 (2010) · Zbl 1429.74079 · doi:10.1137/090774446 |
| [19] | Kočara, M.: Truss topology design with integer variables made easy? Optimization Online (2010) |
| [20] | Rasmussen, M., Stolpe, M.: A note on stress-constrained truss topology optimization. J. Struct. Multidisciplin. Optim. 27(1–2), 136–137 (2004) · doi:10.1007/s00158-003-0370-z |
| [21] | Rasmussen, M., Stolpe, M.: Global optimization of discrete truss topology design problems using a parallel cut-and-branch method. Comput. Struct. 86, 13–14 (2008). 1527–1538 |
| [22] | Rozvany, G.: Difficulties in truss topology optimization with stress, local buckling and system stability constraints. Struct. Multidiscip. Optim. 11(3), 213–217 (1996) · doi:10.1007/BF01197036 |
| [23] | Stingl, M., Kočvara, M., Leugering, G.: Free material optimization with fundamental eigenfrequency constraints. SIAM J. Optim. 20, 524–547 (2009) · Zbl 1239.74011 · doi:10.1137/080717122 |
| [24] | Stolpe, M.: Global optimization of minimum weight truss topology problems with stress, displacement, and local buckling constraints using branch-and-bound. Int. J. Numer. Methods Biomed. Eng. 61(8), 1270–1309 (2004) · Zbl 1075.74603 · doi:10.1002/nme.1112 |
| [25] | Zhou, M.: Difficulties in truss topology optimization with stress and local buckling constraints. Struct. Multidiscip. Optim. 11(1), 134–136 (1996) · doi:10.1007/BF01376857 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
