Semantics for possibilistic answer set programs: Uncertain rules versus rules with uncertain conclusions

Although Answer Set Programming (ASP) is a powerful framework for declarative problem solving, it cannot in an intuitive way handle situations in which some rules are uncertain, or in which it is more important to satisfy some constraints than others. Possibilistic ASP (PASP) is a natural extension of ASP in which certainty weights are associated with each rule. In this paper we contrast two different views on interpreting the weights attached to rules. Under the first view, weights reflect the certainty with which we can conclude the head of a rule when its body is satisfied. Under the second view, weights reflect the certainty that a given rule restricts the considered epistemic states of an agent in a valid way, i.e. it is the certainty that the rule itself is correct. The first view gives rise to a set of weighted answer sets, whereas the second view gives rise to a weighted set of classical answer sets.     

$${\varvec{teaspoon}}$$ : solving the curriculum-based course timetabling problems with answer set programming

Annals of Operations Research - Answer Set Programming (ASP) is an approach to declarative problem solving, combining a rich yet simple modeling language with high performance solving capacities....     

Experimenting with parallelism for the instantiation of ASP programs

In the last few years, microprocessor technologies have been moving towards multi-core architectures, in order to improve performance as well as reduce power consumption. This makes real Symmetric MultiProcessing (SMP) available even on non-dedicated machines, and paves the way to the development of better performing software. Notably, the recent application of Answer Set Programming (ASP) in different emerging areas, such as knowledge management or information extraction/integration, shows that performance is a crucial issue also for ASP systems. Among the tasks performed by such systems, the instantiation process, which consists of generating a variable-free program equivalent to the input one, is one of the most expensive from a computational viewpoint, especially in the case of huge input data. In this paper a new strategy exploiting parallelism for the instantiation of ASP programs is proposed. An implementation of this strategy and its integration with the grounding module of the DLV system is discussed. The results of an experimental analysis are also presented, which confirm that the strategy is effective in making ASP instantiation more efficient.     

Using possibilistic logic for modeling qualitative decision: Answer Set Programming algorithms

A qualitative approach to decision making under uncertainty has been proposed in the setting of possibility theory, which is based on the assumption that levels of certainty and levels of priority (for expressing preferences) are commensurate. In this setting, pessimistic and optimistic decision criteria have been formally justified. This approach has been transposed into possibilistic logic in which the available knowledge is described by formulas which are more or less certainly true and the goals are described in a separate prioritized base. This paper adapts the possibilistic logic handling of qualitative decision making under uncertainty in the Answer Set Programming (ASP) setting. We show how weighted beliefs and prioritized preferences belonging to two separate knowledge bases can be handled in ASP by modeling qualitative decision making in terms of abductive logic programming where (uncertain) knowledge about the world and prioritized preferences are encoded as possibilistic definite logic programs and possibilistic literals respectively. We provide ASP-based and possibilistic ASP-based algorithms for calculating optimal decisions and utility values according to the possibilistic decision criteria. We describe a prototype implementing the algorithms proposed on top of different ASP solvers and we discuss the complexity of the different implementations.     

A core language for fuzzy answer set programming

A number of different Fuzzy Answer Set Programming (FASP) formalisms have been proposed in the last years, which all differ in the language extensions they support. In this paper we investigate the expressivity of these frameworks. Specifically we show how a variety of constructs in these languages can be implemented using a considerably simpler core language. These simulations are important as a compact and simple language is easier to implement and to reason about, while an expressive language offers more options when modeling problems.     

MEPAR-miner: Multi-expression programming for classification rule mining

Classification and rule induction are two important tasks to extract knowledge from data. In rule induction, the representation of knowledge is defined as IF-THEN rules which are easily understandable and applicable by problem-domain experts. In this paper, a new chromosome representation and solution technique based on Multi-Expression Programming (MEP) which is named as MEPAR-miner (Multi-Expression Programming for Association Rule Mining) for rule induction is proposed. Multi-Expression Programming (MEP) is a relatively new technique in evolutionary programming that is first introduced in 2002 by Oltean and Dumitrescu. MEP uses linear chromosome structure. In MEP, multiple logical expressions which have different sizes are used to represent different logical rules. MEP expressions can be encoded and implemented in a flexible and efficient manner. MEP is generally applied to prediction problems; in this paper a new algorithm is presented which enables MEP to discover classification rules. The performance of the developed algorithm is tested on nine publicly available binary and n-ary classification data sets. Extensive experiments are performed to demonstrate that MEPAR-miner can discover effective classification rules that are as good as (or better than) the ones obtained by the traditional rule induction methods. It is also shown that effective gene encoding structure directly improves the predictive accuracy of logical IF-THEN rules.     

