Boolean query optimization and the 0-1 hyperbolic sum problem

An intelligent front-end or logic assistant is an interactive program devised to assist the users of an information retrieval system in the formulation of their queries. In order to provide knowledge usable in such a program, we study a problem of query optimization with an average efficiency criterion. We formulate it as a new combinatorial optimization problem, which we call 0-1 hyperbolic sum, and provide an exact branch-and-bound algorithm and two heuristics (of simulated annealing and tabu search type) to solve it. Computational experience illustrating the effectiveness of the tabu search technique is reported.This research was done in part during a visit of the first author to the Pontifical Catholic University of Rio de Janeiro in July and August 1987, sponsored by CNPq. It was also supported in part by grants 0271 and 0066 of AFOSR to Rutgers University.     

CLSS: An Intelligent Crane Lorry Scheduling System

Companies that provide crane-lorry services are faced with the daily need to perform vehicle and driver allocation and scheduling. Many companies still do this manually due to the lack of suitable technologies. This manual approach is both time consuming and inaccurate and most probably will not lead to an optimized plan that can reduce operational costs. In this paper, we describe the design of a system called Crane Lorry Scheduling System (CLSS) that we have developed for the largest crane lorry company in Hong Kong. A crane lorry company is a company that provides lorries with different types of mounted crane equipment and drivers to service different types of moving and lifting jobs. CLSS is a Web-based application that streamlines communication with customers, subcontractors and employees/lorry drivers. We modeled the lorry-assignment problem as a constraint-satisfaction problem (CSP) algorithm, which we call the Crane Lorry Optimizing Engine (CLOE). CLOE was designed to be easily customizable to match the needs and requirements of different crane lorry companies. We experimented with two versions of CLOE, regular CLOE that finds best solutions and X-CLOE that finds optimal solutions. Results from our tests show that CLOE is faster and generates better quality plans than the manual approach.     

Optimal Design of Internet-Based Auctions

Online auctions are a profitable, exciting, and dynamic part of electronic commerce, and behave in ways, which do not match classical auction theory. This paper models an online auction in terms of a Markov chain on a state space defined by the current price of the item and the number of bidders who have been previously bumped. It provides a mathematical model, some approximations, which were necessary to convert it into a tractable problem and solutions to a small and a medium-sized theoretical auction. The model results were validated through a comparison with real-world online auction data, showing promise as a predictor of final auction prices. The results of the auction model are also useful in solving an optimization problem that incorporates inventory management considerations in determining optimal auction size.     

Some Considerations on the Reason for Bloat

A representation-less model for genetic programming is presented. The model is intended to examine the mechanisms that lead to bloat in genetic programming (GP). We discuss two hypotheses (fitness causes bloat and neutral code is protective) and perform simulations to examine the predictions deduced from these hypotheses. Our observation is that predictions from both hypotheses are realized in the simulated model.     

Solution of trim-loss problem by an integrated simulated annealing and ordinal optimization approach

This work presents a novel optimization method capable of integrating ordinal optimization (OO) and simulated annealing (SA). A general regression neural network (GRNN) is trained using available data to generate a rough model that approximates the response surface in the feasible domain. A set of good enough candidates are generated by conducting a (SA) search on this rough model. Only candidates accepted by the SA search are actually tested by evaluating their true objective functions. The GRNN model is then updated using these new data. The procedure is repeated until a specified number of tests have been performed. The method (SAOO+GRNN) is tested the well-known paper trim loss problem. SAOO+GRNN approach can substantially reduce the number of function calls and the computing time far below those of simple ordinal optimization method with such as horse race selection rule, as well as straightforward simulated annealing.     

A geometric view of parametric linear programming

We present a new definition of optimality intervals for the parametric right-hand side linear programming (parametric RHS LP) Problem () = min{c ^t x¦Ax =b + ¯b,x 0}. We then show that an optimality interval consists either of a breakpoint or the open interval between two consecutive breakpoints of the continuous piecewise linear convex function (). As a consequence, the optimality intervals form a partition of the closed interval {; ¦()¦ < }. Based on these optimality intervals, we also introduce an algorithm for solving the parametric RHS LP problem which requires an LP solver as a subroutine. If a polynomial-time LP solver is used to implement this subroutine, we obtain a substantial improvement on the complexity of those parametric RHS LP instances which exhibit degeneracy. When the number of breakpoints of () is polynomial in terms of the size of the parametric problem, we show that the latter can be solved in polynomial time.This research was partially funded by the United States Navy-Office of Naval Research under Contract N00014-87-K-0202. Its financial support is gratefully acknowledged.     

On Skolemization in constrained logics

