Author name cluster

Nysret Musliu

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

28 papers

2 author rows

JAIR Journal 2026 Journal Article

Integrating Column Generation and Large Neighborhood Search for Bus Driver Scheduling with Complex Break Constraints

Lucas Kletzander
Tommaso Mannelli Mazzoli
Nysret Musliu
Pascal Van Hentenryck

Background: The Bus Driver Scheduling Problem (BDSP) is a combinatorial optimization problem with the goal to design shifts to cover prearranged bus tours. The objective takes into account the operational cost as well as the satisfaction of drivers. This problem is heavily constrained due to strict legal rules and collective agreements. Objectives: The objective of this article is to provide state-of-the-art exact and hybrid solution methods that can provide high-quality solutions for instances of different sizes. Methods: This work presents a comprehensive study of both an exact method, Branch and Price (B&P), as well as a Large Neighborhood Search (LNS) framework which uses B&P or Column Generation (CG) for the repair phase to solve the BDSP. It further proposes and evaluates a novel deeper integration of B&P and LNS, storing the generated columns from the LNS subproblems and reusing them for other subproblems, or to find better global solutions. Results: The article presents a detailed analysis of several components of the solution methods and their impact, including general improvements for the B&P subproblem, which is a high-dimensional Resource Constrained Shortest Path Problem (RCSPP), and the components of the LNS. The evaluation shows that our approach provides new state-of-the-art results for instances of all sizes, including exact solutions for small instances, and low gaps to a known lower bound for mid-sized instances. Conclusions: We observe that B&P provides the best results for small instances, while the tight integration of LNS and CG can provide high-quality solutions for larger instances, further improving over LNS which just uses CG as a black box. The proposed methods are general and can also be applied to other rule sets and related optimization problems.

PDF Details DOI

AIJ Journal 2024 Journal Article

Adaptive large-neighbourhood search for optimisation in answer-set programming

Thomas Eiter
Tobias Geibinger
Nelson Higuera Ruiz
Nysret Musliu
Johannes Oetsch
Dave Pfliegler
Daria Stepanova

Answer-set programming (ASP) is a prominent approach to declarative problem solving that is increasingly used to tackle challenging optimisation problems. We present an approach to leverage ASP optimisation by using large-neighbourhood search (LNS), which is a meta-heuristic where parts of a solution are iteratively destroyed and reconstructed in an attempt to improve an overall objective. In our LNS framework, neighbourhoods can be specified either declaratively as part of the ASP encoding or automatically generated by code. Furthermore, our framework is self-adaptive, i. e. , it also incorporates portfolios for the LNS operators along with selection strategies to adjust search parameters on the fly. The implementation of our framework, the system ALASPO, currently supports the ASP solver clingo, as well as its extensions clingo-dl and clingcon that allow for difference and full integer constraints, respectively. It utilises multi-shot solving to efficiently realise the LNS loop and in this way avoids program regrounding. We describe our LNS framework for ASP as well as its implementation, discuss methodological aspects, and demonstrate the effectiveness of the adaptive LNS approach for ASP on different optimisation benchmarks, some of which are notoriously difficult, as well as real-world applications for shift planning, configuration of railway-safety systems, parallel machine scheduling, and test laboratory scheduling.

Details DOI

AIJ Journal 2024 Journal Article

Hyper-heuristics for personnel scheduling domains

Lucas Kletzander
Nysret Musliu

In real-life applications problems can frequently change or require small adaptations. Manually creating and tuning algorithms for different problem domains or different versions of a problem can be cumbersome and time-consuming. In this paper we consider several important problems with high practical relevance, which are Rotating Workforce Scheduling, Minimum Shift Design, and Bus Driver Scheduling. Instead of designing very specific solution methods, we propose to use the more general approach based on hyper-heuristics which take a set of simpler low-level heuristics and combine them to automatically create a fitting heuristic for the problem at hand. This paper presents a major study on applying hyper-heuristics to these domains, which contributes in four different ways: First, it defines new low-level heuristics for these scheduling domains, allowing to apply hyper-heuristics to them for the first time. Second, it provides a comparison of several state-of-the-art hyper-heuristics on those domains. Third, new best solutions for several instances of the different problem domains are found. Finally, a detailed investigation of the use of low-level heuristics by the hyper-heuristics gives insights in the way hyper-heuristics apply to different domains and the importance of different low-level heuristics. The results show that hyper-heuristics are able to perform well even on very complex practical problem domains in the area of scheduling and, while being more general and requiring less problem-specific adaptation, can in several cases compete with specialized algorithms for the specific problems. Several hyper-heuristics with very good performance across different real-life domains are identified. They can efficiently select low-level heuristics to apply for each domain, but for repeated application they benefit from evaluating and selecting the most useful subset of these heuristics. These results help to improve industrial systems in use for solving different scheduling scenarios by allowing faster and easier adaptation to new problem variants.

