Fulltext

Graph problems arising from parameter identification of discrete dynamical systems

Borchers, Steffen ; Bosio, Sandro ; Findeisen, Rolf ; Haus, Utz-Uwe ; Rumschinski, Philipp ; Weismantel, Robert

In: Mathematical Methods of Operations Research, 2011, vol. 73, no. 3, p. 381-400

Add to personal list
    Title
    • Graph problems arising from parameter identification of discrete dynamical systems
    Author
    • Borchers, Steffen. Institut für Automatisierungstechnik, Otto-von-Guericke Universität, Universitätsplatz 2, 39106, Magdeburg, Germany
    • Bosio, Sandro. Institute for Operations Research (IFOR), Eidgenössischen Technischen Hochschule (ETH) Zürich, Rämistrasse 101, 8092, Zürich, Switzerland
    • Findeisen, Rolf. Institut für Automatisierungstechnik, Otto-von-Guericke Universität, Universitätsplatz 2, 39106, Magdeburg, Germany
    • Haus, Utz-Uwe. Institute for Operations Research (IFOR), Eidgenössischen Technischen Hochschule (ETH) Zürich, Rämistrasse 101, 8092, Zürich, Switzerland
    • Rumschinski, Philipp. Institut für Automatisierungstechnik, Otto-von-Guericke Universität, Universitätsplatz 2, 39106, Magdeburg, Germany
    • Weismantel, Robert. Institute for Operations Research (IFOR), Eidgenössischen Technischen Hochschule (ETH) Zürich, Rämistrasse 101, 8092, Zürich, Switzerland
    Document Type
    • Postprint
    Language
    • English
    Published in
    • Mathematical Methods of Operations Research, 2011, vol. 73, no. 3, p. 381-400. Springer-Verlag
    Other Version
    OAI-PMH Identifier
    • oai:doc.rero.ch:313552
    Summary
    This paper focuses on combinatorial feasibility and optimization problems that arise in the context of parameter identification of discrete dynamical systems. Given a candidate parametric model for a physical system and a set of experimental observations, the objective of parameter identification is to provide estimates of the parameter values for which the model can reproduce the experiments. To this end, we define a finite graph corresponding to the model, to each arc of which a set of parameters is associated. Paths in this graph are regarded as feasible only if the sets of parameters corresponding to the arcs of the path have nonempty intersection. We study feasibility and optimization problems on such feasible paths, focusing on computational complexity. We show that, under certain restrictions on the sets of parameters, some of the problems become tractable, whereas others are NP-hard. In a similar vein, we define and study some graph problems for experimental design, whose goal is to support the scientist in optimally designing new experiments