Search results for: Pinball routing problem

Authors: Huang Xiaoling, Liu Lufeng

Abstract:

In this paper, we seek to determine one reasonable local hub port and optimal routes for a containership fleet, performing pick-ups and deliveries, between the hub and spoke ports in a same region. The relationship between a hub port, and traffic in feeder lines is analyzed. A new network planning method is proposed, an integrated hub port location and route design, a capacitated vehicle routing problem with pick-ups, deliveries and time deadlines are formulated and solved using an improved genetic algorithm for positioning the hub port and establishing routes for a containership fleet. Results on the performance of the algorithm and the feasibility of the approach show that a relatively small fleet of containerships could provide efficient services within deadlines.

Keywords: Route planning, Hub port location, Container feeder service.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2218

Authors: M. Ahmad, M. Gourgand, C. Caux

Abstract:

The Resource-Constrained Project Scheduling Problem (RCPSP) is concerned with single-item or small batch production where limited resources have to be allocated to dependent activities over time. Over the past few decades, a lot of work has been made with the use of optimal solution procedures for this basic problem type and its extensions. Brucker and Knust[1] discuss, how timetabling problems can be modeled as a RCPSP. Authors discuss high school timetabling and university course timetabling problem as an example. We have formulated two mathematical formulations of course timetabling problem in a new way which are the prototype of single-mode RCPSP. Our focus is to show, how course timetabling problem can be transformed into RCPSP. We solve this transformation model with genetic algorithm.

Keywords: Course Timetabling, Integer programming, Combinatorial optimizations

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2016

Authors: Hamed Rajabi, Naser Nematbakhsh, Naser Movahediniya

Abstract:

IP multicasting is a key technology for many existing and emerging applications on the Internet. Furthermore, with increasing popularity of wireless devices and mobile equipment, it is necessary to determine the best way to provide this service in a wireless environment. IETF Mobile IP, that provides mobility for hosts in IP networks, proposes two approaches for mobile multicasting, namely, remote subscription (MIP-RS) and bi-directional tunneling (MIP-BT). In MIP-RS, a mobile host re-subscribes to the multicast groups each time it moves to a new foreign network. MIP-RS suffers from serious packet losses while mobile host handoff occurs. In MIP-BT, mobile hosts send and receive multicast packets by way of their home agents (HAs), using Mobile IP tunnels. Therefore, it suffers from inefficient routing and wastage of system resources. In this paper, we propose a protocol called Mobile Multicast support using Old Foreign Agent (MMOFA) for Mobile Hosts. MMOFA is derived from MIP-RS and with the assistance of Mobile host's Old foreign agent, routes the missing datagrams due to handoff in adjacent network via tunneling. Also, we studied the performance of the proposed protocol by simulation under ns-2.27. The results demonstrate that MMOFA has optimal routing efficiency and low delivery cost, as compared to other approaches.

Keywords: Mobile Multicast, Mobile IP, MMOFA, NS-2. 27.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1468

Authors: M. Jamuna Rani, K. Ramanathan

Abstract:

A steam power plant is housed with various types of equipments like boiler, turbine, heat exchanger etc. These equipments are mainly connected with piping systems. Such a piping layout design depends mainly on stress analysis and flexibility. It will vary with respect to pipe geometrical properties, pressure, temperature, and supports. The present paper is to analyze the presence and effect of hangers and expansion joints in the piping layout/routing using CAESAR-II software. Main aim of piping stress analysis is to provide adequate flexibility for absorbing thermal expansion, code compliance for stresses and displacement incurred in piping system. The design is said to be safe if all these are in allowable range as per code. In this study, a sample problem is considered for analysis as per power piping ASME B31.1 code and the results thus obtained are compared.

Keywords: ASTM B31.1, hanger, expansion joint, CAESAR-II.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 5132

Authors: Mohammed Salem Alzahrani

Abstract:

In this paper the optimality of the solution of an existing real word assignment problem known as the seat assignment problem using Seat Assignment Method (SAM) is discussed. SAM is the newly driven method from three existing methods, Hungarian Method, Northwest Corner Method and Least Cost Method in a special way that produces the easiness & fairness among all methods that solve the seat assignment problem.

Keywords: Assignment Problem, Hungarian Method, Least Cost Method, Northwest Corner Method, Seat Assignment Method (SAM), A Real Word Assignment Problem.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 3446

Authors: Mhand Hifi, Hedi Mhalla, Mustapha Michaphy

Abstract:

In this paper, we study the multi-scenario knapsack problem, a variant of the well-known NP-Hard single knapsack problem. We investigate the use of an adaptive algorithm for solving heuristically the problem. The used method combines two complementary phases: a size reduction phase and a dynamic 2- opt procedure one. First, the reduction phase applies a polynomial reduction strategy; that is used for reducing the size problem. Second, the adaptive search procedure is applied in order to attain a feasible solution Finally, the performances of two versions of the proposed algorithm are evaluated on a set of randomly generated instances.

Keywords: combinatorial optimization, max-min optimization, knapsack, heuristics, problem reduction

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1617

Authors: Zohreh O. Akbari

Abstract:

In this paper a deterministic polynomial-time algorithm is presented for the Clique problem. The case is considered as the problem of omitting the minimum number of vertices from the input graph so that none of the zeroes on the graph-s adjacency matrix (except the main diagonal entries) would remain on the adjacency matrix of the resulting subgraph. The existence of a deterministic polynomial-time algorithm for the Clique problem, as an NP-complete problem will prove the equality of P and NP complexity classes.

Keywords: Clique problem, Deterministic Polynomial-time Algorithm, Equality of P and NP Complexity Classes.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1809

Authors: Ben Mohamed Ahemed Mohamed, Yassine Adnan

Abstract:

The problem of bin-packing in two dimensions (2BP) consists in placing a given set of rectangular items in a minimum number of rectangular and identical containers, called bins. This article treats the case of objects with a free orientation of 90Ôùª. We propose an approach of resolution combining optimization by colony of ants (ACO) and the heuristic method IMA to resolve this NP-Hard problem.

Keywords: Ant colony algorithm, bin-packing problem, heuristics methods.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1842

Authors: K. Vijayalakshmi, S. Radhakrishnan

Abstract:

In this paper we have proposed a novel dynamic least cost multicast routing protocol using hybrid genetic algorithm for IP networks. Our protocol finds the multicast tree with minimum cost subject to delay, degree, and bandwidth constraints. The proposed protocol has the following features: i. Heuristic local search function has been devised and embedded with normal genetic operation to increase the speed and to get the optimized tree, ii. It is efficient to handle the dynamic situation arises due to either change in the multicast group membership or node / link failure, iii. Two different crossover and mutation probabilities have been used for maintaining the diversity of solution and quick convergence. The simulation results have shown that our proposed protocol generates dynamic multicast tree with lower cost. Results have also shown that the proposed algorithm has better convergence rate, better dynamic request success rate and less execution time than other existing algorithms. Effects of degree and delay constraints have also been analyzed for the multicast tree interns of search success rate.

Keywords: Dynamic Group membership change, Hybrid Genetic Algorithm, Link / node failure, QoS Parameters.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1447

Authors: Maricar G. Misola, Bryan B. Navarro

Abstract:

Facility Layout Problem (FLP) is one of the essential problems of several types of manufacturing and service sector. It is an optimization problem on which the main objective is to obtain the efficient locations, arrangement and order of the facilities. In the literature, there are numerous facility layout problem research presented and have used meta-heuristic approaches to achieve optimal facility layout design. This paper presented genetic algorithm to solve facility layout problem; to minimize total cost function. The performance of the proposed approach was verified and compared using problems in the literature.

Keywords: Facility Layout Problem, Genetic Algorithm, Material Handling Cost, Meta-heuristic Approach.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 4740

Authors: Aldy Gunawan, Kien Ming Ng, Kim Leng Poh

Abstract:

This paper presents a hybrid algorithm for solving a timetabling problem, which is commonly encountered in many universities. The problem combines both teacher assignment and course scheduling problems simultaneously, and is presented as a mathematical programming model. However, this problem becomes intractable and it is unlikely that a proven optimal solution can be obtained by an integer programming approach, especially for large problem instances. A hybrid algorithm that combines an integer programming approach, a greedy heuristic and a modified simulated annealing algorithm collaboratively is proposed to solve the problem. Several randomly generated data sets of sizes comparable to that of an institution in Indonesia are solved using the proposed algorithm. Computational results indicate that the algorithm can overcome difficulties of large problem sizes encountered in previous related works.

Keywords: Timetabling problem, mathematical programming model, hybrid algorithm, simulated annealing.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 4572

Authors: Takayuki Shiina

Abstract:

We consider power system expansion planning under uncertainty. In our approach, integer programming and stochastic programming provide a basic framework. We develop a multistage stochastic programming model in which some of the variables are restricted to integer values. By utilizing the special property of the problem, called block separable recourse, the problem is transformed into a two-stage stochastic program with recourse. The electric power capacity expansion problem is reformulated as the problem with first stage integer variables and continuous second stage variables. The L-shaped algorithm to solve the problem is proposed.