Details DOI

ICAPS Conference 2024 Conference Paper

Investigating Large Neighbourhood Search for Bus Driver Scheduling

Tommaso Mannelli Mazzoli
Lucas Kletzander
Pascal Van Hentenryck
Nysret Musliu

The Bus Driver Scheduling Problem (BDSP) is a combinatorial optimisation problem with high practical relevance. The aim is to assign bus drivers to predetermined routes while minimising a specified objective function that considers operating costs as well as employee satisfaction. Since we must satisfy several rules from a collective agreement and European regulations, the BDSP is highly constrained. Hence, using exact methods to solve large real-life-based instances is computationally too expensive, while heuristic methods still have a considerable gap to the optimum. Our paper presents a Large Neighbourhood Search (LNS) approach to solve the BDSP. We propose several novel destroy operators and an approach using column generation to repair the sub-problem. We analyse the impact of the destroy and repair operators and investigate various possibilities to select them, including adaptivity. The proposed approach improves all the upper bounds for larger instances that exact methods cannot solve, as well as for some mid-sized instances, and outperforms existing heuristic approaches for this problem on all benchmark instances.

Details

ICAPS Conference 2024 Conference Paper

Preference Explanation and Decision Support for Multi-Objective Real-World Test Laboratory Scheduling

Florian Mischek
Nysret Musliu

Complex real-world scheduling problems often include multiple conflicting objectives. Decision makers (DMs) can express their preferences over those objectives in different ways, including as sets of weights which are used in a linear combination of objective values. However, finding good sets of weights that result in solutions with desirable qualities is challenging and currently involves a lot of trial and error. We propose a general method to explain objectives

Details

TIST Journal 2023 Journal Article

A System for Automated Industrial Test Laboratory Scheduling

Philipp Danzinger
Tobias Geibinger
David Janneau
Florian Mischek
Nysret Musliu
Christian Poschalko

Automated scheduling solutions are tremendously important for the efficient operation of industrial laboratories. The Test Laboratory Scheduling Problem (TLSP) is an extension of the well-known Resource Constrained Project Scheduling Problem (RCPSP) and captures the specific requirements of such laboratories. In addition to several new scheduling constraints, it features a grouping phase, where the jobs to be scheduled are assembled from smaller units. In this work, we introduce an innovative scheduling system that allows the efficient and flexible generation of schedules for TLSP. It features a new Constraint Programming model that covers both the grouping and the scheduling aspect, as well as a hybrid Very Large Neighborhood Search that internally uses the CP model. Our experimental results on generated and real-world benchmark instances show that good results can be obtained even compared to settings which have a good grouping already provided, including several new best known solutions for these instances. Our algorithms for TLSP have been successfully implemented in a real-world industrial test laboratory. We provide a detailed description of the deployed system as well as additional useful soft constraints supported by the solvers and general lessons learned. This includes a discussion of the choice of soft constraint weights, with an analysis on the impact and relation of different objectives to each other. Our experiments show that some soft constraints complement each other well, while others require explicit trade-offs via their relative weights.

Details DOI

ICAPS Conference 2023 Conference Paper

Dynamic Weight Setting for Personnel Scheduling with Many Objectives

Lucas Kletzander
Nysret Musliu

When large sets of constraints and objectives are combined in a practical optimization problem, managing all these potentially conflicting goals can become very difficult and might require to solve an instance multiple times. First, an instance might be infeasible with the current constraints, in which case our system introduces a novel violation score to help identify the constraints that need to be relaxed for the next run. Second, multiple objectives are often combined using a linear combination with hand-crafted weights, which are very difficult to set such that the result matches the expectations regarding the balance between individual objectives. Instead, the user can tell our system particular thresholds for the expected changes in objectives, e. g. , to reduce objective 1 by 10 % while not increasing objective 2 by more than 5 %. Dynamic weight setting automatically adapts the weights to reach these thresholds or uses the violation scores to explain reasons for not reaching thresholds. It can not only be used for soft constraints, but also to determine weights when hard constraints are internally represented as soft constraints in meta-heuristics. While the methodology is general, we have implemented it in the context of a personnel scheduling framework of our industry partner and present a detailed evaluation on the domain of Bus Driver Scheduling, where its benefits can be seen in multiple scenarios.

