Carlos Mencía

This paper addresses the tasks of explaining and correcting infeasible one machine sequencing problems with a limit on the makespan. Concretely, the paper studies the computation of high-level explanations and corrections, which are given in terms of irreducible subsets of the set of jobs. To achieve these goals, the paper shows that both tasks can be reduced to the general framework of computing a minimal set over a monotone predicate (MSMP). The reductions enable the use of any general-purpose algorithm for solving MSMP, and three well-known approaches are instantiated for the two tasks. Furthermore, the paper details efficient scheduling techniques aimed at enhancing the performance of the proposed algorithms. The experimental results confirm that the proposed approaches are efficient in practice, and that the scheduling optimizations enable critical performance gains.

This paper addresses the problem of scheduling a set of jobs on a machine with time-varying capacity, with the goal of minimizing the total tardiness objective function. This problem arose in the context scheduling the charging times of a fleet of electric vehicles and it is NP-hard. Recent work proposed an efficient memetic algorithm for solving the problem, combining a genetic algorithm and a local search method. The local search procedure is based on swapping consecutive jobs on a C-path, defined as a sequence of consecutive jobs in a schedule. Building on it, this paper develops new memetic algorithms that stem from new local search procedures also proposed in this paper. The local search methods integrate several mechanisms to make them more effective, including a new condition for swapping pairs of jobs, a hill climbing approach, a procedure that operates on several C-paths and a method that interchanges jobs between different C-paths. As a result, the new local search methods enable the memetic algorithms to reach higher-quality solutions. Experimental results show significant improvements over existing approaches.

The analysis of inconsistent formulas finds an ever-increasing range of applications, that include axiom pinpointing in description logics, fault localization in software, model-based diagnosis, optimization problems, but also explainability of machine learning models. This paper overviews approaches for analyzing inconsistent formulas, focusing on finding and enumerating explanations of and corrections for inconsistency, but also on solving optimization problems modeled as inconsistent formulas.

The last decade has witnessed remarkable improvements in the analysis of inconsistent formulas, namely in the case of Boolean Satisfiability (SAT) formulas. However, these successes have been restricted to monotonic logics. Recent work proposed the notion of strong inconsistency for a number of non-monotonic logics, including Answer Set Programming (ASP). This paper shows how algorithms for reasoning about inconsistency in monotonic logics can be extended to the case of ASP programs, in the concrete case of strong inconsistency. Initial experimental results illustrate the potential of the proposed approach.