The Dantzig-Wolfe Decomposition Algorithm

Solving a MILP with DECOMP and PROC OPTMODEL

The following statements use the OPTMODEL procedure and the Dantzig-Wolfe decomposition algorithm to solve the MILP:

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

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

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

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

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

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

Figure 1: Solution Summary and Optimal Solution

The OPTMODEL Procedure

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
Solutions Found	2
Iterations	2
Presolve Time	0.00
Solution Time	0.01

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 2.

Figure 2: 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 3 linear constraints (2 LE, 0 EQ, 1 GE, 0 range).

NOTE: The problem has 8 linear constraint coefficients.

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

NOTE: The SOLVE statement is executing in the distributed computing environment in

single-machine mode.

NOTE: The initial MILP heuristics are applied.

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: The number of block threads has been reduced to 2 threads.

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

of the constraints in the problem.

NOTE: The decomposition subproblems cover 6 (100%) variables and 2 (66.67%) constraints.

NOTE: The deterministic parallel mode is enabled.

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

Iter Best Master Best LP IP CPU Real

Bound Objective Integer Gap Gap Time Time

. 4.0000 3.0000 3.0000 25.00% 25.00% 0 0

1 4.0000 3.0000 3.0000 25.00% 25.00% 0 0

2 4.0000 4.0000 4.0000 0.00% 0.00% 0 0

Node Active Sols Best Best Gap CPU Real

Integer Bound Time Time

0 1 2 4.0000 4.0000 0.00% 0 0

NOTE: The Decomposition algorithm used 32 threads.

NOTE: The Decomposition algorithm time is 0.01 seconds.

NOTE: Optimal.

NOTE: Objective = 4.

Last updated: September 09, 2026