The Decomposition Algorithm

Special Case: Identical Blocks

In the special case of a set partitioning master problem and identical blocks, the underlying algorithm is automatically adjusted to reduce symmetry and improve overall performance. Identical blocks are subproblems that have equivalent feasible regions (and optima) when they are projected. Algebraically, this means that

$\begin{array}{lllllll} \mathbf{A}^1 & =& \mathbf{A}^2 & =& \dots & =& \mathbf{A}^\kappa \\ \mathbf{D}^1 & =& \mathbf{D}^2 & =& \dots & =& \mathbf{D}^\kappa \\ \mathbf{c}^1 & =& \mathbf{c}^2 & =& \dots & =& \mathbf{c}^\kappa \\ \mathbf{b}^1 & =& \mathbf{b}^2 & =& \dots & =& \mathbf{b}^\kappa \\ \mathbf{\overline{x}}^1 & =& \mathbf{\overline{x}}^2 & =& \dots & =& \mathbf{\overline{x}}^\kappa \\ \mathbf{\underline{x}}^1 & =& \mathbf{\underline{x}}^2 & =& \dots & =& \mathbf{\underline{x}}^\kappa \end{array}$

A set partitioning problem is a specific type of integer programming model in which each constraint represents choosing exactly one member of a set. These constraints are often referred to as assignment constraints. The linear relaxation of a set partitioning problem enables an algorithm to choose fractional parts of several members of some set such that they sum to 1. Algebraically, this means $\mathbf{A}\mathbf{x} = \mathbf{1}$ , where all of the coefficients in $\mathbf{A}$ are 0 or 1.

The performance of algorithms that use a branch-and-bound method can be hurt when the formulation contains substructures that are symmetric. In this context, symmetric means that an assignment of solutions can be arbitrarily permuted for some component without affecting the optimality of that solution. For example, if

$\begin{array}{lllll} x_{11}=1 & x_{12}=0 & x_{21}=0 & x_{22}=1 & \mbox{and}\\ x_{11}=0 & x_{12}=1 & x_{21}=1 & x_{22}=0 & \end{array}$

are both optimal, then these solutions, $x_{ij}$ , are considered symmetric on index $j$ . That is, you can interchange $j=1$ and $j=2$ without changing the optimality of the solution. The presence of identical blocks in a mathematical program is an obvious case in which symmetry can hurt performance. In order to overcome this handicap, the decomposition algorithm aggregates the identical blocks into one block when it forms the Dantzig-Wolfe master problem. In addition, because the original master problem is a set partitioning model, the algorithm uses a specialized branching rule known as Ryan-Foster branching. For more information about the aggregate formulation and Ryan-Foster branching, see Barnhart et al. (1998).

Suppose you want to solve the following problem:

$\begin{array}{rrrrrrrrrrrrlll} \mbox{max} & x_{11} & + & 2 x_{21} & + & x_{31} & + & x_{12} & + & 2 x_{22} & + & x_{32} \\ \mbox{subject to} & x_{11} & & & & & & x_{12} & & & & & = & 1 & \mbox{(m1)} \\ & & & x_{21} & & & & & & x_{22} & & & = & 1 & \mbox{(m2)} \\ & 5 x_{11} & + & 7 x_{21} & + & 4 x_{31} & & & & & & & \leq & 11 & \mbox{(s1)} \\ & & & & & & & 5 x_{12} & + & 7 x_{22} & + & 4 x_{32} & \leq & 11 & \mbox{(s2)} \\ & \multicolumn{8}{c}{x_{ij} \in \{ 0,1\} \; \; i \in \{ 1,\dots ,3\} , j \in \{ 1,\dots ,2\} } \\ \end{array}$

If constraints (m1) and (m2) are removed, then the remaining constraints (s1) and (s2) decompose into two independent and identical subproblems. In addition, constraints (m1) and (m2) form a set partitioning master problem.

The following statements use the OPTMODEL procedure and the decomposition algorithm to solve the preceding problem:

proc optmodel;
   var x{i in 1..3, j in 1..2} binary;

   max f =    x[1,1] + 2*x[2,1] +   x[3,1] +
              x[1,2] + 2*x[2,2] +   x[3,2];

   con m1:    x[1,1] +   x[1,2]             =  1;
   con m2:    x[2,1] +   x[2,2]             =  1;
   con s1:  5*x[1,1] + 7*x[2,1] + 4*x[3,1] <= 11;
   con s2:  5*x[1,2] + 7*x[2,2] + 4*x[3,2] <= 11;

   s1.block = 0;
   s2.block = 1;

   solve with milp / presolver=none decomp=(logfreq=1);
   print x;
quit;

Here, the PRESOLVER=NONE option is used again, because otherwise the presolver solves this small instance without invoking any solver. The solution summary and optimal solution are displayed in Figure 14.3.

Figure 14.3: Solution Summary and Optimal Solution