Details

AAAI Conference 2023 Conference Paper

Large-State Reinforcement Learning for Hyper-Heuristics

Lucas Kletzander
Nysret Musliu

Hyper-heuristics are a domain-independent problem solving approach where the main task is to select effective chains of problem-specific low-level heuristics on the fly for an unseen instance. This task can be seen as a reinforcement learning problem, however, the information available to the hyper-heuristic is very limited, usually leading to very limited state representations. In this work, for the first time we use the trajectory of solution changes for a larger set of features for reinforcement learning in the novel hyper-heuristic LAST-RL (Large-State Reinforcement Learning). Further, we introduce a probability distribution for the exploration case in our epsilon-greedy policy that is based on the idea of Iterated Local Search to increase the chance to sample good chains of low-level heuristics. The benefit of the collaboration of our novel components is shown on the academic benchmark of the Cross Domain Heuristic Challenge 2011 consisting of six different problem domains. Our approach can provide state-of-the-art results on this benchmark where it outperforms recent hyper-heuristics based on reinforcement learning, and also demonstrates high performance on a benchmark of complex real-life personnel scheduling domains.

PDF Details DOI

KR Conference 2022 System Paper

ALASPO: An Adaptive Large-Neighbourhood ASP Optimiser

Thomas Eiter
Tobias Geibinger
Nelson Higuera
Nysret Musliu
Johannes Oetsch
Daria Stepanova

We present the system ALASPO which implements Adaptive Large-neighbourhood search for Answer Set Programming (ASP) Optimisation. Large-neighbourhood search (LNS) is a meta-heuristic where parts of a solution are destroyed and reconstructed in an attempt to improve an overall objective. ALASPO currently supports the ASP solver clingo, as well as its extensions clingo-dl and clingcon for difference and full integer constraints, and multi-shot solving for an efficient implementation of the LNS loop. Neighbourhoods can be defined in code or declaratively as part of the ASP encoding. While the method underlying ALASPO has been described in previous work, ALASPO also incorporates portfolios for the LNS operators along with self-adaptive selection strategies as a technical novelty. This improves usability considerably at no loss of solution quality, but on the contrary often yields benefits. To demonstrate this, we evaluate ALASPO on different optimisation benchmarks.

PDF Details DOI

ICAPS Conference 2022 Conference Paper

Hyper-Heuristics for Personnel Scheduling Domains

Lucas Kletzander
Nysret Musliu

In real-life applications problems can frequently change or require small adaptations. Manually creating and tuning algorithms for different problem domains or different versions of a problem can be cumbersome and time-consuming. In this paper we consider several important problems with high practical relevance, which are Bus Driver Scheduling, Rotating Workforce Scheduling, and Minimum Shift Design. Instead of designing very specific solution methods, we propose to use the more general approach based on hyper-heuristics which take a set of simpler low-level heuristics and combine them to automatically create a fitting heuristic for the problem at hand. This paper presents a major study on applying hyper-heuristics to these domains, which contributes in three different ways: First, it defines new low-level heuristics for these scheduling domains, allowing to apply hyper-heuristics to them for the first time. Second, it provides a comparison of several state-of-the-art hyper-heuristics on those domains. Third, new best solutions for several instances of the different problem domains are found. These results show that hyper-heuristics are able to perform well even on very complex practical problem domains in the area of scheduling and, while being more general and requiring less problem-specific adaptation, can in several cases compete with specialized algorithms for the specific problems. These results help to improve industrial systems in use for solving different scheduling scenarios by allowing faster and easier adaptation to new problem variants.

Details

AAAI Conference 2022 Conference Paper

Large-Neighbourhood Search for Optimisation in Answer-Set Solving

Thomas Eiter
Tobias Geibinger
Nelson Higuera Ruiz
Nysret Musliu
Johannes Oetsch
Daria Stepanova

