Design of planar articulated mechanisms using branch and bound. (English) Zbl 1066.70006
Summary: This paper considers an optimization model and a solution method for the design of two-dimensional mechanical mechanisms. The mechanism design problem is modeled as a nonconvex mixed integer program which allows the optimal topology and geometry of the mechanism to be determined simultaneously. The underlying mechanical analysis model is based on a truss representation allowing for large displacements. For mechanisms undergoing large displacements, elastic stability is of major concern. We derive conditions, modeled by nonlinear matrix inequalities, which guarantee that a stable equilibrium is found and that buckling is prevented. The feasible set of the design problem is described by nonlinear differentiable and non-differentiable constraints as well as by nonlinear matrix inequalities.
To solve the mechanism design problem, a branch and bound method based on convex relaxations is developed. To guarantee convergence of the method, two different types of convex relaxations are derived. The relaxations are strengthened by adding valid inequalities to the feasible set and by solving bound contraction sub-problems. Encouraging computational results indicate that the branch and bound method can reliably solve mechanism design problems of realistic size to global optimality.
To solve the mechanism design problem, a branch and bound method based on convex relaxations is developed. To guarantee convergence of the method, two different types of convex relaxations are derived. The relaxations are strengthened by adding valid inequalities to the feasible set and by solving bound contraction sub-problems. Encouraging computational results indicate that the branch and bound method can reliably solve mechanism design problems of realistic size to global optimality.
MSC:
| 70E60 | Robot dynamics and control of rigid bodies |
| 70B15 | Kinematics of mechanisms and robots |
| 74P10 | Optimization of other properties in solid mechanics |
| 74K10 | Rods (beams, columns, shafts, arches, rings, etc.) |
| 90C90 | Applications of mathematical programming |
References:
| [1] | Achtziger, W., Bendsøe, M.P., Ben-Tal, A., Zowe, J.: Equivalent displacement based formulations for maximum strength truss topology design. Impact Comput. Sci. Eng. 4 (4), 315–345 (1992) · Zbl 0769.73054 · doi:10.1016/0899-8248(92)90005-S |
| [2] | Al-Khayyal, F.A.: Jointly constrained bilinear programs and related problems: An overview. Comput. Math. Appl. 19 (11), 53–62 (1990) · Zbl 0706.90074 · doi:10.1016/0898-1221(90)90148-D |
| [3] | Al-Khayyal, F.A.: Generalized bilinear programming: Part I. Models, applications and linear programming relaxation. European J. Oper. Res. 60, 306–314 (1992) · Zbl 0784.90051 |
| [4] | Al-Khayyal, F.A., Falk, J.E.: Jointly constrained biconvex programming. Math. Oper. Res. 8 (2), 273–286 (1983) · Zbl 0521.90087 · doi:10.1287/moor.8.2.273 |
| [5] | Andersen, E.D., Andersen, K.D.: Presolving in linear programming. Math. Program. 71, 221–245 (1995) · Zbl 0846.90068 |
| [6] | Bathe, K.-J.: Finite Element Procedures in Engineering Analysis. Prentice-Hall: Englewood Cliffs, NJ, 1982 |
| [7] | Ben-Tal, A., Bendsøe, M.P.: A new method for optimal truss topology design. SIAM J. Optim. 3 (2), 322–358 (1993) · Zbl 0780.90076 · doi:10.1137/0803015 |
| [8] | Ben-Tal, A., Jarre, F., Kočvara, M., Nemirovski, A., Zowe, J.: Optimal design of trusses under a nonconvex global buckling constraint. Optim. Eng. 1, 189–213 (2000) · Zbl 1106.74388 · doi:10.1023/A:1010091831812 |
| [9] | Ben-Tal, A., Kočvara, M., Zowe, J.: Two non-smooth methods for simultaneous geometry and topology design of trusses. In: M.P. Bendsøe, C.A. Mota Soares (eds.), Topology Design of Structures, Kluwer Academic Publishers, 1993, pp. 31–42 |
| [10] | Ben-Tal, A., Nemirovski, A.: Potential reduction polynomial time method for truss topology design. SIAM J. Optim. 4 (3), 596–612 (1994) · Zbl 0821.90137 · doi:10.1137/0804033 |
| [11] | Ben-Tal, A., Nemirovski, A.: Optimal design of engineering structures. OPTIMA Mathematical Programming Society Newsletter, 1995, No. 47 |
| [12] | Ben-Tal, A., Nemirovski., A.: Robust truss topology design via semidefinite programming. SIAM J. Optim. 7 (4), 991–1016 (1997) · Zbl 0899.90133 · doi:10.1137/S1052623495291951 |
| [13] | Ben-Tal, A., Nemirovski, A..: Handbook of semidefinite programming. Chapter Structural Design, Kluwer Academic Publishers, 2000, pp. 443–467 · Zbl 0957.90529 |
| [14] | Bendsøe, M.P..: Optimization of structural topology, shape, and material. Springer-Verlag, 1995 · Zbl 0822.73001 |
| [15] | Bendsøe, M.P., Ben-Tal, A., Zowe., J.: Optimization methods for truss geometry and topology design. Struct. Optim. 7 (3), 141–158 (1994) · doi:10.1007/BF01742459 |
| [16] | Bendsøe, M.P., Sigmund, O.: Topology Optimization: Theory, Methods and Applications. Springer, 2003 · Zbl 1059.74001 |
| [17] | Bollapragada, S., Ghattas, O., Hooker., J.N.: Optimal design of truss structures by logical-based branch and cut. Oper. Res. 49 (1), 42–51 (2001) · Zbl 1163.90827 · doi:10.1287/opre.49.1.42.11196 |
| [18] | Calladine., C.R.: Buckminster Fuller’s tensegrity structures and Clerk Maxwell’s rules for the construction of stiff frame. Int. J. Solids Struct. 14, 161–172 (1978) · Zbl 0377.73076 · doi:10.1016/0020-7683(78)90052-5 |
| [19] | Crisfield, M.A.: Non-linear Finite Element Analysis of Solids and Structures. Vol. 1: Essentials. John Wiley & Sons, New York, 1997 · Zbl 0855.73001 |
| [20] | Dorn, W.S., Gomory, R.E., Greenberg, H.J..: Automatic design of optimal structures. Journal de Mécanique 3 25–52, 1964. |
| [21] | Erdman., A.G.: Computer-aided mechanism design - now and the future. J. Mech. Design 117, 93–100 (1995) · doi:10.1115/1.2836476 |
| [22] | Erdman, A.G., Sandor, G.N.: Mechanism Design: Analysis and Synthesis. Volume I. Prentice Hall, 2nd edition, 1990 |
| [23] | Eschenauer, H.A., Olhoff, N.: Topology optimization of continuum structures: A review. Applied Mechanics Reviews 54 (4), 331–390 (2001) · doi:10.1115/1.1388075 |
| [24] | Foulds, L.R., Haugland, D., Jörnsten., K.: A bilinear approach to the pooling problem. Optimization 24, 165–180 (1992) · Zbl 0817.90073 · doi:10.1080/02331939208843786 |
| [25] | Fowler, P.W., Guest., S.D.: A symmetry extension of Maxwell’s rule for rigidity of frames. Int. J. Solids Struct. 37, 1793–1804 (2000) · Zbl 0973.74050 · doi:10.1016/S0020-7683(98)00326-6 |
| [26] | Gill, P.E., Murray, W., Saunders, M.A.: User’s guide for SNOPT 5.3: a Fortran package for large-scale nonlinear programming. Technical report, NA 97-5 , Department of Mathematics, University of California, 1997 |
| [27] | Gill, P.E., Murray, W., Saunders., M.A.: SNOPT: An SQP algorithm for large-scale constrained optimization. SIAM J. Optim. 12 (4), 979–1006 (2002) · Zbl 1027.90111 · doi:10.1137/S1052623499350013 |
| [28] | Gill, P.E., Murray, W., Wright, M.: Practical Optimization. Academic Press, 1981 |
| [29] | Hansen., J.M.: Synthesis of mechanisms using time-varying dimensions. Struct. Multidisc. Optim. 7 (1), 127–144 (2002) · Zbl 1012.70003 |
| [30] | Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches. Springer-Verlag, 1993 · Zbl 0704.90057 |
| [31] | Jarre, F., Kočvara, M., Zowe., J.: Optimal truss design by interior point methods. SIAM J. Optim. 8 (4), 1084–1107 (1998) · Zbl 0912.90231 · doi:10.1137/S1052623496297097 |
| [32] | Kawamoto, A., Bendsøe, M.P., Sigmund., O.: Articulated mechanism design with a degree of freedom constraint. Int. J. Numer. Meth. Eng. 61 (9), 1520–1545 (2004) · Zbl 1075.74611 · doi:10.1002/nme.1119 |
| [33] | Kawamoto, A., Bendsøe, M.P., Sigmund., O.: Planar articulated mechanism design by graph theoretical enumeration. Struct. Multidisc. Optim. 27 (4), 295–299 (2004) · doi:10.1007/s00158-004-0409-9 |
| [34] | Kočvara., M.: On the modelling and solving of the truss design problem with global stability constraints. Struct. Multidisc. Optim. 23, 189–203 (2002) · doi:10.1007/s00158-002-0177-3 |
| [35] | McCormick., G.P.: Computability of global solutions to factorable nonconvex programs: part I - convex underestimating problems. Math. Program. 10, 147–175 (1976) · Zbl 0349.90100 · doi:10.1007/BF01580665 |
| [36] | Mészáros, Cs., Suhl., U.H.: Advanced preprocessing techniques for linear and quadratic programming. OR Spectrum 25, 575–595 (2003) · Zbl 1042.90031 · doi:10.1007/s00291-003-0130-x |
| [37] | Minnaar, R.J., Tortorelli, D.A., Snyman, J.A.: On nonassembly in the optimal dimensional synthesis of planar mechanisms. Struct. Multidisc. Optim. 21 (5), 345–354 (2001) · doi:10.1007/s001580100113 |
| [38] | Nishino, F., Duggal., R.: Shape optimum design of trusses under multiple loading. Int. J. Solids Struct. 26, 17–27 (1990) · doi:10.1016/0020-7683(90)90091-9 |
| [39] | Padberg, M., Rinaldi, G..: A branch-and-cut algorithm for the resolution of large-scale traveling salesman problems. SIAM Review 33, 1991 · Zbl 0734.90060 |
| [40] | Pellegrino, S., Calladine., C.R.: Matrix analysis of statically and kinematically indeterminate frameworks. International J. Solids Struct. 22, 409–428 (1986) · doi:10.1016/0020-7683(86)90014-4 |
| [41] | Rozvany, G.I.N., Bendsøe, M.P., Kirsch., U.: Layout optimization of structures. Applied Mechanics Reviews 48, 41–119 (1995) · doi:10.1115/1.3005097 |
| [42] | Ryoo, H.S., Sahinidis., N.V.: A branch-and-reduce approach to global optimization. J. Global Optim. 8, 107–138 (1996) · Zbl 0856.90103 · doi:10.1007/BF00138689 |
| [43] | Savelsbergh., M.W.P.: Preprocessing and probing for mixed integer programming problems. ORSA J. Comput. 6, 445–454 (1994) · Zbl 0814.90093 |
| [44] | Stolpe., M.: Global optimization of minimum weight truss topology problems with stress, displacement, and local buckling constraints using branch-and-bound. Int. J. Numer. Meth. Eng. 61 (8), 1270–1309 (2004) · Zbl 1075.74603 |
| [45] | Stolpe, M., Svanberg., K.: Modeling topology optimization problems as linear mixed 0-1 programs. International J. Numer. Meth. Eng. 57 (5), 723–739 (2003) · Zbl 1062.74593 · doi:10.1002/nme.700 |
| [46] | Sturm, J.F..: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optimization Methods and Software 11–12, 625–653 (1999), Version 1.05 available from, http://fewcal.kub.nl/sturm · Zbl 0973.90526 |
| [47] | Tischler, C.R., Samuel, A.E., Hunt., K.H.: Kinematic chains for robot hands–I. Orderly number-synthesis. Mechanism and Machine Theory 30, 1193–1215 (1995) · doi:10.1016/0094-114X(95)00043-X |
| [48] | Tischler, C.R., Samuel, A.E., Hunt., K.H.: Kinematic chains for robot hands–II. Kinematic constraints, classification, connectivity, and actuation. Mechanism and Machine Theory 30, 1217–1239 (1995) |
| [49] | Vandenberghe, L., Boyd., S.: Semidefinite programming. SIAM Review 38, 45–95 (1996) · Zbl 0845.65023 · doi:10.1137/1038003 |
| [50] | Zamora, J.M., Grossmann., I.E.: A branch and contract algorithm for problems with concave univariate, bilinear and linear fractional terms. J. Global Optim. 14, 217–249 (1999) · Zbl 0949.90097 · doi:10.1023/A:1008312714792 |
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.
