Parallel algorithm for solving integer linear programs

Linear programs, or LPs, are often used in optimization problems, such as improving manufacturing efficiency of maximizing the yield from limited resources. The most common method for solving LPs is the Simplex Method, which will yield a solution, if one exists, but over the real numbers. From a purely numerical standpoint, it will be an optimal solution, but quite often we desire an optimal integer solution. A linear program in which the variables are also constrained to be integers is called an integer linear program or ILP. It is the focus of this report to present a parallel algorithm for solving ILPs. We discuss a serial algorithm using a breadth-first branch-and-bound search to check the feasible solution space, and then extend it into a parallel algorithm using a client-server model. In the parallel mode, the search may not be truly breadth-first, depending on the solution time for each node in the solution tree. Our search takes advantage of pruning, often resulting in super-linear improvements in solution time. Finally, we present results from sample ILPs, describe a few modifications to enhance the algorithm and improve solution time, and offer suggestions for future work.

Exigencies for engaging undergraduates in rhetorical problem solving : insights from engineering managers and A3 report analyses

Undergraduate education has a historical tradition of preparing students to meet the problem-solving challenges they will encounter in work, civic, and personal contexts. This thesis research was conducted to study the role of rhetoric in engineering problem solving and decision making and to pose pedagogical strategies for preparing undergraduate students for workplace problem solving. Exploratory interviews with engineering managers as well as the heuristic analyses of engineering A3 project planning reports suggest that Aristotelian rhetorical principles are critical to the engineer's success: Engineers must ascertain the rhetorical situation surrounding engineering problems; apply and adapt invention heuristics to conduct inquiry; draw from their investigation to find innovative solutions; and influence decision making by navigating workplace decision-making systems and audiences using rhetorically constructed discourse. To prepare undergraduates for workplace problem solving, university educators are challenged to help undergraduates understand the exigence and realize the kairotic potential inherent in rhetorical problem solving. This thesis offers pedagogical strategies that focus on mentoring learning communities in problem-posing experiences that are situated in many disciplinary, work, and civic contexts. Undergraduates build a flexible rhetorical technê for problem solving as they navigate the nuances of relevant problem-solving systems through the lens of rhetorical practice.

Problem Solving Policing: Views of Citizens and Citizens Expectations in Germany

For the last two decades American police experts developed new police philosophies in order to tackle more successful the increasing crime problems. Community Policing tries to improve the cooperation between the population and the police and to increase the trust in the police. A crucial factor is a meaningful cooperation between the police and the citizens. Problem Oriented Policing aims at structural changes in the organisation and the procedures of the police in public. The police have to investigate the hidden problems and conflicts of an individual offence and to create proactive and long term concepts for the social area of conflicts beyond the specific case. It is doubtful whether these philosophies can be implemented in Germany since the legality principle prohibits meaningful, trustworthy relationships between citizens and police officers. However, if one examines the results of surveys on citizens views and expectations towards the police one finds that the majority of the German citizens favour the postulates of community and problem oriented policing. They expect through these measures an improvement of their life situation in the community and the feelings of safety. If one takes these results seriously one has to question if the legality principle is still appropriate. It seems to hamper new, more promising policing styles which seem to improve life of it's citizens and reflect what the citizens want and expect from their police force.

Effectiveness of an Online Social Constructivist Mathematical Problem Solving Course for Malaysian Pre-Service Teachers

This study assessed the effectiveness of an online mathematical problem solving course designed using a social constructivist approach for pre-service teachers. Thirty-seven pre-service teachers at the Batu Lintang Teacher Institute, Sarawak, Malaysia were randomly selected to participate in the study. The participants were required to complete the course online without the typical face-to-face classes and they were also required to solve authentic mathematical problems in small groups of 4-5 participants based on the Polya’s Problem Solving Model via asynchronous online discussions. Quantitative and qualitative methods such as questionnaires and interviews were used to evaluate the effects of the online learning course. Findings showed that a majority of the participants were satisfied with their learning experiences in the course. There were no significant changes in the participants’ attitudes toward mathematics, while the participants’ skills in problem solving for “understand the problem” and “devise a plan” steps based on the Polya’s Model were significantly enhanced, though no improvement was apparent for “carry out the plan” and “review”. The results also showed that there were significant improvements in the participants’ critical thinking skills. Furthermore, participants with higher initial computer skills were also found to show higher performance in mathematical problem solving as compared to those with lower computer skills. However, there were no significant differences in the participants’ achievements in the course based on gender. Generally, the online social constructivist mathematical problem solving course is beneficial to the participants and ought to be given the attention it deserves as an alternative to traditional classes. Nonetheless, careful considerations need to be made in the designing and implementing of online courses to minimize problems that participants might encounter while participating in such courses.