A penalized criterion for variable selection in classification

In this paper, the problem of variable selection in classification is considered. On the basis of recent developments in model selection theory, we provide a criterion based on penalized empirical risk, where the penalization explicitly takes into account the number of variables of the considered models. Moreover, we give an oracle-type inequality that non-asymptotically guarantees the performance of the resulting classification rule. We discuss the optimality of the proposed criterion and present an application of the main result to backward and forward selection procedures.     

Linear discrimination with equicorrelated training vectors

Fisher's linear discrimination rule requires uncorrelated training vectors. In this paper a linear discrimination method is developed to be used when the training vectors are equicorrelated. Also, maximum likelihood ratio tests are proposed to decide whether the training samples are uncorrelated or equicorrelated.     

An efficient modified boosting method for solving classification problems

Based on the Adaboost algorithm, a modified boosting method is proposed in this paper for solving classification problems. This method predicts the class label of an example as the weighted majority voting of an ensemble of classifiers. Each classifier is obtained by applying a given weak learner to a subsample (with size smaller than that of the original training set) which is drawn from the original training set according to the probability distribution maintained over the training set. A parameter is introduced into the reweighted scheme proposed in Adaboost to update the probabilities assigned to training examples so that the algorithm can be more accurate than Adaboost. The experimental results on synthetic and several real-world data sets available from the UCI repository show that the proposed method improves the prediction accuracy, the execution speed as well as the robustness to classification noise of Adaboost. Furthermore, the diversity–accuracy patterns of the ensemble classifiers are investigated by kappa–error diagrams.     

An $$\mathcal{O}(m\log n)$$ algorithm for the weighted stable set problem in claw-free graphs with $$\alpha ({G}) \le 3$$

