Search

In this paper we analyze and implement a second-order-in-time numerical scheme for the three-dimensional phase field crystal (PFC) equation. The numerical scheme was proposed in Hu et al. (2009), with the unique solvability and unconditional energy stability established. However, its convergence analysis remains open. We present a detailed convergence analysis in this article, in which the maximum norm estimate of the numerical solution over grid points plays an essential role. Moreover, we outline the detailed multigrid method to solve the highly nonlinear numerical scheme over a cubic domain, and various three-dimensional numerical results are presented, including the numerical convergence test, complexity test of the multigrid solver and the polycrystal growth simulation. [ABSTRACT FROM AUTHOR]

Abstract: In previous papers, we introduced a new reasoning method based on quantifying linguistic domains, established a new fuzzy control algorithm, called hedge-algebras-based controller (HAC), and applied it to solve some fuzzy control problems. The HAC does not require fuzzy sets to provide the semantics of the linguistic terms used in the fuzzy rule system rather the semantics is obtained through the semantically quantifying mappings (SQMs). It was shown that the new method is very effective, i.e. for these problems it is always able to efficiently control the process toward the stable state. In the algebraic approach, the design of an HAC leads to the determination of the parameters of SQMs, which are the fuzziness measure of primary terms and linguistic hedges occurring in the fuzzy model, and the weights of a weighted averaging operator. However, there exists another problem, namely, how one can determine the optimal parameters of the method. In the present paper, we improved the HAC''s design by adding an optimal step that aims to find the optimal parameters of HAC using a genetic algorithm (GA). To show the effectiveness of the proposed method, we apply it to solve again the inverted pendulum problem and the problem of holding an object on a “hill”. The results demonstrate the good performance of the designed HAC. [Copyright &y& Elsevier]

Abstract: This paper proposes an improvement of an efficient multiobjective optimization algorithm, Non-dominated Sorting Genetic Algorithm II, NSGA-II, that has been here applied to solve the problem of optimal capacitors placement in distribution systems. The studied improvement involves the Crowded Comparison Operator and modifies it in order to handle several constraints. The problem of optimal location and sizing of capacitor banks for losses reduction and voltage profile flattening in medium voltage (MV) automated distribution systems is a difficult combinatorial constrained optimization problem which is deeply studied in literature. In this paper, the efficiency of the proposed Crowded Comparison Operator, CCO1, is compared to the efficiency of another Crowded Comparison Operator, CCO2, whose definition derives from the constraint-domination principle proposed by Deb et al. The two operators are tested on difficult test problems as well as on the optimal capacitors placement problem. [Copyright &y& Elsevier]

For a graph let , and denote its independence number, matching number, and vertex cover number, respectively. If or, equivalently, , then is a König–Egerváry graph. In this paper we give a new characterization of König–Egerváry graphs. [ABSTRACT FROM AUTHOR]

Abstract: An extended formulation of a polytope  is a system of linear inequalities and equations that describe some polyhedron which can be projected onto . Extended formulations of small size (i.e., number of inequalities) are of interest, as they allow to model corresponding optimization problems as linear programs of small sizes. In this paper, we describe several aspects and new results on the main known approach to establish lower bounds on the sizes of extended formulations, which is to bound from below the number of rectangles needed to cover the support of a slack matrix of the polytope. Our main goals are to shed some light on the question how this combinatorial rectangle covering bound compares to other bounds known from the literature, and to obtain a better idea of the power as well as of the limitations of this bound. In particular, we provide geometric interpretations (and a slight sharpening) of Yannakakis’ (1991) [35] result on the relation between minimal sizes of extended formulations and the nonnegative rank of slack matrices, and we describe the fooling set bound on the nonnegative rank (due to Dietzfelbinger et al. (1996) [7]) as the clique number of a certain graph. Among other results, we prove that both the cube as well as the Birkhoff polytope do not admit extended formulations with fewer inequalities than these polytopes have facets, and we show that every extended formulation of a -dimensional neighborly polytope with vertices has size . [Copyright &y& Elsevier]

Abstract: Let denote the largest possible size among all -OOCs. An -OOC with codewords is said to be optimal. In this paper, the exact value of is determined. Equivalently, the size of an optimal optical orthogonal code is calculated. [Copyright &y& Elsevier]

Abstract: The traveling salesman problem is to find a minimum cost (weight) path for a given set of cities (vertices) and roads (edges). The path must start at a specified city and end there after going through all the other given cites only once. It is a classical NP-complete problem in graph theory. In this paper, we consider a DNA procedure for solving the traveling salesman problem in the Adleman–Lipton model. The procedure works in steps for the traveling salesman of an edge-weighted graph with n vertices. [Copyright &y& Elsevier]

