Construction of Selection Indexes with Restrictions

In this paper the problem of unistage selection with inequality constraints is formulated. If the predictor and criterion variables are all normally distributed, this problem can be written as a convex programming problem, with a linear objective function and with linear constraints and a quadratic constraint. Using the duality theory, for convex nonlinear programming it is proved, that its dual problem can be transformed into a convex minimization problem with non-negativity conditions. Good computational methods are known for solving this problem. By the help of the dual problem sufficient conditions for a solution of the original primal problem are derived and illustrated by an example of practical interest.     

A special view on the nature of the allocation problem

One of the remaining important problems of life cycle inventory analysis is the allocation problem. A proper solution of this problem calls for a proper understanding of the nature of the problem itself. This paper argues that the established definition of the allocation problem as the fact that one unit process produces more than one function, is not appropriate. That definition points to an important reason of the occurrence of the problem, but the situation of internal (closed-loop) recycling already indicates that there may be product systems which contain multifunction processes, but which nevertheless need not exhibit an allocation problem. The paper proceeds by examining a number of simple hypothetical cases, and proposes a precise and operational definition of the allocation problem. This enables a systematic categorization of approaches for dealing with the allocation problem.     

Pathocoenoses ancient and modern

Problems concerning the concept of biocoenosis in ecology (the antecedent of the pathocoenosis concept) are discussed first of all. Six main problems are identified: the problem of emergent properties of ecological communities; the problem of ambiguity; the problem of heterogeneity; the boundary problem; the problem of retrospective differential diagnosis; and the problem of explaining change over time. The rest of the paper gives illustrations of these problems in relation to human pathogens drawn mainly from the interactions of malaria with other diseases, particularly but not exclusively in the Mediterranean world, from antiquity through to modern times.     

The component retrieval problem in printed circuit board assembly

Minimization of the makespan of a printed circuit board assembly process is a complex problem. Decisions involved in this problem concern the specification of the order in which components are to be placed on the board and the assignment of component types to the feeder slots of the placement machine. If some component types are assigned to multiple feeder slots, an additional problem emerges: for each placement on the board, one must select the feeder slot from which the required component is to be retrieved. In this paper, we consider this component retrieval problem for placement machines of the Fuji CP type. We explain why simple forward dynamic programming schemes cannot provide a solution to this problem, invalidating the correctness of an algorithm proposed by Bard, Clayton, and Feo (1994). We then present a polynomial algorithm that solves the problem to optimality. The analysis of the component retrieval problem is facilitated by its reformulation as a PERT/CPM problem with design aspects: finding the minimal makespan of the assembly process amounts to identifying a design for which the longest path in the induced PERT/CPM network is shortest. The complexity of this network problem is analyzed, and we prove that the polynomial solvability of the component retrieval problem is caused by the specific structure it inflicts on the arc lengths of the network: in the absence of this structure, the network problem is shown to be NP-hard.     

What Do Experts and Novices ��See�� in Evolutionary Problems?

Considerable research has focused on differences in expert and novice problem representation and performance within physics, chemistry, and genetics. Here, we examine whether models of problem solving based on this work are useful within the domain of evolutionary biology. We utilized card sort tasks, interviews, and paper-and-pencil tests to: (1) delineate problem categorization rules, (2) quantify problem solving success, and (3) measure the relationships between the composition, structure, and coherence of problem solutions. We found that experts and novices perceived different item features to be of significance in card sort tasks, and that sensitivity to item surface features was adversely associated with problem solving success. As in other science domains, evolutionary problem representation and problem solving performance were tightly coupled. Explanatory coherence and the absence of cognitive biases were distinguishing features of evolutionary expertise. We discuss the implications of these findings for biology teaching and learning.     

Construction of DNA restriction maps based on a simplified experiment

MOTIVATION: A formulation of a new problem of the restriction map construction based on a simplified digestion experiment and a development of an algorithm for solving both ideal and noisy data cases of the introduced problem. RESULTS: A simplified partial digest problem and a branch and cut algorithm for finding the solution of the problem.     

The Gene-Duplication Problem: Near-Linear Time Algorithms for NNI-Based Local Searches

