Search results for: traveling salesmen problem

Authors: Sujeet Kumar Singh, Shiv Prasad Yadav

Abstract:

This paper develops an approach for solving intuitionistic fuzzy linear fractional programming (IFLFP) problem where the cost of the objective function, the resources, and the technological coefficients are triangular intuitionistic fuzzy numbers. Here, the IFLFP problem is transformed into an equivalent crisp multi-objective linear fractional programming (MOLFP) problem. By using fuzzy mathematical programming approach the transformed MOLFP problem is reduced into a single objective linear programming (LP) problem. The proposed procedure is illustrated through a numerical example.

Keywords: triangular intuitionistic fuzzy number, linear programming problem, multi objective linear programming problem, fuzzy mathematical programming, membership function

Procedia PDF Downloads 532

Authors: Ching-Shoei Chiang

Abstract:

The Malfatti’s Problem solves the problem of fitting 3 circles into a right triangle such that these 3 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; we call it 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 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 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 Carc. We call these problems the Carc(Tn) problems. The CPU time it takes for Carc(T16) problem, which finds 136 circles inside a convex circular triangle with specified tangency properties, is less than one second.

Keywords: circle packing, computer-aided geometric design, geometric constraint solver, Malfatti’s problem

Procedia PDF Downloads 71

Authors: Noppadon Phumeechanya, Panita Wannapiroon

Abstract:

The purpose of this research is to design the ubiquitous scaffold learning environment using problem-based learning activities that enhance problem-solving skills and context awareness, and to evaluate the suitability of the ubiquitous scaffold learning environment using problem-based learning activities. We divide the research procedures into two phases. The first phase is to design the ubiquitous scaffold learning environment using problem-based learning activities, and the second is to evaluate the ubiquitous scaffold learning environment using problem-based learning activities. The sample group in this study consists of five experts selected using the purposive sampling method. We analyse data by arithmetic mean and standard deviation. The research findings are as follows; the ubiquitous scaffold learning environment using problem-based learning activities consists of three major steps, the first is preparation before learning. This prepares learners to acknowledge details and learn through u-LMS. The second is the learning process, where learning activities happen in the ubiquitous learning environment and learners learn online with scaffold systems for each step of problem solving. The third step is measurement and evaluation. The experts agree that the ubiquitous scaffold learning environment using problem-based learning activities is highly appropriate.

Keywords: ubiquitous learning environment scaffolding, learning activities, problem-based learning, problem-solving skills, context awareness

Procedia PDF Downloads 474

Authors: Kamariah Abu Bakar, Jennifer Way

Abstract:

This study investigated how young children (six years old) constructed and used representations in mathematics classroom; particularly in problem solving. The purpose of this study is to explore the ways children used representations in solving addition problems and to determine whether their representations can play a supportive role in understanding the problem situation and solving them correctly. Data collection includes observations, children’s artifact, photographs and conversation with children during task completion. The results revealed that children were able to construct and use various representations in solving problems. However, they have certain preferences in generating representations to support their problem solving.

Keywords: young children, representations, addition, problem solving

Procedia PDF Downloads 426

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, Pareto solutions, partial permutation set, structural graph

Procedia PDF Downloads 136

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 PDF Downloads 301

Authors: Guilherme Baldo Carlos

Abstract:

The flexible job-shop scheduling problem (FJSP) is an NP-hard combinatorial optimization problem, which can be applied to model several applications in a wide array of industries. This problem will have its importance increase due to the shift in the production mode that modern society is going through. The demands are increasing and for products personalized and customized. This work aims to apply a meta-heuristic called a genetic algorithm (GA) to solve this problem. A GA is a meta-heuristic inspired by the natural selection of Charles Darwin; it produces a population of individuals (solutions) and selects, mutates, and mates the individuals through generations in order to find a good solution for the problem. The results found indicate that the GA is suitable for FJSP solving.

Keywords: genetic algorithm, evolutionary algorithm, scheduling, flexible job-shop scheduling

Procedia PDF Downloads 117

Authors: Tao Zhang, Nan Yan

Abstract:

