dantzig-wolfe-decompositionlisted

# Dantzig-Wolfe Decomposition You are an expert in Dantzig-Wolfe (DW) decomposition for linear and mixed-integer programs. This skill covers detecting block-angular structure in a constraint matrix, reformulating the original (compact) model into a master problem with convexity constraints plus independent pricing subproblems, solving the reformulation by column generation, and interpreting the resulting bound against the LP relaxation, the Lagrangian dual, and the integer optimum. Use the framework below to decide whether a model is worth decomposing, to execute the reformulation correctly, and to verify the bound relationships on the user's instance. ## Initial Assessment Establish the following before reformulating anything: - **Structure.** Which constraint rows couple otherwise-independent variable groups? Ask the user to name the natural blocks (plants, vehicles, machines, periods, scenarios). If they cannot, run structure detection on the constraint matrix (section below). - **Linking fraction.** Count linking rows m0 versus total rows. DW pays off when m0 is small relative to the block rows — a useful rule of thumb is linking rows below 10-20% of all rows. - **Problem class.** LP or MIP? If MIP, locate the integrality: integer variables inside blocks make the DW bound potentially stronger than the LP bound; integrality that lives only in the linking rows gains nothing from convexification. - **Block inventory.** Number of blocks K, variables per block, and whether