Shelah's stability spectrum and homogeneity spectrum in finite diagrams

We present Saharon Shelah's Stability Spectrum and Homogeneity Spectrum theorems, as well as the equivalence between the order property and instability in the framework of Finite Diagrams. Finite Diagrams is a context which generalizes the first order case. Localized versions of these theorems are presented. Our presentation is based on several papers; the point of view is contemporary and some of the proofs are new. The treatment of local stability in Finite Diagrams is new. Received: 12 November 1999 / Revised version: 21 July 2000 / Published online: 3 October 2001     

A block method for the numerical integration of stiff systems of ordinary differential equations

A new approach to the approximate numerical integration of stiff systems of first order ordinary differential equations is developed. In this approach several different formulae are applied in a well defined cyclic order to produce highly accurate integration schemes with infinite regions of absolute stability. The efficiency of these new algorithms, compared with that of certain existing ones, is demonstrated for some particular test problems.     

Evaluation of the multiobjective ant colony algorithm performances on biobjective quadratic assignment problems

The difficulty of resolving the multiobjective combinatorial optimization problems with traditional methods has directed researchers to investigate new approaches which perform better. In recent years some algorithms based on ant colony optimization (ACO) metaheuristic have been suggested to solve these multiobjective problems. In this study these algorithms have been reported and programmed both to solve the biobjective quadratic assignment problem (BiQAP) instances and to evaluate the performances of these algorithms. The robust parameter sets for each 12 multiobjective ant colony optimization (MOACO) algorithms have been calculated and BiQAP instances in the literature have been solved within these parameter sets. The performances of the algorithms have been evaluated by comparing the Pareto fronts obtained from these algorithms. In the evaluation step, a multi significance test is used in a non hierarchical structure, and a performance metric (P metric) essential for this test is introduced. Through this study, decision makers will be able to put in the biobjective algorithms in an order according to the priority values calculated from the algorithms’ Pareto fronts. Moreover, this is the first time that MOACO algorithms have been compared by solving BiQAPs.     

Minimum Inter-Particle Distance at Global Minimizers of Lennard-Jones Clusters

In computer simulations of molecular conformation and protein folding, a significant part of computing time is spent in the evaluation of potential energy functions and force fields. Therefore many algorithms for fast evaluation of potential energy functions and force fields are proposed in the literature. However, most of these algorithms assume that the particles are uniformly distributed in order to guarantee good performance. In this paper, we prove that the minimum inter-particle distance at any global minimizer of Lennard-Jones clusters is bounded away from zero by a positive constant which is independent of the number of particles. As a by-product, we also prove that the global minimum of an n particle Lennard-Jones cluster is bounded between two linear functions. Our first result is useful in the design of fast algorithms for potential function and force field evaluation. Our second result can be used to decide how good a local minimizer is.     

Supply chain performance evaluation using fuzzy network data envelopment analysis: a case study in automotive industry

Supply chain performance evaluation problems are evaluated using data envelopment analysis. This paper proposes a fuzzy network epsilon-based data envelopment analysis for supply chain performance evaluation. In the common data envelopment analysis models which are used for evaluation of decision-maker units efficiency, there are several inputs and outputs. One of the bugs of such models is that the intermediate products and linking activities are overlooked. Considering these intermediate activities and products, the current study evaluates the performance of decision-maker units in an automotive supply chain. There are ten decision-maker units in the supply chain in which there are three suppliers, two manufacturers, two distributors, and four customers. Moreover, the overall efficiency of input-oriented (input-based) model and input-oriented divisional efficiency are calculated. In order to improve the efficiencies, the projections onto the frontiers are obtained by using the outputs of the solved model and Lingo software. In order to show the applicability of the proposed model, it is applied on automotive industry, as a case study, to evaluate supply chain performance. Then, the overall efficiencies of DMUs and each sections (divisions) of DMUs were calculated separately. Therefore, every organization can apply this evaluation method for improving the performance of alternative factors.

     

Markov Limid processes for representing and solving renewal problems

In this paper a new tool for simultaneous optimisation of decisions on multiple time scales is presented. The tool combines the dynamic properties of Markov decision processes with the flexible and compact state space representation of LImited Memory Influence Diagrams (Limids). A temporal version of Limids, TemLimids, is defined by adding time-related functions to utility nodes. As a result, expected discounted utility, as well as expected relative utility might be used as optimisation criteria in TemLimids. Optimisation proceeds as in ordinary Limids. A sequence of such TemLimids can be used to model a Markov Limid Process, where each TemLimid represents a macro action. Algorithms are presented to find optimal plans for a sequence of such macro actions. Use of algorithms is illustrated based on an extended version of an example from pig production originally used to introduce the Limid concept.     

