Shiftable intervals

Consider a set of n fixed length intervals and a set of n (larger) windows, in one-to-one correspondence with the intervals, and assume that each interval can be placed in any position within its window. If the position of each interval has been fixed, the intersection graph of such set of intervals is an interval graph. By varying the position of each interval in all possible ways, we get a family of interval graphs. In the paper we define some optimization problems related to the clique, stability, chromatic, clique cover numbers and cardinality of the minimum dominating set of the interval graphs in the family, mainly focussing on complexity aspects, bounds and solution algorithms. Some problems are proved to be NP-hard, others are solved in polynomial time on some particular classes of instances. Many practical applications can be reduced to these kind of problems, suggesting the use of Shiftable Intervals as a new interesting modeling framework.     

Learning from conflicts in propositional satisfiability

Learning is a general concept, playing an important role in many Artificial intelligence domains. In this paper, we address the learning paradigm used to explain failures or conflicts encountered during search. This explanation, derived by conflict analysis, and generally expressed as a new constraint, is usually used to dynamically avoid future occurrences of similar situations. Before focusing on clause learning in Boolean satisfiability (SAT), we first overview some important works on this powerful reasoning tool in other domains such as constraint satisfaction and truth maintenance systems. Then, we present a comprehensive survey of the most important works having led to what is called today—conflict driven clause learning (CDCL)—which is one of the key components of modern SAT solvers. In theory, current SAT solvers with clause learning are as powerful as general resolution proof systems. In practice, real-world SAT instances with millions of variables and clauses are now in the scope of this solving paradigm.     

Efficient modeling of MIMO systems through Timed Automata based Neuro-Fuzzy Inference Engine

This paper introduces a novel neuro-fuzzy approach for learning and modeling so-called Multi-Input Multi-Output Coupling (MIMO) systems, i.e., systems where the output variables may depend upon all system's input variables. This strong coupling makes the MIMO systems behavior highly oscillatory in time and, as a consequence, it makes these systems not particularly suitable to be learned and represented by using conventional approaches. In order to address this issue, our proposal presents an adaptive supervised learning algorithm capable of forming a suitable collection of Timed Automata based Fuzzy Systems that model the dynamic behavior of a given MIMO system. The adaptive learning is accomplished by taking advantage of the theories coming from the area of times series analysis (such as the Adaptive Piecewise Constant Approximation method) with a well-known neuro-fuzzy framework of the Adaptive Neuro Fuzzy Inference System (ANFIS). In experiments, where our proposal has been tested on the Fuzz-IEEE 2011 Fuzzy Competition dataset, the proposed supervised learning algorithm significantly reduces the output error measure and achieves better performance than the one provided by a conventional application of the ANFIS algorithm.     

模糊支付合作博弈的可信性准核仁

合作博弈是处理局中人之间协同行为的数学理论。有诸如核心、稳定集、沙普利值、准核仁和核仁等不同的解概念。在很多情形,除了借助专家经验和主观直觉,没有恰当的方式来确定支付函数,由此产生了具有模糊支付的合作博弈模型。准核仁是一种重要的解概念,在模糊支付合作博弈中如何恰当定义准核仁是个重要的问题。本文在可信性理论的框架下研究了这个问题,定义了两类可信性准核仁概念并证明了它们的存在性和唯一性,同时研究了可信性核心、可信性核仁与它们之间的关系。     

An Approach to Fuzzy Noncooperative Nash Games

