A linear integer programming bound for maximum-entropy sampling

作     者：Lee, J Williams, J 

作者机构：IBM Corp Thomas J Watson Res Ctr Dept Math Sci Yorktown Hts NY 10598 USA Avaya Inc Westminster CO 80234 USA 

出 版 物：《MATHEMATICAL PROGRAMMING》 (数学规划)

年 卷 期：2003年第94卷第2-3期

页      面：247-256页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0835[工学-软件工程] 0701[理学-数学] 

主　　题：experimental design design of experiments entropy maximum-entropy sampling matching integer program spectral bound Fischer's inequality branch-and-bound dynamic programming 

摘      要：We introduce a new upper bound for the maximum-entropy sampling problem. Our bound is described as the solution of a linear integer program. The bound depends on a partition of the underlying set of random variables. For the case in which each block of the partition has bounded cardinality, we describe an efficient dynamic-programming algorithm to calculate the bound. For the very special case in which the blocks have no more than two elements, we describe an efficient algorithm for calculating the bound based on maximum-weight matching. This latter formulation has particular value for local-search procedures that seek to find a good partition. We relate our bound to recent bounds of Hoffman, Lee and Williams. Finally, we report on the results of some computational experiments.