The Locally Free Relatively Filtered Diagram as an Inductive Completion of a System of Choice

Guitart and Lair have established the existence of Locally Free Diagrams, which can be seen as a purely categorical version of the solution set condition, and of the Lowenheim–Skolem theorem. Their proof is based on a transfinite construction by saturation. An iterative principle is established, but the construction is not effective for every step. The thesis of Gerner contains a more effective proof for the existence of Locally Free Diagrams (with the restriction that the projective bases of the sketch S must all be finite). But the problem of lies in the impossibility to name concretely the elements of the Locally Free Diagrams. The present paper will provide a new construction of the Locally Free Diagram in which the effective and the non-effective part will be much more separated (again the projective bases must all be finite). This construction represents a notable improvement with regard to the proof of allowing the concrete designation of the elements ofthe Locally Free Diagrams. Furthermore we show that the construction is relatively filtered (i.e. satisfies the filtered-property).     

Amortized multi-point evaluation of multivariate polynomials

The evaluation of a polynomial at several points is called the problem of multi-point evaluation. Sometimes, the set of evaluation points is fixed and several polynomials need to be evaluated at this set of points. Several efficient algorithms for this kind of “amortized” multi-point evaluation have been developed recently for the special cases of bivariate polynomials or when the set of evaluation points is generic. In this paper, we extend these results to the evaluation of polynomials in an arbitrary number of variables at an arbitrary set of points. We prove a softly linear complexity bound when the number of variables is fixed. Our method relies on a novel quasi-reduction algorithm for multivariate polynomials, that operates simultaneously with respect to several orderings on the monomials.     

On per-iteration complexity of high order Chebyshev methods for sparse functions with banded Hessians

Some algorithms for unconstrained and differentiable optimization problems involve the evaluation of quantities related to high order derivatives. The cost of these evaluations depends widely on the technique used to obtain the derivatives and on some characteristics of the objective function: its size, structure and complexity. Functions with banded Hessian are a special case that we study in this paper. Because of their partial separability, the cost of obtaining their high order derivatives, subtly computed by the technique of automatic differentiation, makes High order Chebyshev methods more interesting for banded systems than for dense functions. These methods have an attractive efficiency as we can improve their convergence order without increasing significantly their algorithmic costs. This paper provides an analysis of the per-iteration complexities of High order Chebyshev methods applied to sparse functions with banded Hessians. The main result can be summarized as: the per-iteration complexity of a High order Chebyshev method is of order of the objective function’s. This theoretical analysis is verified by numerical illustrations.     

Evaluating computational efficiency: A stochastic approach

This paper introduces the use of stochastic models for the evaluation of relative computational efficiency of algorithms. Such an approach is used for the comparison of computational efficiency of three algorithms for quadratic programming.     

A Computational Study on Bounding the Makespan Distribution in Stochastic Project Networks

Due to the practical importance of stochastic project networks (PERT-networks), many methods have been developed over the past decades in order to obtain information about the random project completion time. Of particular interest are methods that provide (lower and upper) bounds for its distribution, since these aim at balancing efficiency of calculation with accuracy of the obtained information.We provide a thorough computational evaluation of the most promising of these bounding algorithms with the aim to test their suitability for practical applications both in terms of efficiency and quality. To this end, we have implemented these algorithms and compare their behavior on a basis of nearly 2000 instances with up to 1200 activities of different test-sets. These implementations are based on a suitable numerical representation of distributions which is the basis for excellent computational results. Particularly a distribution-free heuristic based on the Central Limit Theorem provides an excellent tool to evaluate stochastic project networks.     

Simple ingredients leading to very efficient heuristics for the maximum clique problem

Starting from an algorithm recently proposed by Pullan and Hoos, we formulate and analyze iterated local search algorithms for the maximum clique problem. The basic components of such algorithms are a fast neighbourhood search (not based on node evaluation but on completely random selection) and simple, yet very effective, diversification techniques and restart rules. A detailed computational study is performed in order to identify strengths and weaknesses of the proposed algorithms and the role of the different components on several classes of instances. The tested algorithms are very fast and reliable: most of the DIMACS benchmark instances are solved within very short CPU times. For one of the hardest tests, a new putative optimum was discovered by one of our algorithms. Very good performances were also shown on recently proposed and more difficult instances. It is important to remark that the heuristics tested in this paper are basically parameter free (the appropriate value for the unique parameter is easily identified and was, in fact, the same value for all problem instances used in this paper).     