The gene-duplication problem is to infer a species supertree from a collection of gene trees that are confounded by complex histories of gene-duplication events. This problem is NP-complete and thus requires efficient and effective heuristics. Existing heuristics perform a stepwise search of the tree space, where each step is guided by an exact solution to an instance of a local search problem. A classical local search problem is the {tt NNI} search problem, which is based on the nearest neighbor interchange operation. In this work, we 1) provide a novel near-linear time algorithm for the {tt NNI} search problem, 2) introduce extensions that significantly enlarge the search space of the {tt NNI} search problem, and 3) present algorithms for these extended versions that are asymptotically just as efficient as our algorithm for the {tt NNI} search problem. The exceptional speedup achieved in the extended {tt NNI} search problems makes the gene-duplication problem more tractable for large-scale phylogenetic analyses. We verify the performance of our algorithms in a comparison study using sets of large randomly generated gene trees.     

Reactive scheduling model for the operating theatre

This paper addresses the disruption management and rescheduling problem of the day-to-day running of a day surgery unit. The problem is modelled as a single machine scheduling problem with sequence dependent processing times and due dates. The proposed optimisation model sequences both elective and non-elective patients in the online environment. The weighted number of expected surgeries to complete on-time is maximised. We propose a branch and bound algorithm to solve the problem. Computational experiments are conducted illustrating its applicability to the problem of reactive scheduling in the operating theatre.     

Extensions and improvements to the chordal graph approach to the multistate perfect phylogeny problem

The multistate perfect phylogeny problem is a classic problem in computational biology. When no perfect phylogeny exists, it is of interest to find a set of characters to remove in order to obtain a perfect phylogeny in the remaining data. This is known as the character removal problem. We show how to use chordal graphs and triangulations to solve the character removal problem for an arbitrary number of states, which was previously unsolved. We outline a preprocessing technique that speeds up the computation of the minimal separators of a graph. Minimal separators are used in our solution to the missing data character removal problem and to Gusfield's solution of the perfect phylogeny problem with missing data.     

Optimal just-in-time schedules for flexible transfer lines

Flexible transfer lines or mixed-model assembly lines are capable of diversified small-lot production due to negligible switch-over costs. With these lines, it is possible to implement just-in-time (JIT) production, which involves producing only the necessary parts in the necessary quantities at the necessary times. The problem of sequencing flexible transfer lines according to the JIT philosophy can be formulated as a nonlinear integer programming problem. Heuristic algorithms to solve the problem have appeared in the literature. In this paper, we show that the problem can be explicitly reduced to an assignment problem. Thus, we provide an efficient algorithm for an optimal solution to the JIT sequencing problem.     

Temporal dynamics of mental impasses underlying insight-like problem solving

Insight problem solving is characterized by mental impasses,states of mind in which the problem solver does not know what to do next.Although many studies have investigated the neural correlates of insight problem solving,however,the question when mental impasses occur during insight problem solving has been rarely studied.The present study adopted high temporal resolution ERPs to investigate the temporal dynamics of an impasse underlying insight problem solving.Time locked ERPs were recorded associated with problems with impasses(PWI) and problems without impasses(POI).The problem types were determined by participants’ subjective responses.The results revealed an early frontocentral P2 was linked with the preconscious awareness of mental impasses and a P3a was associated with fixed attention when the impasse formed.These findings suggest the impasse may occur initially at a relatively early stage and metacognition plays an important role in insight problem solving.     

Modelling the effect of immigration on drinking behaviour

A drinking model with immigration is constructed. For the model with problem drinking immigration, the model admits only one problem drinking equilibrium. For the model without problem drinking immigration, the model has two equilibria, one is problem drinking-free equilibrium and the other is problem drinking equilibrium. By employing the method of Lyapunov function, stability of all kinds of equilibria is obtained. Numerical simulations are also provided to illustrate our analytical results. Our results show that alcohol immigrants increase the difficulty of the temperance work of the region.     

Analysis of mussel growth data*

This short paper considers the problem of estimating the year of birth of a mussel picked at an unknown time. This is an important problem not only for studying a certain mussel population but also for environmental monitoring. A mathematical formulation of the problem is presented, which leads to a combined delay estimation and constrained linear regression problem. A solution is developed and applied to the estimation problem. Examples with mussels picked from a river in Sweden are shown, which demonstrate that the proposed technique works well in practice.     

