nach oben

Erschienen in:

2013 | OriginalPaper | Buchkapitel

A Primal Heuristic for Nonsmooth Mixed Integer Nonlinear Optimization

verfasst von : Martin Schmidt, Marc C. Steinbach, Bernhard M. Willert

Erschienen in: Facets of Combinatorial Optimization

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Complex real-world optimization tasks often lead to mixed-integer nonlinear problems (MINLPs). However, current MINLP algorithms are not always able to solve the resulting large-scale problems. One remedy is to develop problem specific primal heuristics that quickly deliver feasible solutions. This paper presents such a primal heuristic for a certain class of MINLP models. Our approach features a clear distinction between nonsmooth but continuous and genuinely discrete aspects of the model. The former are handled by suitable smoothing techniques; for the latter we employ reformulations using complementarity constraints. The resulting mathematical programs with equilibrium constraints (MPEC) are finally regularized to obtain MINLP-feasible solutions with general purpose NLP solvers.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Exact Algorithms for Combinatorial Optimization Problems with Submodular Objective Functions

Nächstes Kapitel A New Algorithm for MINLP Applied to Gas Transport Energy Cost Minimization

Baumrucker, B.T., Renfro, J.G., Biegler, L.T.: MPEC problem formulations and solution strategies with chemical engineering applications. Comput. Chem. Eng. 32(12), 2903–2913 (2008) CrossRef

Borraz-Sánchez, C., Ríos-Mercado, R.Z.: A hybrid meta-heuristic approach for natural gas pipeline network optimization. In: Blesa, M., Blum, C., Roli, A., Sampels, M. (eds.) Hybrid Metaheuristics. Lecture Notes in Computer Science, vol. 3636, pp. 54–65. Springer, Berlin (2005). doi:10.1007/11546245_6 CrossRef

Boyd, E.A., Scott, L.R., Wu, S.: Evaluating the quality of pipeline optimization algorithms. In: Pipeline Simulation Interest Group 29th Annual Meeting, Tucson, AZ, paper 9709 (1997)

Burgschweiger, J., Gnädig, B., Steinbach, M.C.: Optimization models for operative planning in drinking water networks. Optim. Eng. 10(1), 43–73 (2009). doi:10.1007/s11081-008-9040-8 MathSciNetCrossRef

Burgschweiger, J., Gnädig, B., Steinbach, M.C.: Nonlinear programming techniques for operative planning in large drinking water networks. Open Appl. Math. J. 3, 14–28 (2009). doi: 10.2174/1874114200903010014 MathSciNetCrossRef

Carter, R.G.: Compressor station optimization: computational accuracy and speed. In: Pipeline Simulation Interest Group 28th Annual Meeting, paper 9605 (1996)

Cobos-Zaleta, D., Ríos-Mercado, R.Z.: A MINLP model for a problem of minimizing fuel consumption on natural gas pipeline networks. In: Proc. XI Latin-Ibero-American Conference on Operations Research, paper A48-01, pp. 1–9 (2002)

Dantzig, G.B.: On the significance of solving linear programming problems with some integer variables. Econometrica 28(1), 30–44 (1960). www.jstor.org/stable/1905292 MathSciNetMATHCrossRef

de Wolf, D., Smeers, Y.: The gas transmission problem solved by an extension of the simplex algorithm. Manag. Sci. 46(11), 1454–1465 (2000) MATHCrossRef

10.

DeMiguel, A.V., Friedlander, M.P., Nogales, F.J., Scholtes, S.: A two-sided relaxation scheme for mathematical programs with equilibrium constraints. SIAM J. Optim. 16(1), 587–609 (2005). doi:10.1109/TIT.2005.860448 MathSciNetMATHCrossRef

11.

Domschke, P., Geißler, B., Kolb, O., Lang, J., Martin, A., Morsi, A.: Combination of nonlinear and linear optimization of transient gas networks. INFORMS J. Comput. 23(4), 605–617 (2011). doi:10.1287/ijoc.1100.0429 MathSciNetMATHCrossRef

12.

Ehrhardt, K., Steinbach, M.C.: KKT systems in operative planning for gas distribution networks. Proc. Appl. Math. Mech. 4(1), 606–607 (2004) CrossRef

13.

Ehrhardt, K., Steinbach, M.C.: Nonlinear optimization in gas networks. In: Bock, H.G., Kostina, E., Phu, H.X., Rannacher, R. (eds.) Modeling, Simulation and Optimization of Complex Processes, pp. 139–148. Springer, Berlin (2005) CrossRef