Decomposition algorithms for locating minimal cuts in a network

This paper provides decomposition algorithms for locating minimal cuts in a large directed network. The main theorem provides several cases for the algorithms. In the worst case, it is shown that the efficiency of one of the proposed algorithms is of the same order as a no-decomposition algorithm. As in linear programming, the obvious advantage of the proposed decomposition procedure is its ability to potentially handle larger problems than a no-decomposition algorithm.     

A new approach to discrete stochastic optimization problems

Solving a discrete stochastic optimization problem involves two efforts: one is to sample and search the design space; and the other is to estimate the performance values of the sampled designs. When the amount of computational resources is limited, we need to know how to balance these two efforts in order to obtain the best result. In this paper, two performance measures which quantify the marginal contribution of the searching process as well as the performance evaluation process are proposed. Using these two measures, we recommend a framework that can dynamically allocate the computational resources to the search process and the performance evaluation process. Two algorithms based on the proposed framework are tested on several scenarios, and the results produced are very promising.     

Automatic grading of students' ALGOL programming

The report describes an experiment on automatic grading of student algorithms, using an ALGOL compiler. The experiment is based on an evaluation of the efficiency and logical completeness of the algorithms, not on their formal correctness, which is supposed to be checked in advance by the individual student. The technique used is to embed the student algorithms within a larger grading program structure, which supplies test cases and performs checks and evaluation. The complete text of such a grading program is given. The experience gained through the experiment, and suggestions for further developments, are discussed.     

A modified multi-criterion optimization genetic algorithm for order distribution in collaborative supply chain

Supply chain collaboration is prevalent in today’s business model, and has been recognized to be one of the important issues in improving competition strength. Order distribution is to determine which order should be allocated to which supplier, it plays a very important role in a collaborative supply chain, because different order distribution infers different benefit under different criteria. However, there is not much research on the order distribution methodology. This paper adopted a framework of a central coordination system, which is equipped with a multi-criteria genetic optimization feature. In the previous multi-criterion optimization genetic algorithm (MCOGA), the analytic hierarchy process (AHP) is deployed to evaluate the fitness values. In this paper, a modified MCOGA is proposed based on the technique for order preference by similarity to ideal solution (TOPSIS). There are two main parts, namely, searching and evaluation, in genetic algorithms. Compared with the MCOGA, the proposed method takes the advantage of less complexity in the evaluation stage. The numerical example of order distribution is used to illustrate the efficiency of the proposed method.     

Multi-level substructuring combined with model order reduction methods

In many fields of engineering problems linear time-invariant dynamical systems (LTI systems) play an outstanding role. They result for instance from discretizations of the unsteady heat equation and they are also used in optimal control problems. Often the order of LTI systems is a limiting factor, since it becomes easily very large. As a consequence these systems cannot be treated efficiently without model reduction algorithms. In this paper a new approach for the combination of model order reduction methods and recent multi-level substructuring (MLS) techniques is presented. Similar multi-level substructuring methods have already been applied successfully to huge eigenvalue problems up to several millions of degrees of freedom. However, the presented approach does not make use of a modal analysis like former algorithms. Instead the original system is decomposed in smaller LTI systems which are treated with recent model reduction methods. Furthermore, the error which is induced by this substructuring approach is analysed and numerical examples based on the Oberwolfach benchmark collection are given in this paper.     

A multiple local search algorithm for continuous dynamic optimization

Many real-world optimization problems are dynamic (time dependent) and require an algorithm that is able to track continuously a changing optimum over time. In this paper, we propose a new algorithm for dynamic continuous optimization. The proposed algorithm is based on several coordinated local searches and on the archiving of the optima found by these local searches. This archive is used when the environment changes. The performance of the algorithm is analyzed on the Moving Peaks Benchmark and the Generalized Dynamic Benchmark Generator. Then, a comparison of its performance to the performance of competing dynamic optimization algorithms available in the literature is done. The obtained results show the efficiency of the proposed algorithm.     

Generating efficient schedules for identical parallel machines involving flow-time and tardy jobs

This paper considers the problem of generating a set of efficient (non-dominated) schedules on identical parallel machines involving total flow-time and total number of tardy jobs. In view of the NP-hard nature of this problem, heuristic algorithms are proposed for its solution. Two evaluation methods that provide a scheme by which multiple non-dominated sets can be compared are described and used to compare the performance of the proposed algorithms. Results of several experiments demonstrate the capability of the proposed algorithms and evaluation methodologies to address the problem at hand.