Decomposition example programs that use CPLEX

Answer

The cutstock.cpp cutstock.cpp cutstock.datexample program illustrates column generation applied to the cutting stock problem. For a more generic column generation sample, use this: dwdecomp.c

Lagrangian Relaxation is another commonly used decomposition algorithm. This sample - lagrange.zip shows a Lagrangian relaxation for a location-transportation problem. The original MIP is decomposed into two problems in order to deduce a multiplier for a particular constraint based on Lagrange relaxation. The sample shows multiple optimization through modifications of different models existing in a single environment. The attached file contains two such implementation using OPL Studio and C++ Concert.

Benders' Decomposition, which can be viewed as column generation applied to the dual model, typically is applied to model formulations with large numbers of constraints, perhaps even too many to represent explicitly in the model. The attached sample illustrates Benders' Decomposition on the Asymmetric Travelling Salesman problem.

atsp.dat