Melanie Siebenhofer

Melanie Siebenhofer

Auto-generated profile, based on publicly available information

Melanie Siebenhofer

Alpen-Adria-Universität Klagenfurt, Klagenfurt, Austria

Research Focus & Metrics

Academic Career Length

11Years (2016-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
30 June 2022 in ACM Transactions on Mathematical Software
Verified
Journal Article
Open access
NGNicolò Gusmeroli
Nicolò Gusmeroli
THTimotej Hrga
Timotej Hrga
BLBorut Lužar
Borut Lužar
Janez PovhJanez Povh
Janez Povh
MSMelanie Siebenhofer
Melanie Siebenhofer
AWAngelika Wiegele
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.

12 March 2022 in Mathematical Methods of Operations Research
Verified
Journal Article
Open access
PDF file
EGElisabeth Gaar
Elisabeth Gaar
MSMelanie Siebenhofer
Melanie Siebenhofer
AWAngelika Wiegele
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.

10 October 2016
Verified
Conference Paper
Closed access
PBPeter Matthew De Blank
Peter Matthew De Blank
MMMichael Maurer
Michael Maurer
MSMelanie Siebenhofer
Melanie Siebenhofer
ARAndreas Rogge-Solti
Andreas Rogge-Solti
SSStefan Schönig
Stefan Schönig
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.

5 November 2025 in European Journal of Operational Research
Verified
Journal Article
Open access
FMFrank de Meijer
Frank de Meijer
MSMelanie Siebenhofer
Melanie Siebenhofer
RSRenata Sotirov
Renata Sotirov
AWAngelika Wiegele
Angelika Wiegele

22 May 2024
Verified
Book Chapter
Open access
PDF file
AGAkshay Gupte
Akshay Gupte
MSMelanie Siebenhofer
Melanie Siebenhofer
AWAngelika Wiegele
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.

13 January 2026 in Mathematical Programming Computation
Verified
Journal Article
Open access
PDF file
AGAkshay Gupte
Akshay Gupte
MSMelanie Siebenhofer
Melanie Siebenhofer
AWAngelika Wiegele
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.