  We consider the chance-constrained program (CCP) with random right-hand side
under a finite discrete distribution. It is known that the standard mixed
integer linear programming (MILP) reformulation of the CCP is generally
difficult to solve by general-purpose solvers as the branch-and-cut search
trees are enormously large, partly due to the weak linear programming
relaxation. In this paper, we identify another reason for this phenomenon: the
intersection of the feasible regions of the subproblems in the search tree
could be nonempty, leading to a wasteful duplication of effort in exploring the
uninteresting overlap in the search tree. To address the newly identified
challenge and enhance the capability of the MILP-based approach in solving
CCPs, we first show that the overlap in the search tree can be completely
removed by a family of valid nonlinear if-then constraints, and then propose
two practical approaches to tackle the highly nonlinear if-then constraints. In
particular, we use the concept of dominance relations between different
scenarios of the random variables, and propose a novel branching, called
dominance-based branching, which is able to create a valid partition of the
problem with a much smaller overlap than the classic variable branching.
Moreover, we develop overlap-oriented node pruning and variable fixing
techniques, applied at each node of the search tree, to remove more overlaps in
the search tree. Computational results demonstrate the effectiveness of the
proposed dominance-based branching and overlap-oriented node pruning and
variable fixing techniques in reducing the search tree size and improving the
overall solution efficiency.