The Effect of Proximity, Explicitness, and Representation of Basic Science Information on Student Clinical Problem-Solving

Problem: Medical and veterinary students memorize facts but then have difficulty applying those facts in clinical problem solving. Cognitive engineering research suggests that the inability of medical and veterinary students to infer concepts from facts may be due in part to specific features of how information is represented and organized in educational materials. First, physical separation of pieces of information may increase the cognitive load on the student. Second, information that is necessary but not explicitly stated may also contribute to the student’s cognitive load. Finally, the types of representations – textual or graphical – may also support or hinder the student’s learning process. This may explain why students have difficulty applying biomedical facts in clinical problem solving. Purpose: To test the hypothesis that three specific aspects of expository text – the patial distance between the facts needed to infer a rule, the explicitness of information, and the format of representation – affected the ability of students to solve clinical problems. Setting: The study was conducted in the parasitology laboratory of a college of veterinary medicine in Texas. Sample: The study subjects were a convenience sample consisting of 132 second-year veterinary students who matriculated in 2007. The age of this class upon admission ranged from 20-52, and the gender makeup of this class consisted of approximately 75% females and 25% males. Results: No statistically significant difference in student ability to solve clinical problems was found when relevant facts were placed in proximity, nor when an explicit rule was stated. Further, no statistically significant difference in student ability to solve clinical problems was found when students were given different representations of material, including tables and concept maps. Findings: The findings from this study indicate that the three properties investigated – proximity, explicitness, and representation – had no statistically significant effect on student learning as it relates to clinical problem-solving ability. However, ad hoc observations as well as findings from other researchers suggest that the subjects were probably using rote learning techniques such as memorization, and therefore were not attempting to infer relationships from the factual material in the interventions, unless they were specifically prompted to look for patterns. A serendipitous finding unrelated to the study hypothesis was that those subjects who correctly answered questions regarding functional (non-morphologic) properties, such as mode of transmission and intermediate host, at the family taxonomic level were significantly more likely to correctly answer clinical case scenarios than were subjects who did not correctly answer questions regarding functional properties. These findings suggest a strong relationship (p < .001) between well-organized knowledge of taxonomic functional properties and clinical problem solving ability. Recommendations: Further study should be undertaken investigating the relationship between knowledge of functional taxonomic properties and clinical problem solving ability. In addition, the effect of prompting students to look for patterns in instructional material, followed by the effect of factors that affect cognitive load such as proximity, explicitness, and representation, should be explored.

The role of computational logic as a hinge paradigm among deduction, problem solving, programming, and parallelism

This paper presents some brief considerations on the role of Computational Logic in the construction of Artificial Intelligence systems and in programming in general. It does not address how the many problems in AI can be solved but, rather more modestly, tries to point out some advantages of Computational Logic as a tool for the AI scientist in his quest. It addresses the interaction between declarative and procedural views of programs (deduction and action), the impact of the intrinsic limitations of logic, the relationship with other apparently competing computational paradigms, and finally discusses implementation-related issues, such as the efficiency of current implementations and their capability for efficiently exploiting existing and future sequential and parallel hardware. The purpose of the discussion is in no way to present Computational Logic as the unique overall vehicle for the development of intelligent systems (in the firm belief that such a panacea is yet to be found) but rather to stress its strengths in providing reasonable solutions to several aspects of the task.

Novel fast random search clustering approach for mixing matrix identification in MIMO linear blind inverse problems with sparse inputs