While Answer-Set Programming (ASP) is a prominent approach to declarative problem solving, optimisation problems can still be a challenge for it. Large-Neighbourhood Search (LNS) is a metaheuristic for optimisation where parts of a solution are alternately destroyed and reconstructed that has high but untapped potential for ASP solving. We present a framework for LNS optimisation in answer-set solving in which neighbourhoods can be specified either declaratively as part of the ASP encoding or automatically generated by code. To effectively explore different neighbourhoods, we focus on multi-shot solving as it allows to avoid program regrounding. We illustrate the framework on different optimisation problems some of which are notoriously difficult, including shift planning and a parallel machine scheduling problem from semi-conductor production, which demonstrate the effectiveness of the LNS approach.

PDF Details

IJCAI Conference 2022 Conference Paper

Reinforcement Learning for Cross-Domain Hyper-Heuristics

Florian Mischek
Nysret Musliu

In this paper, we propose a new hyper-heuristic approach that uses reinforcement learning to automatically learn the selection of low-level heuristics across a wide range of problem domains. We provide a detailed analysis and evaluation of the algorithm components, including different ways to represent the hyper-heuristic state space and reset strategies to avoid unpromising areas of the solution space. Our methods have been evaluated using HyFlex, a well-known benchmarking framework for cross-domain hyper-heuristics, and compared with state-of-the-art approaches. The experimental evaluation shows that our reinforcement-learning based approach produces results that are competitive with the state-of-the-art, including the top participants of the Cross Domain Hyper-heuristic Search Competition 2011.

PDF Details DOI

KR Conference 2021 Conference Paper

Answer-Set Programming for Lexicographical Makespan Optimisation in Parallel Machine Scheduling

Thomas Eiter
Tobias Geibinger
Nysret Musliu
Johannes Oetsch
Peter Skočovský
Daria Stepanova

We deal with a challenging scheduling problem on parallel-machines with sequence-dependent setup times and release dates from a real-world application of semiconductor work-shop production. There, jobs can only be processed by dedicated machines, thus few machines can determine the makespan almost regardless of how jobs are scheduled on the remaining ones. This causes problems when machines fail and jobs need to be rescheduled. Instead of optimising only the makespan, we put the individual machine spans in non-ascending order and lexicographically minimise the resulting tuples. This achieves that all machines complete as early as possible and increases the robustness of the schedule. We study the application of Answer-Set Programming (ASP) to solve this problem. While ASP eases modelling, the combination of timing constraints and the considered objective function challenges current solving technology. The former issue is addressed by using an extension of ASP by difference logic. For the latter, we devise different algorithms that use multi-shot solving. To tackle industrial-sized instances, we study different approximations and heuristics. Our experimental results show that ASP is indeed a promising KRR paradigm for this problem and is competitive with state-of-the-art CP and MIP solvers.

PDF Details DOI

ICAPS Conference 2021 Conference Paper

Automated Production Scheduling for Artificial Teeth Manufacturing

Felix Winter
Christoph Mrkvicka
Nysret Musliu
Jakob Preininger

In industrial artificial teeth manufacturing, nowadays a high level of automation is utilized to produce a large quantity of teeth in short production cycles. As a large variety of different product shapes and colors have to be processed on a single machine, the creation of efficient production schedules becomes a very challenging task. Due to the complexity of the problem and several cost minimization objectives that need to be considered, there usually is a large potential to improve the currently manually created schedules with automated solution methods. In this paper, we formally specify and solve a novel challenging real-life machine batch scheduling problem from the area of artificial teeth manufacturing. Additionally, we provide a collection of real-life benchmark instances that can be used to evaluate solution methods for the problem. To efficiently solve the problem, we propose an innovative construction heuristic and metaheuristic approach as well as an exact method using constraint programming. An extensive experimental evaluation shows that exact techniques can efficiently solve small scheduling scenarios and can provide optimal solutions for four instances. Furthermore, we show that the proposed metaheuristic approach is able to reach optimal results for small instances and can find high quality solutions also for large real-life benchmark instances.

Details

AAAI Conference 2021 Conference Paper

Branch and Price for Bus Driver Scheduling with Complex Break Constraints

Lucas Kletzander
Nysret Musliu
Pascal Van Hentenryck