Mathematical Programming - In this paper we show how to solve the Maximum Weight Stable Set Problem in a claw-free graph G(V, E) with $$\alpha (G) \le 3$$ in time $$\mathcal{O}(|E|\log...     

Ensemble Learning Using Multi-Objective Evolutionary Algorithms

Multi-objective evolutionary algorithms for the construction of neural ensembles is a relatively new area of research. We recently proposed an ensemble learning algorithm called DIVACE (DIVerse and ACcurate Ensemble learning algorithm). It was shown that DIVACE tries to find an optimal trade-off between diversity and accuracy as it searches for an ensemble for some particular pattern recognition task by treating these two objectives explicitly separately. A detailed discussion of DIVACE together with further experimental studies form the essence of this paper. A new diversity measure which we call Pairwise Failure Crediting (PFC) is proposed. This measure forms one of the two evolutionary pressures being exerted explicitly in DIVACE. Experiments with this diversity measure as well as comparisons with previously studied approaches are hence considered. Detailed analysis of the results show that DIVACE, as a concept, has promise.     

A matheuristic for the cell formation problem

In this paper we propose a GRASP matheuristic coupled with an Integer Programming refinement based on Set Partitioning to solve the Cell Formation Problem. We use the grouping efficacy measure to evaluate the solutions. As this measure is nonlinear, we propose a fractional Set Partitioning approach and its linearization. Our method is validated on a set of 35 instances from the literature. The experiments found four unknown solutions. For all instances with known optima, our method is able to determine the optimum solutions.     

Execution of logic programs by iterative-deepening A* SLD-tree search

The depth-first search strategy used by PROLOG is supplemented by depth-first iterative-deepening A*, which is complete, i.e. it always succeeds in executing a correct program if enough time and space is available. Iterative-deepening A* is only used for predicates that can be executed faster with iterative-deepening A* instead of depth-first.Since standard iterative-deepening A* is quadratic instead of linear for trees with much one way branching, e.g. most SLD-trees, extrapolation is used to determine a suitable bound on the evaluation function values of nodes that are to be expanded during an iteration. The number of inferences is further reduced by pruning rules such as cutting when the next literal to be evaluated is an alphabetic variant of a literal for which evaluation has failed previously.An advantage of the suggested search strategy is that many more programs can be executed with reasonable efficiency. The main disadvantage is that the programmer either must specify explicitly which strategy to use for a given predicate or provide examples so that the best strategy can be inferred automatically.     

A hybrid algorithm for the Heterogeneous Fleet Vehicle Routing Problem

This paper deals with the Heterogeneous Fleet Vehicle Routing Problem (HFVRP). The HFVRP generalizes the classical Capacitated Vehicle Routing Problem by considering the existence of different vehicle types, with distinct capacities and costs. The objective is to determine the best fleet composition as well as the set of routes that minimize the total costs. The proposed hybrid algorithm is composed by an Iterated Local Search (ILS) based heuristic and a Set Partitioning (SP) formulation. The SP model is solved by means of a Mixed Integer Programming solver that interactively calls the ILS heuristic during its execution. The developed algorithm was tested in benchmark instances with up to 360 customers. The results obtained are quite competitive with those found in the literature and new improved solutions are reported.     

A fuzzy clustering application to precise orbit determination

In recent years, fuzzy logic techniques have been successfully applied in geodesy problems, in particular to GPS. The aim of this work is to test a fuzzy-logic method with an enhanced probability function as a tool to provide a reliable criteria for weighting scheme for satellite-laser-ranging (SLR) station observations, seeking to optimize their contribution to the precise orbit determination (POD) problem. The data regarding the stations were provided by the International Laser Ranging Service (ILRS), NASA/Crustal Dynamics Data Information System (CDDIS) provided the satellite data for testing the method. The software for processing the data is GEODYN II provided by NASA/Goddard Space Flight Center (GSFC). Factors to be considered in the fuzzy-logic clustering are: the total number of LAGEOS passes during the past 12 months, the stability measure of short- and long-term biases, the percentage of LAGEOS normal points that were accepted in CSR weekly LAGEOS analysis, and the RMS uncertainty of the station coordinates. A fuzzy-logic statistical method allows classifying the stations through a clear ‘degree of belonging’ to each station group. This degree of belonging translates into a suitable weight to be assigned to each station in the global solution. The first tests carried out showed improvements in the RMS of the global POD solution as well as individual stations, to within a few millimeters. We expect further work would lead to further improvements.     

Resolving degeneracy in quadratic programming

A technique for the resolution of degeneracy in an Active Set Method for Quadratic Programming is described. The approach generalises Fletcher's method [2] which applies to the LP case. The method is described in terms of an LCP tableau, which is seen to provide useful insights. It is shown that the degeneracy procedure only needs to operate when the degenerate constraints are linearly dependent on those in the active set. No significant overheads are incurred by the degeneracy procedure. It is readily implemented in a null space format, and no complications in the matrix algebra are introduced.The guarantees of termination provided by [2], extending in particular to the case where round-off error is present, are preserved in the QP case. It is argued that the technique gives stronger guarantees than are available with other popular methods such as Wolfe's method [11] or the method of Goldfarb and Idnani [7].Presented at the 14th International Symposium on Mathematical Programming, Amsterdam, August 5–9, 1991.     

Limiting search cost distribution for the move-to-front rule with random request probabilities

Consider a list of n files whose popularities are random. The list is updated according to the move-to-front rule. When the induced Markov chain is at equilibrium, we explicitly compute the limiting distribution of the search-cost per item as n tends to infinity. The uniform distribution results in the largest search cost.     

A Goal Programming model of the reference point method

Real-life decision problems are usually so complex they cannot be modeled with a single objective function, thus creating a need for clear and efficient techniques of handling multiple criteria to support the decision process. The most commonly used technique is Goal Programming. It is clear and appealing, but in the case of multiobjective optimization problems strongly criticized due to its noncompliance with the efficiency (Pareto-optimality) principle. On the other hand, the reference point method, although using similar control parameters as Goal Programming, always generates efficient solutions. In this paper, we show how the reference point method can be modeled within the Goal Programming methodology. It allows us to simplify implementations of the reference point method as well as shows how Goal Programming with relaxation of some traditional assumptions can be extended to a multiobjective optimization technique meeting the efficiency principle.     

The Robust Set Covering Problem with interval data

We study the Set Covering Problem with uncertain costs. For each cost coefficient, only an interval estimate is known, and it is assumed that each coefficient can take on any value from the corresponding uncertainty interval, regardless of the values taken by other coefficients. It is required to find a robust deviation (also called minmax regret) solution. For this strongly NP-hard problem, we present and compare computationally three exact algorithms, where two of them are based on Benders decomposition and one uses Benders cuts in the context of a Branch-and-Cut approach, and several heuristic methods, including a scenario-based heuristic, a Genetic Algorithm, and a Hybrid Algorithm that uses a version of Benders decomposition within a Genetic Algorithm framework.