Abstract: Given a graph with nonnegative costs defined on edges, a positive integer , and a collection of terminal sets , where each is a subset of , the Generalized -Multicut problem asks to find a set of edges at the minimum cost such that its removal from cuts at least terminal sets in . A terminal subset is cut by if all terminals in are disconnected from one another by removing from . This problem is a generalization of the -Multicut problem and the Multiway Cut problem. The famous Densest -Subgraph problem can be reduced to the Generalized -Multicut problem in trees via an approximation preserving reduction. In this paper, we first give an -approximation algorithm for the Generalized -Multicut problem when the input graph is a tree. The algorithm is based on a mixed strategy of LP-rounding and greedy approach. Moreover, the algorithm is applicable to deal with a class of NP-hard partial optimization problems. As its extensions, we then show that the algorithm can be used to give -approximation for the Generalized -Multicut problem in undirected graphs and -approximation for the -Forest problem. [Copyright &y& Elsevier]

Abstract: During the last decade, significant progress has been made in solving the Protein Threading Problem (PTP). However, all previous approaches to PTP only perform global sequence–structure alignment. This obvious limitation is in clear contrast with the “world of sequences”, where local sequence–sequence alignments are widely used to find functionally important regions in families of proteins. This paper presents a novel approach to PTP which allows to align a part of a protein structure onto a protein sequence in order to detect local similarities. We show experimentally that such local sequence–structure alignments improve the quality of the prediction. Our approach is based on Mixed Integer Programming (MIP) which has been shown to be very successful in this domain. We describe five MIP models for local sequence–structure alignments, compare and analyze their performances by using ILOG CPLEX 10 solver on a benchmark of proteins. [Copyright &y& Elsevier]

Abstract: For a connected graph , the restricted edge-connectivity is defined as the minimum cardinality of an edge-cut over all edge-cuts such that there are no isolated vertices in . A graph is said to be -optimal if , where is the minimum edge-degree in defined as , denoting the degree of a vertex . The main result of this paper is that graphs with odd girth and finite even girth of diameter at most are -optimal. As a consequence polarity graphs are shown to be -optimal. [Copyright &y& Elsevier]

Abstract: The Minimum Vertex Cover (MVC) problem is a well-known combinatorial optimization problem of great importance in theory and applications. In recent years, local search has been shown to be an effective and promising approach to solve hard problems, such as MVC. In this paper, we introduce two new local search algorithms for MVC, called EWLS (Edge Weighting Local Search) and EWCC (Edge Weighting Configuration Checking). The first algorithm EWLS is an iterated local search algorithm that works with a partial vertex cover, and utilizes an edge weighting scheme which updates edge weights when getting stuck in local optima. Nevertheless, EWLS has an instance-dependent parameter. Further, we propose a strategy called Configuration Checking for handling the cycling problem in local search. This is used in designing a more efficient algorithm that has no instance-dependent parameters, which is referred to as EWCC. Unlike previous vertex-based heuristics, the configuration checking strategy considers the induced subgraph configurations when selecting a vertex to add into the current candidate solution. A detailed experimental study is carried out using the well-known DIMACS and BHOSLIB benchmarks. The experimental results conclude that EWLS and EWCC are largely competitive on DIMACS benchmarks, where they outperform other current best heuristic algorithms on most hard instances, and dominate on the hard random BHOSLIB benchmarks. Moreover, EWCC makes a significant improvement over EWLS, while both EWLS and EWCC set a new record on a twenty-year challenge instance. Further, EWCC performs quite well even on structured instances in comparison to the best exact algorithm we know. We also study the run-time behavior of EWLS and EWCC which shows interesting properties of both algorithms. [Copyright &y& Elsevier]

Abstract: This paper presents a variant of the asymmetric traveling salesman problem (ATSP) in which the traveling time between each pair of cities is represented by an interval of values (wherein the actual travel time is expected to lie) instead of a fixed (deterministic) value as in the classical ATSP. Here the ATSP (with interval objective) is formulated using the usual interval arithmetic. To solve the interval ATSP (I-ATSP), a genetic algorithm with interval valued fitness function is proposed. For this purpose, the existing revised definition of order relations between interval numbers for the case of pessimistic decision making is used. The proposed algorithm is based on a previously published work and includes some new features of the basic genetic operators. To analyze the performance and effectiveness of the proposed algorithm and different genetic operators, computational studies of the proposed algorithm on some randomly generated test problems are reported. [Copyright &y& Elsevier]

