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

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

分组测试与迫进控制标准

1引言 在第二次世界大战期间,珍珠港事件发生后,美国为了反击德国法西斯挑起的侵略战争,多次进行大规模的征兵活动．在征兵活动中,需要对大量报名入伍者进行健康检查,看其身体是否符合入伍的条件．其中一项健康检查的内容是血液抗体检测,通过血液抗体检测,查出梅毒的携带者．当时,由于被检测者数量巨大,部队又急需补充兵员,检测时间紧、任务重,这就需要找到一种科学的检测方法,用尽可能少的测试次数检测出所有病毒携带者,这一问题后来称为搜索坏硬币的最优化问题．在这个问题中,被检测者抽象为硬币,血液不带病毒者抽象为标准硬币,血液带病毒者抽象为伪硬币,检测的设备称为装置．如何用特定性能的若干台装置,以尽可能少的测试次数从由硬币组成的集合中检测出全部伪硬币,是一个有很强实际背景的最优化问题,正因为如此,近一段时间组合搜索中的伪硬币问题一直受到人们的广泛关注．     

An NP-Completeness Result of Edge Search in Graphs

Consider the following generalization of the classical sequential group testing problem for two defective items: suppose a graph G contains n vertices two of which are defective and adjacent. Find the defective vertices by testing whether a subset of vertices of cardinality at most p contains at least one defective vertex or not. What is then the minimum number c _p (G) of tests, which are needed in the worst case to find all defective vertices? In Gerzen (Discrete Math 309(20):5932–5942, 2009), this problem was partly solved by deriving lower and sharp upper bounds for c _p (G). In the present paper we show that the computation of c _p (G) is an NP-complete problem. In addition, we establish some results on c _p (G) for random graphs.     

Selecting two different defective coins

In this paper, given a balance scale and the information that there are exactly two different defective coins present, the authors consider the problem of ascertaining the minimum number of testing which suffice to determine the two different defective coins in a set of λ coins in same appearance, and here λ  3. A testing algorithm for all the possible values of λ is constructed, and the testing algorithm needs at most one testing step more than the optimal testing algorithm.     

New lower bounds for the three-dimensional finite bin packing problem

The three-dimensional finite bin packing problem (3BP) consists of determining the minimum number of large identical three-dimensional rectangular boxes, bins, that are required for allocating without overlapping a given set of three-dimensional rectangular items. The items are allocated into a bin with their edges always parallel or orthogonal to the bin edges. The problem is strongly NP-hard and finds many practical applications. We propose new lower bounds for the problem where the items have a fixed orientation and then we extend these bounds to the more general problem where for each item the subset of rotations by 90° allowed is specified. The proposed lower bounds have been evaluated on different test problems derived from the literature. Computational results show the effectiveness of the new lower bounds.     

The stochastic generalized bin packing problem

The Generalized Bin Packing Problem (GBPP) is a recently introduced packing problem where, given a set of bins characterized by volume and cost and a set of items characterized by volume and profit (which also depends on bins), we want to select a subset of items to be loaded into a subset of bins which maximizes the total net profit, while satisfying the volume and bin availability constraints. The total net profit is given by the difference between the total profit of the loaded items and the total cost of the used bins. In this paper, we consider the stochastic version of the GBPP (S-GBPP), where the item profits are random variables to take into account the profit oscillations due to the handling operations for bin loading. The probability distribution of these random variables is assumed to be unknown. By using the asymptotic theory of extreme values a deterministic approximation for the S-GBPP is derived.     

Item selection by latent class-based methods: an application to nursing home evaluation

The evaluation of nursing homes is usually based on the administration of questionnaires made of a large number of polytomous items to their patients. In such a context, the latent class model represents a useful tool for clustering subjects in homogenous groups corresponding to different degrees of impairment of the health conditions. It is known that the performance of model-based clustering and the accuracy of the choice of the number of latent classes may be affected by the presence of irrelevant or noise variables. In this paper, we show the application of an item selection algorithm to a dataset collected within a project, named ULISSE, on the quality-of-life of elderly patients hosted in Italian nursing homes. This algorithm, which is closely related to that proposed by Dean and Raftery in 2010, is aimed at finding the subset of items which provides the best clustering according to the Bayesian Information Criterion. At the same time, it allows us to select the optimal number of latent classes. Given the complexity of the ULISSE study, we perform a validation of the results by means of a sensitivity analysis, with respect to different specifications of the initial subset of items, and of a resampling procedure.     

An instantaneous replenishment model under the effect of a sampling policy for defective items

