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
-
ExamplesMulticommodity Flow ProblemGeneralized Assignment ProblemBlock-Diagonal Structure and METHOD=AUTO in Single-Machine ModeBlock-Diagonal Structure and METHOD=AUTO in Distributed ModeBin Packing ProblemResource Allocation ProblemVehicle Routing ProblemATM Cash Management in Single-Machine ModeATM Cash Management in Distributed ModeKidney Donor Exchange
- References
Subsections:
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_decomp0033.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.