Abstract: It is a common task to construct the reviewer group with diverse background between reviewers. This task is complicated considering the multiple criteria and sizable reviewers and groups. However, it has not been clearly addressed in the current studies. This paper investigates this problem and proposes a solution approach. In our study, this problem is firstly formulated as an integrated model that covers the situations of different group number and group size. Then, considering the computational difficulties of solving this model, the grouping genetic algorithm hybridizing the local neighborhood search heuristic is proposed. In the grouping genetic algorithm, the initialization, crossover and mutation are designed according to our problem’s characteristics. Extensive numerical experiments show that the proposed algorithm is computationally efficient. Moreover, the application of the proposed algorithm on a case from NSFC also indicates its effectiveness for practical problems. [ABSTRACT FROM AUTHOR]

Abstract: The minimum Euclidean distance is a fundamental quantity for block coded phase shift keying (PSK). In this paper we improve the bounds for this quantity that are explicit functions of the alphabet size , block length and code size . For , we improve previous results by introducing a general inner distance measure allowing different shapes of a neighborhood for a codeword. By optimizing the parameters of this inner distance measure, we find sharper bounds for the outer distance measure, which is Euclidean. The proof is built upon the Elias critical sphere argument, which localizes the optimization problem to one neighborhood. We remark that any code with that fulfills the bound with equality is best possible in terms of the minimum Euclidean distance, for given parameters and . This is true for many multilevel codes. [Copyright &y& Elsevier]

Abstract: The solution of routing problems with soft time windows has valuable practical applications. Soft time window solutions are needed when: (a) the number of routes needed for hard time windows exceeds the number of available vehicles, (b) a study of cost-service tradeoffs is required, or (c) the dispatcher has qualitative information regarding the relative importance of hard time-window constraints across customers. This paper proposes a new iterative route construction and improvement algorithm to solve vehicle routing problems with soft time windows. Due to its modular and hierarchical design, the solution algorithm is intuitive and able to accommodate general cost and penalty functions. Experimental results indicate that the average run time performance is of order O(n 2). The solution quality and computational time of the new algorithm has been compared against existing results on benchmark problems. The presented algorithm has improved thirty benchmark problem solutions for the vehicle routing problems with soft time windows. [Copyright &y& Elsevier]

Abstract: The paper addresses the problem associated with the optimal wind park design. A combinatorial optimization model for wind turbines type and number choice and placement considering the given wind conditions and wind park area is developed. The wind park investment costs and the total power relation as function of wind turbines number and type are used as optimization criteria. The optimization problem is formulated as a single criterion mixed-integer nonlinear discrete combinatorial task. The different wind park conditions are introduced into optimization tasks formulation as variables relations and restrictions. Two basic wind directions cases are taken into consideration – uniform and predominant wind directions for two wind park area shapes – square and rectangular. The developed wind park design approach was tested numerically by solving of different optimization tasks formulations based on wind turbines real parameters data. The numerical testing shows the applicability of the developed optimization approach. Using it will help to find mathematically reasoned wind turbines choice as contradiction to the heuristic approaches. [Copyright &y& Elsevier]

Abstract: Flexible job-shop scheduling problem (FJSP) is an extension of the classical job-shop scheduling problem. FJSP is NP-hard and mainly presents two difficulties. The first one is to assign each operation to a machine out of a set of capable machines, and the second one deals with sequencing the assigned operations on the machines. This paper proposes a parallel variable neighborhood search (PVNS) algorithm that solves the FJSP to minimize makespan time. Parallelization in this algorithm is based on the application of multiple independent searches increasing the exploration in the search space. The proposed PVNS uses various neighborhood structures which carry the responsibility of making changes in assignment and sequencing of operations for generating neighboring solutions. The results obtained from the computational study have shown that the proposed algorithm is a viable and effective approach for the FJSP. [Copyright &y& Elsevier]

Abstract: In this paper, we are interested in linearization techniques for the exact solution of the Unconstrained Quadratic (0-1) Problem. Our purpose is to propose “economical” linear formulations. We first extend current techniques in a general linearization framework containing many other schemes and propose a new linear formulation. Numerical results comparing classical, Glover’s and the new linearization are reported. [Copyright &y& Elsevier]

