Dantzig–Wolfe Reformulation and Column Generation: Optimization in the Chemical Tanker Industry

Global chemical supply chains rely on chemical tankers for the movement of their raw materials and products. A chemical tanker is a sophisticated multi-compartment cargo ship that transports chemicals between ports. This chapter describes some of the decision problems arising while planning operations of such tankers. Assignment of chemicals to compartments of the tanker is considered in particular. Several domain-specific assignment decisions related to cargo-cargo and cargo-compartment compatibility rules, and tanker balancing safety restrictions make this assignment problem unique. A mixed-integer linear programming (MILP) model for the assignment problem is presented along with some insights on its structure and complexity. A different formulation based on the Dantzig–Wolfe reformulation is derived. The reformulation is solved using a customized column generation framework. This approach enables one to take advantage of multiple special structures in the problem. Some discussions around the implementation nuances are also presented.