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 Problem and METHOD=NETWORKGeneralized Assignment ProblemBlock-Diagonal Structure and METHOD=CONCOMP in Single-Machine ModeBlock-Diagonal Structure and METHOD=CONCOMP in Distributed ModeBlock-Angular Structure and METHOD=AUTOBin Packing ProblemResource Allocation ProblemVehicle Routing ProblemATM Cash Management in Single-Machine ModeATM Cash Management in Distributed ModeKidney Donor Exchange and METHOD=SET
- References
Data Input
This subsection describes the format for describing the partition of the constraint system that defines the subproblem blocks.
In the OPTLP and OPTMILP procedures, partitioning is done by using a data set specified in the BLOCKS= data option in the
DECOMP statement. In PROC OPTMODEL, partitioning is done by using the .block suffix on constraints.
The blocks must be disjoint with respect to variables. If two blocks contain a nonzero coefficient for the same variable, the decomposition algorithm produces an error that contains information about where the blocks overlap.
The BLOCKS= Data Set in PROC OPTMILP and PROC OPTLP
The BLOCKS= data set has two required variables:
See the section Solving a MILP with DECOMP and PROC OPTMILP for an example of using this BLOCKS= data set with PROC OPTMILP.
The .block Constraint Suffix in PROC OPTMODEL
The .block constraint suffix specifies the numeric block identifier for each constraint in the problem. The block identifiers do not
need to start from 0, nor do they need to be consecutive. Master (linking) constraints can be identified by using a missing
value. Listing the linking constraints is optional.
See the section Solving a MILP with DECOMP and PROC OPTMODEL for an example of using the .block constraint suffix with PROC OPTMODEL.