In the present work, we study the optimal reinsurance decision problem in which the Average Value-at-Risk of the retained loss is minimized under Wang's premium principle and is also subject to either (1) a budget constraint on reinsurance premium, or (2) a reinsurer's probabilistic benchmark constraint of his potential loss. We show that the optimal reinsurance is a single-insurance layer under Constraint (1), and a cap insurance or a double-insurance layer under Constraint (2); moreover, under Constraint (2), we further establish that under most common circumstances (see Remark after Theorem 3), a cap insurance will suffice to be optimal. Finally, some numerical illustrations will be provided.