Contributed Session Thu.2.H 2013

Thursday, 13:15 - 14:45 h, Room: H 2013

Cluster 11: Integer & mixed-integer programming [...]

Network analysis


Chair: Stefan Wiesberg



Thursday, 13:15 - 13:40 h, Room: H 2013, Talk 1

Xavier Molinero
Variations in strict separating systems representing a linearly separable function

Coauthor: Josep Freixas


An important consideration when applying neural networks is predict the effect of threshold and weight perturbations on them, i.e., which is the sharpest bound one may consider for weights and threshold to maintain the linearly separable function unchangeable for designing a more robust
and safer neural network.
Two parameters have been introduced to measure the relative errors in weights and threshold of strict separating systems: the tolerance (Hu 1960) and the greatest tolerance (Freixas and Molinero 2008). Given an arbitrary separating system we study which is the equivalent separating system that provides maximum tolerance and maximum greatest tolerance.
We present new results for the maximum tolerance and the maximum greatest tolerance, for instance, we present when the maximum tolerance and maximum greatest tolerance among all equivalent strict separating (natural) systems are attained.
We also give the strict separating (natural) system that attaches the maximum tolerance for n variables. Similar results appear for the maximum greatest tolerance.
Finally, we also give new results for the number of variables n and the number of types of distinguished variables k.



Thursday, 13:45 - 14:10 h, Room: H 2013, Talk 2

Arne Müller
Cycle free flows in large-scale metabolic networks


Genome-scale metabolic networks are used to model all (usually around 2000) chemical reactions occuring in a biological cell. These networks are a generalization of directed hypergraphs (where the reactions are the arcs of the graph) and a specialization of realizable oriented matroids.
We are interested in optimizing the flow through a given reaction in the network. We have the usual constraint of flow conservation and additionally the flow must not contain internal circuits. Internal circuits are flows that do not contain a specific subset of the reactions called exchange reactions.
We show that it is NP-hard to decide if a non-zero flow without internal circuits through a given reaction is possible. However, most genome-scale metabolic networks only contain few internal circuits. Using a specific branching strategy combined with a primal heuristic, we derive a tractability result that is also practically applicable. In fact, it very often suffices to solve only one LP.
For flux variability analysis, where we solve optimization problems for each reaction in the network, we obtain a speed-up of factor 30-300 to previous methods.



Thursday, 14:15 - 14:40 h, Room: H 2013, Talk 3

Stefan Wiesberg
Computing role structures in networks

Coauthor: Gerhard Reinelt


In network analysis, an established way to obtain structural information is to partition the vertices into so-called regular equivalence classes. In such a partitioning, two nodes u and v belong to the same class if for every neighbor of u, there is a neighbor of v in the same class, and vice versa. Thus, for any two classes C and D, either every or no member of C has a neighbor in D. The relationships between the classes can hence be visualized by a graph, the so-called role graph. It is of interest in several fields, for example in sociology, economy, or consumer research.
An NP-hard problem in this context is the following one: Given a network G and a finite set R of role graphs, which element of R represents the role structure of G in the best possible way? We present one of the first exact algorithms for this problem. It is based on an IP formulation with a quadratic objective function and solved by branch-and-cut. Significant running-time improvements compared to currently used methods are reported.


  There are three major facts that should be watched out for in all payday loans in the United States. Thanks to that, they have a great variety of drugs that can help in these cases. Female Viagra is not an exception.