Heuristic and Exact Algorithms for the Precedence-Constrained Knapsack Problem

The knapsack problem (KP) is generalized taking into account a precedence relation between items. Such a relation can be represented by means of a directed acyclic graph, where nodes correspond to items in a one-to-one way. As in ordinary KPs, each item is associated with profit and weight, the knapsack has a fixed capacity, and the problem is to determine the set of items to be included in the knapsack. However, each item can be adopted only when all of its predecessors have been included in the knapsack. The knapsack problem with such an additional set of constraints is referred to as the precedence-constrained knapsack problem (PCKP). We present some dynamic programming algorithms that can solve small PCKPs to optimality, as well as a preprocessing method to reduce the size of the problem. Combining these, we are able to solve PCKPs with up to 2000 items in less than a few minutes of CPU time.     

Approximation algorithms for the test cover problem

In the test cover problem a set of m items is given together with a collection of subsets, called tests. A smallest subcollection of tests is to be selected such that for each pair of items there is a test in the selection that contains exactly one of the two items. It is known that the problem is NP-hard and that the greedy algorithm has a performance ratio O(log m). We observe that, unless P=NP, no polynomial-time algorithm can do essentially better. For the case that each test contains at most k items, we give an O(log k)-approximation algorithm. We pay special attention to the case that each test contains at most two items. A strong relation with a problem of packing paths in a graph is established, which implies that even this special case is NP-hard. We prove APX-hardness of both problems, derive performance guarantees for greedy algorithms, and discuss the performance of a series of local improvement heuristics. Partially supported by the Future and Emerging Technologies Programme of the EU under contract number IST-1999-14186 (ALCOM-FT).Partially supported by a Merck Computational Biology and Chemistry Program Graduate Fellowship from the Merck Company Foundation.Also Iceland Genomics CorporationPartially supported by subcontract No. 16082-RFP-00-2C in the area of ``Combinatorial Optimization in Biology (XAXE),' Los Alamos National Laboratories, and NSF grant CCR-0105548.Mathematics Subject Classification: 90B27     

On the transitivity of the comonotonic and countermonotonic comparison of random variables

A recently proposed method for the pairwise comparison of arbitrary independent random variables results in a probabilistic relation. When restricted to discrete random variables uniformly distributed on finite multisets of numbers, this probabilistic relation expresses the winning probabilities between pairs of hypothetical dice that carry these numbers and exhibits a particular type of transitivity called dice-transitivity. In case these multisets have equal cardinality, two alternative methods for statistically comparing the ordered lists of the numbers on the faces of the dice have been studied recently: the comonotonic method based upon the comparison of the numbers of the same rank when the lists are in increasing order, and the countermonotonic method, also based upon the comparison of only numbers of the same rank but with the lists in opposite order. In terms of the discrete random variables associated to these lists, these methods each turn out to be related to a particular copula that joins the marginal cumulative distribution functions into a bivariate cumulative distribution function. The transitivity of the generated probabilistic relation has been completely characterized. In this paper, the list comparison methods are generalized for the purpose of comparing arbitrary random variables. The transitivity properties derived in the case of discrete uniform random variables are shown to be generic. Additionally, it is shown that for a collection of normal random variables, both comparison methods lead to a probabilistic relation that is at least moderately stochastic transitive.     

分母为平方因子的二项式系数倒数级数

根据一个已知级数,利用反正弦积分与多对数的结果,用积分-裂项法给出分母为1个平方因子,平方因子与1个,2个,3个奇因子乘积的二项式系数倒数级数.利用反三角函数与反双曲函数关系给出分母为平方因子的交错二项式系数倒数级数.所给出二项式系数倒数级数的和式是函数形式.并给出分母含有平方因子的二项式系数倒数数值级数恒等式.     

Repair systems with exchangeable items and the longest queue mechanism

We consider a repair facility consisting of one repairman and two arrival streams of failed items, from bases 1 and 2. The arrival processes are independent Poisson processes, and the repair times are independent and identically exponentially distributed. The item types are exchangeable, and a failed item from base 1 could just as well be returned to base 2, and vice versa. The rule according to which backorders are satisfied by repaired items is the longest queue rule: At the completion of a service (repair), the repaired item is delivered to the base that has the largest number of failed items. We point out a direct relation between our model and the classical longer queue model. We obtain simple expressions for several probabilities of interest, and show how all two-dimensional queue length probabilities may be obtained. Finally, we derive the sojourn time distributions.     

CHARTING ARGUMENTATION SPACE IN CONCEPTUAL LOCALES: TOOLS AT THE BOUNDARY BETWEEN RESEARCH AND PRACTICE