Quantification in first-order logic always involves all elements of the universe. However, it is often more natural to just quantify over those elements of the universe which satisfy a certain condition. Constrained logics therefore provide restricted quantifiers _X:R F and _X:R F whereX is a set of variables, and which can be read as F holds for all elements satisfying the restrictionR and F holds if there exists an element which satisfiesR. In order to test satisfiability of a set of such formulas by means of an appropriately extended resolution principle, one needs a procedure which transforms them into a set of clauses with constraints. Such a procedure essentially differs from the classical transformation of first-oder formulas into a set of clauses, in particular since quantification over the empty set may occur and since the needed Skolemization procedure has to take the restrictions of restricted quantifiers into account. In the first part of this article we present a procedure that transforms formulas with restricted quantifiers into a set of clauses with constraints while preserving satisfiability. The thus obtained clauses are of the formC R whereC is an ordinary clause andR is a restriction, and can be read as C holds ifR holds. These clauses can now be tested on unsatisfiability via the existingconstrained resolution principle. In the second part we generalize the constrained resolution principle in such a way that it allows for further optimization, and we introduce a combination of unification and constraint solving that can be employed to instantiate this kind of optimization.     

Rapid Concept Learning for Mobile Robots

Concept learning in robotics is an extremely challenging problem: sensory data is often high dimensional, and noisy due to specularities and other irregularities. In this paper, we investigate two general strategies to speed up learning, based on spatial decomposition of the sensory representation, and simultaneous learning of multiple classes using a shared structure. We study two concept learning scenarios: a hallway navigation problem, where the robot has to induce features such as opening or wall. The second task is recycling, where the robot has to learn to recognize objects, such as a trash can. We use a common underlying function approximator in both studies in the form of a feedforward neural network, with several hundred input units and multiple output units. Despite the high degree of freedom afforded by such an approximator, we show the two strategies provide sufficient bias to achieve rapid learning. We provide detailed experimental studies on an actual mobile robot called PAVLOV to illustrate the effectiveness of this approach.     

From Conditional Events to Conditional Measures: A New Axiomatic Approach

Our starting point is a definition of conditional event EH which differs from many seemingly similar ones adopted in the relevant literature since 1935, starting with de Finetti. In fact, if we do not assign the same third value u (undetermined) to all conditional events, but make it depend on EH, it turns out that this function t(EH) can be taken as a general conditional uncertainty measure, and we get (through a suitable – in a sense, compulsory – choice of the relevant operations among conditional events) the natural axioms for many different (besides probability) conditional measures.     

A Note on the Ohya-Masuda Quantum Algorithm

We analyze the Ohya-Masuda quantum algorithm that solves the so-called satisfiability problem, which is an NP-complete problem of the complexity theory. We distinguish three steps in the algorithm, and analyze the second step, in which a coherent superposition of states (a pure state) transforms into an incoherent mixture presented by a density matrix. We show that, if nonideal (in analogy with nonideal quantum measurement), this transformation can make the algorithm to fail in some cases. On this basis we give some general notions on the physical implementation of the Ohya-Masuda algorithm.     

Modelling structures in generic space, a condition for adaptiveness of monitoring cognitive agent

The adaptiveness of agents is one of the basic conditions for the autonomy. This paper describes an approach of adaptiveness forMonitoring Cognitive Agents based on the notion of generic spaces. This notion allows the definition of virtual generic processes so that any particular actual process is then a simple configuration of the generic process, that is to say a set of values of parameters. Consequently, generic domain ontology containing the generic knowledge for solving problems concerning the generic process can be developed. This lead to the design of Generic Monitoring Cognitive Agent, a class of agent in which the whole knowledge corpus is generic. In other words, modeling a process within a generic space becomes configuring a generic process and adaptiveness becomes genericity, that is to say independence regarding technology. In this paper, we present an application of this approach on Sachem, a Generic Monitoring Cognitive Agent designed in order to help the operators in operating a blast furnace. Specifically, the NeuroGaz module of Sachem will be used to present the notion of a generic blast furnace. The adaptiveness of Sachem can then be noted through the low cost of the deployment of a Sachem instance on different blast furnaces and the ability of NeuroGaz in solving problem and learning from various top gas instrumentation.     

Low-Rank Approximation of Integral Operators by Interpolation

A central component of the analysis of panel clustering techniques for the approximation of integral operators is the so-called -admissibility condition min {diam(),diam()} 2dist(,) that ensures that the kernel function is approximated only on those parts of the domain that are far from the singularity. Typical techniques based on a Taylor expansion of the kernel function require a subdomain to be far enough from the singularity such that the parameter has to be smaller than a given constant depending on properties of the kernel function. In this paper, we demonstrate that any is sufficient if interpolation instead of Taylor expansionisused for the kernel approximation, which paves the way for grey-box panel clustering algorithms.     