Keywords: electric power capacity expansion problem, integerprogramming, L-shaped method, stochastic programming

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1824

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 2111

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 2558

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 667

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 1906

Authors: Siva Prasad Darla, C. D. Naiju, K. Annamalai, S. S. Rajiv Sushanth

Abstract:

Supply chain consists of all stages involved, directly or indirectly, includes all functions involved in fulfilling a customer demand. In two stage transportation supply chain problem, transportation costs are of a significant proportion of final product costs. It is often crucial for successful decisions making approaches in two stage supply chain to explicit account for non-linear transportation costs. In this paper, deterministic demand and finite supply of products was considered. The optimized distribution level and the routing structure from the manufacturing plants to the distribution centres and to the end customers is determined using developed mathematical model and solved by proposed particle swarm optimization based genetic algorithm. Numerical analysis of the case study is carried out to validate the model.

Keywords: Genetic Algorithm, Particle Swarm Optimization, Production, Remanufacturing

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1840

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 1738

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 351

Authors: Faizal A. Samman, Thomas Hollstein, Manfred Glesner

Abstract:

A synchronous network-on-chip using wormhole packet switching and supporting guaranteed-completion best-effort with low-priority (LP) and high-priority (HP) wormhole packet delivery service is presented in this paper. Both our proposed LP and HP message services deliver a good quality of service in term of lossless packet completion and in-order message data delivery. However, the LP message service does not guarantee minimal completion bound. The HP packets will absolutely use 100% bandwidth of their reserved links if the HP packets are injected from the source node with maximum injection. Hence, the service are suitable for small size messages (less than hundred bytes). Otherwise the other HP and LP messages, which require also the links, will experience relatively high latency depending on the size of the HP message. The LP packets are routed using a minimal adaptive routing, while the HP packets are routed using a non-minimal adaptive routing algorithm. Therefore, an additional 3-bit field, identifying the packet type, is introduced in their packet headers to classify and to determine the type of service committed to the packet. Our NoC prototypes have been also synthesized using a 180-nm CMOS standard-cell technology to evaluate the cost of implementing the combination of both services.

Keywords: Network-on-Chip, Parallel Pipeline Router Architecture, Wormhole Switching, Two-Level Priority Service.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1765

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 1796

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 2422

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 2457

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 1553

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 2328

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 3881

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 7322

Authors: Farzana Yasmeen, Md. Nurul Huda, Md. Enamul Haque, Michihiro Aoki, Shigeki Yamada

Abstract:

Delay-Tolerant Networks (DTNs) are sparse, wireless networks where disconnections are common due to host mobility and low node density. The Message Ferrying (MF) scheme is a mobilityassisted paradigm to improve connectivity in DTN-like networks. A ferry or message ferry is a special node in the network which has a per-determined route in the deployed area and relays messages between mobile hosts (MHs) which are intermittently connected. Increased contact opportunities among mobile hosts and the ferry improve the performance of the network, both in terms of message delivery ratio and average end-end delay. However, due to the inherent mobility of mobile hosts and pre-determined periodicity of the message ferry, mobile hosts may often -miss- contact opportunities with a ferry. In this paper, we propose the combination of stationary ferry access points (FAPs) with MF routing to increase contact opportunities between mobile hosts and the MF and consequently improve the performance of the DTN. We also propose several placement models for deploying FAPs on MF routes. We evaluate the performance of the FAP placement models through comprehensive simulation. Our findings show that FAPs do improve the performance of MF-assisted DTNs and symmetric placement of FAPs outperforms other placement strategies.

Keywords: Service infrastructure, delay-tolerant network, messageferry routing, placement models.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1978

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 143

Authors: R. AliMohammadzadeh, M. Haghir Chehreghani, A. Zarnani, M. Rahgozar

Abstract:

Mining frequent tree patterns have many useful applications in XML mining, bioinformatics, network routing, etc. Most of the frequent subtree mining algorithms (i.e. FREQT, TreeMiner and CMTreeMiner) use anti-monotone property in the phase of candidate subtree generation. However, none of these algorithms have verified the correctness of this property in tree structured data. In this research it is shown that anti-monotonicity does not generally hold, when using weighed support in tree pattern discovery. As a result, tree mining algorithms that are based on this property would probably miss some of the valid frequent subtree patterns in a collection of trees. In this paper, we investigate the correctness of anti-monotone property for the problem of weighted frequent subtree mining. In addition we propose W3-Miner, a new algorithm for full extraction of frequent subtrees. The experimental results confirm that W3-Miner finds some frequent subtrees that the previously proposed algorithms are not able to discover.

Keywords: Semi-Structured Data Mining, Anti-Monotone Property, Trees.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1380