We describe a procedure for developing pedagogical knowledge about the argumentation of groups of children in relation to conceptual locales. The method involved the collection of small groups of children who had made different but significant responses to diagnostic test items, the recording and analysis of their subsequent researcher-managed discourses, and the mapping of the main productive elements of argument and charting a flow through it. Two examples of the method are presented which show how children can develop argument, and how these can be charted. These charts and other tools encapsulate research knowledge on children's learning in a form designed to help teachers to plan argumentation in their classroom practice: i.e. as pedagogical content knowledge. In addition to content-focused results, we also find general teaching strategies which appear to be effective generally, i.e. across conceptual locales. We discuss the relationship of this work to the development of teacher's pedagogical content knowledge and practice.     

Inventory model of deteriorated items with a constraint: A geometric programming approach

An inventory model for deteriorating items is built-up with limited storage space. Here, demand rate for the items is finite, items deteriorate at constant rates and are replenished instantaneously. Following EOQ model, the problem is formulated with and without truncation on the deterioration term and ultimately is converted to the minimization of a signomial expression with a posynomial constraint. It is solved by modified geometric programming (MGP) method and non-linear programming (NLP) method. The problem is supported by numerical examples. The results from two versions of the model (with and without truncation) and two methods (i.e. MGP and NLP) are compared.     

Fixed-bucket binary storage trees

A binary storage tree has a set or bucket of possible items associated with each node. The buckets at deeper levels are refinements of the partitionings at earlier levels. When these buckets are established a priori, rather than determined by the particular items stored, we obtain a storage data structure which is a generalized binary digital tree as well as a binary storage tree. Thus the binary key-values of the items along a path in a fixed-bucket binary storage tree have successively longer common prefixes. This synthesis of two schemes inherits all the desirable properties of both methods. The method is analyzed for uniformly-distributed input and shown to have the same cost statistics as binary digital trees.     

G3连续过渡曲面的构造

过渡曲面在CAD／CAM中具有十分重要的作用，其构造与风荷连续性，几何不变量密切相关。本文通过对几何不变量法曲率，测地挠率和几何连续关系的推导，得到构造G^3几何连续过渡曲面的充分条件，结合连接线定理，用超限插值法解决了两个参数面间G3几何连续时渡问题。     

极小解法求解最大-最小型关系方程的系统研究

最大-最小型关系方程已有许多学者进行过研究并给出一些解法,这些解法在应用中仍显得过于复杂.本文在文献[1]的基础上对最大-最小型关系方程的极小解的性质和特点进行了系统的研究,并对文献[1]提出的求解这类方程的图法和分枝法在理论上进行了补充和完善.研究表明,图法和分枝法是求解最大-最小型关系方程的有效方法.     

Production of double-layer polymer films. Process calculation

A theoretical and experimental study has been made concerning the relation between the rheological characteristics of polymer melts and the basic technological parameters of the extrusion process used for the production of double-layer films. A method is proposed here, and it has been proved out experimentally, for calculating the coextrusion process by which films can be produced from materials whose viscous characteristics follow a power-law relation. A formula is derived which relates the viscous characteristics of melts to the thickness ratios of films and layers of fluid in the extruder head. An equation is proposed for calculating the productivity of such an apparatus, its accuracy having been confirmed experimentally within ±7% for the coextrusion of two domestic grades of polypropylene.     

Determination of economic packaging frequency in a multi-brand joint replenishment inventory system

The search procedure developed in this paper is typically applicable in those inventory systems where a product is packaged immediately after manufacture into a number of container sizes and the packaged items of similar sizes are sold under more than one brand name. The most common example of such items can be seen in supermarkets where grocery items of identical characteristics (produced by the same manufacture) are available under the supermarket's own brand and under the manufacturer's nationally advertised brand. An example has been solved to illustrate the method.     

How Many Comparisons Does Quicksort Use?

We examine the probability distribution of the number of comparisons needed by the Quicksort sorting algorithm, where probability arises due to the items being in random order. We develop a general class of distributions for the permutation of the items to be sorted which includes the uniform distribution on permutations as a special case. For this general class, the distribution of the number of comparisons is given by the solution of a simple recurrence relation. We provide an exact solution of the recurrence for very small n. We show that the solution can be approximated asymptotically by the solution of a "quadratic" operator equation. We exhibit three numerical solutions to the operator equation for two different distributions on permutations from the general class. We also exhibit numerical solutions for the case in which the algorithm is modified so that arrays are partitioned by the median-of-three selected items rather than by a single selected item.     

Design of contract parameters in a closed-loop supply chain

We study an extended joint economic lot size problem which incorporates the return flow of remanufacturable used products. The supply chain under consideration consists of a single supplier and a single buyer. The buyer orders a single product from the supplier, uses it for her own needs, and collects the remanufacturable items after use. The ordered items are shipped from the supplier to the buyer in the lot-for-lot fashion by a vehicle which also returns the collected used items from the buyer to the supplier for remanufacturing and subsequent service of the buyer’s demand in the next order cycle. For satisfying the total demand, the supplier manufactures new items or remanufactures used ones received from the buyer. For given demand, productivity, collection rate, disposal cost, setup cost, order cost, holding cost for serviceable and nonserviceable products at the supplier as well as the buyer the lot size (order size) for the supplier (buyer) has to be found which minimizes the total cost. Furthermore, we address a decentralised decision making of the parties under a two-part tariff and determine their equilibrium strategies within the Nash framework.     