Systems that involve more than one decision maker are often optimized using the theory of games. In the traditional game theory, it is assumed that each player has a well-defined quantitative utility function over a set of the player decision space. Each player attempts to maximize/minimize his/her own expected utility and each is assumed to know the extensive game in full. At present, it cannot be claimed that the first assumption has been shown to be true in a wide variety of situations involving complex problems in economics, engineering, social and political sciences due to the difficulty inherent in defining an adequate utility function for each player in these types of problems. On the other hand, in many of such complex problems, each player has a heuristic knowledge of the desires of the other players and a heuristic knowledge of the control choices that they will make in order to meet their ends.In this paper, we utilize fuzzy set theory in order to incorporate the players' heuristic knowledge of decision making into the framework of conventional game theory or ordinal game theory. We define a new approach to N-person static fuzzy noncooperative games and develop a solution concept such as Nash for these types of games. We show that this general formulation of fuzzy noncooperative games can be applied to solve multidecision-making problems where no objective function is specified. The computational procedure is illustrated via application to a multiagent optimization problem dealing with the design and operation of future military operations.     

Schur-positive sets of permutations via products and grid classes

Characterizing sets of permutations whose associated quasisymmetric function is symmetric and Schur-positive is a long-standing problem in algebraic combinatorics. In this paper, we present a general method to construct Schur-positive sets and multisets, based on geometric grid classes and the product operation. Our approach produces many new instances of Schur-positive sets and provides a broad framework that explains the existence of known such sets that until now were sporadic cases.     

Modeling Dependencies in Operational Risk with Hybrid Bayesian Networks

This paper addresses the problem of quantifying and modeling financial institutions’ operational risk in accordance with the Advanced Measurement Approach put forth in the Basel II Accord. We argue that standard approaches focusing on modeling stochastic dependencies are not sufficient to adequately assess operational risk. In addition to stochastic dependencies, causal topological dependencies between the risk classes are typically encountered. These dependencies arise when risk units have common information- and/or work-flows and when failure of upstream processes imply risk for downstream processes. In this paper, we present a modeling strategy that explicitly captures both topological and stochastic dependencies between risk classes. We represent the operational-risk taxonomy in the framework of a hybrid Bayesian network (BN) and provide an intuitively compelling approach for handling causal relationships and external influences. We demonstrate the use of hybrid BNs as a tool for mapping causal dependencies between frequencies and severities of risk events and for modeling common shocks. Monte-Carlo simulations illustrate that the impact of topological dependencies on triggering overall system breakdowns can be substantial.     

A new approach for modeling and solving set packing problems

In recent years the unconstrained quadratic binary program has emerged as a unified modeling and solution framework for a variety of combinatorial optimization problems. Experience reported in the literature with several problem classes has demonstrated that this unified approach works surprisingly well in terms of solution quality and computational times, often rivaling and sometimes surpassing special purpose methods. In this paper we report on the application of this unified framework to set packing problems with a variety of coefficient distributions. Computational experience is reported illustrating the attractiveness of the approach. In particular, our results highlight both the effectiveness and robustness of our approach across a wide array of test problems.     

More efficient left-to-right matching for overlapping pattern

Pattern matching is a fundamental feature in many applications such as functional programming, logic programming, theorem proving, term rewriting and rule-based expert systems. Usually, patterns are pre-processed into a deterministic finite automaton. Using such an automaton allows one to determine the matched pattern(s) by a single scan of the input term. The matching automaton is typically based on left-to-right traversal of patterns. In this paper, we propose a method to build such an automaton. Then, we propose an incremental method to build a deterministic concise automaton for non-necessarily sequential rewriting systems. With ambiguous patterns a subject term may be an instance of more than one pattern. To select the pattern to use, a priority rule is usually engaged. The pre-processing of the patterns adds new patterns, which are instances of the original ones. When the original patterns are ambiguous, some of the instances supplied may be irrelevant for the matching process. They may cause an unnecessary increase in the space requirements of the automaton and may also reduce the time efficiency of the matching process. Here, we devise a new pre-processing operation that recognises and avoids such irrelevant instances. Hence improves space and time requirements for the matching automaton.     

The break scheduling problem: complexity results and practical algorithms

