Carnap,Goguen, and the Hyperontologies: Logical Pluralism and Heterogeneous Structuring in Ontology Design

This paper addresses questions of universality related to ontological engineering, namely aims at substantiating (negative) answers to the following three basic questions: (i) Is there a ‘universal ontology’?, (ii) Is there a ‘universal formal ontology language’?, and (iii) Is there a universally applicable ‘mode of reasoning’ for formal ontologies? To support our answers in a principled way, we present a general framework for the design of formal ontologies resting on two main principles: firstly, we endorse Rudolf Carnap’s principle of logical tolerance by giving central stage to the concept of logical heterogeneity, i.e. the use of a plurality of logical languages within one ontology design. Secondly, to structure and combine heterogeneous ontologies in a semantically well-founded way, we base our work on abstract model theory in the form of institutional semantics, as forcefully put forward by Joseph Goguen and Rod Burstall. In particular, we employ the structuring mechanisms of the heterogeneous algebraic specification language HetCasl for defining a general concept of heterogeneous, distributed, highly modular and structured ontologies, called hyperontologies. Moreover, we distinguish, on a structural and semantic level, several different kinds of combining and aligning heterogeneous ontologies, namely integration, connection, and refinement. We show how the notion of heterogeneous refinement can be used to provide both a general notion of sub-ontology as well as a notion of heterogeneous equivalence of ontologies, and finally sketch how different modes of reasoning over ontologies are related to these different structuring aspects.     

Operational aircraft maintenance routing problem with remaining time consideration

The aircraft maintenance routing problem is one of the most studied problems in the airline industry. Most of the studies focus on finding a unique rotation that will be repeated by each aircraft in the fleet with a certain lag. In practice, using a single rotation for the entire fleet is not applicable due to stochasticity and operational considerations in the airline industry. In this study, our aim is to develop a fast responsive methodology which provides maintenance feasible routes for each aircraft in the fleet over a weekly planning horizon with the objective of maximizing utilization of the total remaining flying time of fleet. For this purpose, we formulate an integer linear programming (ILP) model by modifying the connection network representation. The proposed model is solved by using branch-and-bound under different priority settings for variables to branch on. A heuristic method based on compressed annealing is applied to the same problem and a comparison of exact and heuristic methods are provided. The model and the heuristic method are extended to incorporate maintenance capacity constraints. Additionally, a rolling horizon based procedure is proposed to update the existing routes when some of the maintenance decisions are already fixed.     

The spectrum of a finite pseudocomplemented modular lattice

We propose the minimal representation of an element in a pseudocomplemented modular lattice satisfying the descending chain condition and prove that the minimal representation of an element is unique. Then we give necessary and sufficient conditions under which a sequence can be the spectrum of a modular lattice and a distributive lattice, respectively. These results settle two problems raised by G. Grätzer, D. S. Gunderson and R. W. Quackenbush in 2009.     

Mathematical knowledge ontologies and recommender systems for collections of documents in physics and mathematics

An approach to the implementation of a recommender system based on ontologies of mathematical knowledge is presented. On the basis of a document browsed by a user, the system forms on line a list of recommendations, which include similar documents, key words, and definitions of these words from ontology and other terminological sources. The method of recommendations yields a vector representation of documents, taking into account the position of terms in the logical structure of the document and their ontological connections. On the basis of the cosine measure, a measure of proximity between documents is calculated. The order of documents in the list of recommendations is determined by values of the proximity measure. Various adaptations of the system to user scenarios aimed at the preparation of personalized recommendations are discussed.     

Z-eigenvalue methods for a global polynomial optimization problem

As a global polynomial optimization problem, the best rank-one approximation to higher order tensors has extensive engineering and statistical applications. Different from traditional optimization solution methods, in this paper, we propose some Z-eigenvalue methods for solving this problem. We first propose a direct Z-eigenvalue method for this problem when the dimension is two. In multidimensional case, by a conventional descent optimization method, we may find a local minimizer of this problem. Then, by using orthogonal transformations, we convert the underlying supersymmetric tensor to a pseudo-canonical form, which has the same E-eigenvalues and some zero entries. Based upon these, we propose a direct orthogonal transformation Z-eigenvalue method for this problem in the case of order three and dimension three. In the case of order three and higher dimension, we propose a heuristic orthogonal transformation Z-eigenvalue method by improving the local minimum with the lower-dimensional Z-eigenvalue methods, and a heuristic cross-hill Z-eigenvalue method by using the two-dimensional Z-eigenvalue method to find more local minimizers. Numerical experiments show that our methods are efficient and promising. This work is supported by the Research Grant Council of Hong Kong and the Natural Science Foundation of China (Grant No. 10771120).     

Preventive maintenance scheduling of power generating units

