A problem reduction based approach to discrete optimization algorithm design

The paper presents a novel approach to formal algorithm design for a typical class of discrete optimization problems. Using a concise set of program calculation rules, our approach reduces a problem into subproblems with less complexity based on function decompositions, constructs the problem reduction graph that describes the recurrence relations between the problem and subproblems, from which a provably correct algorithm can be mechanically derived. Our approach covers a large variety of algorithms and bridges the relationship between conventional methods for designing efficient algorithms (including dynamic programming and greedy) and some effective methods for coping with intractability (including approximation and parameterization).     

A tabu search approach to an urban transport problem in northern Spain

In this work we analyze an urban transport problem that the City Council of Burgos, a city in northern Spain, has posed to the authors. Given a fleet of buses and drivers, the problem consists in designing routes and assigning buses to the routes such that the service level is optimized. The optimality of the service level is measured in terms of the waiting time at the bus stops and the duration of the trip. Thus, the problem comprises two decision levels (route design and bus assignment) and differs from other urban transport models found in the literature. In order to solve the problem, we propose two algorithms: one with a local search strategy and another with a tabu search strategy. In both cases, the solutions of the two decision levels are modified in alternating steps. The proposed algorithms obtained significantly better results than the tools currently applied by the transport authorities. In addition, the solutions obtained are very robust with respect to variations on demand, as shown by the experiments.     

A GRASP approach to the container-loading problem

The container-loading problem aims to determine the arrangement of items in a container. We present GRMODGRASP, a new algorithm for the CLP based on the GRASP (greedy randomized adaptive search procedure) paradigm. We evaluate GRMODGRASP'S performance in terms of volume use and load stability and by comparing it with nine well-known algorithms. Our approach produces solutions that surpass other approaches' solutions in terms of volume use and cargo stability.     

A lazy approach to symmetry reduction

Symmetry reduction is a technique to counter state explosion for systems with regular structure. It relies on idealistic assumptions about indistinguishable components, which in practice may only be similar. In this article, we present a flexible, lazy approach to symmetry-reducing a structure without any prior knowledge about its global symmetry. Instead of a-priori checking for compliance with symmetry conditions, each encountered state is annotated on the fly with information about how symmetry is violated along the path leading to it. The method naturally favors “very symmetric” systems: more similarity among the components leads to greater compression. A notion of subsumption is used to prune the annotated search space during exploration. Previous solutions to the approximate symmetry reduction problem are restricted to specific types of asymmetry, such as up to bisimilarity, or incur a large overhead, either during preprocessing of the structure or during the verification run. In contrast, the strength of our method is its balance between ease of implementation and algorithmic flexibility. We include analytic and experimental results that witness its efficiency.     

A multiple criteria approach to the location-allocation problem

This paper presents a model for the location-allocation problem which considers both qualitative and quantitative factors. The proposed model is based on a weighted objective function. The weights are determined on the basis of the relative importance assigned to the qualitative factors. Applications of the proposed method to real-world problems are discussed and two examples are presented to describe the proposed method. The familiar transportation method of linear programming is used to obtain optimal solutions. Solutions for the examples were compared with those obtained from using only the quantitative factor (transportation cost) and the corresponding results are discussed.     

A stochastic realization approach to the smoothing problem

The purpose of this paper is to develop a theory of smoothing for finite dimensional linear stochastic systems in the context of stochastic realization theory. The basic idea is to embed the given stochastic system in a class of similar systems all having the same output process and the same Kalman-Bucy filter. This class has a lattice structure with a smallest and a largest element; these two elements completely determine the smoothing estimates. This approach enables us to obtain stochastic interpretations of many important smoothing formulas and to explain the relationship between them.     

A neural network approach to the classification problem

The task of classifying observations into known groups is a common problem in decision making. A wealth of statistical approaches, commencing with Fisher's linear discriminant function, and including variations to accomodate a variety of modeling assumptions, have been proposed. In addition, nonparametric approaches based on various mathematical programming models have also been proposed as solutions. All of these proposed aolutions have performed well when conditions favorable to the specific model are present. The modeler, therefore, can usually be assured of a good solution to his problem of he chooses a model which fits his situation. In this paper, the performance of a neural network as a classifier is evaluated. It is found that the performance of the neural network is comparable to the best of otheother methods under a wide variety of modeling assumptions. The use of neural networks as classifiers thus relieves the modeler of testing assumptions which would otherwise be critical to the performance of the usual classification techniques.     

A parallel approach to the Eulerian cycle problem

A novel parallel approach for constructing Eulerian cycles of a given graph is presented. The proposed approach constitutes a combination of genetic algorithms and artificial neural networks. By tackling the Eulerian cycle problem as a constraint optimization problem, Eulerian cycle existence is determined, and either Eulerian cycles (if they exist) or paths encompassing the greatest possible number of edges (maximal traversal of edges, with edges traversed no more than once) are consistently constructed. Apart from being of theoretical interest, Eulerian cycle existence and construction have recently found significant applications in such areas of VLSI circuit design, RAM fault detection, and CPU access. © 2002 Wiley Periodicals, Inc.     

A knowledge-based approach to the iris segmentation problem