Break scheduling problems arise in working areas where breaks are indispensable, e.g., in air traffic control, supervision, or assembly lines. We regard such a problem from the area of supervision personnel. The objective is to find a break assignment for an existing shiftplan such that various constraints reflecting legal demands or ergonomic criteria are satisfied and such that staffing requirement violations are minimised. We prove the NP-completeness of this problem when all possible break patterns for each shift are given explicitly as part of the input. To solve our problem we propose two variations of a memetic algorithm. We define genetic operators, a local search based on three neighbourhoods, and a penalty system that helps to avoid local optima. Parameters influencing the algorithms are experimentally evaluated and assessed with statistical methods. We compare our algorithms, each with the best parameter setting according to the evaluation, with the state-of-the-art algorithm on a set of 30 real-life and randomly generated instances that are publicly available. One of our algorithms returns improved results on 28 out of the 30 benchmark instances. To the best of our knowledge, our improved results for the real-life instances constitute new upper bounds for this problem     

A new model for the asymmetric vehicle routing problem with simultaneous pickup and deliveries

The asymmetric vehicle routing problem with simultaneous pickup and deliveries is considered. This paper develops four new classes of valid inequalities for the problem. We generalize the idea of a no-good cut. Together, these help us solve 45-node randomly generated problem instances more efficiently. We report results on a set of benchmark instances in literature. In this set, we are able to show an order of magnitude improvement in computational times over currently published results in literature.     

An efficient grouping genetic algorithm for U-shaped assembly line balancing problems with maximizing production rate

U-type assembly line is one of the important tools that may increase companies’ production efficiency. In this study, two different modeling approaches proposed for the assembly line balancing problems have been used in modeling type-II U-line balancing problems, and the performances of these models have been compared with each other. It has been shown that using mathematical formulations to solve medium and large size problem instances is impractical since the problem is NP-hard. Therefore, a grouping genetic and simulated annealing algorithms have been developed, and a particle swarm optimization algorithm is adapted to compare with the proposed methods. A special crossover operator that always obtains feasible offspring has been suggested for the proposed grouping genetic algorithm. Furthermore, a local search procedure based on problem-specific knowledge was applied to increase the intensification of the algorithm. A set of well-known benchmark instances was solved to evaluate the effectiveness of the proposed and existing methods. Results showed that while the mathematical formulations can only be used to solve small size instances, metaheuristics can obtain high quality solutions for all size problem instances within acceptable CPU times. Moreover, grouping genetic algorithm has been found to be superior to the other methods according to the number of optimal solutions, or deviations from the lower bound values.     

Some classes of abstract simplicial complexes motivated by module theory

In this paper we analyze some classes of abstract simplicial complexes relying on algebraic models arising from module theory. To this regard, we consider a left-module on a unitary ring and find models of abstract complexes and related set operators having specific regularity properties, which are strictly interrelated to the algebraic properties of both the module and the ring.Next, taking inspiration from the aforementioned models, we carry out our analysis from modules to arbitrary sets. In such a more general perspective, we start with an abstract simplicial complex and an associated set operator. Endowing such a set operator with the corresponding properties obtained in our module instances, we investigate in detail and prove several properties of three subclasses of abstract complexes.More specifically, we provide uniformity conditions in relation to the cardinality of the maximal members of such classes. By means of the notion of OSS-bijection, we prove a correspondence theorem between a subclass of closure operators and one of the aforementioned families of abstract complexes, which is similar to the classic correspondence theorem between closure operators and Moore systems. Next, we show an extension property of a binary relation induced by set systems when they belong to one of the above families.Finally, we provide a representation result in terms of pairings between sets for one of the three classes of abstract simplicial complexes studied in this work.     

Isomorphic scheduling problems

We consider general properties of isomorphic scheduling problems that constitute a new class of pairs of mutually related scheduling problems. Any such a pair is composed of a scheduling problem with fixed job processing times and its time-dependent counterpart with processing times that are proportional-linear functions of the job starting times. In order to introduce the class formally, first we formulate a generic scheduling problem with fixed job processing times and define isomorphic problems by a one-to-one transformation of instances of the generic problem into instances of time-dependent scheduling problems with proportional-linear job processing times. Next, we prove basic properties of isomorphic scheduling problems and show how to convert polynomial algorithms for scheduling problems with fixed job processing times into polynomial algorithms for proportional-linear counterparts of the original problems. Finally, we show how are related approximation algorithms for isomorphic problems. Applying the results, we establish new worst-case results for time-dependent parallel-machine scheduling problems and prove that many single- and dedicated-machine time-dependent scheduling problems with proportional-linear job processing times are polynomially solvable.     

