Random polytopes: Their definition,generation and aggregate properties

The definition of random polytope adopted in this paper restricts consideration to those probability measures satisfying two properties. First, the measure must induce an absolutely continuous distribution over the positions of the bounding hyperplanes of the random polytope; and second, it must result in every point in the space being equally as likely as any other point of lying within the random polytope. An efficient Monte Carlo method for their computer generation is presented together with analytical formulas characterizing their aggregate properties. In particular, it is shown that the expected number of extreme points for such random polytopes increases monotonically in the number of constraints to the limiting case of a polytope topologically equivalent to a hypercube. The implied upper bound of 2 ⁿ wheren is the dimensionality of the space is significantly less than McMullen's attainable bound on the maximal number of vertices even for a moderate number of constraints.     

Polyhedral extensions of some theorems of linear programming

Three theorems of linear programming form our starting point: Tucker's theorem (1956) concerning the existence of optimal solutions satisfying the complementary slackness conditions strictly, and Williams' two theorems (1970) concerning the coordinatewise complementary behavior of feasible and optimal solutions. Here, we establish that the same phenomena hold in another, more versatile framework involving general polyhedral convexity. As one main application, the results are transferred into the context of the monotone complementarity problem. Several other theoretical applications are indicated.Research supported in part by the National Science Foundation under grant number MCS 79-05793 at the University of Illinois at Urbana-Champaign.     

Conforming finite element computations applied to a spatially periodic,harmonic Navier-Stokes problem

In this paper computations in the two dimensional case of a harmonic Navier-Stokes problem with periodic boundary conditions are presented. This study of an incompressible viscous fluid leads to a non-symmetric linear problem (very low Reynolds number). Moreover unknown functions have complex values (monochromatic dynamic behaviour). Numerical treatment of the incompressibility condition is a generalization of the classical treatment of Stokes problem. A mixed formulation, where discrete pressure plays the role of Lagrange multipliers is used (Uzawa algorithm). Two conforming finite element methods are tested on different meshes. The second one uses a classical refinement in the shape function: the so-called bulb function. All computational tests show that the use of a bulb function on each element gives better results than refinement in the mesh without introducing too many degrees of freedom. Finally numerical results are compared to experimental data.     

Steiner's problem and fagnano's result on the sphere

This note describes the nature of optimal solutions for the spherical Steiner-Weber location problem for the case of unit weights and either 3 or 4 demand points (requireing 4 demand points to lie in an open hemisphere). Geometrically appealing results which are necessary conditions for optimum solutions and spherical analogs of known planar results are obtained.     

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.     

Examining the design features of a communication-rich,problem-centred mathematics professional development

While there is considerable scholarship describing principles for effective professional development, there have been few attempts to examine these principles in practice. In this paper, we identify and examine the particular design features of a mathematics professional development experience provided for middle grades teachers over 14 weeks. The professional development was grounded in a set of mathematical tasks that each had one right answer, but multiple solution paths. The facilitator engaged participants in problem solving and encouraged participants to work collaboratively to explore different solution paths. Through analysis of this collaborative learning environment, we identified five design features for supporting teacher learning of important mathematics and pedagogy in a problem-solving setting. We discuss these design features in depth and illustrate them by presenting an elaborated example from the professional development. This study extends the existing guidance for the design of professional development by examining and operationalizing the relationships among research-based features of effective professional development and the enacted features of a particular design.     

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.     

Prospective teachers anticipate challenges fostering the mathematical practice of making sense

Problem solving has long been a priority in mathematics education, and the first Common Core mathematical practice (SMP1) focuses on this priority through the language of “Make sense of problems and persevere in solving them.” We present findings from a survey about how prospective elementary teachers' (PTs) make sense of potential difficulties with fostering SMP1. Findings suggested that PTs' common anticipated difficulties relate to planning a solution pathway and self monitoring whether the solution makes sense. Moreover, a third of PTs disclosed that their anticipated difficulties are linked to their own personal struggles with aspects of SMP1. An alternative interpretation of SMP1 surfaced in which a small number of PTs described SMP1 as necessitating that a teacher teach multiple solution methods to students, instead of engaging students in productive struggle to develop their own strategies. We present a framework illustrating the connections between SMP 1 and Pólya's problem solving phases, and we discuss how these findings connect to and build on previous research of PTs' experiences with problem solving. We offer implications for the targeted support needed in teacher preparation programs to address these struggles, to prevent them from being replicated in their students.     

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%.