IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v70y2018i3d10.1007_s10589-018-9993-2.html
   My bibliography  Save this article

Combinatorial optimal control of semilinear elliptic PDEs

Author

Listed:
  • Christoph Buchheim

    (TU Dortmund)

  • Renke Kuhlmann

    (TU Dortmund)

  • Christian Meyer

    (TU Dortmund)

Abstract

Optimal control problems (OCPs) containing both integrality and partial differential equation (PDE) constraints are very challenging in practice. The most wide-spread solution approach is to first discretize the problem, which results in huge and typically nonconvex mixed-integer optimization problems that can be solved to proven optimality only in very small dimensions. In this paper, we propose a novel outer approximation approach to efficiently solve such OCPs in the case of certain semilinear elliptic PDEs with static integer controls over arbitrary combinatorial structures, where we assume the nonlinear part of the PDE to be non-decreasing and convex. The basic idea is to decompose the OCP into an integer linear programming (ILP) master problem and a subproblem for calculating linear cutting planes. These cutting planes rely on the pointwise concavity or submodularity of the PDE solution with respect to the control variables. The decomposition allows us to use standard solution techniques for ILPs as well as for PDEs. We further benefit from reoptimization strategies for the PDE solution due to the iterative structure of the algorithm. Experimental results show that the new approach is capable of solving the combinatorial OCP of a semilinear Poisson equation with up to 180 binary controls to global optimality within a 5 h time limit. In the case of the screened Poisson equation, which yields semi-infinite integer linear programs, problems with as many as 1400 binary controls are solved.