Abstract: In this paper, one novel genetic algorithm dynamic chain-like agent genetic algorithm (CAGA) is proposed for solving global numerical optimization problem and feature selection problem. The CAGA combines the chain-like agent structure with dynamic neighboring genetic operators to get higher optimization capability. An agent in chain-like agent structure represents a candidate solution to the optimization problem. Any agent interacts with neighboring agents to evolve. With dynamic neighboring genetic operators, they compete and cooperate with their neighbors, and can use knowledge to increase energies. Global numerical optimization problem and feature selection problem are the most important problems for evolutionary algorithm, especially for genetic algorithm. Hence, the experiments of global numerical optimization and feature selection are necessary to verify the performance of genetic algorithms. Corresponding experiments have been done and show that CAGA is suitable for real coding and binary coding optimization problems, and has more precise and more stable optimization results. [Copyright &y& Elsevier]

Abstract: Gene selection, a significant preprocessing of the discriminant analysis of microarray data, is to select the most informative genes from the whole gene set. In this paper, an efficient mutual information-based gene selection algorithm (MIGS) is proposed, in which genes are sequentially forward selected according to an approximate measure of the mutual information between the class and the selected genes. In order to improve the efficiency of the MIGS, an effective pruning strategy is introduced in the selection procedure as well as the employment of Parzen window density estimation technique. Extensive experiments are conducted on three public gene expression datasets and the experimental results confirm the efficiency and effectiveness of the algorithm. Though the computational cost of MIGS-Pruning increases with the number of selected genes, it still has good performance applied in the microarray problems. [Copyright &y& Elsevier]

Abstract: This paper deals with the use of importance measures (IMs) for the risk-informed optimization of system design and operation. It builds on previous work by the authors in which IMs are incorporated in the formulation of a genetic algorithm (GA) multi-objective optimization problem to drive the design towards a solution which is ‘balanced’ in the importance values of the components. This allows designing systems that are optimal from the point of view of economics and safety, without excessively low- or unnecessarily high-performing components. Different definitions of IMs quantify the risk- or safety-significance of components according to specific views of their role in the system: depending on the optimization problem at hand (e.g. system design optimization and/or maintenance strategy optimization) the use of one IM definition as a balancing criterion may be more appropriate than another. In this regard, a comparison of the Fussell–Vesely (FV), Birnbaum (B) and risk achievement worth (RAW) IMs is performed, with respect to their appropriateness for the optimization of test/maintenance intervals. The RAW is found inappropriate for the purpose, since this measure relates to the defense of the system against the failure of components, which is independent on how often the component is tested. Instead, the use of the FV or B measures allows allocating test/maintenance activities according to the importance of the components they relate to, in agreement with the principle of the risk-informed philosophy of avoiding unnecessary regulatory burdens and defining more efficient inspection and maintenance activities. [Copyright &y& Elsevier]

Abstract: The purpose of functional tolerancing process is to define the geometrical specifications (tolerances) of parts ensuring functional requirements. An important distinction in tolerance process is that engineers are more commonly faced with the problem of tolerance synthesis rather than tolerance analysis. In tolerance analysis the parts tolerances are all known and the resulting geometrical requirement respect is calculated. In tolerance synthesis, on the other hand, the geometrical requirement is known from design requirements, whereas the magnitudes of the parts tolerances to meet these requirements are unknown. In this paper, we focus on the gear tolerances, and we propose an approach based statistical analysis for tolerance analysis and genetic algorithm for tolerance synthesis. Usually, statistical tolerance analysis uses a relationship between parts deviations and functional characteristics. In the case of tolerance analysis of gears, thus relationship is not available in analytic form, the determination of a functional characteristic (kinematic error,…) involves a numerical simulation. Therefore the Monte Carlo simulation, as the simplest and effectual method, is introduced into the frame. Moreover, to optimize the tolerance cost, genetic algorithm is improved. Indeed, this optimization problem is so complex that for traditional optimization algorithms it may be difficult or impossible to solve it because the objective function is not available in analytic form. For the evaluation of the fitness of each individual based on Monte Carlo simulation, the number of samples is the key of precision. By a large number of samples, the precision can be improved, but the computational cost will be increased. In order to reduce the computational cost of this optimization based on Monte Carlo simulation and genetic algorithms, the strategy is to adopt different precision of fitness; different numbers of samples during the optimization procedure are introduced into our algorithms. [Copyright &y& Elsevier]