This paper presents a Branch and Price approach for a reallife Bus Driver Scheduling problem with a complex set of break constraints. The column generation uses a set partitioning model as master problem and a resource constrained shortest path problem as subproblem. Due to the complex constraints, the branch and price algorithm adopts several novel ideas to improve the column generation in the presence of a high-dimensional subproblem, including exponential arc throttling and a dedicated two-stage dominance algorithm. Evaluation on a publicly available set of benchmark instances shows that the approach provides the first provably optimal solutions for small instances, improving best-known solutions or proving them optimal for 48 out of 50 instances, and yielding an optimality gap of less than 1% for more than half the instances.

PDF Details

AAAI Conference 2021 Conference Paper

Constraint Logic Programming for Real-World Test Laboratory Scheduling

Tobias Geibinger
Florian Mischek
Nysret Musliu

The Test Laboratory Scheduling Problem (TLSP) and its subproblem TLSP-S are real-world industrial scheduling problems that are extensions of the Resource-Constrained Project Scheduling Problem (RCPSP). Besides several additional constraints, TLSP includes a grouping phase where the jobs to be scheduled have to be assembled from smaller tasks and derive their properties from this grouping. For TLSP-S such a grouping is already part of the input. In this work, we show how TLSP-S can be solved by Answerset Programming extended with ideas from other constraint solving paradigms. We propose a novel and efficient encoding and apply an answer-set solver for constraint logic programs called clingcon. Additionally, we utilize our encoding in a Very Large Neighborhood Search framework and compare our methods with the state of the art approaches. Our approach provides new upper bounds and optimality proofs for several existing benchmark instances in the literature.

PDF Details

TIST Journal 2021 Journal Article

Constraint-based Scheduling for Paint Shops in the Automotive Supply Industry

Felix Winter
Nysret Musliu

Factories in the automotive supply industry paint a large number of items requested by car manufacturing companies on a daily basis. As these factories face numerous constraints and optimization objectives, finding a good schedule becomes a challenging task in practice, and full-time employees are expected to manually create feasible production plans. In this study, we propose novel constraint programming models for a real-life paint shop scheduling problem. We evaluate and compare our models experimentally by performing a series of benchmark experiments using real-life instances in the industry. We also show that the decision variant of the paint shop scheduling problem is NP-complete.

Details DOI

AAAI Conference 2020 Conference Paper

Explaining Propagators for String Edit Distance Constraints

Felix Winter
Nysret Musliu
Peter Stuckey

The computation of string similarity measures has been thoroughly studied in the scientiﬁc literature and has applications in a wide variety of different areas. One of the most widely used measures is the so called string edit distance which captures the number of required edit operations to transform a string into another given string. Although polynomial time algorithms are known for calculating the edit distance between two strings, there also exist NP-hard problems from practical applications like scheduling or computational biology that constrain the minimum edit distance between arrays of decision variables. In this work, we propose a novel global constraint to formulate restrictions on the minimum edit distance for such problems. Furthermore, we describe a propagation algorithm and investigate an explanation strategy for an edit distance constraint propagator that can be incorporated into state of the art lazy clause generation solvers. Experimental results show that the proposed propagator is able to significantly improve the performance of existing exact methods regarding solution quality and computation speed for benchmark problems from the literature.

PDF Details

ICAPS Conference 2020 Conference Paper

Solving Large Real-Life Bus Driver Scheduling Problems with Complex Break Constraints

Lucas Kletzander
Nysret Musliu

When scheduling drivers for public transport, in addition to covering the demand and dealing with the spatial dimension, a range of legal requirements, collective agreements and company policies need to be respected. The level of concentration required while driving leads to strict rules for break assignments. This results in a complex problem where creating cost-efficient and employee-friendly schedules is challenging. This paper deals with bus driver scheduling using the rules of the Austrian collective agreement for private omnibus providers. The contributions are the formalization of the complex Austrian rules for bus drivers, a new set of publicly available instances based on the characteristics of real-life instances, and a metaheuristic solution approach for the problem. The algorithm was able to significantly improve the solutions of real-life instances and is evaluated on the generated instances. Further we provide insight in the necessity of objectives for employee satisfaction and their effects. Our method can even be successfully applied to improve results on a problem with very different constraints from Brasil.

Details

ICAPS Conference 2020 Conference Paper

Solving the Test Laboratory Scheduling Problem with Variable Task Grouping