Suggested Citation

  • Christoph Buchheim & Renke Kuhlmann & Christian Meyer, 2018. "Combinatorial optimal control of semilinear elliptic PDEs," Computational Optimization and Applications, Springer, vol. 70(3), pages 641-675, July.
  • Handle: RePEc:spr:coopap:v:70:y:2018:i:3:d:10.1007_s10589-018-9993-2
    DOI: 10.1007/s10589-018-9993-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10589-018-9993-2
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10589-018-9993-2?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Falk Hante & Sebastian Sager, 2013. "Relaxation methods for mixed-integer optimal control of partial differential equations," Computational Optimization and Applications, Springer, vol. 55(1), pages 197-225, May.
    2. M. Santis & G. Pillo & S. Lucidi, 2012. "An active set feasible method for large-scale minimization problems with bound constraints," Computational Optimization and Applications, Springer, vol. 53(2), pages 395-423, October.
    3. Sebastian Sager & Michael Jung & Christian Kirches, 2011. "Combinatorial integral approximation," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 73(3), pages 363-380, June.
    4. Björn Geißler & Oliver Kolb & Jens Lang & Günter Leugering & Alexander Martin & Antonio Morsi, 2011. "Mixed integer linear models for the optimization of dynamical transport networks," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 73(3), pages 339-362, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Julia Grübel & Richard Krug & Martin Schmidt & Winnifried Wollner, 2023. "A Successive Linear Relaxation Method for MINLPs with Multivariate Lipschitz Continuous Nonlinearities," Journal of Optimization Theory and Applications, Springer, vol. 198(3), pages 1077-1117, September.
    2. Carolin Natemeyer & Daniel Wachsmuth, 2021. "A proximal gradient method for control problems with non-smooth and non-convex control cost," Computational Optimization and Applications, Springer, vol. 80(2), pages 639-677, November.
    3. Jeffrey Larson & Sven Leyffer & Prashant Palkar & Stefan M. Wild, 2021. "A method for convex black-box integer global optimization," Journal of Global Optimization, Springer, vol. 80(2), pages 439-477, June.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Marvin Severitt & Paul Manns, 2023. "Efficient Solution of Discrete Subproblems Arising in Integer Optimal Control with Total Variation Regularization," INFORMS Journal on Computing, INFORMS, vol. 35(4), pages 869-885, July.
    2. S. Göttlich & A. Potschka & C. Teuber, 2019. "A partial outer convexification approach to control transmission lines," Computational Optimization and Applications, Springer, vol. 72(2), pages 431-456, March.
    3. Sven Leyffer & Paul Manns & Malte Winckler, 2021. "Convergence of sum-up rounding schemes for cloaking problems governed by the Helmholtz equation," Computational Optimization and Applications, Springer, vol. 79(1), pages 193-221, May.
    4. Mengying Xue & Tianhu Deng & Zuo‐Jun Max Shen, 2019. "Optimizing natural gas pipeline transmission with nonuniform elevation: A new initialization approach," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(7), pages 547-564, October.
    5. Martin Siebenborn, 2018. "A Shape Optimization Algorithm for Interface Identification Allowing Topological Changes," Journal of Optimization Theory and Applications, Springer, vol. 177(2), pages 306-328, May.
    6. Kazda, Kody & Li, Xiang, 2024. "A linear programming approach to difference-of-convex piecewise linear approximation," European Journal of Operational Research, Elsevier, vol. 312(2), pages 493-511.
    7. Enrico Bettiol & Lucas Létocart & Francesco Rinaldi & Emiliano Traversi, 2020. "A conjugate direction based simplicial decomposition framework for solving a specific class of dense convex quadratic programs," Computational Optimization and Applications, Springer, vol. 75(2), pages 321-360, March.
    8. Pipicelli, Michele & Muccillo, Massimiliano & Gimelli, Alfredo, 2023. "Influence of the control strategy on the performance of hybrid polygeneration energy system using a prescient model predictive control," Applied Energy, Elsevier, vol. 329(C).
    9. Yan-Chao Liang & Jane J. Ye, 2021. "Optimality Conditions and Exact Penalty for Mathematical Programs with Switching Constraints," Journal of Optimization Theory and Applications, Springer, vol. 190(1), pages 1-31, July.
    10. Falk M. Hante & Martin Schmidt, 2019. "Complementarity-based nonlinear programming techniques for optimal mixing in gas networks," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 7(3), pages 299-323, September.
    11. Andrea Cristofari & Marianna Santis & Stefano Lucidi & Francesco Rinaldi, 2020. "An active-set algorithmic framework for non-convex optimization problems over the simplex," Computational Optimization and Applications, Springer, vol. 77(1), pages 57-89, September.
    12. Steffen Rebennack, 2016. "Computing tight bounds via piecewise linear functions through the example of circle cutting problems," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 84(1), pages 3-57, August.
    13. Andrea Cristofari & Gianni Di Pillo & Giampaolo Liuzzi & Stefano Lucidi, 2022. "An Augmented Lagrangian Method Exploiting an Active-Set Strategy and Second-Order Information," Journal of Optimization Theory and Applications, Springer, vol. 193(1), pages 300-323, June.
    14. Frison, Lilli & Kollmar, Manuel & Oliva, Axel & Bürger, Adrian & Diehl, Moritz, 2024. "Model predictive control of bidirectional heat transfer in prosumer-based solar district heating networks," Applied Energy, Elsevier, vol. 358(C).
    15. Björn Geißler & Antonio Morsi & Lars Schewe & Martin Schmidt, 2018. "Solving Highly Detailed Gas Transport MINLPs: Block Separability and Penalty Alternating Direction Methods," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 309-323, May.
    16. Er-Rahmadi, Btissam & Ma, Tiejun, 2022. "Data-driven mixed-Integer linear programming-based optimisation for efficient failure detection in large-scale distributed systems," European Journal of Operational Research, Elsevier, vol. 303(1), pages 337-353.
    17. Martin Gugat & Günter Leugering & Alexander Martin & Martin Schmidt & Mathias Sirvent & David Wintergerst, 2018. "MIP-based instantaneous control of mixed-integer PDE-constrained gas transport problems," Computational Optimization and Applications, Springer, vol. 70(1), pages 267-294, May.
    18. Andrea Cristofari & Marianna Santis & Stefano Lucidi & Francesco Rinaldi, 2017. "A Two-Stage Active-Set Algorithm for Bound-Constrained Optimization," Journal of Optimization Theory and Applications, Springer, vol. 172(2), pages 369-401, February.
    19. Bürger, Adrian & Bohlayer, Markus & Hoffmann, Sarah & Altmann-Dieses, Angelika & Braun, Marco & Diehl, Moritz, 2020. "A whole-year simulation study on nonlinear mixed-integer model predictive control for a thermal energy supply system with multi-use components," Applied Energy, Elsevier, vol. 258(C).
    20. Sebastian Sager & Mathieu Claeys & Frédéric Messine, 2015. "Efficient upper and lower bounds for global mixed-integer optimal control," Journal of Global Optimization, Springer, vol. 61(4), pages 721-743, April.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:coopap:v:70:y:2018:i:3:d:10.1007_s10589-018-9993-2. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.