The problem of preventive maintenance planning of electric power generating units can be formulated as a mixed-integer linear optimization problem. An extension of the model is presented to deal with more realistic assumptions about utilization of power resource. We propose a heuristic iterative exchange procedure to solve these problems. We introduce two methods to prevent jamming situations outside the feasible domain or at a local optimum. The first method is a recursive exchange procedure called multiple exchanges method and the second relies on Lagrangian relaxation. Furthermore, we compare these procedures with a tabu search.This research was supported by NSERC (Grant A8312) and FCAR (Grant ER-0289).Michèle Charest had an NSERC Scholarship to work on this project.     

Hybridizing exact methods and metaheuristics: A taxonomy

The interest about hybrid optimization methods has grown for the last few years. Indeed, more and more papers about cooperation between heuristics and exact techniques are published. In this paper, we propose to extend an existing taxonomy for hybrid methods involving heuristic approaches in order to consider cooperative schemes between exact methods and metaheuristics. First, we propose some natural approaches for the different schemes of cooperation encountered, and we analyse, for each model, some examples taken from the literature. Then we recall and complement the proposed grammar and provide an annotated bibliography.     

The application of an oblique-projected Landweber method to a model of supervised learning

This paper brings together a novel information representation model for use in signal processing and computer vision problems, with a particular algorithmic development of the Landweber iterative algorithm. The information representation model allows a representation of multiple values for a variable as well as an expression for confidence. Both properties are important for effective computation using multi-level models, where a choice between models will be implementable as part of the optimization process. It is shown that in this way the algorithm can deal with a class of high-dimensional, sparse, and constrained least-squares problems, which arise in various computer vision learning tasks, such as object recognition and object pose estimation. While the algorithm has been applied to the solution of such problems, it has so far been used heuristically. In this paper we describe the properties and some of the peculiarities of the channel representation and optimization, and put them on firm mathematical ground. We consider the optimization a convexly constrained weighted least-squares problem and propose for its solution a projected Landweber method which employs oblique projections onto the closed convex constraint set. We formulate the problem, present the algorithm and work out its convergence properties, including a rate-of-convergence result. The results are put in perspective with currently available projected Landweber methods. An application to supervised learning is described, and the method is evaluated in an experiment involving function approximation, as well as application to transient signals.     

A dual ascent procedure for the set partitioning problem

The set partitioning problem is a fundamental model for many important real-life transportation problems, including airline crew and bus driver scheduling and vehicle routing.In this paper we propose a new dual ascent heuristic and an exact method for the set partitioning problem. The dual ascent heuristic finds an effective dual solution of the linear relaxation of the set partitioning problem and it is faster than traditional simplex based methods. Moreover, we show that the lower bound achieved dominates the one achieved by the classic Lagrangean relaxation of the set partitioning constraints. We describe a simple exact method that uses the dual solution to define a sequence of reduced set partitioning problems that are solved by a general purpose integer programming solver. Our computational results indicate that the new bounding procedure is fast and produces very good dual solutions. Moreover, the exact method proposed is easy to implement and it is competitive with the best branch and cut algorithms published in the literature so far.     

Superconvergence in H1-norm of a difference finite element method for the heat equation in a 3D spatial domain with almost-uniform mesh

Numerical Algorithms - In this paper, we propose a novel difference finite element (DFE) method based on the P1-element for the 3D heat equation on a 3D bounded domain. One of the novel ideas of...     

Variable neighbourhood search for bandwidth reduction

The problem of reducing the bandwidth of a matrix consists of finding a permutation of rows and columns of a given matrix which keeps the non-zero elements in a band as close as possible to the main diagonal. This NP-complete problem can also be formulated as a vertex labelling problem on a graph, where each edge represents a non-zero element of the matrix. We propose a variable neighbourhood search based heuristic for reducing the bandwidth of a matrix which successfully combines several recent ideas from the literature. Empirical results for an often used collection of 113 benchmark instances indicate that the proposed heuristic compares favourably to all previous methods. Moreover, with our approach, we improve best solutions in 50% of instances of large benchmark tests.     

A finite element frequency domain method for 2D photonic crystals

In this paper we propose a new finite element frequency domain (FEFD) method to compute the band spectra of 2D photonic crystals without impurities. Exploiting periodicity to identify discretization points differing by a period, it increases the effectiveness of the algorithm and reduces significantly its computational complexity. The results of an extensive experimentation indicate that our method offers an effective alternative to the most quoted methods in the literature.     

A high order discontinuous Galerkin Nitsche method for elliptic problems with fictitious boundary

We present a discontinuous Galerkin method, based on the classical method of Nitsche, for elliptic problems with an immersed boundary representation on a structured grid. In such methods very small elements typically occur at the boundary, leading to breakdown of the discrete coercivity as well as numerical instabilities. In this work we propose a method that avoids using very small elements on the boundary by associating them to a neighboring element with a sufficiently large intersection with the domain. This construction allows us to prove the crucial inverse inequality that leads to a coercive bilinear form and as a consequence we obtain optimal order a priori error estimates. Furthermore, we prove a bound of the condition number of the stiffness matrix. All the results are valid for polynomials of arbitrary order. We also discuss the implementation of the method and present numerical examples in three dimensions.     

Linear programming for the 0–1 quadratic knapsack problem

