The National Cancer Institute13 has received proposals from 22 states to participate in its newest smoking intervention study. The first j = 1,

c, 5 are from the Northeast region, the next j = 6,

c, 11 from the Southeast, numbers j = 12,

c, 17 from the Midwest, and the last j = 18,

c, 22 from the West. At least 3 are to be selected from each region. Each proposal has been evaluated and rated with a merit score rj based on rankings by a panel of experts. Selected project budgets bj (in millions of dollars) must total no more than the $15 million available for the study, and the number of smokers sj (in millions)

living in chosen states must sum to at least 11 million. Proposals j = 2, 7, 11, 19 come from states in the highest quartile with respect to the fraction of the population that smokes; proposals j = 1, 4, 13, 14, 21 come from the lowest quartile.

At least 2 states must be selected from each of these outlier groups. Formulate an ILP model to choose a maximum merit feasible set of proposals to fund using the decision variables (j = 1,

c, 22)

xj ! e 1 if proposal j is selected 0 otherwise