We propose to study a EOQ-type inventory model with unreliable supply, with each order containing a random proportion of defective items. Every time an order is received, an acceptance sampling plan is applied to the lot, according to which only a sample is inspected instead of the whole lot. If the sample conforms to the standards, i.e. if the number of imperfect items is below an “acceptance number”, no further screening is performed. Otherwise, the lot is subject to 100% screening. We formulate an integer non-linear mathematical program that integrates inventory and quality decisions into a unified profit model, to jointly determine the optimal lot size and optimal sampling plan, characterized by a sample size, and an acceptance number. The optimal decisions are determined in a way to achieve a certain average outgoing quality limit (AOQL), which is the highest proportion of defective items in the outgoing material sold to customers. We provide a counter-example demonstrating that the expected profit function, objective of the mathematical program, is not jointly concave in the lot and sample size. However, we show that for a given sampling plan, the expected profit function is concave in the lot size. A solution procedure is presented to compute the optimal solution. Numerical analysis is provided to gain managerial insights by analyzing the impact of changing various model parameters on the optimal solution. We also show numerically that the optimal profit determined using this model is significantly higher when compared to the optimal profit obtained using Salameh and Jaber (2000)’s [1] model, indicating much higher profits when acceptance sampling is used.     

Generalized lot sentencing rule for estimating the value of production lot for sale

In the traditional lot sentencing rule, a buyer arrives to one of two decisions regarding lot disposition; either accept or reject a lot. However, it is more appropriate to consider choices between those two extreme decisions. A clear case where the traditional lot sentencing rule is not flexible is when a buyer purchases a lot from an English auction. In this paper, we propose a model that helps a buyer in estimating the value of a production lot. This model can be used by a bidder before the bidding process starts to estimate the value of an auctioned lot. The model provides an action plan that includes the estimated acquisition cost as a function of the number of defective items found in a random sample. Unlike the traditional lot sentencing rule, the proposed rule is more flexible and provides buyers with wider range of possible actions.     

Optimal Group Testing with Processing Times and Incomplete Identification

We consider the group testing problem for a finite population of possibly defective items with the objective of sampling a prespecified demanded number of nondefective items at minimum cost. Group testing means that items can be pooled and tested together; if the group comes out clean, all items in it are nondefective, while a contaminated group is scrapped. Every test takes a random amount of time and a given deadline has to be met. If the prescribed number of nondefective items is not reached, the demand has to be satisfied at a higher (penalty) cost. We derive explicit formulas for the distributions underlying the cost functionals of this model. It is shown in numerical examples that these results can be used to determine the optimal group size.     

Heuristics for container loading of furniture

We consider a container loading problem that occurs at a typical furniture manufacturer. Each furniture item has an associated profit. Given container dimensions and a set of furniture items, the problem is to determine a subset of items with maximal profit sum that is loadable in the container. In the studied company, the problem arises hundreds of times daily during transport planning. Instances may contain more than one hundred different items with irregular shapes. To solve this complex problem we apply a set of heuristics successively that each solve one part of the problem. Large items are combined in specific structures to ensure proper protection of the items during transportation and to simplify the problem. The solutions generated by the heuristic has an average loading utilization of 91.3% for the most general instances with average running times around 100 seconds.     

关于两个伪硬币问题的一些新结果

下面的问题被称为n个外观不可区分硬币的分组测试问题,每个硬币可以是伪硬币或是标准硬币.本文所涉及的问题是:已知一个由n个硬币组成的集合中有两个伪(较重的)硬币,用一台天平以最小的称重次数,从这n个硬币组成的集合中探测出两个伪(较重的)硬币. 我们构造了找出两个伪(较重的)硬币的两个算法,并且这两个算法是最优的.     

A queueing model for general group screening policies and dynamic item arrivals

Classification of items as good or bad can often be achieved more economically by examining the items in groups rather than individually. If the result of a group test is good, all items within it can be classified as good, whereas one or more items are bad in the opposite case. Whether it is necessary to identify the bad items or not, and if so, how, is described by the screening policy. In the course of time, a spectrum of group screening models has been studied, each including some policy. However, the majority ignores that items may arrive at random time epochs at the testing center in real life situations. This dynamic aspect leads to two decision variables: the minimum and maximum group size. In this paper, we analyze a discrete-time batch-service queueing model with a general dependency between the service time of a batch and the number of items within it. We deduce several important quantities, by which the decision variables can be optimized. In addition, we highlight that every possible screening policy can, in principle, be studied, by defining the dependency between the service time of a batch and the number of items within it appropriately.     

