A multiobjective GRASP–VND algorithm to solve the waste collection problem

In this paper, the waste collection problem (WCP) of a city in the south of Spain is addressed as a multiobjective routing problem that considers three objectives. From the company's perspective, the minimization of the travel cost is desired as well as that of the total number of vehicles. Additionally, from the employee's point of view, a set of balanced routes is also sought. Four variants of a multiobjective hybrid algorithm are proposed. Specifically, a GRASP (greedy randomized adaptive search procedure) with a VND (variable neighborhood descent) is combined. The best GRASP–VND algorithm found is applied in order to solve the real‐world WCP of a city in the south of Spain.     

Relation collection using Pollard special-q sieving to solve integer factorization and discrete logarithm problem

The strength of many security protocols lies on the computational intractability of the integer factorization and discrete logarithm problems. Currently, the best-known techniques employed are number field sieve (NFS) family of algorithms. They come under the class of sub-exponential time algorithms. This class of algorithms comprises of multiple steps. The relation collection (sieving step) is one of the computationally costly and highly memory-dependent phase of these algorithms. This paper discusses various ways to improve the efficiency of the relation collection phase by using parallelization techniques. Experiments have been carried out by using function field sieve, which is one of the NFS family algorithms, to show the computation efficiency of parallelization techniques along with the suitable sieving techniques and the key parameters. The result of our basic implementation is compared with the parallelized version of it. The result analysis depicts that the relation collection phase can be improved by using parallelization techniques up to fourfold.

     

Mark scan garbage collection on a distributed architecture

In any computer architecture designed for the evaluation of declarative languages, efficient reclamation of redundant (garbage) storage is essential. High performance, exploiting the inherent parallelism of such languages, is now typically achieved by parallel architectures, computational graphs thus being distributed across many processing elements.This paper describes a real-time mark-scan garbage collection algorithm for a distributed machine with local store. The algorithm allows collection on a per-process basis, and several collections may run concurrently and asynchronously. Both non real-time and real-time versions are provided.It is hoped to publish implementation results for the algorithm when such are available.     

Simple generational garbage collection and fast allocation

Generational garbage collection algorithms achieve efficiency because newer records point to older records; the only way an older record can point to a newer record is by a store operation to a previously created record, and such operations are rare in many languages. A garbage collector that concentrates just on recently allocated records can take advantage of this fact. Such a garbage collector can be so efficient that the allocation of records costs more than their disposal. A scheme for quick record allocation attacks this bottleneck. Many garbage-collected environments do not know when to ask the operating system for more memory. A robust heuristic solves this problem. This paper presents a simple, efficient, low-overhead version of generational garbage collection with fast allocation, suitable for implementation in a Unix environment.     

Reducing the computation required to solve a standard minimax problem

Minimax optimization problems have a long and rich history in the area of control. We show how the computation required to find the solution of a popular and widely applicable minimax problem can be significantly reduced. This reduction in computation results from an observation concerning the inner level (finite) maximization. In particular, we show that the number of parameter combinations that must be considered may be significantly reduced. We next indicate how this optimization problem can be used to synthesize a robust state feedback control for a system with parameter uncertainty. We conclude with an example robust control design problem that has 15 independent uncertain parameters and would not be practical were it not for the reduced computational requirement.     

Algorithm to solve the generalized Markowitz problem

A relation between the VaR and CVaR criteria was established in terms of income and loss. Consideration was given to the generalized Markowitz problem, and an algorithm to solve it approximately for the piecewise-linear and bilinear income functions was presented. An analytical solution was given for the case of the scalar bilinear income function under a uniform distribution of income. A numerical algorithm was presented to solve the problem in the case of multivariable bilinear income function under normal distribution of incomes.     

How to solve the Santa Claus problem

John Trono (1994) published a new exercise in concurrent programming – the Santa Claus problem – and provided a solution based on semaphores. His solution is incorrect because it assumes that a process released from waiting on a semaphore will necessarily be scheduled for execution. We give a simple solution in Ada 95 using higher-order synchronization primitives: protected objects and rendezvous. We then give a solution in Java, although this solution is not as elegant as the Ada 95 solution because the Java synchronization primitives are rather limited. The problem demonstrates that semaphores, designed for low-level mutual exclusion, are not appropriate for solving difficult concurrent programming problems. © 1998 John Wiley & Sons, Ltd.     

Concurrent and distributed garbage collection of active objects

This paper shows how to perform concurrent and distributed automatic garbage collection of objects possessing their own thread of control. The relevance of garbage collection and active objects to distributed applications is briefly discussed and the specific model of active objects used in the paper is explained. The collector is comprised of independent local collectors, one per node, and a distributed global collector. The mutator (application), the local collectors and the global collector run concurrently. An important part of this paper is the detailed presentation of the algorithms necessary to achieve correct concurrent operation among the collectors and between the collectors and the mutator. The collector builds on previous algorithms for taking snapshots in distributed systems and for detecting termination     

Genetic algorithm to solve the p-centre and p-radius problem on a network

The p-centre problem is to locate p facilities on a network so as to minimize the largest distance from a demand point to its nearest facility. The problem is NP-complete for an arbitrary network. In this paper, genetic algorithms (GAs) to solve this problem are developed via two different representations. The nodes are taken as weighted, and the demand points are assumed to coincide with the nodes. Computational results obtained from the proposed GAs for different network sizes and different values of p are presented and compared for two different representations.     

Metamodel-assisted Kalai-Smorodinsky equilibria to solve a multicriteria optimization problem