Philipp Danzinger
Tobias Geibinger
Florian Mischek
Nysret Musliu

The Test Laboratory Scheduling Problem (TLSP) is an extension of the Resource-Constrained Project Scheduling Problem (RCPSP). Besides several additional constraints, it includes a grouping phase where the jobs to be scheduled have to be assembled from smaller tasks and derive their properties from this grouping. Previous solution approaches for TLSP have focused primarily on the scheduling subproblem (TLSP-S), for which it is assumed that a suitable grouping is already given as part of the input. In this paper, we provide for the first time a solution approach that encompasses the full problem including grouping. We propose both a Constraint Programming model for TLSP and a Very Large Neighborhood Search algorithm based on that model. Furthermore, we apply our algorithms to real-world instances as well as randomly generated ones and compare our results to the best existing solutions. Experimental results show that our solution methods consistently outperform those for TLSP-S when both are initialised with a good grouping and in many cases even when this grouping is provided only to the latter.

Details

ICAPS Conference 2019 Conference Paper

Exact Methods for Extended Rotating Workforce Scheduling Problems

Lucas Kletzander
Nysret Musliu
Johannes Gärtner
Thomas Krennwallner
Werner Schafhauser

In many professions daily demand for different shifts varies during the week. The rotating workforce scheduling problem deals with the creation of repeating schedules for such demand and is therefore of high practical relevance. This paper investigates solving this real-life problem with several new practically relevant features. This includes early recognition of certain infeasibility criteria, complex rest time constraints regarding weekly rest time, and optimization goals to deal with optimal assignments of free weekends. We introduce a state-of-the-art constraint model and evaluate it with different extensions. The evaluation shows that many real-life instances can be solved to optimality using a constraint solver. Our approach is under deployment in a state-of-the-art commercial solver for rotating workforce scheduling.

Details

ICAPS Conference 2019 Conference Paper

Solution Approaches for an Automotive Paint Shop Scheduling Problem

Felix Winter
Nysret Musliu
Emir Demirovic
Christoph Mrkvicka

In the paint shops of the automotive supply industry, a large number of synthetic material pieces need to be painted every day to provide the large variety of items required for car manufacturing. Because of the sophisticated automated production process and the tight due dates requested by car manufacturers, finding an optimized production schedule becomes a challenging task that is at the present time performed by multiple human planners. In this paper, we formulate and solve a novel real-life paint shop scheduling problem from the automotive supply industry which introduces unique constraints and objectives that do not appear in the existing literature. Additionally, we provide a new collection of benchmark instances based on real-life planning scenarios that can be used to evaluate solution techniques for the problem. An exact approach based on constraint programming is able to provide optimal solutions for smaller instances, but many larger instances could not be solved yet. Therefore, we propose a metaheuristic method based on local search that uses novel neighborhood relations and various ways to escape local optima. Our approach is able to provide feasible solutions for all instances within reasonable running time.

Details

JAIR Journal 2019 Journal Article

Solving the Torpedo Scheduling Problem

Martin Josef Geiger
Lucas Kletzander
Nysret Musliu

The article presents a solution approach for the Torpedo Scheduling Problem, an operational planning problem found in steel production. The problem consists of the integrated scheduling and routing of torpedo cars, i. e. steel transporting vehicles, from a blast furnace to steel converters. In the continuous metallurgic transformation of iron into steel, the discrete transportation step of molten iron must be planned with considerable care in order to ensure a continuous material flow. The problem is solved by a Simulated Annealing algorithm, coupled with an approach of reducing the set of feasible material assignments. The latter is based on logical reductions and lower bound calculations on the number of torpedo cars. Experimental investigations are performed on a larger number of problem instances, which stem from the 2016 implementation challenge of the Association of Constraint Programming (ACP). Our approach was ranked first (joint first place) in the 2016 ACP challenge and found optimal solutions for all used instances in this challenge.

PDF Details DOI

IS Journal 2017 Journal Article

A Hybrid Approach for the Sudoku Problem: Using Constraint Programming in Iterated Local Search

Nysret Musliu
Felix Winter

