The Separation Problem for Binary Decision Diagrams.
André A. Ciré, John Hooker · ISAIM · 2014
The separation problem is central to mathematical programming. It asks how a continuous relaxation of an optimization problem can be strengthened by adding constraints that separate or cut off an infeasible solution. We study an analogous separation problem for a discrete relaxation based on binary decision diagrams (BDDs), which have recently proved useful in optimization and constraint programming. The algorithm modifies a relaxed BDD so as to exclude a single solution or family of solutions specified by a partial assignment. A key issue is the growth of the separating BDD when a sequence of solutions are cut off. We prove lower and upper bounds on the growth rate. We also examine growth empirically in a logicbased Benders method for a home health care scheduling problem. We find that the separating BDD tends to grow only linearly with the number of Benders cuts. Introduction The separation problem is fundamental for mathematical programming methods. It is generally understood as the problem of finding a constraint that “separates” or “cuts off” a given infeasible solution. The separation problem normally arises when a relaxation of the problem is solved to obtain a bound on the optimal value of the problem. When the solution of the relaxation is infeasible in the original problem, the relaxation is augmented with one or more constraints that cut off the solution. The tighter relaxation that results can then be solved to obtain a different solution, perhaps one that is feasible in the original problem or provides a better bound. For example, integer programming (IP) solvers typically solve a continuous relaxation of the problem. When the solution is infeasible, separating cuts in the form of linear inequality constraints may be generated and added to the relaxation. The cuts may be general Gomory cuts or mixed-integer rounding cuts, or they may be special-purpose cuts that exploit the problem structure (see (Marchand et al. 2002) for a survey). Given this, one may ask whether separation can be useful for other kinds of relaxations in an optimization context. One possible relaxation is a discrete relaxation based on binary decision diagrams (BDDs), which have recently been applied to optimization and constraint programming (CP). BDDs have long been used for circuit design, configuration, and related purposes (Akers 1978; Lee 1959; Bryant 1986; Hu 1995), but relaxed BDDs can provide an enhancement to the traditional CP domain store, bounds for branchand-bound methods, and a master problem formulation for Benders decomposition (Andersen et al. 2007; Hadžic et al. 2008; Hoda, van Hoeve, and Hooker 2010; Hadžic and Hooker 2006; 2007; Becker et al. 2005; Behle and Eisenbrand 2007). In this paper, we study the separation problem for BDDs. We present a general separation algorithm and investigate the complexity of separation, both analytically and empirically. The algorithm and analysis can be easily extended to multivalued decision diagrams (MDDs). Separating BDDs For our purposes, a BDD is a directed acyclic graph in which the nodes are partioned into layers, with the root node r in layer 1 and the terminal node t in layer n + 1. Layers 1, . . . , n correspond to binary variables x1, . . . , xn, and each arc leaving a node in layer i is labeled 0 or 1 to indicate a value of xi. Each path from the root to the terminal node therefore corresponds to a possible assignment to x = (x1, . . . , xn). Examples of BDDs appear in Fig. 1, where dashed arcs are 0-arcs and solid arcs are 1-arcs. A BDD is reduced when it is the smallest BDD that represents a given set of assignments to x. It can be shown that there is a unique reduced BDD for a given variable ordering (Bryant 1986). Any 0-1 optimization problem with variables x can be represented by a BDD whose r-t paths correspond to feasible solutions of the problem. A separable objective function ∑ i fi(xi) can be represented by assigning length fi(0) to 0-arcs leaving layer i and fi(1) to 1-arcs. An optimal solution of the problem corresponds to a shortest (or longest) path in the BDD. Nonseparable objective functions can be represented by assigning canonical costs as described in (Hooker 2013).