Abstract: The thresholding process based on the optimization of one criterion only does not work well for a lot of images. In many cases, even when equipped with the optimal value of the threshold of its single criterion, the thresholding program does not produce a satisfactory result. In this paper, we propose to use the multiobjective optimization approach to find the optimal thresholds of three criteria: the within-class criterion, the entropy and the overall probability of error criterion. In addition we develop a new variant of simulated annealing adapted to continuous problems to solve the Gaussian curve-fitting problem. Some examples of test images are presented to compare our segmentation method, based on the multiobjective optimization approach, with that of four competing methods: Otsu method, Gaussian curve fitting-based method, valley-emphasis-based method and two-dimensional Tsallis entropy-based method. From the viewpoints of visualization, object size and image contrast, our experimental results show that the thresholding method based on multiobjective optimization performs better than the competing methods. [Copyright &y& Elsevier]

Personalisation of web information systems (WISs) means customisation of the presented data content to the needs of users, restricting the available functionality to the goals and preferences of users, and tailoring the web presentation according to used devices and style options. This paper primarily concentrates on the customisation of functionality by making all those operations available to a user that are needed to achieve a specified goal, and by organising them in an action scheme called plot that is in accordance with the behavioural preferences of the user. Plots are formalised by algebraic expressions in Kleene algebras with tests (KATs). Then personalisation can be formalised as an optimisation problem with equational preference rules, for which a term rewriting approach is proposed. In a second step the approach is extended to conditional term rewriting thereby dispensing with the particular need to associate preference rules with user profiles. Finally, the approach is refined by taking content specifications via extended views and abstract programs on these views into account. This leads us to reformulating the personalisation problem in higher-order dynamic logic. [Copyright &y& Elsevier]

Abstract: In this paper, let the backorder rate be a control variable to widen applications of Wu and Tsai’s model [J.W. Wu, H.Y. Tsai, Mixture inventory model with back orders and lost sales for variable lead time demand with the mixtures of normal distribution, International Journal of Systems Science 32 (2001) 259–268.]. And, we also assume that the backorder rate is dependent on the length of lead time through the amount of shortages. In addition, we assume that the lead time demand follows a mixture of normal distributions, and then we relax the assumption about the form of the mixture of distributions for the lead time demand and apply the minimax distribution free procedure to solve the problem. Further, instead of having a stock-out term in the objective function, a service level constraint is added to the models. Finally, we develop two computational algorithms to find the optimal order quantity and the optimal lead time. Furthermore, two numerical examples are also given to illustrate the results. [Copyright &y& Elsevier]

Abstract: Stochastic searching methods have been applied widely to areas such as continuous and combinatorial optimization problems in a number of disciplines. Many existing methods solve these problems by navigating on the surface of the possibly rugged landscape. This kind of navigation is not very effective because the property of the landscape at different resolutions can be very different. Time spent at the beginning of the search on the detailed part of the landscape is often useless. Appropriate searching strategies should be adopted at different resolutions. In this paper, we propose a new probabilistic searching model for global optimization. The main contributions of the model are (1) to provide a basis for resolution control and smoothing of search space and (2) to introduce continuous memory into stochastic search. The basis of resolution control is achieved by dividing the search space into a finite number of n-dimensional partitions structurally. The number of partitions governs the resolution of the search space. The more the partitions, the finer is the search space and the more detailed and rugged is the landscape. The benefits are twofold. First, the rugged landscape problem can be smoothed, because the ruggedness is a matter of the number of partitions. Hence, the difficulty in search due to the ruggedness of the landscape can be controlled. Second, it provides a basis to implement algorithms that may change the ‘view’ of the landscape during the search process because we can dynamically divide the search space accordingly. Another important feature that we use is continuous memory. Throughout the search process, searching experience is continuously accumulated in order to shape the global picture of the search space guiding the future searching direction. We present results on the algorithm performance in handling numerical function optimization. The empirical results show that our new model is comparable to, and in many cases performs better than, that of the other advanced methods in terms of solution quality and computation required. [Copyright &y& Elsevier]

Abstract: Research on a new metaheuristic for optimization is often initially focused on proof-of-concept applications. It is only after experimental work has shown the practical interest of the method that researchers try to deepen their understanding of the method''s functioning not only through more and more sophisticated experiments but also by means of an effort to build a theory. Tackling questions such as “how and why the method works’’ is important, because finding an answer may help in improving its applicability. Ant colony optimization, which was introduced in the early 1990s as a novel technique for solving hard combinatorial optimization problems, finds itself currently at this point of its life cycle. With this article we provide a survey on theoretical results on ant colony optimization. First, we review some convergence results. Then we discuss relations between ant colony optimization algorithms and other approximate methods for optimization. Finally, we focus on some research efforts directed at gaining a deeper understanding of the behavior of ant colony optimization algorithms. Throughout the paper we identify some open questions with a certain interest of being solved in the near future. [Copyright &y& Elsevier]