MSMelanie Siebenhofer

Melanie Siebenhofer

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Melanie Siebenhofer has a total of 13 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Correction: Edge expansion of a graph: SDP-based computational strategies

    by Akshay Gupte, Melanie Siebenhofer, Angelika Wiegele


  • Open Access

    Edge expansion of a graph: SDP-based computational strategies

    by Akshay Gupte, Melanie Siebenhofer, Angelika Wiegele

    Computing the edge expansion of a graph is a famously hard combinatorial problem for which there have been many approximation studies. We present two variants of exact algorithms using semidefinite programming (SDP) to compute this constant for any graph. The first variant uses the SDP relaxation first to reduce the search space considerably. The problem is then transformed into instances of max-cut problems which are solved with an SDP-based state-of-the-art solver. Our second variant to compute the edge expansion uses Dinkelbach’s algorithm for fractional programming. This is, we have to solve a parametrized optimization problem and again we use semidefinite programming to obtain solutions of the parametrized problems. Numerical results demonstrate that with our algorithms one can compute the edge expansion on graphs up to 400 vertices in a routine way, including instances where standard branch-and-cut solvers fail. To the best of our knowledge, these are the first SDP-based solvers for computing the edge expansion of a graph.


  • Open Access

    Spanning and splitting: Integer semidefinite programming for the quadratic minimum spanning tree problem

    by Frank de Meijer, Melanie Siebenhofer, Renata Sotirov, Angelika Wiegele


  • Open Access

    Computing the Edge Expansion of a Graph Using Semidefinite Programming

    by Akshay Gupte, Melanie Siebenhofer, Angelika Wiegele

    Computing the edge expansion of a graph is a famously hard combinatorial problem for which there have been many approximation studies. We present two versions of an exact algorithm using semidefinite programming (SDP) to compute this constant for any graph. The SDP relaxation is used to first reduce the search space considerably. One version applies then an SDP-based branch-and-bound algorithm, along with heuristic search. The other version transforms the problem into an instance of a max-cut problem and solves this using a state-of-the-art solver. Numerical results demonstrate that we clearly outperform mixed-integer quadratic solvers as well as another SDP-based algorithm from the literature.


  • Open Access

    Sum-of-Squares Certificates for Vizing's Conjecture via Determining Gröbner Bases

    by Elisabeth Gaar, Melanie Siebenhofer

    The famous open Vizing conjecture claims that the domination number of the Cartesian product graph of two graphs $G$ and $H$ is at least the product of the domination numbers of $G$ and $H$. Recently Gaar, Krenn, Margulies and Wiegele used the graph class $\mathcal{G}$ of all graphs with $n_\mathcal{G}$ vertices and domination number $k_\mathcal{G}$ and reformulated Vizing's conjecture as the problem that for all graph classes $\mathcal{G}$ and $\mathcal{H}$ the Vizing polynomial is sum-of-squares (SOS) modulo the Vizing ideal. By solving semidefinite programs (SDPs) and clever guessing they derived SOS-certificates for some values of $k_\mathcal{G}$, $n_\mathcal{G}$, $k_\mathcal{H}$, and $n_\mathcal{H}$. In this paper, we consider their approach for $k_\mathcal{G} = k_\mathcal{H} = 1$. For this case we are able to derive the unique reduced Gr\"obner basis of the Vizing ideal. Based on this, we deduce the minimum degree $(n_\mathcal{G} + n_\mathcal{H} - 1)/2$ of an SOS-certificate for Vizing's conjecture, which is the first result of this kind. Furthermore, we present a method to find certificates for graph classes $\mathcal{G}$ and $\mathcal{H}$ with $n_\mathcal{G} + n_\mathcal{H} -1 = d$ for general $d$, which is again based on solving SDPs, but does not depend on guessing and depends on much smaller SDPs. We implement our new method in SageMath and give new SOS-certificates for all graph classes $\mathcal{G}$ and $\mathcal{H}$ with $k_\mathcal{G}=k_\mathcal{H}=1$ and $n_\mathcal{G} + n_\mathcal{H} \leq 15$.

  • Open Access

    BiqBin: A Parallel Branch-and-bound Solver for Binary Quadratic Problems with Linear Constraints

    by Nicolò Gusmeroli, Timotej Hrga, Borut Lužar, Janez Povh, Melanie Siebenhofer, Angelika Wiegele

    We present BiqBin, an exact solver for linearly constrained binary quadratic problems. Our approach is based on an exact penalty method to first efficiently transform the original problem into an instance of Max-Cut, and then to solve the Max-Cut problem by a branch-and-bound algorithm. All the main ingredients are carefully developed using new semidefinite programming relaxations obtained by strengthening the existing relaxations with a set of hypermetric inequalities, applying the bundle method as the bounding routine and using new strategies for exploring the branch-and-bound tree.Furthermore, an efficient C implementation of a sequential and a parallel branch-and-bound algorithm is presented. The latter is based on a load coordinator-worker scheme using MPI for multi-node parallelization and is evaluated on a high-performance computer.The new solver is benchmarked against BiqCrunch, GUROBI, and SCIP on four families of (linearly constrained) binary quadratic problems. Numerical results demonstrate that BiqBin is a highly competitive solver. The serial version outperforms the other three solvers on the majority of the benchmark instances. We also evaluate the parallel solver and show that it has good scaling properties. The general audience can use it as an on-line service available athttp://www.biqbin.eu.


  • Open Access

    An SDP-based approach for computing the stability number of a graph

    by Elisabeth Gaar, Melanie Siebenhofer, Angelika Wiegele

    Finding the stability number of a graph, i.e., the maximum number of vertices of which no two are adjacent, is a well known NP-hard combinatorial optimization problem. Since this problem has several applications in real life, there is need to find efficient algorithms to solve this problem. Recently, Gaar and Rendl enhanced semidefinite programming approaches to tighten the upper bound given by the Lovász theta function. This is done by carefully selecting some so-called exact subgraph constraints (ESC) and adding them to the semidefinite program of computing the Lovász theta function. First, we provide two new relaxations that allow to compute the bounds faster without substantial loss of the quality of the bounds. One of these two relaxations is based on including violated facets of the polytope representing the ESCs, the other one adds separating hyperplanes for that polytope. Furthermore, we implement a branch and bound (B&B) algorithm using these tightened relaxations in our bounding routine. We compare the efficiency of our B&B algorithm using the different upper bounds. It turns out that already the bounds of Gaar and Rendl drastically reduce the number of nodes to be explored in the B&B tree as compared to the Lovász theta bound. However, this comes with a high computational cost. Our new relaxations improve the run time of the overall B&B algorithm, while keeping the number of nodes in the B&B tree small.


  • Open Access

    An SDP-Based Approach for Computing the Stability Number of a Graph

    by Elisabeth Gaar, Melanie Siebenhofer, Angelika Wiegele

    Finding the stability number of a graph, i.e., the maximum number of vertices of which no two are adjacent, is a well known NP-hard combinatorial optimization problem. Since this problem has several applications in real life, there is need to find efficient algorithms to solve this problem. Recently, Gaar and Rendl enhanced semidefinite programming approaches to tighten the upper bound given by the Lov\'asz theta function. This is done by carefully selecting some so-called exact subgraph constraints (ESC) and adding them to the semidefinite program of computing the Lov\'asz theta function. First, we provide two new relaxations that allow to compute the bounds faster without substantial loss of the quality of the bounds. One of these two relaxations is based on including violated facets of the polytope representing the ESCs, the other one adds separating hyperplanes for that polytope. Furthermore, we implement a branch and bound (B&B) algorithm using these tightened relaxations in our bounding routine. We compare the efficiency of our B&B algorithm using the different upper bounds. It turns out that already the bounds of Gaar and Rendl drastically reduce the number of nodes to be explored in the B&B tree as compared to the Lov\'asz theta bound. However, this comes with a high computational cost. Our new relaxations improve the run time of the overall B&B algorithm, while keeping the number of nodes in the B&B tree small.

  • Open Access

    BiqBin: a parallel branch-and-bound solver for binary quadratic problems with linear constraints

    by Nicolò Gusmeroli, Timotej Hrga, Borut Lužar, Janez Povh, Melanie Siebenhofer, Angelika Wiegele

    We present BiqBin, an exact solver for linearly constrained binary quadratic problems. Our approach is based on an exact penalty method to first efficiently transform the original problem into an instance of Max-Cut, and then to solve the Max-Cut problem by a branch-and-bound algorithm. All the main ingredients are carefully developed using new semidefinite programming relaxations obtained by strengthening the existing relaxations with a set of hypermetric inequalities, applying the bundle method as the bounding routine and using new strategies for exploring the branch-and-bound tree. Furthermore, an efficient C implementation of a sequential and a parallel branch-and-bound algorithm is presented. The latter is based on a load coordinator-worker scheme using MPI for multi-node parallelization and is evaluated on a high-performance computer. The new solver is benchmarked against BiqCrunch, GUROBI, and SCIP on four families of (linearly constrained) binary quadratic problems. Numerical results demonstrate that BiqBin is a highly competitive solver. The serial version outperforms the other three solvers on the majority of the benchmark instances. We also evaluate the parallel solver and show that it has good scaling properties. The general audience can use it as an on-line service available at http://www.biqbin.eu.

  • Location-Aware Path Alignment in Process Mining

    by Peter Blank, Michael Maurer, Melanie Siebenhofer, Andreas Rogge-Solti, Stefan Schonig

    Location-aware log data is an untapped source of information that promises new business analysis insights. This is in particular the case for business processes that can be linked to sensor data such as RFID or WiFi signals. Technically, this question can be formulated as a special type of alignment problem, which is well known in process mining. In this paper, we formalize the alignment problem for spatio-temporal event data. Our contribution is a novel algorithm that finds sensor IDs that travel together on the basis of their location information. Questions centered around spatio-temporal event logs may include all kinds of movements, such as customers in shops highlighting 'Hot and Cold areas' or tracking of material and goods in a production plant. For this paper, we choose a specific challenge for retail companies, which is to find out if customers are alone or visit the shop together with family or friends. Therefore, the algorithm is tested using positioning-data of a retail shop from the fashion industry. Our results highlight the benefits of location-based process mining by showing its applicability in real scenarios.