In this paper we propose a novel fast random search clustering (RSC) algorithm for mixing matrix identification in multiple input multiple output (MIMO) linear blind inverse problems with sparse inputs. The proposed approach is based on the clustering of the observations around the directions given by the columns of the mixing matrix that occurs typically for sparse inputs. Exploiting this fact, the RSC algorithm proceeds by parameterizing the mixing matrix using hyperspherical coordinates, randomly selecting candidate basis vectors (i.e. clustering directions) from the observations, and accepting or rejecting them according to a binary hypothesis test based on the Neyman–Pearson criterion. The RSC algorithm is not tailored to any specific distribution for the sources, can deal with an arbitrary number of inputs and outputs (thus solving the difficult under-determined problem), and is applicable to both instantaneous and convolutive mixtures. Extensive simulations for synthetic and real data with different number of inputs and outputs, data size, sparsity factors of the inputs and signal to noise ratios confirm the good performance of the proposed approach under moderate/high signal to noise ratios. RESUMEN. Método de separación ciega de fuentes para señales dispersas basado en la identificación de la matriz de mezcla mediante técnicas de "clustering" aleatorio.

Implementing the weakest failure detector for solving consensus

The concept of unreliable failure detector was introduced by Chandra and Toueg as a mechanism that provides information about process failures. This mechanism has been used to solve several agreement problems, such as the consensus problem. In this paper, algorithms that implement failure detectors in partially synchronous systems are presented. First two simple algorithms of the weakest class to solve the consensus problem, namely the Eventually Strong class (⋄S), are presented. While the first algorithm is wait-free, the second algorithm is f-resilient, where f is a known upper bound on the number of faulty processes. Both algorithms guarantee that, eventually, all the correct processes agree permanently on a common correct process, i.e. they also implement a failure detector of the class Omega (Ω). They are also shown to be optimal in terms of the number of communication links used forever. Additionally, a wait-free algorithm that implements a failure detector of the Eventually Perfect class (⋄P) is presented. This algorithm is shown to be optimal in terms of the number of bidirectional links used forever.

Membrane Systems Working with the PFactor: Best Strategy to Solve Complex Problems.

A membrane system is a massive parallel system, which is inspired by the living cells when processing information. As a part of unconventional computing, membrane systems are proven to be effective in solving complex problems. A new factor is introduced. This factor can decide whether a technique is worthwhile being used or not. The use of this factor provides the best chances for selecting the strategy for the rules application phase. Referring to the “best” is in reference to the one that reduces execution time within the membrane system. A pre-analysis of the membrane system determines the P-factor, which in return advises the optimal strategy to use. In particular, this paper compares the use of two strategies based on the P-factor and provides results upon the application of them. The paper concludes that the P-factor is an effective indicator for choosing the right strategy to implement the rules application phase in membrane systems.

The Proper Generalized Decomposition With Application In Problems Of Dynamics

In this paper we address the new reduction method called Proper Generalized Decomposition (PGD) which is a discretization technique based on the use of separated representation of the unknown fields, specially well suited for solving multidimensional parametric equations. In this case, it is applied to the solution of dynamics problems. We will focus on the dynamic analysis of an one-dimensional rod with a unit harmonic load of frequency (ω) applied at a point of interest. In what follows, we will present the application of the methodology PGD to the problem in order to approximate the displacement field as the sum of the separated functions. We will consider as new variables of the problem, parameters models associated with the characteristic of the materials, in addition to the frequency. Finally, the quality of the results will be assessed based on an example.

A time-domain finite element method for seakeeping and wave resistance problems