An Omega(n2/ log n) speed-up of TBR heuristics for the gene-duplication problem

The gene-duplication problem is to infer a species supertree from gene trees that are confounded by complex histories of gene duplications. This problem is NP-hard and thus requires efficient and effective heuristics. Existing heuristics perform a stepwise search of the tree space, where each step is guided by an exact solution to an instance of a local search problem. We improve on the time complexity of the local search problem by a factor of n2= log n, where n is the size of the resulting species supertree. Typically, several thousand instances of the local search problem are solved throughout a stepwise heuristic search. Hence, our improvement makes the gene-duplication problem much more tractable for large-scale phylogenetic analyses.     

Effective haplotype assembly via maximum Boolean satisfiability

The haplotype assembly problem seeks the haplotypes of an individual from which a set of aligned SNP fragments are available. The problem is important as the haplotypes contain all the SNP information, which is essential to such studies as the analysis of the association between specific diseases and their potential genetic causes. Using Minimum Error Correction as the objective function, the problem is NP-hard, which raises the demand for effective yet affordable solutions. In this paper, we propose a new method to solve the problem by providing a novel Max-2-SAT formulation for the problem. The proposed method is compared with several well-known algorithms proposed for the problem in the literature on a recent extensive benchmark, outperforming them all by achieving solutions of higher average quality.     

生态学中一类n维反应扩散方程组解的性质

本文讨论一类不满足所谓的拟单调条件的反应扩散方程组的初边值问题．应用谱论和单调性方法证明了问题解的存在唯一性和平衡解的渐近稳定性．并进一步讨论了生态学中n种群单食物链模型的第二初值问题,得到了问题的非负平衡解的存在性和渐近性以及相应的吸引区域．     

Genome aliquoting revisited

We prove that the genome aliquoting problem, the problem of finding a recent polyploid ancestor of a genome, with breakpoint distance can be solved in polynomial time. We propose an aliquoting algorithm that is a 2-approximation for the genome aliquoting problem with double cut and join distance, improving upon the previous best solution to this problem, Feij?o and Meidanis' 4-approximation algorithm.     

Is optimal solution of every NP-complete or NP-hard problem determined from its characteristic for DNA-based computing

Cook's Theorem [Cormen, T.H., Leiserson, C.E., Rivest, R.L., 2001. Introduction to Algorithms, second ed., The MIT Press; Garey, M.R., Johnson, D.S., 1979. Computer and Intractability, Freeman, San Fransico, CA] is that if one algorithm for an NP-complete or an NP-hard problem will be developed, then other problems will be solved by means of reduction to that problem. Cook's Theorem has been demonstrated to be correct in a general digital electronic computer. In this paper, we first propose a DNA algorithm for solving the vertex-cover problem. Then, we demonstrate that if the size of a reduced NP-complete or NP-hard problem is equal to or less than that of the vertex-cover problem, then the proposed algorithm can be directly used for solving the reduced NP-complete or NP-hard problem and Cook's Theorem is correct on DNA-based computing. Otherwise, a new DNA algorithm for optimal solution of a reduced NP-complete problem or a reduced NP-hard problem should be developed from the characteristic of NP-complete problems or NP-hard problems.     

Perfect phylogenetic networks with recombination.

The perfect phylogeny problem is a classical problem in evolutionary tree construction. In this paper, we propose a new model called phylogenetic network with recombination that takes recombination events into account. We show that the problem of finding a perfect phylogenetic network with the minimum number of recombination events is NP-hard; we also present an efficient polynomial time algorithm for an interesting restricted version of the problem.     

蚂蚁群落优化算法在蛋白质折叠二维亲-疏水格点模型中的应用

氨基酸的亲疏水格点模型是研究蛋白质折叠的一种重要的简化模型,其优化问题是一个非确定型的多项式问题。采用蚂蚁群落优化算法对这一问题进行了研究,对测试数据的计算结果表明,在一定规模下,此算法能够有效地获得亲-疏水格点模型的最优解,其效率优于传统的Monte Carlo仿真等方法。