Linear multiplicative programming

An algorithm for solving a linear multiplicative programming problem (referred to as LMP) is proposed. LMP minimizes the product of two linear functions subject to general linear constraints. The product of two linear functions is a typical non-convex function, so that it can have multiple local minima. It is shown, however, that LMP can be solved efficiently by the combination of the parametric simplex method and any standard convex minimization procedure. The computational results indicate that the amount of computation is not much different from that of solving linear programs of the same size. In addition, the method proposed for LMP can be extended to a convex multiplicative programming problem (CMP), which minimizes the product of two convex functions under convex constraints.     

Computational complexity of convoy movement planning problems

Convoy movement planning problems arise in a number of important logistical contexts, including military planning, railroad optimization and automated guided vehicle routing. In the convoy movement problem (CMP), a set of convoys, with specified origins and destinations, are to be routed with the objective of minimizing either makespan or total flow time, while observing a number of side constraints. This paper characterizes the computational complexity of several restricted classes of CMPs. The principal objective is to identify the most parsimonious set of problem features that make the CMP intractable. A polynomial-time algorithm is provided for the single criterion two-convoy movement problem. The performance of a simple prioritization–idling approximation algorithm is also analyzed for the K-convoy movement problem. Error bounds are developed for the makespan and flow time objectives.     

Multiple-input dual-output adjustment scheme for semiconductor manufacturing processes using a dynamic dual-response approach

This paper presents an optimization-based, multiple-input dual-output (MIDO) run-to-run (R2R) controller for general semiconductor manufacturing processes. This controller, termed ‘adaptive dual-response optimizing controller’ (ADROC), can serve as a recipe regulator between consecutive runs of wafer fabrication. In ADROC, an on-line estimation technique is implemented in a self-tuning (ST) control manner for the adaptation purpose. Subsequently, an ad hoc global optimization algorithm based on the dual-response approach is used to seek the optimum recipe within the acceptability region for the execution of next run. In addition, a ‘responsive-type’ adjustment method is devised, serving as a post hoc filter to alleviate the over-control problem and maintain a better trade-off between two potentially conflicting process responses in MIDO R2R situations. Typical applications of R2R control to chemical mechanical planarization (CMP) in semiconductor manufacturing are demonstrated through simulated processes to illustrate ADROC. The procedure is compared to three benchmark methods (OAQC, single- and double-EWMA controllers) in a simulation experiment.     

How a standards-based mathematics curriculum differs from a traditional curriculum: with a focus on intended treatments of the ideas of variable

Analyzing the important features of different curricula is critical to understand their effects on students’ learning of algebra. Since the concept of variable is fundamental in algebra, this article compares the intended treatments of variable in an NSF-funded standards-based middle school curriculum (CMP) and a more traditionally based curriculum (Glencoe Mathematics). We found that CMP introduces variables as quantities that change or vary, and then it uses them to represent relationships. Glencoe Mathematics, on the other hand, treats variables predominantly as placeholders or unknowns, and then it uses them primarily to represent unknowns in equations. We found strong connections among variables, equation solving, and linear functions in CMP. Glencoe Mathematics, in contrast, emphasizes less on the connections between variables and functions or between algebraic equations and functions, but it does have a strong emphasis on the relation between variables and equation solving.     

The CMP inverse for rectangular matrices

We extend the notation of the CMP inverse for a square matrix to a rectangular matrix. Precisely, we define and characterize a new generalized inverse called the weighted CMP inverse. Also, we investigate properties of the weighted CMP inverse using a representation by block matrices. Some new characterizations and properties of the CMP inverse are obtained.     

An investigation of teachers’ intentions and reflections about using Standards-based and traditional textbooks in the classroom

This study analyzed teachers’ intentions for and reflections on their use of Standards-based [Connected Mathematics Program (CMP)] textbooks and traditional (non-CMP) mathematics textbooks to guide instruction. In this investigation of the interplay between textbooks and instruction, we focused on learning goals, instructional tasks, teachers’ anticipation of students’ difficulties, and their perceptions of students’ achievement of learning goals. All of these are aspects of teachers’ intentions and reflections that have proved fruitful in comparing the roles of the CMP and non-CMP mathematics textbooks in our Longitudinal Investigation of the Effect of Curriculum on Algebra Learning project. Whereas the cognitive level of the teachers’ intended learning goals appeared generally to reflect the emphases of their respective textbooks, we found that the CMP teachers’ intended learning goals were not as well aligned with the CMP textbooks as the non-CMP teachers’ learning goals were aligned with their non-CMP textbooks. The CMP and non-CMP teachers’ implementations of the lessons seemed to reduce the degree of difference between the cognitive levels of their intended goals. Even so, we found that significantly more CMP lessons than non-CMP lessons were implemented at a high level of cognitive demand. Although the non-CMP teachers’ intended learning goals were better aligned with their textbook’s learning goals, we found that the CMP teachers were more likely than the non-CMP teachers to follow the guidance of their textbooks in designing and selecting instructional tasks for a lesson. Future research should consider other aspects of teachers’ intentions and reflections that may shed a broader light on the role of textbooks and curriculum materials in teachers’ crafting of instructional experiences for their students.     

