An algebraic and combinatorial approach to the analysis of line drawings of polyhedra

Mathematical structures of line drawings of polyhedral scenes are studied from the viewpoint of scene analysis. First, algebraic structures of line drawings are elucidated, and a necessary and sufficient condition is obtained for a line drawing to represent a polyhedron. Next, combinatorial structures are investigated and the class of pictures that represent nontrivial three-dimensional configurations when vertices are drawn in general position is characterized by incidence structures of polyhedra. The results are furthermore applied to correction of vertex-position errors, discrimination between correct and incorrect line drawings, recognition of unique solvability of some figure-construction problems, classification of line drawings, and other related problems.     

On a learning precedence graph concept for the automotive industry

Assembly line balancing problems (ALBP) consist in assigning the total workload for manufacturing a product to stations of an assembly line as typically applied in automotive industry. The assignment of tasks to stations is due to restrictions which can be expressed in a precedence graph. However, (automotive) manufacturers usually do not have sufficient information on their precedence graphs. As a consequence, the elaborate solution procedures for different versions of ALBP developed by more than 50 years of intensive research are often not applicable in practice.Unfortunately, the known approaches for precedence graph generation are not suitable for the conditions in the automotive industry. Therefore, we describe a new graph generation approach that is based on learning from past feasible production sequences and forms a sufficient precedence graph that guarantees feasible line balances. Computational experiments indicate that the proposed procedure is able to approximate the real precedence graph sufficiently well to detect optimal or nearly optimal solutions for a well-known benchmark data set. Even for additional large instances with up to 1,000 tasks, considerable improvements of line balances are possible. Thus, the new approach seems to be a major step to close the gap between theoretical line balancing research and practice of assembly line planning.     

Designing a mixed-model,open-station assembly line using mixed-integer programming