This paper describes a knowledge-based approach to the problem of locating and segmenting the iris in images showing close-up human eyes. This approach is inspired in the expert system’s paradigm but, due the specific processing problems associated with image analysis, uses direct encoding of the “decision rules”, instead of a classic, formalized, knowledge base. The algorithm involves a succession of phases that deal with image pre-processing, pupil location, iris location, combination of pupil and iris, eyelids detection, and filtering of reflections. The development was iterative, based on successive improvements tested over a set of training images. The results that were achieved indicate that this global approach can be useful to solve image analysis problems over which human “experts” have better performance than the present computer-based solutions.     

A new approach to the surface intersection problem

Planar cut and surface intersection software is an important part of any computer aided design system. This paper presents two new ideas in the numerical solution of such problems. The first is the notion of topology resolution. In this process, the structure of the intersection curves, including the identification of closed interior loops, is determined prior to their actual numerical solution. The second idea is to compute the intersection curves as the numerical solution of a differential algebraic equation, yielding intersection curves which are (nearly) parametrized by arclength.     

A Bayesian approach to the stereo correspondence problem

I present a probabilistic approach to the stereo correspondence problem. Rather than trying to find a single solution in which each point in the left retina is assigned a partner in the right retina, all possible matches are considered simultaneously and assigned a probability of being correct. This approach is particularly suitable for stimuli where it is inappropriate to seek a unique partner for each retinal position--for instance, where objects occlude each other, as in Panum's limiting case. The probability assigned to each match is based on a Bayesian analysis previously developed to explain psychophysical data (Read, 2002). This provides a convenient way to incorporate constraints that enable the ill-posed correspondence problem to be solved. The resulting model behaves plausibly for a variety of different stimuli.     

A learning approach to the bandwidth multicolouring problem

In this article, a generalisation of the vertex colouring problem known as bandwidth multicolouring problem (BMCP), in which a set of colours is assigned to each vertex such that the difference between the colours, assigned to each vertex and its neighbours, is by no means less than a predefined threshold, is considered. It is shown that the proposed method can be applied to solve the bandwidth colouring problem (BCP) as well. BMCP is known to be NP-hard in graph theory, and so a large number of approximation solutions, as well as exact algorithms, have been proposed to solve it. In this article, two learning automata-based approximation algorithms are proposed for estimating a near-optimal solution to the BMCP. We show, for the first proposed algorithm, that by choosing a proper learning rate, the algorithm finds the optimal solution with a probability close enough to unity. Moreover, we compute the worst-case time complexity of the first algorithm for finding a 1/(1–?) optimal solution to the given problem. The main advantage of this method is that a trade-off between the running time of algorithm and the colour set size (colouring optimality) can be made, by a proper choice of the learning rate also. Finally, it is shown that the running time of the proposed algorithm is independent of the graph size, and so it is a scalable algorithm for large graphs. The second proposed algorithm is compared with some well-known colouring algorithms and the results show the efficiency of the proposed algorithm in terms of the colour set size and running time of algorithm.     

A new approach to solve the k-server problem based on network flows and flow cost reduction

This paper is concerned with two algorithms for solving the k-server problem: the optimal off-line algorithm (OPT) and the on-line work function algorithm (WFA). Both algorithms are usually implemented by network flow techniques including the flow augmentation method. In the paper a new implementation approach is proposed, which is again based on network flows, but uses simpler networks and the cost reduction method. The paper describes in detail the corresponding new implementations of OPT and WFA, respectively. All necessary correctness proofs are given. Also, experiments are presented, which confirm that the new approach assures faster execution of both algorithms.     

A recursive deconvolution approach to disturbance reduction

Active noise control (ANC) uses an estimate of the noise affecting a system in order to remove its effect from the output. In some applications, it is possible to directly measure the noise and a feedforward compensator can be used. Other applications require instead that the noise be estimated from its effect on the system. This results in an adaptive feedback ANC, see a previous paper by Gan and Kuo. The identification of the disturbance from the output of the linear system is a deconvolution problem. In this paper, we study a deconvolution technique for the active reduction of the influence of the disturbance on the output of a linear control system. The regulator that we present does not affect the behavior of the system in the absence of disturbances.     

A realization approach to stochastic model reduction

The problem of discrete-time stochastic model reduction (approximation) is considered. Using the canonical correlation analysis approach of Akaike (1975), a new order-reduction algorithm is developed. Furthermore, it is shown that the inverse of the reduced-order realization is asymptotically stable. Next, an explicit relationship between canonical variables and the linear least-squares estimate of the state vector is established. Using this, a more direct approach for order reduction is presented, and also a new design for reduced-order Kalman filters is developed. Finally, the uniqueness and symmetry properties for the new realization—the balanced stochastic realization—along with a simulation result, are presented.     

A transformation approach to stochastic model reduction

A new and direct approach to stochastic model reduction is developed. The order reduction algorithm is obtained by establishing an equivalence between canonical correlation analysis and solutions to algebraic Riccati equations. Also the concept of balanced stochastic realization (BSR) plays a fundamental role. Asymptotic stability of the reduced-order realization is established, and spectral domain interpretations for the BSR are given.