Sudoku is not only a popular puzzle but also an interesting and challenging constraint satisfaction problem. Therefore, automatic solving methods have been the subject of several publications in the past two decades. Although current methods provide good solutions for small-sized puzzles, larger instances remain challenging. This article introduces a new local search technique based on the min-conflicts heuristic for Sudoku. Furthermore, the authors propose an innovative hybrid search technique that exploits constraint programming as a perturbation technique within the iterated local search framework. They experimentally evaluate their methods on challenging benchmarks for Sudoku and report improvements over state-of-the-art solutions. To show the generalizability of the proposed approach, they also applied their method on another challenging scheduling problem. The results show that the proposed method is also robust in another problem domain.

Details DOI

JAIR Journal 2017 Journal Article

Improving the Efficiency of Dynamic Programming on Tree Decompositions via Machine Learning

Michael Abseher
Nysret Musliu
Stefan Woltran

Dynamic Programming (DP) over tree decompositions is a well-established method to solve problems - that are in general NP-hard - efficiently for instances of small treewidth. Experience shows that (i) heuristically computing a tree decomposition has negligible runtime compared to the DP step; and (ii) DP algorithms exhibit a high variance in runtime when using different tree decompositions; in fact, given an instance of the problem at hand, even decompositions of the same width might yield extremely diverging runtimes. We thus propose here a novel and general method that is based on selection of the best decomposition from an available pool of heuristically generated ones. For this purpose, we require machine learning techniques that provide automated selection based on features of the decomposition rather than on the actual problem instance. Thus, one main contribution of this work is to propose novel features for tree decompositions. Moreover, we report on extensive experiments in different problem domains which show a significant speedup when choosing the tree decomposition according to this concept over simply using an arbitrary one of the same width.

PDF Details DOI

IJCAI Conference 2017 Conference Paper

Personnel Scheduling as Satisfiability Modulo Theories

Christoph Erkinger
Nysret Musliu

Rotating workforce scheduling (RWS) is an important real-life personnel rostering problem that appears in a large number of different business areas. In this paper, we propose a new exact approach to RWS that exploits the recent advances on Satisfiability Modulo Theories (SMT). While solving can be automated by using a number of so-called SMT-solvers, the most challenging task is to find an efficient formulation of the problem in first-order logic. We propose two new modeling techniques for RWS that encode the problem using formulas over different background theories. The first encoding provides an elegant approach based on linear integer arithmetic. Furthermore, we developed a new formulation based on bitvectors in order to achieve a more compact representation of the constraints and a reduced number of variables. These two modeling approaches were experimentally evaluated on benchmark instances from literature using different state-of-the-art SMT-solvers. Compared to other exact methods, the results of this approach showed an important improvement in the number of found solutions.

PDF Details

IJCAI Conference 2015 Conference Paper

Improving the Efficiency of Dynamic Programming on Tree Decompositions via Machine Learning

Michael Abseher
Frederico Dusberger
Nysret Musliu
Stefan Woltran

Dynamic Programming (DP) over tree decompositions is a well-established method to solve problems – that are in general NP-hard – efficiently for instances of small treewidth. Experience shows that (i) heuristically computing a tree decomposition has negligible runtime compared to the DP step; (ii) DP algorithms exhibit a high variance in runtime when using different tree decompositions; in fact, given an instance of the problem at hand, even decompositions of the same width might yield extremely diverging runtimes. We thus propose here a novel and general method that is based on a selection of the best decomposition from an available pool of heuristically generated ones. For this purpose, we require machine learning techniques based on features of the decomposition rather than on the actual problem instance. We report on extensive experiments in different problem domains which show a significant speedup when choosing the tree decomposition according to this concept over simply using an arbitrary one of the same width.

PDF Details

IS Journal 2010 Journal Article

An AI-Based Break-Scheduling System for Supervisory Personnel

Andreas Beer
Johannes Gartner
Nysret Musliu
Werner Schafhauser
Wolfgang Slany

Designing shift plans represents a difficult but interesting task because they must satisfy various, often conflicting, requirements. In this article, we address a complex real-world break-scheduling problem for supervisory personnel and present a scheduling system that can help professional planners create high-quality shift plans. Supervisory personnel spend most of their workday in front of computer monitors, addressing critical and constantly changing situations. For employees working under such conditions to always maintain high levels of concentration, it's essential that they take occasional breaks. Usually, the amount of break time, as well as the position and duration of breaks within their work time (shift) are regulated by labor rules that must be satisfied by a feasible shift plan. Moreover, to guarantee effective supervision, a minimum number of employees must be working at any given time.

Details DOI