A Note on “Discrete Sequential Search with Group Activities”
针对Wagner和Davis关于离散序贯搜索问题的整数规划模型，构造了一个反例，证明其提出的线性规划松弛解与整数规划最优解不同，从而否定了他们关于该问题可线性求解的猜想。
ABSTRACT This note comments on a paper published by Wagner and Davis [ Decision Sciences (2001), 32(4), 557–573]. These authors present an integer‐programming model for the single‐item discrete sequential search problem with group activities. Based on their experiments, they conjecture that the problem can be solved as a linear program. In this note, we provide a counterexample for which the optimal value of the linear program they propose is different from the optimal value of the integer‐programming model, hence contradicting their conjecture for the specific linear program that they specify. To the best of our knowledge, the conjecture settled in this note was still an open question.