Reducing cost and abandoned E-components in incomplete identification

After some types of electronic components are produced, each component is either good or defective, but this is not known before testing. A group of these components can be examined together in one incomplete identification test, and the testing outcome will be either “success” or “failure”. The failure outcome happens if and only if there exists one or more defective units among the test group of components. Usually the whole group with the failure outcome is abandoned because the testing cost is much higher than the component cost per unit. On the other hand, electronic garbage has resulted serious environmental pollution. In this study, we show that the manufacturer can achieve lower expected costs and less waste through ordering less components and retesting part of the failed group. As a result, electronic garbage is reduced and so is environmental pollution. The corresponding optimal policy is attained by solving a set of simultaneous equations of a dynamic programming. The component supplier can also improve profit by the retesting strategy.     

笛卡尔乘积图里的最小k-路点覆盖

对于子集$S\subseteq V(G)$,如果图$G$里的每一条$k$路都至少包含$S$中的一个点,那么我们称集合$S$是图$G$的一个$k$-路点覆盖.很明显,这个子集并不唯一.我们称最小的$k$-路点覆盖的基数为$k$-路点覆盖数, 记作$\psi_k(G)$.本文给出了一些笛卡尔乘积图上$\psi_k(G)$值的上界或下界.     

Integer linear programming approaches for non-unique probe selection

In addition to their prevalent use for analyzing gene expression, DNA microarrays are an efficient tool for biological, medical, and industrial applications because of their ability to assess the presence or absence of biological agents, the targets, in a sample. Given a collection of genetic sequences of targets one faces the challenge of finding short oligonucleotides, the probes, which allow detection of targets in a sample by hybridization experiments. The experiments are conducted using either unique or non-unique probes, and the problem at hand is to compute a minimal design, i.e., a minimal set of probes that allows to infer the targets in the sample from the hybridization results. If we allow to test for more than one target in the sample, the design of the probe set becomes difficult in the case of non-unique probes.Building upon previous work on group testing for microarrays we describe the first approach to select a minimal probe set for the case of non-unique probes in the presence of a small number of multiple targets in the sample. The approach is based on an integer linear programming formulation and a branch-and-cut algorithm. Our implementation significantly reduces the number of probes needed while preserving the decoding capabilities of existing approaches.     

Statistical group testing with queueing involved

We consider a queueing model in which items wait to undergo group testing in batches of sizem. However, if fewer thanm items are present at the beginning of a service, items are tested singly. Ifm or more items are waiting at such an epoch, a group of sizem is tested and, if the group passes the test, allm items leave the system. When a group is found to contain at least one defective item, them items in it are retested individually. An algorithm is developed to compute many steady-state probabilities related to this queue. Comparisons of these probabilities are used to assess the effect of the group sizem on the behavior of the queue of items waiting for testing.This research was supported in part by Grant Nr. ECS-8601203 from the National Science Foundation.     

Rectangular tileability and complementary tileability are undecidable

Does a given set of polyominoes tile some rectangle? We show that this problem is undecidable. In a different direction, we also consider tiling a cofinite subset of the plane. The tileability is undecidable for many variants of this problem. However, we present an algorithm for testing whether the complement of a finite region is tileable by a set of rectangles.     

The min-Knapsack problem with compactness constraints and applications in statistics

In the min-Knapsack problem, one is given a set of items, each having a certain cost and weight. The objective is to select a subset with minimum cost, such that the sum of the weights is not smaller than a given constant. In this paper, we introduce an extension of the min-Knapsack problem with additional “compactness constraints” (mKPC), stating that selected items cannot lie too far apart. This extension has applications in statistics, including in algorithms for change-point detection in time series. We propose three solution methods for the mKPC. The first two methods use the same Mixed-Integer Programming (MIP) formulation but with two different approaches: passing the complete model with a quadratic number of constraints to a black-box MIP solver or dynamically separating the constraints using a branch-and-cut algorithm. Numerical experiments highlight the advantages of this dynamic separation. The third approach is a dynamic programming labelling algorithm. Finally, we focus on the particular case of the unit-cost mKPC (1c-mKPC), which has a specific interpretation in the context of the statistical applications mentioned above. We prove that the 1c-mKPC is solvable in polynomial time with a different ad-hoc dynamic programming algorithm. Experimental results show that this algorithm vastly outperforms both generic approaches for the mKPC and a simple greedy heuristic from the literature.     

十硬币集中四坏硬币的最优测试方法

在前人研究成果的基础上,给出用无砝码天平从10个硬币中搜索4枚坏硬币的最优搜索方法.