Search results for "Algorithm"
showing 10 items of 4887 documents
A fuzzy method to repair infeasibility in linearly constrained problems
2001
Abstract In this paper we introduce a fuzzy method to deal with infeasibility in linearly constrained programs. Given an infeasible instance, we determine how much we should perturb the right-hand side coefficients in order to attain feasibility and propose a ‘feasible reformulation’ of the problem. Although we prove that our algorithm always finds such a reformulation the convenience of using it can be decided by the analyst. By this, we mean that the method also provides a simple way to compute lower bounds on the changes on every right-hand side coefficient, and if the decision maker considers that some of the magnitudes are unacceptable, he or she simply stops at this step. We think tha…
Branch-and-Cut
2010
This chapter focuses on the approach for solving the LOP to optimality which can currently be seen as the most successful one. It is a branch-and-bound algorithm, where the upper bounds are computed using linear programming relax- ations.
Lower and upper bounds for the mixed capacitated arc routing problem
2006
This paper presents a linear formulation, valid inequalities, and a lower bounding procedure for the mixed capacitated arc routing problem (MCARP). Moreover, three constructive heuristics and a memetic algorithm are described. Lower and upper bounds have been compared on two sets of randomly generated instances. Computational results show that the average gaps between lower and upper bounds are 0.51% and 0.33%, respectively.
A Quick Simulation Technique for a Fluid Information Storage Problem
2001
Summary In this paper we present an application of Importance Sampling (IS) for quick simulation of buffer overflow probability in a statistical multiplexer loaded with a number of independent Markov modulated fluid sources. Runtime improvement is deducible from NMCσ2(p) and NISσ2(p*) that characterize the trade-offs between sample size and variance of the estimators of buffer overflow probability experienced in Monte Carlo (MC) and Importance Sampling simulations. By assuming that the same precision is achieved for the two kinds of simulations if σ2(p)=σ2(p*), an approximate closed form expression for the ratio NIS/NMC is derived, and it is minimized with respect to the load of the multipl…
Self-stabilizing Balls & Bins in Batches
2016
A fundamental problem in distributed computing is the distribution of requests to a set of uniform servers without a centralized controller. Classically, such problems are modelled as static balls into bins processes, where m balls (tasks) are to be distributed to n bins (servers). In a seminal work, [Azar et al.; JoC'99] proposed the sequential strategy Greedy[d] for n = m. When thrown, a ball queries the load of d random bins and is allocated to a least loaded of these. [Azar et al.; JoC'99] showed that d=2 yields an exponential improvement compared to d=1. [Berenbrink et al.; JoC'06] extended this to m ⇒ n, showing that the maximal load difference is independent of m for d=2 (in contrast…
A new method for creating sparse design velocity fields
2006
We present a novel method for the computation of mesh node sensitivities with respect to the boundary node movement. The sensitivity field is sparse in a sense that movement of each boundary node affects only given amount of inner mesh nodes, which can result in considerable savings in the storage space. The method needs minimal control from the user, and it does not place any restrictions (such as block structure) on the mesh. Use of the method is demonstrated with a shape optimization problem using CAD-free parametrization. A solution to the classical die-swell free boundary problem by coupling the boundary node locations with the state variables is also presented. In that case, sparsity …
Improving Computing Systems Automatic Multiobjective Optimization Through Meta-Optimization
2016
This paper presents the extension of framework for automatic design space exploration (FADSE) tool using a meta-optimization approach, which is used to improve the performance of design space exploration algorithms, by driving two different multiobjective meta-heuristics concurrently. More precisely, we selected two genetic multiobjective algorithms: 1) non-dominated sorting genetic algorithm-II and 2) strength Pareto evolutionary algorithm 2, that work together in order to improve both the solutions’ quality and the convergence speed. With the proposed improvements, we ran FADSE in order to optimize the hardware parameters’ values of the grid ALU processor (GAP) micro-architecture from a b…
Memetic Variation Local Search vs. Life-Time Learning in Electrical Impedance Tomography
2009
In this article, various metaheuristics for a numerical optimization problem with application to Electric Impedance Tomography are tested and compared. The experimental setup is composed of a real valued Genetic Algorithm, the Differential Evolution, a self adaptive Differential Evolution recently proposed in literature, and two novel Memetic Algorithms designed for the problem under study. The two proposed algorithms employ different algorithmic philosophies in the field of Memetic Computing. The first algorithm integrates a local search into the operations of the offspring generation, while the second algorithm applies a local search to individuals already generated in the spirit of life-…
Error Estimates and Automatic Adaptive Mesh Refinement for the Metal Forming FEM Analysis
1988
The Authors propose a new technique which enables a estimation of the error inherent with the FEM analysis of metal forming processes. The aim is to evaluate the zones where the error is higher in order to proceed to a refinement of the mesh in such zones, and to obtain a smaller value of the global error. Moreover, to simplify the analyst work in the progressive refinement of the mesh, it has been prepared a software able to read the drawing created by a CAD program and to generate, automatically, all the geometrical and topological data necessary to perform the analysis on Personal Computer. The automatic renumbering of the elements in the refined mesh has been performed with the aim to r…
Distributed Resource Allocation in Underlay Multicast D2D Communications
2021
Multicast device-to-device communications operating underlay with cellular networks is a spectral efficient technique for disseminating data to nearby receivers. However, due to the critical challenge of having an intelligent interference coordination between multicast groups along with the cellular network, it is necessary to judiciously perform resource allocation for the combined network. In this work, we present a framework for a joint channel and power allocation strategy to maximize the sum rate of the combined network while guaranteeing minimum rate to individual groups and cellular users. The objective function is augmented by an austerity function that penalizes excessive assignmen…