The Paul A M Dirac papers at Florida State University: a search for informal mathematical investigations

The research discussed in this article is an archival study of pages of mathematical work produced by the physicist Paul A M Dirac. The pages, referred to as the ‘shoebox papers’, are thought to date back at least to Dirac's time as a student at the University of Cambridge in the 1920s. Florida State University, where the research was conducted and where Dirac worked for the last fourteen years of his life, received the entirety of his papers after his death in 1984. The research so far has identified major themes that recur throughout the collection of papers, including an interest in combinatorics and their relation to algebra problems. Due to Dirac's importance as a physicist and a possible relation to combinatorics work by Leibniz, the collection may have significant implications for the history of mathematics.     

Exact and approximate methods for a one-dimensional minimax bin-packing problem

One-dimensional bin-packing problems require the assignment of a collection of items to bins with the goal of optimizing some criterion related to the number of bins used or the ‘weights’ of the items assigned to the bins. In many instances, the number of bins is fixed and the goal is to assign the items such that the sums of the item weights for each bin are approximately equal. Among the possible applications of one-dimensional bin-packing in the field of psychology are the assignment of subjects to treatments and the allocation of students to groups. An especially important application in the psychometric literature pertains to splitting of a set of test items to create distinct subtests, each containing the same number of items, such that the maximum sum of item weights across all bins is minimized. In this context, the weights typically correspond to item statistics derived from difficulty and discrimination indices. We present a mixed zero-one integer linear programming (MZOILP) formulation of this one-dimensional minimax bin-packing problem and develop an approximate procedure for its solution that is based on the simulated annealing algorithm. In two comparisons that focused on 34 practically-sized test problems (up to 6000 items and 300 bins), the simulated annealing heuristic generally provided better solutions than were obtained when using a commercial mathematical programming software package to solve the MZOILP formulation directly.     

Multiple Container Packing: A Case Study of Pipe Packing

While the problem of packing single containers and pallets has been thoroughly investigated very little attention has been given to the efficient packing of multiple container loads. Normally in practice a multiple container load is packed by a single container algorithm used in a greedy fashion. This paper introduces the issues involved in multiple container loading. It lays out three different strategies for solving the problem: sequential packing using a single container heuristic, pre-allocating items to the containers and choosing container loads using simultaneous packing models. The principal simultaneous models are pattern selection IP models. We present an application of packing pipes in shipping containers using two pattern selection IP models, a pattern selection heuristic, a sequential greedy algorithm and a pre-allocation method. The experimental results use randomly generated data sets. We discuss several useful insights into the methods and show that for this application the pattern selection methods perform best.     

Resource capacity allocation to stochastic dynamic competitors: knapsack problem for perishable items and index-knapsack heuristic

In this paper we propose an approach for solving problems of optimal resource capacity allocation to a collection of stochastic dynamic competitors. In particular, we introduce the knapsack problem for perishable items, which concerns the optimal dynamic allocation of a limited knapsack to a collection of perishable or non-perishable items. We formulate the problem in the framework of Markov decision processes, we relax and decompose it, and we design a novel index-knapsack heuristic which generalizes the index rule and it is optimal in some specific instances. Such a heuristic bridges the gap between static/deterministic optimization and dynamic/stochastic optimization by stressing the connection between the classic knapsack problem and dynamic resource allocation. The performance of the proposed heuristic is evaluated in a systematic computational study, showing an exceptional near-optimality and a significant superiority over the index rule and over the benchmark earlier-deadline-first policy. Finally we extend our results to several related revenue management problems.     

Cycle-transitive comparison of independent random variables

The discrete dice model, previously introduced by the present authors, essentially amounts to the pairwise comparison of a collection of independent discrete random variables that are uniformly distributed on finite integer multisets. This pairwise comparison results in a probabilistic relation that exhibits a particular type of transitivity, called dice-transitivity. In this paper, the discrete dice model is generalized with the purpose of pairwisely comparing independent discrete or continuous random variables with arbitrary probability distributions. It is shown that the probabilistic relation generated by a collection of arbitrary independent random variables is still dice-transitive. Interestingly, this probabilistic relation can be seen as a graded alternative to the concept of stochastic dominance. Furthermore, when the marginal distributions of the random variables belong to the same parametric family of distributions, the probabilistic relation exhibits interesting types of isostochastic transitivity, such as multiplicative transitivity. Finally, the probabilistic relation generated by a collection of independent normal random variables is proven to be moderately stochastic transitive.