[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Methods for optimization of nonlinear problems with discrete variables: A review

  • Review Papers
  • Published:
Structural optimization Aims and scope Submit manuscript

Abstract

The methods for discrete-integer-continuous variable nonlinear optimization are reviewed. They are classified into the following six categories: branch and bound, simulated annealing, sequential linearization, penalty functions, Lagrangian relaxation, and other methods. Basic ideas of each method are described and details of some of the algorithms are given. They are transcribed into a step-by-step format for easy implementation into a computer. Under “other methods”, rounding-off, heuristic, cutting-plane, pure discrete, and genetic algorithms are described. For nonlinear problems, none of the methods are guaranteed to produce the global minimizer; however, “good practical” solutions can be obtained.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Abbreviations

BBM:

branch and bound method

D:

set of discrete values for all the discrete variables

D i :

set of discrete values for thei-th variable

d ij :

j-th discrete value for thei-th variable

f :

cost function to be minimized

f * :

upper bound for the cost function

g i :

i-th constraint function

IP:

integer programming

ILP:

integer linear programming

L:

Lagrangian

LP:

linear programming

m :

total number of constraints

MDLP:

mixed-discrete linear programming

MDNLP:

mixed-discrete nonlinear programming

n d :

number of discrete variables

NLP:

nonlinear programming

p :

number of equality constraints; acceptance probability used in simulated annealing

q i :

number of discrete values for thei-th variable

SLP:

sequential linear programming

SQP:

sequential quadratic programming

x:

design variable vector of dimension n

x iL :

smallest allowed value for thei-th variable

x iU :

largest allowed value for thei-th variable

∇:

the gradient operator

References

  • Allufi-Pentini, F.; Parisi, V.; Zirilli, F. 1985: A global optimization and stochastic differential equations.J. Optim. Theory and Appl. 47, 1–16

    Google Scholar 

  • Amir, H.M.; Hesagawa, T. 1989: Nonlinear mixed-discrete structural optimization.J. Struct. Engng., ASCE 115, 626–646

    Google Scholar 

  • Arora, J.S. 1989:Introduction to optimal design. New York: McGraw-Hill

    Google Scholar 

  • Arora, J.S. 1990: Computational design optimization: a review and future directions.Struct. Safety 7, 131–148

    Google Scholar 

  • Balas, E. 1965: An additive algorithm for solving linear problems with zero–one variables.Operations Research 13, 1485–1525

    Google Scholar 

  • Balas, E. 1991: Discrete programming by the filter method.Operations Research 5, 915–958

    Google Scholar 

  • Balling, R.J. 1991: Optimal steel frame design by simulated annealing.J. Struct. Eng. 117, 1780–1795

    Google Scholar 

  • Bauer, J. 1992: Algorithms of nondifferentiable optimization in discrete optimum structural design.ZAMM 72, 563–566

    Google Scholar 

  • Bauer, J.; Gutkowski, W.; Iwanow, Z. 1981: A discrete method for lattice structures optimization.Eng. Opt. 5, 121–128

    Google Scholar 

  • Belegundu, A.D.; Arora, J.S. 1979: Discrete variable optimization in structural engineering: a survey.Technical Report No. 49, Materials Engineering, The University of Iowa

  • Beveridge, G.S.; Schechter, R.S. 1970:Optimization: theory and practice. New York: McGraw-Hill

    Google Scholar 

  • Bremicker, M.; Papalambros, P.Y.; Loh, H.T. 1990: Solution of mixed-discrete structural optimization problems with a new sequential linearization algorithm.Comp. & Struct. 37, 451–461

    Google Scholar 

  • Cameron, G.E.; Xu, L.; Grierson, D.E. 1991: Discrete optimal design of 3d frameworks. In: Ural, O.; Wang, T.-L. (eds.)Electronic computation, pp. 181–188. New York: ASCE

    Google Scholar 

  • Cella A.; Logcher, R. 1971: Automated optimum design from discrete components.J. Struct. Div., ASCE 97, 175–188

    Google Scholar 

  • Cerny, V. 1985: Thermodynamical approach to the travelling salesman problem: an efficient simulation algorithm.J. Optim. Theory Appl. 45, 41–51

    Google Scholar 

  • Cha, J.Z.; Mayne, R.W. 1989: Optimization with discrete variables via recursive quadratic programming.J. Mech. Des. ASME 111, 124–136

    Google Scholar 

  • Cha, J.Z.; Mayne, R.W. 1991: The symmetric rank one formula and its application in discrete nonlinear optimization.J. Mech. Des. ASME 113, 312–317

    Google Scholar 

  • Choi, C.K.; Kwak, H.G. 1990: Optimum RC member design with predetermined discrete sections.J. Struct. Engng. 116, 2634–2655

    Google Scholar 

  • Dakin, R.J. 1965: A tree-search algorithm for mixed integer programming problems.Comput. J. 8, 250–255

    Google Scholar 

  • Davydov, E.G.; Sigal, I. 1972: Application of penalty function method in integer programming problems.Engng. Cybernetics 10, 21–24

    Google Scholar 

  • Farkas, J.; Szabo, L. 1980: Optimum design of beams and frames of welded I-sections by means of backtrack programming.Acta Tech. Acad. Sci. Hung. 91, 121–135

    Google Scholar 

  • Fleury, C.; Braibant, V. 1986: Structural optimization — a new dual method using mixed variables.Int. J. Num. Meth. Engng. 23, 409–428

    Google Scholar 

  • Fox, D.B.; Liebmann, J.S. 1981: A discrete nonlinear simplex method for optimized engineering design.Engng. Optim. 5, 129–149

    Google Scholar 

  • Fu, J.-F.; Fenton, R.G.; Cleghorn, W.L. 1991: A mixed integer-discrete-continuous programming method and its application to engineering design optimization.Engng. Optim. 17, 263–280

    Google Scholar 

  • Garfinkel, R.; Nemhauser, G. 1972:Integer programming. New York: John Wiley & Sons

    Google Scholar 

  • Geoffrion, A.M. 1967: Integer programming by implicit enumeration approach for integer programming.Operations Research 9, 178–190

    Google Scholar 

  • Geoffrion, A.M. 1969: An improved implicit enumeration approach for integer programming.Operations Research 17, 437–454

    Google Scholar 

  • Geoffrion, A.M. 1972: Generalized Bender's decomposition.J. Optim. Theory Appl. 2, 82–114

    Google Scholar 

  • Geoffrion, A.M. 1974: Lagrangian relaxation for integer programming.Mathematical Programming Study 10, 237–260

    Google Scholar 

  • Geoffrion, A.M.; Marsten, R.E. 1972: Integer programming algorithms: a framework and state-of-the-art survey.Management Science 18, 465–491

    Google Scholar 

  • Ghattas, O.N.; Grossman, I.E. 1991: MINLP and MILP strategies for discrete sizing structural optimization problems. In: Ural, O.; Wang, T.-L. (eds.)Electronic computation, pp. 181–188. New York: ASCE

    Google Scholar 

  • Gisvold, K.M.; Moe, J. 1972: A method for nonlinear mixed integer programming and its application to design problems.J. Engng. Ind. ASME 94, 353–364

    Google Scholar 

  • Glankwahmdee, A.; Liebmann, J.S.; Hogg, G.L. 1979: Unconstrained discrete nonlinear programming.Eng. Opt. 4, 95–107

    Google Scholar 

  • Glover, F. 1965: A multiphase-dual algorithm for the zero–one integer programming problem.Operations Research 13, 879–919

    Google Scholar 

  • Glover, F. 1968: Surrogate constraints.Operations Research 16, 741–749

    Google Scholar 

  • Glover, F.; Sommer, D. 1975: Pitfalls of rounding in discrete management decision problems.Decision Science 22, 43–50

    Google Scholar 

  • Goldberg, D.E.; Kuo, C.H. 1987: Genetic algorithms in pipeline optimization.J. Computing in Civil Engng. 1, 128–141

    Google Scholar 

  • Gomory, R.E. 1958: An algorithm for integer solutions to linear programs.Technical Report 1, Princeton-IB; Mathematical Research Project

  • Gomory, R.E. 1963: An algorithm for integer solutions to linear programs. In: Graves, G.W.; Wolfe, P. (eds.)Recent advances in mathematical programming. New York: McGraw-Hill

    Google Scholar 

  • Grierson, D.E.; Cameron, G.E. 1989: Microcomputer-based optimization of steel structures in professional practice.Microcomputers in Civil Engineering 4

  • Grierson, D.E.; Lee, W.H. 1984: Optimal synthesis of steel frameworks using standard sections.J. Struct. Mech. 12, 335–370

    Google Scholar 

  • Gue, R.L.; Liggett, J.C.; Cain, K.C. 1968: Analysis of algorithms for the zero–one programming problem.Comm. Assoc. Computing Machinery 11, 837–844

    Google Scholar 

  • Gupta, O.K.; Ravindran, A. 1983: Nonlinear integer programming and discrete optimization.J. Mech. Trans. Autom. Des. ASME 105, 160–164

    Google Scholar 

  • Hadley, G. 1962:Linear programming. Reading, MA: Addison-Wesley

    Google Scholar 

  • Hager, K.; Balling, R.J.1988: New approach for discrete structural optimization.J. Struct. Engng. ASCE 114, 1120–1134

    Google Scholar 

  • Hajela, P. 1989: Genetic search — an approach to the nonconvex optimization problem.Proc. 30th AIAA/ASME/ASCE/ASHS Structures, Structural Materials and Dynamics Conf. (held in Mobile, Alabama), pp. 165–175

  • Hajela, P.; Shih, C.-J. 1990: Multiobjective optimum design in mixed integer and discrete design variable problems.AIAA J. 28, 670–675

    Google Scholar 

  • Hua, H.M. 1983: Optimization of structures with discrete-size elements.Comp. & Struct. 17, 327–333

    Google Scholar 

  • John, K.V.; Ramakrishnan, C.V.; Sharma, K.G. 1988: Optimum design of trusses from available sections-use of sequential linear programming with branch and bound algorithm.Engng. Optim. 13, 119–145

    Google Scholar 

  • Jonsson, Ö.; Larsson, T. 1990: Lagrangean relaxation and subgradient optimization applied to optimal design with discrete sizing.Eng. Opt. 16, 221–233

    Google Scholar 

  • Kelahan, R.C.; Gaddy, J.L. 1978: Application of the adaptive random search to discrete and mixed integer optimization.Int. J. Num. Meth. Eng. 13, 119–145

    Google Scholar 

  • Kelly, J.E. 1969: The cutting plane method for solving convex programs.J. SIAM 8, 702–712

    Google Scholar 

  • Kincaid, R.K.; Padula, S.L. 1990: Minimizing distortion and internal forces in truss structures by simulated annealing.Proc. 31st AIAA/ASME/ASCE/AHS/ASC Structures, Structural Materials and Dynamics Conf. (held in Long Beach, California), Paper No, AIAA-90-1095-CP, pp. 327–333

  • Kirkpatrick, S.; Gelatt, C.D.; Vecchi, M.P. 1983: Optimization by simulated annealing.Science 220, 671–680

    Google Scholar 

  • Land, A.M.; Doig, A.G. 1960: An automatic method of solving discrete programming problems.Esconometrica 28, 497–520

    Google Scholar 

  • Lawler, E.L.; Bell, M.D. 1966: A method for solving discrete optimization problems.Operations Research 14, 1098–1112

    Google Scholar 

  • Lee, T.W.; Freudenstein, F. 1976: Heuristic combinatorial optimization in the kinematic design of mechanisms.ASME J. Engineering for Industry 4, 1277–1284

    Google Scholar 

  • Lin, C.-Y.; Hajela, P. 1992: Genetic algorithms in optimization problems with discrete and integer design variables.Engng. Optim. 19, 309–327

    Google Scholar 

  • Lin, S.; Kernighan, B.W. 1973: An effective heuristic algorithm for solving mixed-discrete nonlinear design optimization problems.Operations Research 21, 498–516

    Google Scholar 

  • Loh, H.T.; Papalambros, P.Y. 1991: A sequential linearization approach for solving mixed-discrete nonlinear design optimization.J. Mech. Des. ASME 113, 325–334

    Google Scholar 

  • Loh, H.T.; Papalambros, P.Y. 1991: Computational implementaion and tests for solving mixed-discrete nonlinear design optimization problems.J. Mech. Des. ASME 113, 335–345

    Google Scholar 

  • Lucidi, S.; Piccioni, M. 1989: Random tunneling by means of acceptance-rejection sampling for global optimization.J. Optim. Theory Appl. 62, 255–277

    Google Scholar 

  • Luenberger, D. 1984:Linear and nonlinear programming. Reading, MA: Addison-Wesley

    Google Scholar 

  • May, S.A.; Balling, R.J. 1991: Strategies which permit multiple discrete section properties per member in 3D frameworks. In: Ural, O.; Wang, T.-L. (eds.)Electronic computation, pp. 189–196. New York: ASCE

    Google Scholar 

  • May, S.A.; Balling, R.J. 1992: A filtered simulated annealing strategy for discrete optimization of 3D steel frameworks.Struct. Optim. 4, 142–148

    Google Scholar 

  • Mesquita, L.; Kamat, M. 1987: Optimization of stiffened laminated composite plates with frequency constraints.Engng. Optim. 11, 77–88

    Google Scholar 

  • Metropolis, N.; Rosenbluth, A.W.; Rosenbluth, M.N.; Teller, A.H.; Teller, E. 1953: Equations of state calculations by fast computing machines.J. Chemical Physics 21, 1087–1092

    Google Scholar 

  • Ming-Zhu, D. 1986: An improved Templeman's algorithm for the optimum design of trusses with discrete member sizes.Eng. Opt. 9, 303–312

    Google Scholar 

  • Minoux, M. 1986:Mathematical programming theory and algorithms. New York: John-Wiley & Sons

    Google Scholar 

  • Mottl, J. 1992: Excavator optimization using the “voting method”.Comp. Meth. Appl. Mech. Engng. 98, 227–250

    Google Scholar 

  • Olsen, G.R.; Vanderplaats, G.N. 1989: Method for nonlinear optimization with discrete design variables.AIAA J. 27, 1584–1589

    Google Scholar 

  • Pyrz, M. 1990: Discrete optimization of geometrically nonlinear truss structures under stability constraints.Struct. Optim. 2, 125–131

    Google Scholar 

  • Reinschmidt, K. 1971: Discrete structural optimization.J. Struct. Div. ASCE 94, 133–156

    Google Scholar 

  • Reiter, S.; Rice, D.B. 1966: Discrete optimizing solution procedures for linear and nonlinear integer programming problems.Management Science 12, 829–850

    Google Scholar 

  • Reiter, S.; Sherman, G. 1965: Discrete programming.J. Society for Industrial and Applied Mathematics 13, 864–889

    Google Scholar 

  • Ringertz, U.T. 1988: On methods for discrete structural optimization.Engng. Optim. 13, 47–64

    Google Scholar 

  • Salajegheh, E.; Vanderplaats, G.N. 1993: Optimum design of trusses with sizing and shape variables.Struct. Optim. 6, 79–85

    Google Scholar 

  • Salkin, H.M. 1975:Integer programming. Reading, MA: Addison-Wesley

    Google Scholar 

  • Salmon, C.G.; Johnson, J.E. 1979:Steel structures design and behavior. New York: Harper and Row

    Google Scholar 

  • Sandgren, E. 1990a: Nonlinear integer and discrete programming in mechanical design optimization.ASME J. Mech. Des. 112, 223–229

    Google Scholar 

  • Sandgren, E. 1990b: Nonlinear integer and discrete programming for topological decision making in engineering design.ASME J. Mech. Des. 112, 118–122

    Google Scholar 

  • Schmit, L.; Fleury, C. 1980: Discrete-continuous variable structural synthesis using dual methods.AIAA J. 18, 1515–1524

    Google Scholar 

  • Schrage, L. 1983:LINDO — linear interactive discrete optimizer. Chicago: University of Chicago

    Google Scholar 

  • Sepulveda, A.; Cassis, J. 1986: An efficient algorithm for the optimum design of trusses with discrete variables.Int. J. Num. Meth. Eng. 23, 1111–1130

    Google Scholar 

  • Shin, D. D.K.; Gurdal, Z.; Griffin, O.H., Jr. 1990: A penalty approach for nonlinear optimization with discrete variables.Int. J. Num. Meth. Eng. 23, 1111–1130

    Google Scholar 

  • Siddall, J.N. 1982:Optimal engineering design. New York: Marcel Decker

    Google Scholar 

  • Sugimoto, H. 1992: Discrete optimization of truss structures and genetic algorithms. In: Choi, C.-K.; Sugimoto, H.; Yun, C.-B. (eds.)Proc. Korea-Japan Joint Seminar on Structural Optimization (held in Seoul, Korea), pp. 1–10. Computational Structural Engineering Institute of Korea, Seoul

    Google Scholar 

  • Templeman, A.B.; Yates, D.F. 1983a: A linear programming approach to the discrete optimum design of trusses. In: Eschenauer, H.; Olhoff, N. (eds.)Optimization methods in structural design, pp. 133–139. Mannheim: BI Wissenschaftsverlag

    Google Scholar 

  • Templeman, A.B.; Yates, D.F. 1983b: A segmental method for the discrete optimum design of structures.Engng. Optim. 6, 145–155

    Google Scholar 

  • Toakley, A.R. 1968: Optimum design using available sections.ASCE J. Struct. Div. ASCE 34, 1219–1241

    Google Scholar 

  • Tseng, C.H.; Wang, L.W.; Ling, S.F. 1992: A numerical study of the branch-and-bound method in structural optimization.Technical Report, Department of Mechanical Engineering, National Chiao Tung University, Taiwan

    Google Scholar 

  • Vanderplaats, G.N.; Thanedar, P.B. 1991: A survey of discrete variable optimization for structural design. In: Ural, O.; Wang, T.-L. (eds.)Electronic computation, pp. 173–180. New York: ASCE

    Google Scholar 

  • Yuan, K.Y.; Liang, C.C.; Ma, Y.C. 1990: The estimation of the accuracy and efficiency of the backtrack programming method for discrete-variable structural optimization problems.Comp. & Struct. 36, 211–222

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Optimal Design Laboratory, College of Engineering, The University of Iowa, 52242, Iowa City, IA, USA

    J. S. Arora & M. W. Huang

  2. GM Systems Engineering, 48020, Troy, MI, USA

    C. C. Hsieh

Authors
  1. J. S. Arora
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M. W. Huang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. C. C. Hsieh
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Arora, J.S., Huang, M.W. & Hsieh, C.C. Methods for optimization of nonlinear problems with discrete variables: A review. Structural Optimization 8, 69–85 (1994). https://doi.org/10.1007/BF01743302

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01743302

Keywords