Search results for: Quadratic eigenvalue problem
3573 On Optimum Stratification
Authors: M. G. M. Khan, V. D. Prasad, D. K. Rao
Abstract:
In this manuscript, we discuss the problem of determining the optimum stratification of a study (or main) variable based on the auxiliary variable that follows a uniform distribution. If the stratification of survey variable is made using the auxiliary variable it may lead to substantial gains in precision of the estimates. This problem is formulated as a Nonlinear Programming Problem (NLPP), which turn out to multistage decision problem and is solved using dynamic programming technique.
Keywords: Auxiliary variable, Dynamic programming technique, Nonlinear programming problem, Optimum stratification, Uniform distribution.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 20993572 Enhanced Traveling Salesman Problem Solving by Genetic Algorithm Technique (TSPGA)
Authors: Buthainah Fahran Al-Dulaimi, Hamza A. Ali
Abstract:
The well known NP-complete problem of the Traveling Salesman Problem (TSP) is coded in genetic form. A software system is proposed to determine the optimum route for a Traveling Salesman Problem using Genetic Algorithm technique. The system starts from a matrix of the calculated Euclidean distances between the cities to be visited by the traveling salesman and a randomly chosen city order as the initial population. Then new generations are then created repeatedly until the proper path is reached upon reaching a stopping criterion. This search is guided by a solution evaluation function.
Keywords: Genetic algorithms, traveling salesman problem solving, optimization.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 25463571 The Relationship of Eigenvalues between Backward MPSD and Jacobi Iterative Matrices
Authors: Zhuan-de Wang, Hou-biao Li, Zhong-xi Gao
Abstract:
In this paper, the backward MPSD (Modified Preconditioned Simultaneous Displacement) iterative matrix is firstly proposed. The relationship of eigenvalues between the backward MPSD iterative matrix and backward Jacobi iterative matrix for block p-cyclic case is obtained, which improves and refines the results in the corresponding references.
Keywords: Backward MPSD iterative matrix, Jacobi iterative matrix, eigenvalue, p-cyclic matrix.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 17693570 Two-Stage Approach for Solving the Multi-Objective Optimization Problem on Combinatorial Configurations
Authors: Liudmyla Koliechkina, Olena Dvirna
Abstract:
The statement of the multi-objective optimization problem on combinatorial configurations is formulated, and the approach to its solution is proposed. The problem is of interest as a combinatorial optimization one with many criteria, which is a model of many applied tasks. The approach to solving the multi-objective optimization problem on combinatorial configurations consists of two stages; the first is the reduction of the multi-objective problem to the single criterion based on existing multi-objective optimization methods, the second stage solves the directly replaced single criterion combinatorial optimization problem by the horizontal combinatorial method. This approach provides the optimal solution to the multi-objective optimization problem on combinatorial configurations, taking into account additional restrictions for a finite number of steps.Keywords: Discrete set, linear combinatorial optimization, multi-objective optimization, multipermutation, Pareto solutions, partial permutation set, permutation, structural graph.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 6533569 P-ACO Approach to Assignment Problem in FMSs
Authors: I. Mahdavi, A. Jazayeri, M. Jahromi, R. Jafari, H. Iranmanesh
Abstract:
One of the most important problems in production planning of flexible manufacturing system (FMS) is machine tool selection and operation allocation problem that directly influences the production costs and times .In this paper minimizing machining cost, set-up cost and material handling cost as a multi-objective problem in flexible manufacturing systems environment are considered. We present a 0-1 integer linear programming model for the multiobjective machine tool selection and operation allocation problem and due to the large scale nature of the problem, solving the problem to obtain optimal solution in a reasonable time is infeasible, Paretoant colony optimization (P-ACO) approach for solving the multiobjective problem in reasonable time is developed. Experimental results indicate effectiveness of the proposed algorithm for solving the problem.
Keywords: Flexible manufacturing system, Production planning, Machine tool selection, Operation allocation, Multiobjective optimization, Metaheuristic.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 18983568 The Diophantine Equation y2 − 2yx − 3 = 0 and Corresponding Curves over Fp
Authors: Ahmet Tekcan, Arzu Özkoç, Hatice Alkan
Abstract:
In this work, we consider the number of integer solutions of Diophantine equation D : y2 - 2yx - 3 = 0 over Z and also over finite fields Fp for primes p ≥ 5. Later we determine the number of rational points on curves Ep : y2 = Pp(x) = yp 1 + yp 2 over Fp, where y1 and y2 are the roots of D. Also we give a formula for the sum of x- and y-coordinates of all rational points (x, y) on Ep over Fp.Keywords: Diophantine equation, Pell equation, quadratic form.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 12543567 Effect of a Magnetic Field on the Onset of Marangoni Convection in a Micropolar Fluid
Authors: Mohd Nasir Mahmud, Ruwaidiah Idris, Ishak Hashim
Abstract:
With the presence of a uniform vertical magnetic field and suspended particles, thermocapillary instability in a horizontal liquid layer is investigated. The resulting eigenvalue is solved by the Galerkin technique for various basic temperature gradients. It is found that the presence of magnetic field always has a stability effect of increasing the critical Marangoni number.
Keywords: Marangoni convection, Magnetic field, Micropolar fluid, Non-uniform thermal gradient, Thermocapillary.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 16223566 A Comparison of Exact and Heuristic Approaches to Capital Budgeting
Authors: Jindřiška Šedová, Miloš Šeda
Abstract:
This paper summarizes and compares approaches to solving the knapsack problem and its known application in capital budgeting. The first approach uses deterministic methods and can be applied to small-size tasks with a single constraint. We can also apply commercial software systems such as the GAMS modelling system. However, because of NP-completeness of the problem, more complex problem instances must be solved by means of heuristic techniques to achieve an approximation of the exact solution in a reasonable amount of time. We show the problem representation and parameter settings for a genetic algorithm framework.Keywords: Capital budgeting, knapsack problem, GAMS, heuristic method, genetic algorithm.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 17283565 Transfer Knowledge from Multiple Source Problems to a Target Problem in Genetic Algorithm
Authors: Tami Alghamdi, Terence Soule
Abstract:
To study how to transfer knowledge from multiple source problems to the target problem, we modeled the Transfer Learning (TL) process using Genetic Algorithms as the model solver. TL is the process that aims to transfer learned data from one problem to another problem. The TL process aims to help Machine Learning (ML) algorithms find a solution to the problems. The Genetic Algorithms (GA) give researchers access to information that we have about how the old problem is solved. In this paper, we have five different source problems, and we transfer the knowledge to the target problem. We studied different scenarios of the target problem. The results showed that combined knowledge from multiple source problems improves the GA performance. Also, the process of combining knowledge from several problems results in promoting diversity of the transferred population.
Keywords: Transfer Learning, Multiple Sources, Knowledge Transfer, Domain Adaptation, Source, Target.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 3283564 Optimization Using Simulation of the Vehicle Routing Problem
Authors: Nayera E. El-Gharably, Khaled S. El-Kilany, Aziz E. El-Sayed
Abstract:
A key element of many distribution systems is the routing and scheduling of vehicles servicing a set of customers. A wide variety of exact and approximate algorithms have been proposed for solving the vehicle routing problems (VRP). Exact algorithms can only solve relatively small problems of VRP, which is classified as NP-Hard. Several approximate algorithms have proven successful in finding a feasible solution not necessarily optimum. Although different parts of the problem are stochastic in nature; yet, limited work relevant to the application of discrete event system simulation has addressed the problem. Presented here is optimization using simulation of VRP; where, a simplified problem has been developed in the ExtendSimTM simulation environment; where, ExtendSimTM evolutionary optimizer is used to minimize the total transportation cost of the problem. Results obtained from the model are very satisfactory. Further complexities of the problem are proposed for consideration in the future.Keywords: Discrete event system simulation, optimization using simulation, vehicle routing problem.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 58363563 Tabu Search to Draw Evacuation Plans in Emergency Situations
Authors: S. Nasri, H. Bouziri
Abstract:
Disasters are quite experienced in our days. They are caused by floods, landslides, and building fires that is the main objective of this study. To cope with these unexpected events, precautions must be taken to protect human lives. The emphasis on disposal work focuses on the resolution of the evacuation problem in case of no-notice disaster. The problem of evacuation is listed as a dynamic network flow problem. Particularly, we model the evacuation problem as an earliest arrival flow problem with load dependent transit time. This problem is classified as NP-Hard. Our challenge here is to propose a metaheuristic solution for solving the evacuation problem. We define our objective as the maximization of evacuees during earliest periods of a time horizon T. The objective provides the evacuation of persons as soon as possible. We performed an experimental study on emergency evacuation from the tunisian children’s hospital. This work prompts us to look for evacuation plans corresponding to several situations where the network dynamically changes.
Keywords: Dynamic network flow, Load dependent transit time, Evacuation strategy, Earliest arrival flow problem.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 17893562 Blockchain for Decentralized Finance: Impact, Challenges and Remediation
Authors: Rishabh Garg
Abstract:
Blockchain technology can allow remote, untrusted parties in the banking and financial sector to reach consensus on the state of databases without the involvement of gatekeepers. Like a bookkeeper, it can manage all financial transactions including payments, settlements, fundraising, securities management, loans, credits and trade finance. It can outperform existing systems in terms of identity verification, asset transfers, peer-to-peer transfers, hedge funds, security and auditability. Blockchain-based decentralized finance (DeFi) is a new financial protocol. Being open and programmable, it enables various DeFi use-cases, including asset management, tokenization, tokenized derivatives, decentralized autonomous organizations, data analysis and valuation, payments, lending and borrowing, insurance, margin trading, prediction market, gambling and yield-farming, etc. In addition, it can ease financial transactions, cash-flow, use of programmable currency, no-loss lotteries, etc. This paper aims to assess the potential of decentralized finance by leveraging the blockchain-enabled Ethereum platform as an alternative to traditional finance. The study also aims to find out the impact of decentralized finance on prediction markets, quadratic funding and crowd-funding, together with the potential challenges and solutions associated with its implementation.
Keywords: Advance trading, crowd funding, exchange tokens, fund aggregation, margin trading, quadratic funding, smart contracts, streaming money, token derivatives.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 3183561 Design and Performance Improvement of Three-Dimensional Optical Code Division Multiple Access Networks with NAND Detection Technique
Authors: Satyasen Panda, Urmila Bhanja
Abstract:
In this paper, we have presented and analyzed three-dimensional (3-D) matrices of wavelength/time/space code for optical code division multiple access (OCDMA) networks with NAND subtraction detection technique. The 3-D codes are constructed by integrating a two-dimensional modified quadratic congruence (MQC) code with one-dimensional modified prime (MP) code. The respective encoders and decoders were designed using fiber Bragg gratings and optical delay lines to minimize the bit error rate (BER). The performance analysis of the 3D-OCDMA system is based on measurement of signal to noise ratio (SNR), BER and eye diagram for a different number of simultaneous users. Also, in the analysis, various types of noises and multiple access interference (MAI) effects were considered. The results obtained with NAND detection technique were compared with those obtained with OR and AND subtraction techniques. The comparison results proved that the NAND detection technique with 3-D MQC\MP code can accommodate more number of simultaneous users for longer distances of fiber with minimum BER as compared to OR and AND subtraction techniques. The received optical power is also measured at various levels of BER to analyze the effect of attenuation.Keywords: Cross correlation, three-dimensional optical code division multiple access, spectral amplitude coding optical code division multiple access, multiple access interference, phase induced intensity noise, three-dimensional modified quadratic congruence/modified prime code.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 15203560 Avoiding Pin Ball Routing Problem in Network Mobility Hand-Off Management
Authors: M. Dinakaran, P. Balasubramanie
Abstract:
With the demand of mobility by users, wireless technologies have become the hotspot developing arena. Internet Engineering Task Force (IETF) working group has developed Mobile IP to support node mobility. The concept of node mobility indicates that in spite of the movement of the node, it is still connected to the internet and all the data transactions are preserved. It provides location-independent access to Internet. After the incorporation of host mobility, network mobility has undergone intense research. There are several intricacies faced in the real world implementation of network mobility significantly the problem of nested networks and their consequences. This article is concerned regarding a problem of nested network called pinball route problem and proposes a solution to eliminate the above problem. The proposed mechanism is implemented using NS2 simulation tool and it is found that the proposed mechanism efficiently reduces the overload caused by the pinball route problem.Keywords: Mobile IP, Pinball routing problem, NEMO
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 18353559 Optimal Capacitor Placement in Distribution Feeders
Authors: N. Rugthaicharoencheep, S. Auchariyamet
Abstract:
Optimal capacitor allocation in distribution systems has been studied for a long times. It is an optimization problem which has an objective to define the optimal sizes and locations of capacitors to be installed. In this works, an overview of capacitor placement problem in distribution systems is briefly introduced. The objective functions and constraints of the problem are listed and the methodologies for solving the problem are summarized.Keywords: Capacitor Placement, Distribution Systems, Optimization Techniques
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 24103558 Semi-Blind Two-Dimensional Code Acquisition in CDMA Communications
Authors: Rui Wu, Tapani Ristaniemi
Abstract:
In this paper, we propose a new algorithm for joint time-delay and direction-of-arrival (DOA) estimation, here called two-dimensional code acquisition, in an asynchronous directsequence code-division multiple-access (DS-CDMA) array system. This algorithm depends on eigenvector-eigenvalue decomposition of sample correlation matrix, and requires to know desired user-s training sequence. The performance of the algorithm is analyzed both analytically and numerically in uncorrelated and coherent multipath environment. Numerical examples show that the algorithm is robust with unknown number of coherent signals.
Keywords: Two-Dimensional Code Acquisition, EV-t, DSCDMA
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 15123557 Reconstruction of Binary Matrices Satisfying Neighborhood Constraints by Simulated Annealing
Authors: Divyesh Patel, Tanuja Srivastava
Abstract:
This paper considers the NP-hard problem of reconstructing binary matrices satisfying exactly-1-4-adjacency constraint from its row and column projections. This problem is formulated into a maximization problem. The objective function gives a measure of adjacency constraint for the binary matrices. The maximization problem is solved by the simulated annealing algorithm and experimental results are presented.
Keywords: Discrete Tomography, exactly-1-4-adjacency, simulated annealing.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 24443556 On Detour Spectra of Some Graphs
Authors: S.K.Ayyaswamy, S.Balachandran
Abstract:
The Detour matrix (DD) of a graph has for its ( i , j) entry the length of the longest path between vertices i and j. The DD-eigenvalues of a connected graph G are the eigenvalues for its detour matrix, and they form the DD-spectrum of G. The DD-energy EDD of the graph G is the sum of the absolute values of its DDeigenvalues. Two connected graphs are said to be DD- equienergetic if they have equal DD-energies. In this paper, the DD- spectra of a variety of graphs and their DD-energies are calculated.Keywords: Detour eigenvalue (of a graph), detour spectrum(of a graph), detour energy(of a graph), detour - equienergetic graphs.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 15043555 Evaluating the Response of Rainfed-Chickpea to Population Density in Iran, Using Simulation
Authors: Manoochehr Gholipoor
Abstract:
The response of growth and yield of rainfed-chickpea to population density should be evaluated based on long-term experiments to include the climate variability. This is achievable just by simulation. In this simulation study, this evaluation was done by running the CYRUS model for long-term daily weather data of five locations in Iran. The tested population densities were 7 to 59 (with interval of 2) stands per square meter. Various functions, including quadratic, segmented, beta, broken linear, and dent-like functions, were tested. Considering root mean square of deviations and linear regression statistics [intercept (a), slope (b), and correlation coefficient (r)] for predicted versus observed variables, the quadratic and broken linear functions appeared to be appropriate for describing the changes in biomass and grain yield, and in harvest index, respectively. Results indicated that in all locations, grain yield tends to show increasing trend with crowding the population, but subsequently decreases. This was also true for biomass in five locations. The harvest index appeared to have plateau state across low population densities, but decreasing trend with more increasing density. The turning point (optimum population density) for grain yield was 30.68 stands per square meter in Isfahan, 30.54 in Shiraz, 31.47 in Kermanshah, 34.85 in Tabriz, and 32.00 in Mashhad. The optimum population density for biomass ranged from 24.6 (in Tabriz) to 35.3 stands per square meter (Mashhad). For harvest index it varied between 35.87 and 40.12 stands per square meter.Keywords: Rainfed-chickpea, biomass, harvest index, grain yield, simulation.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 13253554 Vibration Base Identification of Impact Force Using Genetic Algorithm
Authors: R. Hashemi, M.H.Kargarnovin
Abstract:
This paper presents the identification of the impact force acting on a simply supported beam. The force identification is an inverse problem in which the measured response of the structure is used to determine the applied force. The identification problem is formulated as an optimization problem and the genetic algorithm is utilized to solve the optimization problem. The objective function is calculated on the difference between analytical and measured responses and the decision variables are the location and magnitude of the applied force. The results from simulation show the effectiveness of the approach and its robustness vs. the measurement noise and sensor location.Keywords: Genetic Algorithm, Inverse problem, Optimization, Vibration.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 15393553 Solving the Set Covering Problem Using the Binary Cat Swarm Optimization Metaheuristic
Authors: Broderick Crawford, Ricardo Soto, Natalia Berrios, Eduardo Olguin
Abstract:
In this paper, we present a binary cat swarm optimization for solving the Set covering problem. The set covering problem is a well-known NP-hard problem with many practical applications, including those involving scheduling, production planning and location problems. Binary cat swarm optimization is a recent swarm metaheuristic technique based on the behavior of discrete cats. Domestic cats show the ability to hunt and are curious about moving objects. The cats have two modes of behavior: seeking mode and tracing mode. We illustrate this approach with 65 instances of the problem from the OR-Library. Moreover, we solve this problem with 40 new binarization techniques and we select the technical with the best results obtained. Finally, we make a comparison between results obtained in previous studies and the new binarization technique, that is, with roulette wheel as transfer function and V3 as discretization technique.Keywords: Binary cat swarm optimization, set covering problem, metaheuristic, binarization methods.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 23203552 An Effective Algorithm for Minimum Weighted Vertex Cover Problem
Authors: S. Balaji, V. Swaminathan, K. Kannan
Abstract:
The Minimum Weighted Vertex Cover (MWVC) problem is a classic graph optimization NP - complete problem. Given an undirected graph G = (V, E) and weighting function defined on the vertex set, the minimum weighted vertex cover problem is to find a vertex set S V whose total weight is minimum subject to every edge of G has at least one end point in S. In this paper an effective algorithm, called Support Ratio Algorithm (SRA), is designed to find the minimum weighted vertex cover of a graph. Computational experiments are designed and conducted to study the performance of our proposed algorithm. Extensive simulation results show that the SRA can yield better solutions than other existing algorithms found in the literature for solving the minimum vertex cover problem.
Keywords: Weighted vertex cover, vertex support, approximation algorithms, NP-complete problem.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 38673551 Creative Thinking Skill Approach Through Problem-Based Learning: Pedagogy and Practice in the Engineering Classroom
Authors: Halizah Awang, Ishak Ramly
Abstract:
Problem-based learning (PBL) is one of the student centered approaches and has been considered by a number of higher educational institutions in many parts of the world as a method of delivery. This paper presents a creative thinking approach for implementing Problem-based Learning in Mechanics of Structure within a Malaysian Polytechnics environment. In the learning process, students learn how to analyze the problem given among the students and sharing classroom knowledge into practice. Further, through this course-s emphasis on problem-based learning, students acquire creative thinking skills and professional skills as they tackle complex, interdisciplinary and real-situation problems. Once the creative ideas are generated, there are useful additional techniques for tender ideas that will grow into a productive concept or solution. The combination of creative skills and technical abilities will enable the students to be ready to “hit-the-ground-running" and produce in industry when they graduate.Keywords: Creative Thinking Skills, Problem-based Learning, Problem Solving.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 72953550 The Algorithm to Solve the Extend General Malfatti’s Problem in a Convex Circular Triangle
Authors: Ching-Shoei Chiang
Abstract:
The Malfatti’s problem solves the problem of fitting three circles into a right triangle such that these three circles are tangent to each other, and each circle is also tangent to a pair of the triangle’s sides. This problem has been extended to any triangle (called general Malfatti’s problem). Furthermore, the problem has been extended to have 1 + 2 + … + n circles inside the triangle with special tangency properties among circles and triangle sides; it is called the extended general Malfatti’s problem. In the extended general Malfatti’s problem, call it Tri(Tn), where Tn is the triangle number, there are closed-form solutions for the Tri(T₁) (inscribed circle) problem and Tri(T₂) (3 Malfatti’s circles) problem. These problems become more complex when n is greater than 2. In solving the Tri(Tn) problem, n > 2, algorithms have been proposed to solve these problems numerically. With a similar idea, this paper proposed an algorithm to find the radii of circles with the same tangency properties. Instead of the boundary of the triangle being a straight line, we use a convex circular arc as the boundary and try to find Tn circles inside this convex circular triangle with the same tangency properties among circles and boundary as in Tri(Tn) problems. We call these problems the Carc(Tn) problems. The algorithm is a mO(Tn) algorithm, where m is the number of iterations in the loop. It takes less than 1000 iterations and less than 1 second for the Carc(T16) problem, which finds 136 circles inside a convex circular triangle with specified tangency properties. This algorithm gives a solution for circle packing problem inside convex circular triangle with arbitrarily-sized circles. Many applications concerning circle packing may come from the result of the algorithm, such as logo design, architecture design, etc.
Keywords: Circle packing, computer-aided geometric design, geometric constraint solver, Malfatti’s problem.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1113549 Implementation of Heuristics for Solving Travelling Salesman Problem Using Nearest Neighbour and Minimum Spanning Tree Algorithms
Authors: Fatma A. Karkory, Ali A. Abudalmola
Abstract:
The travelling salesman problem (TSP) is a combinatorial optimization problem in which the goal is to find the shortest path between different cities that the salesman takes. In other words, the problem deals with finding a route covering all cities so that total distance and execution time is minimized. This paper adopts the nearest neighbor and minimum spanning tree algorithm to solve the well-known travelling salesman problem. The algorithms were implemented using java programming language. The approach is tested on three graphs that making a TSP tour instance of 5-city, 10 –city, and 229–city. The computation results validate the performance of the proposed algorithm.
Keywords: Heuristics, minimum spanning tree algorithm, Nearest Neighbor, Travelling Salesman Problem (TSP).
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 78093548 Partial Derivatives and Optimization Problem on Time Scales
Authors: Francisco Miranda
Abstract:
The optimization problem using time scales is studied. Time scale is a model of time. The language of time scales seems to be an ideal tool to unify the continuous-time and the discrete-time theories. In this work we present necessary conditions for a solution of an optimization problem on time scales. To obtain that result we use properties and results of the partial diamond-alpha derivatives for continuous-multivariable functions. These results are also presented here.Keywords: Lagrange multipliers, mathematical programming, optimization problem, time scales.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 17123547 Solving Bus Terminal Location Problem Using Genetic Algorithm
Authors: S. Babaie-Kafaki, R. Ghanbari, S.H. Nasseri, E. Ardil
Abstract:
Bus networks design is an important problem in public transportation. The main step to this design, is determining the number of required terminals and their locations. This is an especial type of facility location problem, a large scale combinatorial optimization problem that requires a long time to be solved. The genetic algorithm (GA) is a search and optimization technique which works based on evolutionary principle of natural chromosomes. Specifically, the evolution of chromosomes due to the action of crossover, mutation and natural selection of chromosomes based on Darwin's survival-of-the-fittest principle, are all artificially simulated to constitute a robust search and optimization procedure. In this paper, we first state the problem as a mixed integer programming (MIP) problem. Then we design a new crossover and mutation for bus terminal location problem (BTLP). We tested the different parameters of genetic algorithm (for a sample problem) and obtained the optimal parameters for solving BTLP with numerical try and error.Keywords: Bus networks, Genetic algorithm (GA), Locationproblem, Mixed integer programming (MIP).
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 22963546 Constant Factor Approximation Algorithm for p-Median Network Design Problem with Multiple Cable Types
Authors: Chaghoub Soraya, Zhang Xiaoyan
Abstract:
This research presents the first constant approximation algorithm to the p-median network design problem with multiple cable types. This problem was addressed with a single cable type and there is a bifactor approximation algorithm for the problem. To the best of our knowledge, the algorithm proposed in this paper is the first constant approximation algorithm for the p-median network design with multiple cable types. The addressed problem is a combination of two well studied problems which are p-median problem and network design problem. The introduced algorithm is a random sampling approximation algorithm of constant factor which is conceived by using some random sampling techniques form the literature. It is based on a redistribution Lemma from the literature and a steiner tree problem as a subproblem. This algorithm is simple, and it relies on the notions of random sampling and probability. The proposed approach gives an approximation solution with one constant ratio without violating any of the constraints, in contrast to the one proposed in the literature. This paper provides a (21 + 2)-approximation algorithm for the p-median network design problem with multiple cable types using random sampling techniques.Keywords: Approximation algorithms, buy-at-bulk, combinatorial optimization, network design, p-median.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 5823545 An Incomplete Factorization Preconditioner for LMS Adaptive Filter
Authors: Shazia Javed, Noor Atinah Ahmad
Abstract:
In this paper an efficient incomplete factorization preconditioner is proposed for the Least Mean Squares (LMS) adaptive filter. The proposed preconditioner is approximated from a priori knowledge of the factors of input correlation matrix with an incomplete strategy, motivated by the sparsity patter of the upper triangular factor in the QRD-RLS algorithm. The convergence properties of IPLMS algorithm are comparable with those of transform domain LMS(TDLMS) algorithm. Simulation results show efficiency and robustness of the proposed algorithm with reduced computational complexity.
Keywords: Autocorrelation matrix, Cholesky's factor, eigenvalue spread, Markov input.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 17793544 Solving Facility Location Problem on Cluster Computing
Authors: Ei Phyo Wai, Nay Min Tun
Abstract:
Computation of facility location problem for every location in the country is not easy simultaneously. Solving the problem is described by using cluster computing. A technique is to design parallel algorithm by using local search with single swap method in order to solve that problem on clusters. Parallel implementation is done by the use of portable parallel programming, Message Passing Interface (MPI), on Microsoft Windows Compute Cluster. In this paper, it presents the algorithm that used local search with single swap method and implementation of the system of a facility to be opened by using MPI on cluster. If large datasets are considered, the process of calculating a reasonable cost for a facility becomes time consuming. The result shows parallel computation of facility location problem on cluster speedups and scales well as problem size increases.Keywords: cluster, cost, demand, facility location
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1476