A Study of Reinforcement Learning in the Continuous Case by the Means of Viscosity Solutions

This paper proposes a study of Reinforcement Learning (RL) for continuous state-space and time control problems, based on the theoretical framework of viscosity solutions (VSs). We use the method of dynamic programming (DP) which introduces the value function (VF), expectation of the best future cumulative reinforcement. In the continuous case, the value function satisfies a non-linear first (or second) order (depending on the deterministic or stochastic aspect of the process) differential equation called the Hamilton-Jacobi-Bellman (HJB) equation. It is well known that there exists an infinity of generalized solutions (differentiable almost everywhere) to this equation, other than the VF. We show that gradient-descent methods may converge to one of these generalized solutions, thus failing to find the optimal control.In order to solve the HJB equation, we use the powerful framework of viscosity solutions and state that there exists a unique viscosity solution to the HJB equation, which is the value function. Then, we use another main result of VSs (their stability when passing to the limit) to prove the convergence of numerical approximations schemes based on finite difference (FD) and finite element (FE) methods. These methods discretize, at some resolution, the HJB equation into a DP equation of a Markov Decision Process (MDP), which can be solved by DP methods (thanks to a strong contraction property) if all the initial data (the state dynamics and the reinforcement function) were perfectly known. However, in the RL approach, as we consider a system in interaction with some a priori (at least partially) unknown environment, which learns from experience, the initial data are not perfectly known but have to be approximated during learning. The main contribution of this work is to derive a general convergence theorem for RL algorithms when one uses only approximations (in a sense of satisfying some weak contraction property) of the initial data. This result can be used for model-based or model-free RL algorithms, with off-line or on-line updating methods, for deterministic or stochastic state dynamics (though this latter case is not described here), and based on FE or FD discretization methods. It is illustrated with several RL algorithms and one numerical simulation for the Car on the Hill problem.     

Nash-Cournot Equilibria in Power Markets on a Linearized DC Network with Arbitrage: Formulations and Properties

Extending a prior arbitrage-free model of Hobbs (2001), this article presents two models of an electric power market with arbitrage on a linearized DC network with a affine price functions. The two models represent a decentralized system involving bilateral contracts between producers and consumers in which the system operator's role is limited to providing transmission services. The two models differ in how arbitrage is handled. In the first model, the producers anticipate the effect of arbitrage upon prices at different locations (Stackelberg assumption), and therefore treat the arbitrage amounts as decision variables in their profit maximization problems. In the second model, the firms take the arbitrage quantities as inputs in their problems (Cournot assumption), and the arbitrager solves a separate profit maximization problem that takes the electricity prices and the transmission costs as inputs. In each model, we adopt a Nash-Cournot equilibrium as the solution concept for the game among producers. We show that the resulting equilibrium problems can be formulated as monotone mixed linear complementarity problems. Based on such a formulation, we obtain existence,uniqueness,and various quantitative properties of the equilibrium solutions to the models. It is also demonstrated that these two models of a bilateral market yield the same prices, producer outputs, and profits as a model of Cournot competition in a Poolco system,in which a system operator runs a centralized auction and buys all production, and then resells it to consumers. This result implies that Cournot competition among producers yields the same outcomes for two distinct market designs. Finally, we present a numerical example to illustrate the theoretical results.     

Consumer Satisfaction for Internet Service Providers: An Analysis of Underlying Processes

A key managerial challenge, of interest to academics and practitioners alike, is the assessment and management of customer satisfaction. In this paper, we examine the underlying processes involving consumer satisfaction and switching patterns among ISPs using different satisfaction models, including the expectations-disconfirmation model, the attribution model, and an affective model. Our results indicate that the satisfaction levels of ISP consumers are generally relatively low, despite the fact that consumer expectations of ISPs are also low, reflecting mediocrity in the marketplace. In addition, consumers attribute their dissatisfaction to ISP indifference and believe that managing dissatisfaction is within the control of the ISP. Moreover, affective factors play an important role in satisfaction processes and switching behavior. Customer service including technical support and responsiveness of service staff is an important determinant factor in ISP selection. We suggest that as the ISP market matures, service providers that pay attention to affective factors and to building relationships with their customers will have a competitive advantage in the marketplace of the future.     

Quantitative Characterization of Event Streams in Analysis of Hard Real-Time Applications