A Lagrangian relaxation-based heuristic for the vehicle routing with full container load

We address a problem of vehicle routing that arises in picking up and delivering full container load from/to an intermodal terminal. The substantial cost and time savings are expected by efficient linkage between pickup and delivery tasks, if the time of tasks and the suitability of containers for cargo allow. As this problem is NP-hard, we develop a subgradient heuristic based on a Lagrangian relaxation which enables us to identify a near optimal solution. The heuristic consists of two sub-problems: the classical assignment problem and the generalized assignment problem. As generalized assignment problem is also NP-hard, we employ an efficient solution procedure for a bin packing based problem, which replaces the generalized assignment problem. The heuristic procedure is tested on a wide variety of problem examples. The test results demonstrate that the procedure developed here can efficiently solve large instances of the problem.     

Reformulation of the support set selection problem in the logical analysis of data

The paper is concerned with the problem of binary classification of data records, given an already classified training set of records. Among the various approaches to the problem, the methodology of the logical analysis of data (LAD) is considered. Such approach is based on discrete mathematics, with special emphasis on Boolean functions. With respect to the standard LAD procedure, enhancements based on probability considerations are presented. In particular, the problem of the selection of the optimal support set is formulated as a weighted set covering problem. Testable statistical hypothesis are used. Accuracy of the modified LAD procedure is compared to that of the standard LAD procedure on datasets of the UCI repository. Encouraging results are obtained and discussed.     

组合的分组测试算法的近似控制标准

对于给定的一个集合,分组测试问题是通过一系列的测试去确定这个集合的一个子集. 在文中, 作者首先运用动态规划的理论与方法, 建立了一个近似控制标准, 目的是对分组测试算法的构建过程进行有效控制, 使所构建的算法达到最优. 其次, 应用该近似控制标准研究了在n个硬币集合中确定一个伪硬币的最小平均测试数的问题. 文中所涉及的近似控制问题, 给出了在一个给定集合中去确定这个集合的一个子集的最优分组测试算法, 该最优分组测试算法是在平均测试步骤最少意义下的最优分组测试算法.     

Lifting the facets of zero–one polytopes

We discuss a procedure to obtain facets and valid inequalities for the convex hull of the set of solutions to a general zero–one programming problem. Basically, facets and valid inequalities defined on lower dimensional subpolytopes are lifted into the space of the original problem. The procedure generalizes the previously known techniques for lifting facets in two respects. First, the general zero–one programming problem is considered rather than various special cases. Second, the procedure is exhaustive in the sense that it accounts for all the facets (valid inequalities) which are liftings of a given lower dimensional facet (valid inequality).     

A dynamic programming based heuristic for the assembly line balancing problem

The simple assembly line balancing problem is the simplification of a real problem associated to the assignment of the elementary tasks required for assembly of a product in an assembly line. This problem has been extensively studied in the literature for more than half a century. The present work proposes a new procedure to solve the problem we call Bounded Dynamic Programming. This use of the term Bounded is associated not only with the use of bounds to reduce the state space but also to the reduction of such space based on heuristics. This procedure is capable of obtaining an optimal solution rate of 267 out of 269 instances, which have been used in previous works, thus obtaining the best-known performance for the problem. These results are an improvement from any previous procedure found in the literature even when using smaller computing times.     

Minimizing the sum of squares lateness on a single machine

This paper proposes a new procedure that considers the use of inserted idle time to optimally solve the single machine scheduling problem where the objective is to minimize the sum of squares lateness. A heuristic procedure is also proposed for this problem. These procedures and an existing procedure developed by Gupta and Sen are tested using problems of various sizes in terms of the number of jobs to be scheduled and for different degrees of due date tightness. The performance measures are CPU time and sum of squares lateness of the solutions generated. The results show that a simple descent procedure yields very good results and is efficient even on large problems.     

A compromise procedure for the multiple objective linear fractional programming problem

A generalization of a well-known multiple objective linear fractional programming (MOLFP) problem, the multiple objective fractional programming (MOFP) problem, is formulated. A concept of multiple objective programming (MOP) problem corresponding to MOFP is introduced and some relations between those problems are examined. Based on these results, a compromise procedure for MOLFP problem is proposed. A numerical example is given to show how the procedure works.     

