An exact solution approach based on column generation and a partial-objective constraint to design a cellulosic biofuel supply chain

This study provides an exact solution method to solve a mixed-integer linear programming model that prescribes an optimal design of a cellulosic biofuel supply chain. An embedded structure can be transformed to a generalized minimum cost flow problem, which is used as a sub-problem in a column generation approach, to solve the linear relaxation of the mixed-integer program. This study proposes a dynamic programming algorithm to solve the sub-problem in O(m) time, generating improving pathflows. It proposes an inequality, called the partial objective constraint, which is based on the portion of the objective function associated with binary variables, to underlie a branch-and-cut approach. Computational tests show that the proposed solution approach solves most instances faster than a state-of-the-art commercial solver (CPLEX). (C) 2014 The Authors. Published by Elsevier Ltd.