## F. Theory of Computation

### Refine

#### Document Type

- ZIB-Report (4)

#### Language

- English (4)

#### Has Fulltext

- yes (4)

#### Is part of the Bibliography

- no (4)

#### Keywords

- ASTS orientations (1)
- Bayesian hierarchical modeling (1)
- Bayesian inference (1)
- DS-MLE (1)
- EM algorithm (1)
- Jeffreys prior (1)
- MPLE (1)
- NPMLE (1)
- adhesive categories (1)
- amalgamated graph transformation (1)

#### Institute

Improved optimization models for potential-driven network flow problems via ASTS orientations
(2019)

The class of potential-driven network flow problems provides important models for a range of infrastructure networks that lead to hard-to-solve MINLPs in real-world applications. On large-scale meshed networks the relaxations usually employed are rather weak due to cycles in the network. To address this situation, we introduce the concept of ASTS orientations, a generalization of bipolar orientations, as a combinatorial relaxation of feasible solutions of potential-driven flow problems, study their structure, and show how they can be used to strengthen existing relaxations and thus provide improved optimization models. Our computational results indicate that ASTS orientations can be used to derive much stronger bounds on the flow variables than existing bound tightening methods and to yield significant performance improvements for an existing state-of-the-art MILP model for large-scale gas networks.

When estimating a probability density within the empirical Bayes framework, the non-parametric maximum likelihood estimate (NPMLE) usually tends to overfit the data. This issue is usually taken care of by regularization - a penalization term is subtracted from the marginal log-likelihood before the maximization step, so that the estimate favors smooth solutions, resulting in the so-called maximum penalized likelihood estimation (MPLE).
The majority of penalizations currently in use are rather arbitrary brute-force solutions, which lack invariance under transformation of the parameters(reparametrization) and measurements.
This contradicts the principle that, if the underlying model
has several equivalent formulations, the methods of inductive inference should lead to consistent results. Motivated by this principle and using an information-theoretic point of view, we suggest an entropy-based penalization term that guarantees this kind of invariance. The resulting density estimate can be seen as a generalization of reference priors. Using the reference prior as a hyperprior, on the other hand, is argued to be a poor choice for regularization. We also present an insightful connection between the NPMLE, the cross entropy
and the principle of minimum discrimination information suggesting another method of inference that contains the doubly-smoothed maximum likelihood estimation as a special case.

Amalgamated graph transformation allows to define schemes of rules
coinciding in common core activities and differing over additional parallel independent
activities. Consequently, a rule scheme is specified by a kernel rule and a set of extending multi-rules forming an interaction scheme. Amalgamated
transformations have been increasingly used in various modeling contexts.
Critical Pair Analysis (CPA) can be used to show local confluence of graph transformation
systems. It is an open challenge to lift the CPA to amalgamated graph transformation systems, especially since infinite many pairs of amalgamated rules
occur in general. As a first step towards an efficient local confluence analysis of
amalgamated graph transformation systems, we show that the analysis of a finite
set of critical pairs suffices to prove local confluence.

Attributes are an important concept for modeling data in practical applications. Up to now there is no adequate way to define attributes for different kinds of models used in M-adhesive transformation systems, which are a special kind of graph transformation systems based on M-adhesive categories. Especially a proper representation and definition of attributes and their values as well as a suitable handling of the data does not fit well with other graph transformation formalisms.
In this paper, we propose a new method to define attributes in a natural, but still formally precise and widely applicable way. We define a new kind of adhesive category, called W-adhesive, that can be used for transformations of attributes, while the underlying models are still M-adhesive ones. As a result, attributed models can be used as they are intended to be, but with a formal background and proven well-behavior.