Enumeration and Cartesian Product Decomposition of Alternate Optimal Fluxes in Cellular Metabolism

We introduce a framework for finding and analyzing all optimal solutions to a linear‐programming‐based model for cellular metabolism. The implementation of a pivoting‐based method for generating alternate optimal reaction fluxes is described. We present a novel strongly polynomial algorithm to decompose a matrix of alternate optimal solutions of an optimization problem into independent subsets of variables and their respective alternate solutions. The matrix can be reconstructed as a Cartesian product of these subsets of alternate solutions. We demonstrate that our strategy for enumeration is more efficient than other methods, and that our Cartesian product matrix decomposition can quickly recover independent substructures. The framework is applied to analyze the metabolic reconstruction of a disease‐causing organism, revealing metabolic pathways that are independently regulated. Data and the online supplement are available at https://doi.org/10.1287/ijoc.2016.0724.