Structural and Multidisciplinary Optimization - The main idea of solving a multicriteria optimization problem (MOP) is to find non-dominated solutions belonging to the Pareto frontier (e.g., a...     

Program logic and equivalence in the presence of garbage collection

It is generally thought that reasoning about programs in memory safe, garbage collected languages is much easier than in languages where the programmer has more explicit control over memory. Paradoxically, existing program logics are based on a low-level view of storage that is sensitive to the presence or absence of unreachable cells, and Reynolds has pointed out that the Hoare triples derivable in these logics are even incompatible with garbage collection. We present a study of a small language whose operational semantics includes a rule for reclaiming garbage. Our main results include an analysis of propositions that are garbage insensitive, and full abstraction results connecting partial and total correctness to two natural notions of observational equivalence between programs.     

Genetic algorithms to solve the cover printing problem

Inspired by successful application of evolutionary algorithms to solving difficult optimization problems, we explore in this paper, the applicability of genetic algorithms (GAs) to the cover printing problem, which consists in the grouping of book covers on offset plates in order to minimize the total production cost. We combine GAs with a linear programming solver and we propose some innovative features such as the “unfixed two-point crossover operator” and the “binary stochastic sampling with replacement” for selection. Two approaches are proposed: an adapted genetic algorithm and a multiobjective genetic algorithm using the Pareto fitness genetic algorithm. The resulting solutions are compared. Some computational experiments have also been done to analyze the effects of different genetic operators on both algorithms.     

Using logic to solve the submodule construction problem

Submodule construction is the problem of finding a new submodule which, together with a given submodule, provides a behavior that conforms to a given desired global behavior. A new formulation of this problem and its solution in first-order logic is presented, and it is shown how the known solutions to this problem in the context of various communication paradigms and specification formalisms can be derived. Communication paradigms are: synchronous rendezvous at several interfaces; interleaved rendezvous; input/output automata with complete or partial behavior specifications and with synchronous or interleaved communication. A new algorithm for deriving a progressive solution is also presented.     

Java垃圾回收新算法刍探

由Java语言与C/C++对象在内存管理方式的不同,引出了Java语言的优势技术--垃圾处理技术.通过对GC工作原理的阐述及对一些传统的垃圾收集器的分析,提出了一种新的垃圾处理算法,一定程度上改善和提高了Java垃圾处理的性能.     

Exploiting array manipulation habits to optimize garbage collection and type flow analysis

A widespread practice to implement a flexible array is to consider the storage area into two parts: the used area, which is already available for read/write operations, and the supply area, which is used in case of enlargement of the array. The main purpose of the supply area is to avoid as much as possible the reallocation of the whole storage area in case of enlargement. As the supply area is not used by the application, the main idea of the paper is to convey the information to the garbage collector, making it possible to avoid completely the marking of the supply area. We also present a simple method to analyze the types of objects, which are stored in an array as well as the possible presence of NULL values within the array. This allows us to better specialize the work of the garbage collector when marking the used area, and also, by transitivity, to improve overall results for type analysis of all expressions of the source code. After introducing several abstract data types, which represent the main arrays concerned by our technique (i.e., zero or variable indexing, circular arrays and hash maps), we measure its impact during the bootstrap of two compilers whose libraries are equipped with these abstract data types. We then measure, on various software products we have not written, the frequency of certain habits of manipulation of arrays, to assess the validity of our approach. Copyright © 2014 John Wiley & Sons, Ltd.     

Theoretical study of a numerical method to solve a diffusion-convection problem

The paper analyzes the approximation, stability, convergence, monotonicity, and dissipative and dispersion properties of the diffusion-convection method. The spatial mesh is considered nonuniform. The application of the method to a problem with the third boundary condition is considered. The computational complexity of the algorithm is estimated. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 161–170, March–April 2008.     

A knapsack problem as a tool to solve the production planning problem in small foundries

According to recent research carried out in the foundry sector, one of the most important concerns of the industries is to improve their production planning. A foundry production plan involves two dependent stages: (1) determining the alloys to be merged and (2) determining the lots that will be produced. The purpose of this study is to draw up plans of minimum production cost for the lot-sizing problem for small foundries. As suggested in the literature, the proposed heuristic addresses the problem stages in a hierarchical way. Firstly, the alloys are determined and, subsequently, the items that are produced from them. In this study, a knapsack problem as a tool to determine the items to be produced from furnace loading was proposed. Moreover, we proposed a genetic algorithm to explore some possible sets of alloys and to determine the production planning for a small foundry. Our method attempts to overcome the difficulties in finding good production planning presented by the method proposed in the literature. The computational experiments show that the proposed methods presented better results than the literature. Furthermore, the proposed methods do not need commercial software, which is favorable for small foundries.     

A heuristic-based framework to solve a complex aircraft sizing problem

Aircraft sizing studies consist in determining the main characteristics of an aircraft starting from a set of requirements. These studies can be summarized as global constrained optimization problems. The constraints express physical feasibility and the requirements to be satisfied; the objectives are market-driven performances of the aircraft. These optimizations are currently manually conducted as many input data frequently evolve during the study. This work introduced mathematical methods that are useful in a sizing tool to ease, fasten and enhance the aircraft configuration optimization problem. Using genetic algorithms, large amounts of design points satisfying the requirements were rapidly produced, despite some issues inherent to the aircraft model: numerical noise or physically meaningless design points due to the vast design space. Then, multicriteria optimization methods were introduced, as several criteria were considered concurrently. As calculation times became important, the aircraft model was substituted by a surrogate model. Radial basis functions approximated the constraint and the objective functions. Finally, a possible outcome of the integration of these different techniques was proposed in order to yield the engineers a global and operational perception of the design space.