14.

Fischer, A.: A special Newton-type optimization method. Optimization 24(3–4), 269–284 (1992). doi:10.1080/02331939208843795 MathSciNetMATHCrossRef

15.

Fügenschuh, A., Geißler, B., Gollmer, R., Hayn, C., Henrion, R., Hiller, B., Humpola, J., Koch, T., Lehmann, T., Martin, A., Mirkov, R., Morsi, A., Römisch, W., Rövekamp, J., Schewe, L., Schmidt, M., Schultz, R., Schwarz, R., Schweiger, J., Stangl, C., Steinbach, M.C., Willert, B.M.: Mathematical optimization for challenging network planning problems in unbundled liberalized gas markets. Technical report ZR 13-13, ZIB (2013)

16.

GAMS—A Users Guide. Redwood City (1988)

17.

Grossmann, I.E.: Review of nonlinear mixed-integer and disjunctive programming techniques. Optim. Eng. 3(3), 227–252 (2002). doi:10.1023/A:1021039126272 MathSciNetMATHCrossRef

18.

Hoheisel, T., Kanzow, C., Schwartz, A.: Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints. Preprint 299, Institute of Mathematics, University of Würzburg (2010)

19.

Hu, X.M., Ralph, D.: Convergence of a penalty method for mathematical programming with complementarity constraints. J. Optim. Theory Appl. 123, 365–390 (2004) MathSciNetCrossRef

20.

Koch, T., Bargmann, D., Ebbers, M., Fügenschuh, A., Geißler, B., Geißler, N., Gollmer, R., Gotzes, U., Hayn, C., Heitsch, H., Henrion, R., Hiller, B., Humpola, J., Joormann, I., Kühl, V., Lehmann, T., Leövey, H., Martin, A., Mirkov, R., Möller, A., Morsi, A., Oucherif, D., Pelzer, A., Pfetsch, M.E., Schewe, L., Römisch, W., Rövekamp, J., Schmidt, M., Schultz, R., Schwarz, R., Schweiger, J., Spreckelsen, K., Stangl, C., Steinbach, M.C., Steinkamp, A., Wegner-Specht, I., Willert, B.M., Vigerske, S. (eds.): From Simulation to Optimization: Evaluating Gas Network Capacities. In preparation

21.

Kraemer, K., Marquardt, W.: Continuous reformulation of MINLP problems. In: Diehl, M., Glineur, F., Jarlebring, E., Michiels, W. (eds.) Recent Advances in Optimization and Its Applications in Engineering, pp. 83–92. Springer, Berlin (2010). doi:10.1007/978-3-642-12598-0_8 CrossRef

22.

LaMaTTO++. www.mso.math.fau.de/edom/projects/lamatto.html

23.

Leyffer, S., López-Calva, G., Nocedal, J.: Interior methods for mathematical programs with complementarity constraints. SIAM J. Optim. 17, 52–77 (2004) CrossRef

24.

Markowitz, H.M., Manne, A.S.: On the solution of discrete programming problems. Econometrica 25(1), 84–110 (1957). www.jstor.org/stable/1907744 MathSciNetMATHCrossRef

25.

Martin, A., Möller, M.: Cutting planes for the optimization of gas networks. In: Bock, H.G., Kostina, E., Phu, H.X., Rannacher, R. (eds.) Modeling, Simulation and Optimization of Complex Processes, pp. 307–329. Springer, Berlin (2005) CrossRef

26.

Martin, A., Möller, M., Moritz, S.: Mixed integer models for the stationary case of gas network optimization. Math. Program., Ser. B 105(2–3), 563–582 (2006). doi:10.1007/s10107-005-0665-5 MATHCrossRef

27.

Martin, A., Mahlke, D., Moritz, S.: A simulated annealing algorithm for transient optimization in gas networks. Math. Methods Oper. Res. 66(1), 99–115 (2007). doi:10.1007/s00186-006-0142-9 MathSciNetMATHCrossRef

28.

Meyer, R.R.: Mixed integer minimization models for piecewise-linear functions of a single variable. Discrete Math. 16(2), 163–171 (1976). doi:10.1016/0012-365X(76)90145-X MathSciNetMATHCrossRef

29.

Osiadacz, A.: Nonlinear programming applied to the optimum control of a gas compressor station. Int. J. Numer. Methods Eng. 15(9), 1287–1301 (1980). doi:10.1002/nme.1620150902 MathSciNetMATHCrossRef

