We analyzed the planning problem for HIV screening, testing and care. This problem consists of determining the optimal fraction of patients to be screened in every period as well as the optimum staffing level at each part of the health care system to maximize the total health benefits to the patients measured by Quality-Adjusted Life-Years (QALYs) gained.We modeled this problem as a nonlinear mixed integer programming program comprising of disease progression (the transition of the patients across health states), system dynamics (the flow of patients in different health states across various parts of the health care delivery system), budgetary and capacity constraints.We applied the model to the Greater Los Angeles (GLA) station in the Veterans Health Administration (VHA) system. We found that a Center for Disease Control recommended routine screening policy in which all patients visiting the system are screened for HIV irrespective of risk factors may not be feasible due to budgetary constraints. Consequently, we used the model to develop and evaluate managerially relevant policies within existent capacity and budgetary constraints to improve upon the current risk based screening policy of screening only high risk patients. Our computational analysis showed that the GLA station can achieve substantial increase (20% to 300%) in the QALYs gained by using these policies over risk based screening.The GLA station has already adapted two of these policies that could yield better patient health outcomes over the next few years. In addition, our model insights have influenced the decision making process at this station