Solution Summary
Solver	MILP
Algorithm	Decomposition
Objective Function	f
Solution Status	Optimal
Objective Value	4

Relative Gap	0
Absolute Gap	0
Primal Infeasibility	0
Bound Infeasibility	0
Integer Infeasibility	0

Best Bound	4
Nodes	1
Iterations	3
Presolve Time	0.08
Solution Time	0.86

x
	1	2
1	0	1
2	1	0
3	1	1

The iteration log, which displays the problem statistics, the progress of the solution, and the optimal objective value, is shown in Figure 14.4.

Figure 14.4: Log

NOTE: Problem generation will use 4 threads.

NOTE: The problem has 6 variables (0 free, 0 fixed).

NOTE: The problem has 6 binary and 0 integer variables.

NOTE: The problem has 4 linear constraints (2 LE, 2 EQ, 0 GE, 0 range).

NOTE: The problem has 10 linear constraint coefficients.

NOTE: The problem has 0 nonlinear constraints (0 LE, 0 EQ, 0 GE, 0 range).

NOTE: The MILP presolver value NONE is applied.

NOTE: The MILP solver is called.

NOTE: The Decomposition algorithm is used.

NOTE: The Decomposition algorithm is executing in single-machine mode.

NOTE: The DECOMP method value USER is applied.

NOTE: All blocks are identical.

NOTE: The Decomposition algorithm is using an aggregate formulation and Ryan-Foster

branching.

NOTE: The problem has a decomposable structure with 2 blocks. The largest block

covers 25.00% of the constraints in the problem.

NOTE: The decomposition subproblems cover 6 (100.00%) variables and 2 (50.00%)

constraints.

NOTE: The deterministic parallel mode is enabled.

NOTE: The Decomposition algorithm is using up to 4 threads.

Iter Best Master Best LP IP CPU Real

Bound Objective Integer Gap Gap Time Time

NOTE: Starting phase 1.

1 0.0000 1.0000 . 1.00e+00 . 0 0

2 0.0000 0.0000 . 0.00% . 0 0

NOTE: Starting phase 2.

. 6.0000 5.0000 5.0000 16.67% 16.67% 0 0

3 6.0000 5.0000 5.0000 16.67% 16.67% 0 0

4 5.0000 5.0000 5.0000 0.00% 0.00% 0 0

Node Active Sols Best Best Gap CPU Real

Integer Bound Time Time

0 0 1 5.0000 5.0000 0.00% 0 0

NOTE: The Decomposition algorithm used 1 threads.

NOTE: The Decomposition algorithm time is 0.01 seconds.

NOTE: Optimal.

NOTE: Objective = 5.

The decomposition solver recognizes the fact that the master is a set partitioning formulation and that each block is identical. It formulates the aggregate master and uses Ryan-Foster branching to solve the model.

In the presence of identical blocks, under certain circumstances, the aggregate formulation can also be used with a set covering master formulation. A set covering problem is an integer programming model in which each constraint represents choosing at least one member of a set. Algebraically, this means $\mathbf{A}\mathbf{x} \geq \mathbf{1}$ , where all of the coefficients in $\mathbf{A}$ are 0 or 1. Aggregate formulation and Ryan-Foster branching can be used if there exists an optimal solution, $\mathbf{x}^*$ , that is binding at equality ( $\mathbf{A}\mathbf{x^{*}} = \mathbf{1}$ ). For example, this is true in the case of a minimization problem where all the objective coefficients are nonnegative. In that case, it would never be optimal to over-cover some assignment constraint. When given a set covering master formulation, the solver automatically checks these conditions and applies the aggregate formulation, if appropriate. The decomposition algorithm usually performs better when it uses a set covering formulation as opposed to a set partitioning formulation, because it is generally easier to find integer feasible solutions. If the models are equivalent, using the set covering formulation is recommended. For two examples, see Example 14.5, which shows the bin-packing problem, and Example 14.7, which shows the vehicle routing problem.

A set packing problem is an integer programming model in which each constraint represents choosing at most one member of a set. Algebraically, this means $\mathbf{A}\mathbf{x} \leq \mathbf{1}$ , where all of the coefficients in $\mathbf{A}$ are 0 or 1. This type of master formulation does not work directly with the aggregate formulation and Ryan-Foster branching. However, any set packing model can be transformed into a set partitioning model by introducing a zero-cost slack variable for each packing constraint. See Example 14.10, which shows an application that optimizes a kidney donor exchange.

The decomposition algorithm automatically searches for identical blocks and a set partitioning or set covering master formulation. If it finds these, it automatically generates the aggregate formulation and uses Ryan-Foster branching. The aggregate model needs to process only one block at each subproblem iteration. Therefore, parallel execution, as described in Parallel Execution, cannot improve performance. For this reason, when the decomposition algorithm runs in distributed mode, it does not create the aggregate formulation nor does it use Ryan-Foster branching, even if the blocks are found to be identical.