30.

Pfetsch, M.E., Fügenschuh, A., Geißler, B., Geißler, N., Gollmer, R., Hiller, B., Humpola, J., Koch, T., Lehmann, T., Martin, A., Morsi, A., Rövekamp, J., Schewe, L., Schmidt, M., Schultz, R., Schwarz, R., Schweiger, J., Stangl, C., Steinbach, M.C., Vigerske, S., Willert, B.M.: Validation of nominations in gas network optimization: models, methods, and solutions. Technical report ZR 12-41, ZIB (2012)

31.

Pratt, K.F., Wilson, J.G.: Optimization of the operation of gas transmission systems. Trans. Inst. Meas. Control 6(5), 261–269 (1984). doi:10.1177/014233128400600411 CrossRef

32.

Raman, R., Grossmann, I.E.: Modeling and computational techniques for logic based integer programming. Comput. Chem. Eng. 18(7), 563–578 (1994) CrossRef

33.

Ríos-Mercado, R.Z., Wu, S., Scott, L.R., Boyd, A.E.: A reduction technique for natural gas transmission network optimization problems. Ann. Oper. Res. 117, 217–234 (2002) MATHCrossRef

34.

Ríos-Mercado, R.Z., Kim, S., Boyd, A.E.: Efficient operation of natural gas transmission systems: a network-based heuristic for cyclic structures. Comput. Oper. Res. 33(8), 2323–2351 (2006). doi:10.1016/j.cor.2005.02.003 MATHCrossRef

35.

Scheel, H., Scholtes, S.: Mathematical programs with complementarity constraints: stationarity, optimality and sensitivity. Math. Oper. Res. 25, 1–22 (2000) MathSciNetMATHCrossRef

36.

Schmidt, M., Steinbach, M.C., Willert, B.M.: High detail stationary optimization models for gas networks—part 1: model components. IfAM preprint 94, Inst. of Applied Mathematics, Leibniz Universität Hannover (2012, submitted)

37.

Schmidt, M., Steinbach, M.C., Willert, B.M.: High detail stationary optimization models for gas networks—part 2: validation and results (2013, in preparation)

38.

Scholtes, S.: Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim. 11(4), 918–936 (2001) MathSciNetMATHCrossRef

39.

Stein, O., Oldenburg, J., Marquardt, W.: Continuous reformulations of discrete-continuous optimization problems. Comput. Chem. Eng. 28(10), 1951–1966 (2004) CrossRef

40.

Steinbach, M.C.: On PDE solution in transient optimization of gas networks. J. Comput. Appl. Math. 203(2), 345–361 (2007). doi:10.1016/j.cam.2006.04.018 MathSciNetMATHCrossRef

41.

Sun, D., Qi, L.: On NCP-functions. Computational optimization—a tribute to Olvi Mangasarian, part II. Comput. Optim. Appl. 13(1–3), 201–220 (1999). doi:10.1023/A:1008669226453 MathSciNetMATHCrossRef

42.

Vielma, J.P., Nemhauser, G.L.: Modeling disjunctive constraints with a logarithmic number of binary variables and constraints. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, vol. 5035, pp. 199–213. Springer, Berlin (2008). doi:10.1007/978-3-540-68891-4_14 CrossRef

43.

Wächter, A., Biegler, L.T.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106(1), 25–57 (2006). doi:10.1007/s10107-004-0559-y MathSciNetMATHCrossRef

44.

Wright, S., Somani, M., Ditzel, C.: Compressor station optimization. In: Pipeline Simulation Interest Group 30th Annual Meeting, paper 9805 (1998)

45.

Wu, S., Ríos-Mercado, R.Z., Boyd, A.E., Scott, L.R.: Model relaxations for the fuel cost minimization of steady-state gas pipeline networks. Technical report TR-99-01, University of Chicago (1999)

Titel: A Primal Heuristic for Nonsmooth Mixed Integer Nonlinear Optimization
verfasst von: Martin Schmidt
Marc C. Steinbach
Bernhard M. Willert
Verlag: Springer Berlin Heidelberg
Buch: Facets of Combinatorial Optimization
Print ISBN: 978-3-642-38188-1

Electronic ISBN: 978-3-642-38189-8

Copyright-Jahr: 2013
DOI: https://doi.org/10.1007/978-3-642-38189-8_13

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"