Bias Reduction in Stochastic Covering Problems via a Bayesian Approach with a Conjugate Prior

• Activity Number: 414
• Type: Contributed
• Date/Time: Thursday, August 12, 2004 : 8:30 AM to 10:20 AM
• Sponsor: Section on Bayesian Statistical Science
• Author(s): James J. Cochran*+
• Companies: Louisiana Tech University
• Keywords: combinatorial optimization ; stochastic programming ; Bayesian statistics ; Dirichlet distribution

Abstract

Finding a subset collection that provides optimal population coverage is a frequently encountered deterministic Integer Programming (IP) problem. A random sample is often used to formulate the IP model, which is then used to select the subsets that provide the estimated optimal population coverage. The result is a constrained combinatorial optimization problem with a fixed, known feasible space and a stochastic objective function; such problems are ubiquitous and occur in both the public and private sectors. Examples include media selection, placement of municipal services such as sirens and waste dumps, and reserve site selection. When the estimators used to derive objective function coefficients for this class of problems are not negatively biased, the associated estimate of the maximand (maximum value of the objective function) is positively biased. To demonstrate how well a Bayesian approach utilizing a conjugate prior mitigates this bias, we randomly partition large instances of this class of problem (with live data) the data into smaller, computationally manageable problems, calculate the exact bias for these smaller problems, and compare estimates generated by the Bayesian approach to these values.