A restricted Lagrangean approach to the traveling salesman problem

We describe an algorithm for the asymmetric traveling salesman problem (TSP) using a new, restricted Lagrangean relaxation based on the assignment problem (AP). The Lagrange multipliers are constrained so as to guarantee the continued optimality of the initial AP solution, thus eliminating the need for repeatedly solving AP in the process of computing multipliers. We give several polynomially bounded procedures for generating valid inequalities and taking them into the Lagrangean function with a positive multiplier without violating the constraints, so as to strengthen the current lower bound. Upper bounds are generated by a fast tour-building heuristic. When the bound-strengthening techniques are exhausted without matching the upper with the lower bound, we branch by using two different rules, according to the situation: the usual subtour breaking disjunction, and a new disjunction based on conditional bounds. We discuss computational experience on 120 randomly generated asymmetric TSP's with up to 325 cities, the maximum time used for any single problem being 82 seconds. This is a considerable improvement upon earlier methods. Though the algorithm discussed here is for the asymmetric TSP, the approach can be adapted to the symmetric TSP by using the 2-matching problem instead of AP.Research supported by the National Science Foundation through grant no. MCS76-12026 A02 and the U.S. Office of Naval Research through contract no. N0014-75-C-0621 NR 047-048.     

On the number of solutions to a class of complementarity problems

In this paper we consider the problem of establishing the number of solutions to the complementarity problem. For the case when the Jacobian of the mapping has all principal minors negative, and satisfies a condition at infinity, we prove that the problem has either 0, 1, 2 or 3 solutions. We also show that when the Jacobian has all principal minors positive, and satisfies a condition at infinity, the problem has a unique solution.Sponsored by the United States Army under Contract No. DAAG29-75-C-0024. This material is based upon work supported by the National Science Foundation under Grant No. MCS77-03472 and Grant No. MCS78-09525. This work appeared as an MRC Technical Report No. 1964, University of Wisconsin, Madison, WI, June 1979.     

Facilitating an Elementary Engineering Design Process Module

STEM education in elementary school is guided by the understanding that engineering represents the application of science and math concepts to make life better for people. The Engineering Design Process (EDP) guides the application of creative solutions to problems. Helping teachers understand how to apply the EDP to create lessons develops a classroom where students are engaged in solving real world problems by applying the concepts they learn about science and mathematics. This article outlines a framework for developing such lessons and units, and discusses the underlying theory of systems thinking. A model lesson that uses this framework is discussed. Misconceptions regarding the EDP that children have displayed through this lesson and other design challenge lessons are highlighted. Through understanding these misconceptions, teachers can do a better job of helping students understand the system of ideas that helps engineers attack problems in the real world. Getting children ready for the 21st century requires a different outlook. Children need to tackle problems with a plan and not shrivel when at first, they fail. Seeing themselves as engineers will help more underrepresented students see engineering and other STEM fields as viable career options, which is our ultimate goal.     

Ants can orienteer a thief in their robbery

The Thief Orienteering Problem (ThOP) is a multi-component problem that combines features of two classic combinatorial optimization problems: Orienteering Problem and Knapsack Problem. The ThOP is challenging due to the given time constraint and the interaction between its components. We propose an Ant Colony Optimization algorithm together with a new packing heuristic to deal individually and interactively with problem components. Our approach outperforms existing work on more than 90% of the benchmarking instances, with an average improvement of over 300%.     

Investigating young students’ multiplicative thinking: The 12 little ducks problem

Children’s multiplicative thinking as the visualization of equal group structures and the enumeration the composite units was the subject of this study. The results were obtained from a small sample of Australian children (n = 18) in their first year of school (mean age 5 years 6 months) who participated in a lesson taught by their classroom teacher. The 12 Little Ducks problem stimulated children to visualize and to draw different ways of making equal groups. Fifteen children (83 %) could identify and create equal groups; eight of these children (44 %) could also quantify the number of groups they formed. These findings show that some young children understand early multiplicative ideas and can visualize equal group situations and communicate about these through their drawings and talk. The study emphasises the value of encouraging mathematical visualization from an early age; using open thought-provoking problems to reveal children’s thinking; and promoting drawing as a form of mathematical communication.     