In recent years, the Chaoshan area, a special place located in the southeast of Guangdong province in China, actively protects religious heritage and is developing religious tourism, which is attracting many expatriate Chinese who are coming back for travel and to worship. This paper discussed three questions. Firstly, what is the current situation about the different social background of tourists’ motivation, satisfaction and behavioral intention? Secondly, is there a relationship between the motivation, satisfaction and behavioral intention and the different social backgrounds of tourists? Thirdly, what is the relationship between religious tourists’ motivation, satisfaction and behavioral intention? The research methods use a combination of qualitative analysis and quantitative analysis. Qualitative analysis uses the method of observation and interviews. Convenient sampling technique was used for quantitative analysis. The study showed that the different social backgrounds of tourists’ forms diverse cognition and experiences about religious tourism, and their motivations, satisfaction and behavioral intention as tourists vary. Tourists’ motivation and satisfaction has a positive phase relation. Tourists’ motivation with satisfaction as the intervening variable also has a positive phase effect on tourists’ behavior intention. The result shows that religious tourists’ motivations include experiencing a religious atmosphere, and having a rest and recreation. The result also shows that religious tourists want to travel with their family members and friends. While traveling, religious tourists like to talk with Buddhist monks or nuns. Compared to other tourism types, religious tourists have higher expectations about temple environment, traveling experience, peripheral service and temple management.

Keywords: behavioral intension, motivation, religious tourism, satisfaction

Procedia PDF Downloads 296

Authors: Laissa Mae Francisco, John Rolex Ingreso, Anna Krizel Menguito, Criselda Robrigado, Rej Maegan Tuazon

Abstract:

This study aims to determine and describe the existing relationship between number sense proficiency and problem-solving performance of grade seven students from Victorino Mapa High School, Manila. A paper pencil exam containing of 50-item number sense test and 5-item problem-solving test which measures their number sense proficiency and problem-solving performance adapted from McIntosh, Reys, and Bana were used as the research instruments. The data obtained from this study were interpreted and analyzed using the Pearson – Product Moment Coefficient of Correlation to determine the relationship between the two variables. It was found out that students who were low in number sense proficiency tend to be the students with poor problem-solving performance and students with medium number sense proficiency are most likely to have an average problem-solving performance. Likewise, students with high number sense proficiency are those who do excellently in problem-solving performance.

Keywords: number sense, performance, problem solving, proficiency

Procedia PDF Downloads 397

Authors: Pei Chin Lim

Abstract:

School of Mathematics and Science of Singapore Polytechnic offers a Basic Mathematics module to students who did not pass GCE O-Level Additional Mathematics. These students are weaker in Mathematics. In particular, they struggle with word problems and tend to leave them blank in tests and examinations. In order to improve students’ problem-solving skills, the school redesigned the Basic Mathematics module to incorporate Polya’s problem-solving methodology. During tutorial lessons, students have to work through learning activities designed to raise their metacognitive awareness by following Polya’s problem-solving process. To assess the effectiveness of the redesign, students’ working for a challenging word problem in the mid-semester test were analyzed. Sixty-five percent of students attempted to understand the problem by making sketches. Twenty-eight percent of students went on to devise a plan and implement it. Only five percent of the students still left the question blank. These preliminary results suggest that with regular exposure to an explicit and systematic problem-solving approach, weak students’ problem-solving skills can potentially be improved.

Keywords: mathematics education, metacognition, problem solving, weak students

Procedia PDF Downloads 134

Authors: Lamia Bourdache, Amar Djema

Abstract:

The effect of non-Newtonian property (power law index n) on traveling waves of thin layer of power law fluid flowing over an inclined plane is investigated. For this, a simplified second-order two-equation model (SM) is used. The complete model is second-order four-equation (CM). It is derived by combining the weighted residual integral method and the lubrication theory. This is due to the fact that at the beginning of the instability waves, a very small number of waves is observed. Using a suitable set of test functions, second order terms are eliminated from the calculus so that the model is still accurate to the second order approximation. Linear, spatial, and temporal stabilities are studied. For travelling waves, a particular type of wave form that is steady in a moving frame, i.e., that travels at a constant celerity without changing its shape is studied. This type of solutions which are characterized by their celerity exists under suitable conditions, when the widening due to dispersion is balanced exactly by the narrowing effect due to the nonlinearity. Changing the parameter of celerity in some range allows exploring the entire spectrum of asymptotic behavior of these traveling waves. The (SM) model is converted into a three dimensional dynamical system. The result is that the model exhibits bifurcation scenarios such as heteroclinic, homoclinic, Hopf, and period-doubling bifurcations for different values of the power law index n. The influence of the non-Newtonian parameter on the nonlinear development of these travelling waves is discussed. It is found at the end that the qualitative characters of bifurcation scenarios are insensitive to the variation of the power law index.

