Fundamenta Informaticae - Volume 167, issue 1-2

Authors: Maratea, Marco | Serina, Ivan | Torroni, Paolo

Article Type: Other

DOI: 10.3233/FI-2019-1807

Citation: Fundamenta Informaticae, vol. 167, no. 1-2, pp. v-vii, 2019

Authors: Alviano, Mario

Article Type: Research Article

Abstract: The fundamental mechanism that humans use in argumentation can be formalized in abstract argumentation frameworks. Many semantics are associated with abstract argumentation frameworks, each one consisting of a set of extensions, that is, a set of sets of arguments. Some of these semantics are based on preference relations that essentially impose to maximize or minimize some property. This paper presents the argumentation reasoner PYGLAF , which provides a uniform view of many semantics for abstract argumentation frameworks in terms of circumscription. Specifically, several computational problems of abstract argumentation frameworks are reduced to circumscription by means of linear encodings, and a …few others are solved by means of a sequence of calls to an oracle for circumscription. Finally, grounded extensions are obtained in polynomial time by unit propagation, and acceptance problems are addressed by first checking cardinality optimal models of circumscribed theories, so that the naive extension enumeration is possibly avoided. Show more

Keywords: abstract argumentation frameworks, propositional circumscription, minimal model enumeration, incremental solving

DOI: 10.3233/FI-2019-1808

Citation: Fundamenta Informaticae, vol. 167, no. 1-2, pp. 1-30, 2019

Authors: Alviano, Mario | Dodaro, Carmine

Article Type: Research Article

Abstract: Modern, efficient Answer Set Programming solvers implement answer set search via non-chronological backtracking algorithms. The extension of these algorithms to answer set enumeration is nontrivial. In fact, adding blocking constraints to discard already computed answer sets is inadequate because the introduced constraints may not fit in memory or deteriorate the efficiency of the solver. On the other hand, the algorithm implemented by CLASP , which can run in polynomial space, requires to modify the answer set search procedure. The algorithm is revised in this paper so as to make it almost independent from the underlying answer set search procedure, provided …that the procedure accepts as input a logic program and a list of assumption literals, and returns an answer set (and associated branching literals). In fact, thanks to an alternative view in terms of transition systems, the revised algorithm is suitable to easily accommodate the enumerate of models of other Boolean languages, among them classical models of propositional theories. On a pragmatic level, the paper presents two implementations of the enumeration algorithm, in WASP for answer set enumeration, and in GLUCOSE for classical models enumeration. The implemented systems are compared empirically to the state of the art solver CLASP . Show more

Keywords: Answer Set Programming, Enumeration, Assumption Literals

DOI: 10.3233/FI-2019-1809

Citation: Fundamenta Informaticae, vol. 167, no. 1-2, pp. 31-58, 2019

Authors: Charwat, Günther | Woltran, Stefan

Article Type: Research Article

Abstract: In recent years various approaches for quantified Boolean formula (QBF) solving have been developed, including methods based on expansion, skolemization and search. Here, we present a novel expansion-based solving technique that is motivated by concepts from the area of parameterized complexity. Our approach relies on dynamic programming over the tree decomposition of QBFs in prenex conjunctive normal form (PCNF). Hereby, binary decision diagrams (BDDs) are used for compactly storing partial solutions. Towards efficiency in practice, we integrate dependency schemes and develop dedicated heuristic strategies. Our experimental evaluation reveals that our implementation is competitive to state-of-the-art solvers on instances with …one quantifier alternation. Furthermore, it performs particularly well on instances up to a treewidth of approximately 80, even for more quantifier alternations. Results indicate that our approach is orthogonal to existing techniques, with a large number of uniquely solved instances. Show more

Keywords: QBF, expansion, dynamic programming, QSAT, treewidth

DOI: 10.3233/FI-2019-1810

Citation: Fundamenta Informaticae, vol. 167, no. 1-2, pp. 59-92, 2019

Authors: González, Miguel A. | Oddi, Angelo | Rasconi, Riccardo

Article Type: Research Article

Abstract: One of the most recent and interesting trends in intelligent scheduling is trying to reduce the energy consumption in order to obtain lower production costs and smaller carbon footprint. In this work we consider the energy-aware job shop scheduling problem, where we have to minimize at the same time an efficiency-based objective, as is the total weighted tardiness, and also the overall energy consumption. We experimentally show that we can reduce the energy consumption of a given schedule by delaying some operations, and to this end we design a heuristic procedure to improve a given schedule. As the problem is …computationally complex, we design three approaches to solve it: a Pareto-based multiobjective evolutionary algorithm, which is hybridized with a multiobjective local search method and a linear programming step, a decomposition-based multiobjective evolutionary algorithm hybridized with a single-objective local search method, and finally a constraint programming approach. We perform an extensive experimental study to analyze our algorithms and to compare them with the state of the art. Show more

Keywords: Multiobjective optimization, job shop, energy, metaheuristics

DOI: 10.3233/FI-2019-1811

Citation: Fundamenta Informaticae, vol. 167, no. 1-2, pp. 93-132, 2019

Authors: Santucci, Valentino | Baioletti, Marco | Milani, Alfredo

Article Type: Research Article

Abstract: Particle Swarm Optimization (PSO), though originally introduced for continuous search spaces, has been increasingly applied to combinatorial optimization problems. In this paper, we focus on the PSO applications to permutation-based problems. As far as we know, the most popular and general PSO schemes for permutation solutions are those based on random key techniques. After highlighting the main criticalities of the random key approach, we introduce a discrete PSO variant for permutation-based optimization problems. By simulating search moves through a vector space, the proposed algorithm, Algebraic PSO (APSO), allows the original PSO design to be applied to the permutation search space. …APSO directly represents both particle positions and velocities as permutations. The APSO search scheme is based on a general algebraic framework for combinatorial optimization based on strong mathematical foundations. However, in order to make this new scheme viable, some challenges have to be overcome: the choice of the order of the velocity terms, and the rationale behind the PSO inertial move. Design solutions have been proposed for both the issues. Furthermore, an alternative geometric interpretation of classical PSO dynamics allows to introduce a major APSO variant based on a novel concept of convex combination between permutation objects. In total, four APSO schemes have been introduced. Experiments have been held to compare the performances of the APSO schemes with respect to the random key based PSO schemes in literature. Widely adopted benchmark instances of four popular permutation problems have been considered. The experimental results clearly show that, with high statistical evidence, APSO outperforms its competitors and it reaches results comparable with state-of-the-art on most of the instances considered. Show more

Keywords: Algebraic Particle Swarm Optimization, Permutation Problems, Permutation Search Space

DOI: 10.3233/FI-2019-1812

Citation: Fundamenta Informaticae, vol. 167, no. 1-2, pp. 133-158, 2019