Classes de Nevanlinna dans certains domaines strictement pseudoconvexes non lisses

We define Nevanlinna classes in strictly pseudoconvex domains that are not necessarily smooth. If the boundary is defined by a Morse function we give sufficient conditions of Blaschke type for an analytic set to be the zero set of a function in a given Nevanlinna class. In particular, in the case of a smooth boundary we obtain new and rather explicit proofs of the theorems of Henkin-Skoda and Dautov-Henkin.     

Approaches to measuring inconsistency for stratified knowledge bases

A number of proposals have been proposed for measuring inconsistency for knowledge bases. However, it is rarely investigated how to incorporate preference information into inconsistency measures. This paper presents two approaches to measuring inconsistency for stratified knowledge bases. The first approach, termed the multi-section inconsistency measure (MSIM for short), provides a framework for characterizing the inconsistency at each stratum of a stratified knowledge base. Two instances of MSIM are defined: the naive MSIM and the stratum-centric MSIM. The second approach, termed the preference-based approach, aims to articulate the inconsistency in a stratified knowledge base from a global perspective. This approach allows us to define measures by taking into account the number of formulas involved in inconsistencies as well as the preference levels of these formulas. A set of desirable properties are introduced for inconsistency measures of stratified knowledge bases and studied with respect to the inconsistency measures introduced in the paper. Computational complexity results for these measures are presented. In addition, a simple but explanatory example is given to illustrate the application of the proposed approaches to requirements engineering.     

Incongruent restricted disjoint covering systems

We define an incongruent restricted disjoint covering system on [1,n] as a set of congruence classes such that each integer in the interval [1,n] belongs to exactly one class, and each class contains at least two members of the interval. In this paper we report some computational and structural results and present some open problems concerning such systems.     

Intelligent data analysis and model interpretation with spectral analysis fuzzy symbolic modeling

This paper proposes fuzzy symbolic modeling as a framework for intelligent data analysis and model interpretation in classification and regression problems. The fuzzy symbolic modeling approach is based on the eigenstructure analysis of the data similarity matrix to define the number of fuzzy rules in the model. Each fuzzy rule is associated with a symbol and is defined by a Gaussian membership function. The prototypes for the rules are computed by a clustering algorithm, and the model output parameters are computed as the solutions of a bounded quadratic optimization problem. In classification problems, the rules’ parameters are interpreted as the rules’ confidence. In regression problems, the rules’ parameters are used to derive rules’ confidences for classes that represent ranges of output variable values. The resulting model is evaluated based on a set of benchmark datasets for classification and regression problems. Nonparametric statistical tests were performed on the benchmark results, showing that the proposed approach produces compact fuzzy models with accuracy comparable to models produced by the standard modeling approaches. The resulting model is also exploited from the interpretability point of view, showing how the rule weights provide additional information to help in data and model understanding, such that it can be used as a decision support tool for the prediction of new data.     

有偏抽样下带信息观察和删失的面板数据的统计分析

面板数据经常出现在许多研究领域, 比如纵向跟踪研究. 在很多情况下, 纵向反应变量与观察 时间和删失时间都有关系. 本文在有偏抽样下, 针对这些相关性存在的情况, 利用一个不能观察的潜在 变量, 提出了一个联合建模方法来刻画纵向反应变量与观察时间和删失时间的相关性, 获得了模型中 回归参数的估计方程以及估计的渐近性质, 并通过数值模拟验证了这些估计在小样本下也是有效的, 同时把该估计方法用于一组实际的膀胱癌数据分析中.