Keywords: inclined plane, nonlinear stability, non-Newtonian, thin film

Procedia PDF Downloads 257

Authors: Derkaoui Orkia, Lehireche Ahmed

Abstract:

The topic of this article is to exploring the potentialities of a powerful optimization technique, namely Semidefinite Programming, for solving NP-hard problems. This approach provides tight relaxations of combinatorial and quadratic problems. In this work, we solve the maximum clique problem using this relaxation. The clique problem is the computational problem of finding cliques in a graph. It is widely acknowledged for its many applications in real-world problems. The numerical results show that it is possible to find a maximum clique in polynomial time, using an algorithm based on semidefinite programming. We implement a primal-dual interior points algorithm to solve this problem based on semidefinite programming. The semidefinite relaxation of this problem can be solved in polynomial time.

Keywords: semidefinite programming, maximum clique problem, primal-dual interior point method, relaxation

Procedia PDF Downloads 192

Authors: Mehmet Hakan Karaata

Abstract:

In this paper, we first coin a new graph theocratic problem with numerous applications. Second, we provide two algorithms for the problem. The first solution is using a brute-force techniques, whereas the second solution is based on an initial identification of the cycles in the given graph. We then provide a correctness proof of the algorithm. The applications of the problem include graph analysis, graph drawing and network structuring.

Keywords: algorithm, cycle, graph algorithm, graph theory, network structuring

Procedia PDF Downloads 357

Authors: Hashini E. Mohottala

Abstract:

We report the combine use of Wikispaces (WikiS) and Group Problem Solving (GPS) sessions conducted in the introductory level physics classes. As a part of this new teaching tool, some essay type problems were posted on the WikiS in weekly basis and students were encouraged to participate in problem solving without providing numerical final answers but the steps. Wikispace is used as a platform for students to meet online and create discussions. Each week students were further evaluated on problem solving skills opening up more opportunity for peer interaction through GPS. Each group was given a different problem to solve and the answers were graded. Students developed a set of skills in decision-making, problem solving, communication, negotiation, critical and independent thinking and teamwork through the combination of WikiS and GPS.

Keywords: group problem solving (GPS), wikispace (WikiS), physics education, learning

Procedia PDF Downloads 388

Authors: Sourabh Joshi, Tarun Sharma, Anurag Sharma

Abstract:

Ant Colony Optimization is heuristic Algorithm which has been proven a successful technique applied on number of combinatorial optimization problems. Two variants of Ant Colony Optimization algorithm named Ant System and Max-Min Ant System are implemented in MATLAB to solve travelling Salesman Problem and the results are compared. In, this paper both systems are analyzed by solving the some Travelling Salesman Problem and depict which system solve the problem better in term of cost and time.

Keywords: Ant Colony Optimization, Travelling Salesman Problem, Ant System, Max-Min Ant System

Procedia PDF Downloads 447

Authors: Terence Soule, Tami Al Ghamdi

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 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, genetic algorithm, evolutionary computation, source and target

Procedia PDF Downloads 113

Authors: Ocotlán Díaz-Parra, Jorge A. Ruiz-Vanoye, Alejandro Fuentes-Penna, Beatriz Bernabe-Loranca, Patricia Ambrocio-Cruz, José J. Hernández-Flores

Abstract:

The Maritime Platform Transport Problem of Solid, Special and Dangerous Waste consist of to minimize the monetary value of carry different types of waste from one location to another location using ships. We offer a novel mathematical, the characterization of the problem and the use CPLEX to find the optimal values to solve the Solid, Special and Hazardous Waste Transportation Problem of offshore platforms instances of Mexican state-owned petroleum company (PEMEX). The set of instances used are WTPLib real instances and the tool CPLEX solver to solve the MPTPSSDW problem.

Keywords: oil platform, transport problem, waste, solid waste

Procedia PDF Downloads 441

Authors: Kalpana Dahiya

Abstract:

This paper discusses a two-level hierarchical time minimization transportation problem, which is an important class of transportation problems arising in industries. This problem has been studied by various researchers, and a number of polynomial time iterative algorithms are available to find its solution. All the existing algorithms, though efficient, have some shortcomings. The current study proposes an alternate solution algorithm for the problem that is more efficient in terms of computational time than the existing algorithms. The results justifying the underlying theory of the proposed algorithm are given. Further, a detailed comparison of the computational behaviour of all the algorithms for randomly generated instances of this problem of different sizes validates the efficiency of the proposed algorithm.

Keywords: global optimization, hierarchical optimization, transportation problem, concave minimization

Procedia PDF Downloads 121

Authors: Ivan Baravy

Abstract:

Interpolation problem, as it was initially posed in terms of polynomials, is well researched. However, further mathematical developments extended it significantly. Trigonometric interpolation is widely used in Fourier analysis, while its generalized representation as exponential interpolation is applicable to such problem of mathematical physics as modelling of Ziegler-Biersack-Littmark repulsive interatomic potentials. Formulated for finite fields, this problem arises in decoding Reed--Solomon codes. This paper shows the relation between different interpretations of the problem through the class of matrices of special structure - Hankel matrices.

Keywords: Berlekamp-Massey algorithm, exponential interpolation, finite fields, Hankel matrices, Hankel polynomials

Procedia PDF Downloads 483

Authors: Mahmoud Lot

Abstract:

In this article, we will discuss the solution of elliptic optimal control problem. First, by using the nite element method, we obtain the discrete form of the problem. The obtained discrete problem is actually a large scale constrained optimization problem. Solving this optimization problem with traditional methods is difficult and requires a lot of CPU time and memory. But split Bergman method converts the constrained problem to an unconstrained, and hence it saves time and memory requirement. Then we use the split Bregman method for solving this problem, and examples show the speed and accuracy of split Bregman methods for solving these types of problems. We also use the SQP method for solving the examples and compare with the split Bregman method.

Keywords: Split Bregman Method, optimal control with elliptic partial differential equation constraint, finite element method

Procedia PDF Downloads 115

Authors: Mohsen Ziaee

Abstract:

Almost all existing researches on the flowshop scheduling problems focus on the permutation schedules and there is insufficient study dedicated to the general flowshop scheduling problems in the literature, since the modeling and solving of the general flowshop scheduling problems are more difficult than the permutation ones, especially for the large-size problem instances. This paper considers the general flowshop scheduling problem with the objective function of the makespan (F//Cmax). We first find the optimal solution of the problem by solving a mixed integer linear programming model. An efficient heuristic method is then presented to solve the problem. An ant colony optimization algorithm is also proposed for the problem. In order to evaluate the performance of the methods, computational experiments are designed and performed. Numerical results show that the heuristic algorithm can result in reasonable solutions with low computational effort and even achieve optimal solutions in some cases.

Keywords: scheduling, general flow shop scheduling problem, makespan, heuristic

Procedia PDF Downloads 178

Authors: Cagri Memis, Muzaffer Kapanoglu

Abstract:

The school bus routing problem (SBRP) is a variant of the Vehicle Routing Problem (VRP) classified as a location-allocation-routing problem. In this study, the SBRP is decomposed into two sub-problems: (1) bus route generation and (2) bus stop selection to solve large instances of the SBRP in reasonable computational times. To solve the first sub-problem, we propose a genetic algorithm to generate bus routes. Once the routes have been fixed, a sub-problem remains of allocating students to stops considering the capacity of the buses and the walkability constraints of the students. While the exact method solves small-scale problems, treating large-scale problems with the exact method becomes complex due to computational problems, a deficiency that the genetic algorithm can overcome. Results obtained from the proposed approach on 150 instances up to 250 stops show that the matheuristic algorithm provides better solutions in reasonable computational times with respect to benchmark algorithms.

Keywords: genetic algorithm, matheuristic, school bus routing problem, vehicle routing problem

Procedia PDF Downloads 40

Authors: Javier Barrachina, Piedad Garrido, Manuel Fogue, Julio A. Sanguesa, Francisco J. Martinez

Abstract:

It is very common to observe, especially in Computer Science studies that students have difficulties to correctly understand how some mechanisms based on Artificial Intelligence work. In addition, the scope and limitations of most of these mechanisms are usually presented by professors only in a theoretical way, which does not help students to understand them adequately. In this work, we focus on the problems found when teaching Evolutionary Algorithms (EAs), which imitate the principles of natural evolution, as a method to solve parameter optimization problems. Although this kind of algorithms can be very powerful to solve relatively complex problems, students often have difficulties to understand how they work, and how to apply them to solve problems in real cases. In this paper, we present two interactive graphical applications which have been specially designed with the aim of making Evolutionary Algorithms easy to be understood by students. Specifically, we present: (i) TSPS, an application able to solve the ”Traveling Salesman Problem”, and (ii) FotEvol, an application able to reconstruct a given image by using Evolution Strategies. The main objective is that students learn how these techniques can be implemented, and the great possibilities they offer.

Keywords: education, evolutionary algorithms, evolution strategies, interactive learning applications

Procedia PDF Downloads 311

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, binarization methods, metaheuristic, set covering problem

Procedia PDF Downloads 367

Authors: Hernández Eva Selene, Reyna Mary Carmen, Rivera Héctor, Barragán Irving

Abstract:

We propose an approach that jointly addresses the layout of a facility and the scheduling of a sequence of jobs. In real production, these two problems are interrelated. However, they are treated separately in the literature. Our approach is an extension of the job shop problem with transportation delay, where the location of the machines is selected among possible sites. The model minimizes the makespan, using the short processing times rule with two algorithms; the first one considers all the permutations for the location of machines, and the second only a heuristic to select some specific permutations that reduces computational time. Some instances are proved and compared with literature.

Keywords: layout problem, job shop scheduling problem, concurrent scheduling and layout problem, metaheuristic

Procedia PDF Downloads 580

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, tabu search metaheuristic

Procedia PDF Downloads 346

Authors: Geyang Xia

Abstract:

In many countries, governments have responded to the growing demand for educational resources through school district systems, and there is substantial evidence that school district systems have been effective in promoting inter-district and inter-school equity in educational resources. However, the scarcity of quality educational resources has brought about varying levels of education among different school districts, making it a common choice for many parents to buy a house in the school district where a quality school is located, and they are even willing to bear huge commuting costs for this purpose. Moreover, this is evidenced by the fact that parents of families in school districts with quality education resources have longer average commute lengths and longer average commute distances than parents in average school districts. This "unequal traveling" under the influence of the school district system is more common in school districts at the primary level of education. This further reinforces the differential hierarchy of educational resources and raises issues of inequitable educational public services, education-led residential segregation, and gentrification of school district housing. Against this background, this paper takes Nanjing, a famous educational city in China, as a case study and selects the school districts where the top 10 public elementary schools are located. The study first identifies the spatio-temporal behavioral trajectory dataset of these high-quality school district households by using spatial vector data, decrypted cell phone signaling data, and census data. Then, by constructing a "house-school-work (HSW)" commuting pattern of the population in the school district where the high-quality educational resources are located, and based on the classification of the HSW commuting pattern of the population, school districts with long employment hours were identified. Ultimately, the mechanisms and patterns inherent in this unequal commuting are analyzed in terms of six aspects, including the centrality of school district location, functional diversity, and accessibility. The results reveal that the "unequal commuting" of Nanjing's high-quality school districts under the influence of the school district system occurs mainly in the peripheral areas of the city, and the schools matched with these high-quality school districts are mostly branches of prestigious schools in the built-up areas of the city's core. At the same time, the centrality of school district location and the diversity of functions are the most important influencing factors of unequal commuting in high-quality school districts. Based on the research results, this paper proposes strategies to optimize the spatial layout of high-quality educational resources and corresponding transportation policy measures.

Keywords: school-district system, high quality school district, commuting pattern, unequal traveling

Procedia PDF Downloads 64

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, binary matrices

Procedia PDF Downloads 374

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 PDF Downloads 165

Authors: Abubakar Sa’adatu Mohammed

Abstract:

This paper reports on a study of problem solving differences between expert and novice Problem solvers for effective physics teaching. Significant differences were found both at the conceptual level and at the level of critical thinking, creative thinking and reasoning. It is suggested for a successful solution of a problem, conceptual knowledge alone may not be sufficient. There is the need of the knowledge of how the conceptual knowledge should be applied (problem solving skills). It is hoped that this research might contribute to efforts of exploring ways for students to acquire a powerful conceptual toolkit based on experts like problem solvers approach for effective teaching delivery.

Keywords: conceptual knowledge, procedural knowledge, critical thinking, creative thinking, reasoning ability

Procedia PDF Downloads 265