El objetivo de la tesis es la investigación de algoritmos numéricos para el desarrollo de herramientas numéricas para la simulación de problemas tanto de comportamiento en la mar como de resistencia al avance de buques y estructuras flotantes. La primera herramienta desarrollada resuelve el problema de difracción y radiación de olas. Se basan en el método de los elementos finitos (MEF) para la resolución de la ecuación de Laplace, así como en esquemas basados en MEF, integración a lo largo de líneas de corriente, y en diferencias finitas desarrollados para la condición de superficie libre. Se han desarrollado herramientas numéricas para la resolución de la dinámica de sólido rígido en sistemas multicuerpos con ligaduras. Estas herramientas han sido integradas junto con la herramienta de resolución de olas difractadas y radiadas para la resolución de problemas de interacción de cuerpos con olas. También se han diseñado algoritmos de acoplamientos con otras herramientas numéricas para la resolución de problemas multifísica. En particular, se han realizado acoplamientos con una herramienta numérica basada de cálculo de estructuras con MEF para problemas de interacción fluido-estructura, otra de cálculo de líneas de fondeo, y con una herramienta numérica de cálculo de flujos en tanques internos para problemas acoplados de comportamiento en la mar con “sloshing”. Se han realizado simulaciones numéricas para la validación y verificación de los algoritmos desarrollados, así como para el análisis de diferentes casos de estudio con aplicaciones diversas en los campos de la ingeniería naval, oceánica, y energías renovables marinas. ABSTRACT The objective of this thesis is the research on numerical algorithms to develop numerical tools to simulate seakeeping problems as well as wave resistance problems of ships and floating structures. The first tool developed is a wave diffraction-radiation solver. It is based on the finite element method (FEM) in order to solve the Laplace equation, as well as numerical schemes based on FEM, streamline integration, and finite difference method tailored for solving the free surface boundary condition. It has been developed numerical tools to solve solid body dynamics of multibody systems with body links across them. This tool has been integrated with the wave diffraction-radiation solver to solve wave-body interaction problems. Also it has been tailored coupling algorithms with other numerical tools in order to solve multi-physics problems. In particular, it has been performed coupling with a MEF structural solver to solve fluid-structure interaction problems, with a mooring solver, and with a solver capable of simulating internal flows in tanks to solve couple seakeeping-sloshing problems. Numerical simulations have been carried out to validate and verify the developed algorithms, as well as to analyze case studies in the areas of marine engineering, offshore engineering, and offshore renewable energy.

A stochastic approximation algorithm with Markov chain Monte-Carlo method for incomplete data estimation problems

We propose a general procedure for solving incomplete data estimation problems. The procedure can be used to find the maximum likelihood estimate or to solve estimating equations in difficult cases such as estimation with the censored or truncated regression model, the nonlinear structural measurement error model, and the random effects model. The procedure is based on the general principle of stochastic approximation and the Markov chain Monte-Carlo method. Applying the theory on adaptive algorithms, we derive conditions under which the proposed procedure converges. Simulation studies also indicate that the proposed procedure consistently converges to the maximum likelihood estimate for the structural measurement error logistic regression model.

An iterative method for solving nonsymmetric linear systems with dynamic estimation of parameters /

Vita.

Studies to develop and investigate an inverse formulation for numerically solving three-dimensional free surface potential fluid flows,

Research carried out under Naval Ship Systems Command, General Hydromechanics Research Program, subproject SR 009 01 01, administered by the Naval Ship Research and Development Center, contract no. N00014-67-A-0220-0003.

Theoretical and numerical analysis of large-scale heat transfer problems with temperature-dependent pore-fluid densities

Purpose - In many scientific and engineering fields, large-scale heat transfer problems with temperature-dependent pore-fluid densities are commonly encountered. For example, heat transfer from the mantle into the upper crust of the Earth is a typical problem of them. The main purpose of this paper is to develop and present a new combined methodology to solve large-scale heat transfer problems with temperature-dependent pore-fluid densities in the lithosphere and crust scales. Design/methodology/approach - The theoretical approach is used to determine the thickness and the related thermal boundary conditions of the continental crust on the lithospheric scale, so that some important information can be provided accurately for establishing a numerical model of the crustal scale. The numerical approach is then used to simulate the detailed structures and complicated geometries of the continental crust on the crustal scale. The main advantage in using the proposed combination method of the theoretical and numerical approaches is that if the thermal distribution in the crust is of the primary interest, the use of a reasonable numerical model on the crustal scale can result in a significant reduction in computer efforts. Findings - From the ore body formation and mineralization points of view, the present analytical and numerical solutions have demonstrated that the conductive-and-advective lithosphere with variable pore-fluid density is the most favorite lithosphere because it may result in the thinnest lithosphere so that the temperature at the near surface of the crust can be hot enough to generate the shallow ore deposits there. The upward throughflow (i.e. mantle mass flux) can have a significant effect on the thermal structure within the lithosphere. In addition, the emplacement of hot materials from the mantle may further reduce the thickness of the lithosphere. Originality/value - The present analytical solutions can be used to: validate numerical methods for solving large-scale heat transfer problems; provide correct thermal boundary conditions for numerically solving ore body formation and mineralization problems on the crustal scale; and investigate the fundamental issues related to thermal distributions within the lithosphere. The proposed finite element analysis can be effectively used to consider the geometrical and material complexities of large-scale heat transfer problems with temperature-dependent fluid densities.