Covering shadows with a smaller volume

For n?2 a construction is given for convex bodies K and L in Rn such that the orthogonal projection Lu onto the subspace u^⊥ contains a translate of Ku for every direction u, while the volumes of K and L satisfy Vn(K)>Vn(L).A more general construction is then given for n-dimensional convex bodies K and L such that each orthogonal projection Lξ onto a k-dimensional subspace ξ contains a translate of Kξ, while the mth intrinsic volumes of K and L satisfy Vm(K)>Vm(L) for all m>k.For each k=1,…,n, we then define the collection Cn,k to be the closure (under the Hausdorff topology) of all Blaschke combinations of suitably defined cylinder sets (prisms).It is subsequently shown that, if L∈Cn,k, and if the orthogonal projection Lξ contains a translate of Kξ for every k-dimensional subspace ξ of Rn, then Vn(K)?Vn(L).The families Cn,k, called k-cylinder bodies of Rn, form a strictly increasing chain

Cn,1⊂Cn,2⊂?⊂Cn,n−1⊂Cn,n,     

Engaging in problem posing activities in a dynamic geometry setting and the development of prospective teachers’ mathematical knowledge

In the present study we explore changes in perceptions of our class of prospective mathematics teachers (PTs) regarding their mathematical knowledge. The PTs engaged in problem posing activities in geometry, using the “What If Not?” (WIN) strategy, as part of their work on computerized inquiry-based activities. Data received from the PTs’ portfolios reveals that they believe that engaging in the inquiry-based activity enhanced both their mathematical and meta-mathematical knowledge. As to the mathematical knowledge, they deepened their knowledge regarding the geometrical concepts and shapes involved, and during the process of creating the problem and checking its validity and its solution, they deepened their understanding of the interconnections among the concepts and shapes involved. As to meta-mathematical knowledge, the PTs refer to aspects such as the meaning of the givens and their relations, validity of an argument, the importance and usefulness of the definitions of concepts and objects, and the importance of providing a formal proof.     

Systematic approaches to experimentation: The case of Pick's theorem

In this paper two 10th graders having an accumulated experience on problem-solving ancillary to the concept of area confronted the task to find Pick's formula for a lattice polygon's area. The formula was omitted from the theorem in order for the students to read the theorem as a problem to be solved. Their working is examined and emphasis is given to highlighting the students’ range of systematic approaches to experimentation in the context of problem solving and aspects of control that are reflected in these approaches.     

弱化希尔伯特第16问题及其研究现状

V.I.Arnold多次提出如下问题:对于给定的自然数n≥2,所有n次多项式1-形式,沿一切可能的m≥3次闭代数曲线族的阿贝尔积分的孤立零点的最大个数Z(m,n)=?由Poincare-Pontryagin定理可知,当阿贝尔积分不恒为零时,A(n)=Z(n+1,n)给出n次Hamilton系统在n次多项式扰动下从原有周期环域分支出极限环的最大个数,因此Arnold把这个问题称为弱化的希尔伯特第16问题.30多年来,对此问题的研究取得了一定进展,也遇到了很大困难.本文拟对这个问题和相关研究工作做一个粗浅的介绍.     

A multi-level search strategy for the 0-1 Multidimensional Knapsack Problem

We propose an exact method based on a multi-level search strategy for solving the 0-1 Multidimensional Knapsack Problem. Our search strategy is primarily based on the reduced costs of the non-basic variables of the LP-relaxation solution. Considering that the variables are sorted in decreasing order of their absolute reduced cost value, the top level branches of the search tree are enumerated following Resolution Search strategy, the middle level branches are enumerated following Branch & Bound strategy and the lower level branches are enumerated according to a simple Depth First Search enumeration strategy. Experimentally, this cooperative scheme is able to solve optimally large-scale strongly correlated 0-1 Multidimensional Knapsack Problem instances. The optimal values of all the 10 constraint, 500 variable instances and some of the 30 constraint, 250 variable instances of the OR-Library were found. These values were previously unknown.