An open-station assembly line that manufactures mixed models of sheet metal cabinets is considered in this research. The problem minimizes the total cost of the idle and utility times incurred in an assembly line with different line parameters (such as launch interval, station length, starting point of work, upstream walk, locus of the operator's movement, etc.) and operation sequences of the mixed models. An open-station system plays a significant controlling role in determining the optimal line parameters that minimize the total cost of idle and utility times in a mixed-model assembly line. Thus, a mixed-integer programming model for an open-station system is developed here to determine line parameters optimally. The model is tested on a three-station mixed-model line, which is a partial representation of a complete long assembly line. This research obtained a set of line parameters that minimize the total cost of idle and utility times optimally. Results indicate that the minimum total cost of idle and utility times in an open-station system decreases with line length. Other results pertinent to the line design are also demonstrated.     

Convergence of nonmonotone line search method

In this paper, we develop a new nonmonotone line search for general line search method and establish some global convergence theorems. The new nonmonotone line search is a novel form of the nonmonotone Armijo line search and allows one to choose a larger step size at each iteration, which is available in constructing new line search methods and possibly reduces the function evaluations at each iteration. Moreover, we analyze the convergence rate of some special line search methods with the new line search. Preliminary numerical results show that some line search methods with the new nonmonotone line search are available and efficient in practical computation.     

Convergence of descent method with new line search

An efficient descent method for unconstrained optimization problems is line search method in which the step size is required to choose at each iteration after a descent direction is determined. There are many ways to choose the step sizes, such as the exact line search, Armijo line search, Goldstein line search, and Wolfe line search, etc. In this paper we propose a new inexact line search for a general descent method and establish some global convergence properties. This new line search has many advantages comparing with other similar inexact line searches. Moreover, we analyze the global convergence and local convergence rate of some special descent methods with the new line search. Preliminary numerical results show that the new line search is available and efficient in practical computation.     

Computing a flattest, undercut-free parting line for a convex polyhedron, with application to mold design

A parting line for a polyhedron is a closed curve on its surface, which identifies the two halves of the polyhedron for which mold-boxes must be made. A parting line is undercut-free if the two halves that it generates do not contain facets that obstruct the de-molding of the polyhedron. Computing an undercut-free parting line that is as “flat” as possible is an important problem in mold design. In this paper, algorithms are presented to compute such a parting line for a convex polyhedron, based on different flatness criteria.     

The Envelope of Lines Meeting a Fixed Line and Tangent to Two Spheres

We study the set of lines that meet a fixed line and are tangent to two spheres and classify the configurations consisting of a single line and three spheres for which there are infinitely many lines tangent to the three spheres that also meet the given line. All such configurations are degenerate. The path to this result involves the interplay of some beautiful and intricate geometry of real surfaces in 3-space, complex projective algebraic geometry, explicit computation and graphics.     

A branch-and-bound algorithm to minimize the line length of a two-sided assembly line

A new branch-and-bound algorithm is presented to solve the two-sided assembly line balancing problem of type 1 (TALB-1). First, a pair of two directly facing station is defined as a position, and then the two-sided assembly line (TAL) is relaxed to a one-sided assembly line (OAL). Some new lower bound on positions are computed, and dominance rules and reduction rules for the one-sided assembly line balancing problem of type 1 (OALB-1) are extended and incorporated into a station-oriented assignment procedure for the TALB-1 problem. Finally, the tests are carried out on a well-known benchmark set of problem instances, and experimental results demonstrate that the proposed procedure is efficient.     

On the Helly Number for Line Transversals to Parallel Triangles

We prove two results about the problem of finding the Helly number for line transversals to a family of parallel triangles in the plane: (1) If each three triangles of a family of parallel right triangles are intersected by an ascending (or a descending) line, then there is an ascending (or a descending) line that intersects all     

Line perfect graphs

The concept of line perfection of a graph is defined so that a simple graph is line perfect if and only if its line graph is perfect in the usual sense. Line perfect graphs are characterized as those which contain no odd cycles of size larger than 3. Two well-know theorems of König for bipartite graphs are shown to hold also for line perfect graphs; this extension provides a reinterpretation of the content of these theorems.Supported by National Science Foundation Grants GK-42095 and ENG 76-09936.     

Some fundamental issues of basic line search algorithm for linear programming problems

In this article we present the fundamental idea, concepts and theorems of a basic line search algorithm for solving linear programming problems which can be regarded as an extension of the simplex method. However, unlike the iteration of the simplex method from a basic point to an improved adjacent basic point via pivot operation, the basic line search algorithm, also by pivot operation, moves from a basic line which contains two basic feasible points to an improved basic line which also contains two basic feasible points whose objective values are no worse than that of the two basic feasible points on the previous basic line. The basic line search algorithm may skip some adjacent vertices so that it converges to an optimal solution faster than the simplex method. For example, for a 2-dimensional problem, the basic line search algorithm can find an optimal solution with only one iteration.     

Global convergence of BFGS and PRP methods under a modified weak Wolfe–Powell line search

The BFGS method is one of the most effective quasi-Newton algorithms for optimization problems. However, its global convergence for general functions is still open. In this paper, under a new line search technique, this problem is solved, and it is shown that other methods in the Broyden class also possess this property. Moreover, the global convergence of the PRP method is established in the case of this new line search. Numerical results are reported to show that the new line search technique is competitive to that of the normal line search.     

Production variability in manufacturing systems: Bernoulli reliability case

The problem of production variability in serial manufacturing lines with unreliable machines is addressed. Bernoulli statistics of machine reliability are assumed. Three problems are considered: the problem of production variance, the problem of constant demand satisfaction, and the problem of random demand satisfaction generated by another (unreliable) production line. For all three problems, bounds on the respective variability measures are derived. These bounds show that long lines smooth out the production and reduce the variability. More precisely, these bounds state that the production variability of a line with many machines is smaller than that of a single machine system with production volume and reliability characteristics similar to those of the longer line. Since all the variability measures for a single machine line can be calculated relatively easily, these bounds provide analytical tools for analysis and design of serial production lines from the point of view of the customer demand satisfaction.     

Modelling transfer line design problem via a set partitioning problem

The design of a transfer line is considered. This line is used for a repetitive execution of a given set of operations to produce identical items. The line is composed of a sequence of workstations equipped with processing modules (blocks). Each block performs specific operations. The machined items move along the workstations in the same direction. There is the same cost associated with each workstation and different costs associated with diverse blocks. The problem is to determine the number of workstations, select a set of blocks and assign the selected blocks to the workstations so that, for each item, each operation is performed exactly once with total line cost to be minimized. The specificity of the problem is that all operations of the same workstation are performed in parallel. There are inclusion, exclusion, and precedence relations that restrict the assignment of blocks and operations to the same workstation and constrain the processing order of the operations on the transfer line. We suggest a reduction of this transfer line design problem to a simple set partitioning problem. This reduction is based on the concept of a locally feasible workstation.     

On the Nonmonotone Line Search

The technique of nonmonotone line search has received many successful applications and extensions in nonlinear optimization. This paper provides some basic analyses of the nonmonotone line search. Specifically, we analyze the nonmonotone line search methods for general nonconvex functions along different lines. The analyses are helpful in establishing the global convergence of a nonmonotone line search method under weaker conditions on the search direction. We explore also the relations between nonmonotone line search and R-linear convergence assuming that the objective function is uniformly convex. In addition, by taking the inexact Newton method as an example, we observe a numerical drawback of the original nonmonotone line search and suggest a standard Armijo line search when the nonmonotone line search condition is not satisfied by the prior trial steplength. The numerical results show the usefulness of such suggestion for the inexact Newton method.     

一种高效快速的裁剪算法

本文的裁剪策略是，巧妙的利用窗口与线段的两种不同数学描述，将有效交点的判定、求交运算及包含性检验，归结为三个条件的判别。     

Global convergence of conjugate gradient method

In this article, we consider the global convergence of the Polak–Ribiére–Polyak conjugate gradient method (abbreviated PRP method) for minimizing functions that have Lipschitz continuous partial derivatives. A novel form of non-monotone line search is proposed to guarantee the global convergence of the PRP method. It is also shown that the PRP method has linear convergence rate under some mild conditions when the non-monotone line search reduces to a related monotone line search. The new non-monotone line search needs to estimate the Lipschitz constant of the gradients of objective functions, for which two practical estimations are proposed to help us to find a suitable initial step size for the PRP method. Numerical results show that the new line search approach is efficient in practical computation.     

Orthogonal segment stabbing

We study a class of geometric stabbing/covering problems for sets of line segments, rays and lines in the plane. While we demonstrate that the problems on sets of horizontal/vertical line segments are NP-complete, we show that versions involving (parallel) rays or lines are polynomially solvable.     

Descent Property and Global Convergence of a New Search Direction Method for Unconstrained Optimization

Conjugate gradient methods are probably the most famous iterative methods for solving large scale optimization problems in scientific and engineering computation, characterized by the simplicity of their iteration and their low memory requirements. It is well known that the search direction plays a main role in the line search method. In this article, we propose a new search direction with the Wolfe line search technique for solving unconstrained optimization problems. Under the above line searches and some assumptions, the global convergence properties of the given methods are discussed. Numerical results and comparisons with other CG methods are given.     

Locating negative decimals on the number line: Insights into the thinking of pre-service primary teachers

This paper explores misconceptions of the number line which are revealed when pre-service primary teachers locate negative decimals on a number line. Written test responses from 94 pre-service primary teachers provide an initial data source which is supplemented by group responses to worksheets completed during a lesson and individual interviews. Two main misconceptions leading to incorrect placement of negative decimals on a number line are identified. One relates to having separate number ‘rays’ for positive and negative numbers, which are aligned according to context. The other (with several variations) results from creating the negative part of the number line by amalgamating translated positive intervals. These misconceptions explain a large percentage of wrong answers. The most important implication for education at school, as well as in teacher education, is that the teaching of negative numbers and of the number line must not be confined to integers, as is frequently the case, but must also include negative fractions and decimals.