Many real-time embedded systems process event streams that are composed of a finite number of different event types. Each different event type on the stream would typically impose a different workload to the system, and thus the knowledge of possible correlations and dependencies between the different event types could be exploited to get tighter analytic performance bounds of the complete system. We propose an abstract stream model to characterize such an event stream. The model captures the needed information of all possible traces of a class of event streams. Hence, it can be used to obtain hard bounded worst-case and best-case analysis results of a system. We show how the proposed abstract stream model can be obtained from a concrete stream specification, and how it can be used for performance analysis. The applicability of our approach and its advantages over traditional worst-case performance analysis are shown in a case study of a multimedia application.Ernesto Wandeler is a Ph.D. student at the Computer Engineering and Networks Laboratory of the Swiss Federal Institute of Technology, Zurich. His research interests include models, methods and tools for system-level performance analysis of real-time embedded systems. He holds a Dipl. El.-Ing. degree from ETH Zurich. In 2003, he received the Willi Studer Price and the ETH Medal, both from the Swiss Federal Institute of Technology, Zurich. He is a student member of the IEEE and the ACM.Alexander Maxiaguine is a Ph.D. student at the Computer Engineering and Networks Laboratory of the Swiss Federal Institute of Technology, Zurich. His research interests include models and methods for system-level performance analysis and scheduling of embedded multiprocessor architectures, especially for real-time multimedia applications. Maxiaguine has an M.S. in electrical engineering from the Moscow Technical University of Communications and Informatics. He is a member of the IEEE and the ACM.Lothar Thiele is a full professor of computer engineering at the Swiss Federal Institute of Technology, Zurich. His research interests include models, methods and software tools for the design of embedded systems, embedded software and bioinspired optimization techniques. In 1986 he received the Dissertation Award of the Technical University of Munich, in 1987, the Outstanding Young Author Award of the IEEE Circuits and Systems Society, in 1988, the Browder J. Thompson Memorial Award of the IEEE, and in 2000–2001, the IBM Faculty Partnership Award. In 2004, he joined the German Academy of Natural Scientists Leopoldina.     

States and the free orthogonality monoid

Let (X, #) be an orthogonality space such that the lattice C(X, #) of closed subsets of (X, #) is orthomodular and let (, ) denote the free orthogonality monoid over (X, #). Let C₀(, ) be the subset of C(, ), consisting of all closures of bounded orthogonal sets. We show that C₀(, ) is a suborthomodular lattice of C(, ) and we provide a necessary and sufficient condition for C₀(, ) to carry a full set of dispersion free states.The work of the second author on this paper was supported by National Science Foundation Grant GP-9005.     

Mesh Selection for a Nearly Singular Boundary Value Problem

In this paper, we investigate the numerical solution of a model equation u _xx = exp(– ) (and several slightly more general problems) when 1 using the standard central difference scheme on nonuniform grids. In particular, we are interested in the error behaviour in two limiting cases: (i) the total mesh point number N is fixed when the regularization parameter 0, and (ii) is fixed when N. Using a formal analysis, we show that a generalized version of a special piecewise uniform mesh 12 and an adaptive grid based on the equidistribution principle share some common features. And the optimal meshes give rates of convergence bounded by |log()| as 0 and N is given, which are shown to be sharp by numerical tests.     

Choosing reference classes and building provisional models

A well-known problem in default logic is the ability of naive reasoners to explain bothg and ¬g from a set of observations. This problem is treated in at least two different ways within that camp.One approach is examination of the various explanations and choosing among them on the basis of various explanation comparators. A typical comparator is choosing the explanation that depends on the most specific observation, similar to the notion of narrowest reference class.Others examine default extensions of the observations and choose whatever is true in any extension, or what is true in all extensions or what is true in preferred extensions. Default extensions are sometimes thought of as acceptable models of the world that are discarded as more knowledge becomes available.We argue that the notions of specificity and extension lack clear semantics. Furthermore, we show that the problems these ideas were supposed to solve can be handled easily within a probabilistic framework.     

Automated Synthesis of Recursive Programs from a ∀∃ Logical Specification

The specification of a function is often given by a logical formula, called a -formula, of the following form: xy(x,y). More precisely, a specification is given in the context of a certain theory E and is stated by the judgment E xy (x,y).In this paper, we consider the case in which E is an equational theory. It is divided into two parts. In the first part, we develop a theory for the automated proof of such judgments in the initial model ofE . The validity in the initial model means that we consider not only equational theorems but also inductive ones. From our theory we deduce an automated method for the proof of a class of such judgments. In the second part, we present an automatedmethod for program synthesis. We show how the previous proof method can be used to generate a recursive program for a function f that satisfies a judgment E x (x, f(x)).We illustrate our method with the automated synthesis of some recursive programs on domains such as integers and lists. Finally, we describe our system LEMMA, which is an implementation in Common Lisp of these new methods.