CPLEX functionality for column generation and branch and price

Answer

The CPLEX C, C++, Java, and .NET APIs all provide the functions required to implement most column generation procedures involving linear and quadratic programs (including the root node associated with a MIP or MIQP) fairly quickly. Column generation typically involves a series of optimizations of a master and subproblem, where the solution from one problem is used to modify the other problem. All CPLEX APIs have the necessary functionality to maintain multiple problems, obtain solution values, and add constraints or variables to a problem. For example, look at the CutStock.java or cutstock.cpp example programs provided with the CPLEX software distribution.

When solving MIPs, the CPLEX APIs offer limited functionality to apply column generation to child node problems (also known as branch and price). This limitation arises because CPLEX does not directly permit the modification of node problems, a modification which is essential for column generation in the CPLEX branch and bound algorithm.

IBM offers a wide variety of optimization consulting services, including development of column generation applications when suitable. Click here for more information and contacts.