A core approach to the 0–1 equality knapsack problem

For the 0–1 knapsack problem with equality constraint a partitioning procedure is introduced which focuses on the core of the problem. The purpose of the procedure is to reduce the required preliminary sorting for large problem instances. Computational results are presented for an improved heuristic as well as for a complete (exact) algorithm showing the success of the core approach. Test problems of size up to 15–000 objects are solved within 400–ms on a standard personal computer, that is, within the time that is needed for sorting the profit-weight ratios. The core algorithm reduces the solution times by a factor of up to four for large problem instances.     

An enumeration procedure for the assembly line balancing problem based on branching by non-decreasing idle time

In this article, we present a new exact algorithm for solving the simple assembly line balancing problem given a determined cycle time (SALBP-1). The algorithm is a station-oriented bidirectional branch-and-bound procedure based on a new enumeration strategy that explores the feasible solutions tree in a non-decreasing idle time order. The procedure uses several well-known lower bounds, dominance rules and a new logical test based on the assimilation of the feasibility problem for a given cycle time and number of stations (SALBP-F) to a maximum-flow problem.     

Embedding learning capability in Lagrangean relaxation: An application to the travelling salesman problem

This paper presents an effective procedure that finds lower bounds for the travelling salesman problem based on the 1-tree using a learning-based Lagrangian relaxation technique. The procedure can dynamically alter its step-size depending upon its previous iterations. Along with having the capability of expansion–contraction, the procedure performs a learning process in which Lagrange multipliers are influenced by a weighted cost function of their neighbouring nodes. In analogy with simulated annealing paradigm, here a learning process is equivalent to escaping local optimality via exploiting the structure of the problem. Computational results conducted on Euclidean benchmarks from the TSPLIB library show that the procedure is very effective.     

Determining the boundary of a two-dimensional region from the solution of the external initial boundary-value problem for the heat equation

We determine the boundary of a two-dimensional region using the solution of the external initial boundary-value problem for the nonhomogeneous heat equation. The initial values for the boundary determination include the right-hand side of the equation and the solution of the initial boundary-value problem given for finitely many points outside the region. The inverse problem is reduced to solving a system of two integral equations nonlinear in the function defining the sought boundary. An iterative procedure is proposed for numerical solution of the problem involving linearization of integral equations. The efficiency of the proposed procedure is investigated by a computer experiment.     

Optimizing the packing of cylinders into a rectangular container: A nonlinear approach

The container loading problem has important industrial and commercial applications. An increase in the number of items in a container leads to a decrease in cost. For this reason the related optimization problem is of economic importance. In this work, a procedure based on a nonlinear decision problem to solve the cylinder packing problem with identical diameters is presented. This formulation is based on the fact that the centers of the cylinders have to be inside the rectangular box defined by the base of the container (a radius far from the frontier) and far from each other at least one diameter. With this basic premise the procedure tries to find the maximum number of cylinder centers that satisfy these restrictions. The continuous nature of the problem is one of the reasons that motivated this study. A comparative study with other methods of the literature is presented and better results are achieved.     

A filter-and-fan approach to the job shop scheduling problem

The job shop scheduling problem (JSSP) is a notoriously difficult problem in combinatorial optimization. Extensive investigation has been devoted to developing efficient algorithms to find optimal or near-optimal solutions. This paper proposes a new heuristic algorithm for the JSSP that effectively combines the classical shifting bottleneck procedure (SBP) with a dynamic and adaptive neighborhood search procedure. Our new search method, based on a filter-and-fan (F&F) procedure, uses the SBP as a subroutine to generate a starting solution and to enhance the best schedules produced. The F&F approach is a local search procedure that generates compound moves by a strategically abbreviated form of tree search. Computational results carried out on a standard set of 43 benchmark problems show that our F&F algorithm performs more robustly and effectively than a number of leading metaheuristic algorithms and rivals the best of these algorithms.     

A general method for determining the set of all efficient solutions to a linear vectormaximum problem

To solve a linear vectormaximum problem means, in general, to determine the set E of all efficient solutions. A multiparametric method based on earlier works of the author is presented. In the procedure efficient vertices and efficient edges are generated via one subprogram, which works as a simple linear programming problem, and just by inspection of these results higher dimensional efficient faces are determined. The procedure does not depend on special properties of the restriction set and/or of the system of given objective functions. Illustrative examples are presented. Two appendixes provide a survey on a multiparametric algorithm and on a solution procedure for the auxiliary problem, both of which are the background for the method.