The Decomposition Algorithm
- Overview
-
Getting Started
-
SyntaxDecomposition Algorithm Options in the PROC OPTLP Statement or the SOLVE WITH LP Statement in PROC OPTMODELDecomposition Algorithm Options in the PROC OPTMILP Statement or the SOLVE WITH MILP Statement in PROC OPTMODELDECOMP StatementDECOMP_MASTER StatementDECOMP_MASTER_IP StatementDECOMP_SUBPROB Statement
-
Details
-
Examples
- References
Getting Started: Decomposition Algorithm
This example illustrates how you can use the decomposition algorithm to solve a simple mixed integer linear program. Suppose you want to solve the following problem:
![\[ \begin{array}{rrrrrrrrrrrrlll} \mbox{max} & x_{11} & + & 2 x_{21} & + & x_{31} & + & & + & x_{22} & + & x_{32} \\ \mbox{subject to} & x_{11} & & & & & & x_{12} & & & & & \geq & 1 & \mbox{(m)} \\ & 5 x_{11} & + & 7 x_{21} & + & 4 x_{31} & & & & & & & \leq & 11 & \mbox{(s1)} \\ & & & & & & & x_{12} & + & 2 x_{22} & + & x_{32} & \leq & 2 & \mbox{(s2)} \\ & \multicolumn{8}{c}{x_{ij} \in \{ 0,1\} \; \; i \in \{ 1,\dots ,3\} , j \in \{ 1,\dots ,2\} } \\ \end{array} \]](images/ormpug_decomp0028.png) |
It is obvious from the structure of the problem that if constraint (m) is removed, then the remaining constraints (s1) and (s2) decompose into two independent subproblems. The next two sections describe how to solve this MILP by using the decomposition algorithm in the OPTMODEL procedure and OPTMILP procedure, respectively.