In this paper we consider the quadratic knapsack problem which consists in maximizing a positive quadratic pseudo-Boolean function subject to a linear capacity constraint. We propose a new method for computing an upper bound. This method is based on the solution of a continuous linear program constructed by adding to a classical linearization of the problem some constraints rebundant in 0–1 variables but nonredundant in continuous variables. The obtained upper bound is better than the bounds given by other known methods. We also propose an algorithm for computing a good feasible solution. This algorithm is an elaboration of the heuristic methods proposed by Chaillou, Hansen and Mahieu and by Gallo, Hammer and Simeone. The relative error between this feasible solution and the optimum solution is generally less than 1%. We show how these upper and lower bounds can be efficiently used to determine the values of some variables at the optimum. Finally we propose a branch-and-bound algorithm for solving the quadratic knapsack problem and report extensive computational tests.     

几乎不可压线弹性问题的新的Uzawa型自适应有限元方法

本文针对几乎不可压线弹性问题设计新的Uzawa型自适应有限元方法,该方法可克服"闭锁"现象·通过引入"压力"变量将弹性问题转化为一个鞍点系统,对该系统将Uzawa型迭代法和自适应有限元方法相结合,建立了Uzawa型自适应有限元方法,并给出了该算法的收敛性.该算法采用低阶协调有限元通近空间变量,选取的有限元空间对无需满足离散的BB条件.最后,数值算例验证了理论结果的正确性.     

A thermo-electrical problem with a nonlocal radiation boundary condition

A coupled problem arising in induction heating furnaces is studied. The thermal problem, which involves a change of phase, has a nonlocal radiation boundary condition. Convective heat transfer in the liquid is also included which makes necessary to compute the liquid motion. For the space discretization, we propose finite element methods which are combined with characteristics methods in the thermal and flow models to handle the convective terms. In the electromagnetic model they are coupled with boundary element methods (BEM/FEM). An iterative algorithm is introduced for the whole coupled model and numerical results for an industrial induction furnace are presented.     

CALCULATING AN ELEMENT OF B-DIFFERENTIAL FOR A VECTOR-VALUED MAXIMUM FUNCTION*

In this paper, we propose a method of calculating an element of B-differential, also an element of Clarke generalized Jacobian, for a vector-valued maximum function. This calculation is required in many existing numerical methods for the solution of nonsmooth equations and for the nonsmooth optimization. The generalization of our method to a vector-valued smooth composition of maximum functions is also discussed. Particularly, we propose a method of obtaining the set of B-differential for a vector-valued maximum of affine functions.

     

Greedy algorithm for the general multidimensional knapsack problem

In this paper, we propose a new greedy-like heuristic method, which is primarily intended for the general MDKP, but proves itself effective also for the 0-1 MDKP. Our heuristic differs from the existing greedy-like heuristics in two aspects. First, existing heuristics rely on each item’s aggregate consumption of resources to make item selection decisions, whereas our heuristic uses the effective capacity, defined as the maximum number of copies of an item that can be accepted if the entire knapsack were to be used for that item alone, as the criterion to make item selection decisions. Second, other methods increment the value of each decision variable only by one unit, whereas our heuristic adds decision variables to the solution in batches and consequently improves computational efficiency significantly for large-scale problems. We demonstrate that the new heuristic significantly improves computational efficiency of the existing methods and generates robust and near-optimal solutions. The new heuristic proves especially efficient for high dimensional knapsack problems with small-to-moderate numbers of decision variables, usually considered as “hard” MDKP and no computationally efficient heuristic is available to treat such problems. Supported in part by the NSF grant DMI 9812994.     

Ontological aspects of the implementation of norms in agent-based electronic institutions

In order to regulate different circumstances over an extensive period of time, norms in institutions are stated in a vague and often ambiguous manner, thereby abstracting from concrete aspects which become instead relevant for the actual functioning of the institutions. If agent-based electronic institutions, which adhere to a set of abstract requirements, are to be built, how can those requirements be translated into more concrete constraints, the impact of which can be described directly in the institution? We address this issue considering institutions as normative systems based on articulate ontologies of the agent domain they regulate. Ontologies, we hold, are used by institutions to relate the abstract concepts in which their norms are formulated, to their concrete application domain. In this view, different institutions can implement the same set of norms in different ways as far as they presuppose divergent ontologies of the concepts in which that set of norms is formulated. In this paper we analyse this phenomenon introducing a notion of contextual ontology. We will focus on the formal machinery necessary to characterise it as well.     

Structural modeling in a class of systems using fuzzy sets theory

On the basis of fuzzy sets theory, we propose a method for structuring hierarchy for the several complex problems, and call it Fuzzy Structural Modeling (FSM) method. An important requirement for structural modeling of complex systems is that the necessary data is acquired and organized into a form such that a structural model can be developed. The main purpose of this method is to describe and illustrate a formal procedure for constructing the graphic presentation of the hierarchical arrangement given the necessary information concerning the relation of each element to each other element. The procedure permits an automatic development of the graphic structure that portrays the hierarchy.