IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v29y2017i2p197-210.html
   My bibliography  Save this article

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

Author

Listed:
  • Onur Şeref

    (Department of Business Information Technology, Virginia Polytechnic Institute and State University, Blacksburg, Virginia 24061)

  • J. Paul Brooks

    (Department of Statistical Sciences and Operations Research and the Center for the Study of Biological Complexity, Virginia Commonwealth University, Richmond, Virginia 23284)

  • Bernice Huang

    (Department of Microbiology and Immunology and the Center for the Study of Biological Complexity, Virginia Commonwealth University, Richmond, Virginia 23298)

  • Stephen S. Fong

    (Department of Chemical and Life Sciences and the Center for the Study of Biological Complexity, Virginia Commonwealth University, Richmond, Virginia 23284)

Abstract

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.

Suggested Citation

  • Onur Şeref & J. Paul Brooks & Bernice Huang & Stephen S. Fong, 2017. "Enumeration and Cartesian Product Decomposition of Alternate Optimal Fluxes in Cellular Metabolism," INFORMS Journal on Computing, INFORMS, vol. 29(2), pages 197-210, May.
    • Handle: RePEc:inm:orijoc:v:29:y:2017:i:2:p:197-210
    DOI: 10.1287/ijoc.2016.0724
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2016.0724
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2016.0724?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. François Vanderbeck, 2000. "On Dantzig-Wolfe Decomposition in Integer Programming and ways to Perform Branching in a Branch-and-Price Algorithm," Operations Research, INFORMS, vol. 48(1), pages 111-128, February.
    2. T. H. Matheiss & David S. Rubin, 1980. "A Survey and Comparison of Methods for Finding All Vertices of Convex Polyhedral Sets," Mathematics of Operations Research, INFORMS, vol. 5(2), pages 167-185, May.
    3. Peter C. Fishburn, 1976. "Utility Independence on Subsets of Product Sets," Operations Research, INFORMS, vol. 24(2), pages 245-255, April.
    4. Theodore J. Lambert & Marina A. Epelman & Robert L. Smith, 2005. "A Fictitious Play Approach to Large-Scale Optimization," Operations Research, INFORMS, vol. 53(3), pages 477-489, June.
    5. G Appa, 2002. "On the uniqueness of solutions to linear programs," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(10), pages 1127-1132, October.
    6. Alp Muharremoglu & John N. Tsitsiklis, 2008. "A Single-Unit Decomposition Approach to Multiechelon Inventory Systems," Operations Research, INFORMS, vol. 56(5), pages 1089-1103, October.
    7. François Sainfort & Jean M. Deichtmann, 1996. "Decomposition of Utility Functions on Subsets of Product Sets," Operations Research, INFORMS, vol. 44(4), pages 609-616, August.
    8. E. Almaas & B. Kovács & T. Vicsek & Z. N. Oltvai & A.-L. Barabási, 2004. "Global organization of metabolic fluxes in the bacterium Escherichia coli," Nature, Nature, vol. 427(6977), pages 839-843, February.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Arpan Rijal & Marco Bijvank & Asvin Goel & René de Koster, 2021. "Workforce Scheduling with Order-Picking Assignments in Distribution Facilities," Transportation Science, INFORMS, vol. 55(3), pages 725-746, May.
    2. Ogbe, Emmanuel & Li, Xiang, 2017. "A new cross decomposition method for stochastic mixed-integer linear programming," European Journal of Operational Research, Elsevier, vol. 256(2), pages 487-499.
    3. Preil, Deniz & Krapp, Michael, 2022. "Bandit-based inventory optimisation: Reinforcement learning in multi-echelon supply chains," International Journal of Production Economics, Elsevier, vol. 252(C).
    4. Matthias Winkenbach & Alain Roset & Stefan Spinler, 2016. "Strategic Redesign of Urban Mail and Parcel Networks at La Poste," Interfaces, INFORMS, vol. 46(5), pages 445-458, October.
    5. Oliver Faust & Jochen Gönsch & Robert Klein, 2017. "Demand-Oriented Integrated Scheduling for Point-to-Point Airlines," Transportation Science, INFORMS, vol. 51(1), pages 196-213, February.
    6. Ganesh Janakiraman & John A. Muckstadt, 2009. "A Decomposition Approach for a Class of Capacitated Serial Systems," Operations Research, INFORMS, vol. 57(6), pages 1384-1393, December.
    7. Laurent, Monique & Vargas, Luis Felipe, 2022. "Finite convergence of sum-of-squares hierarchies for the stability number of a graph," Other publications TiSEM 3998b864-7504-4cf4-bc1d-f, Tilburg University, School of Economics and Management.
    8. repec:cep:stiecm:em/2012/559 is not listed on IDEAS
    9. Van-Anh Truong, 2014. "Approximation Algorithm for the Stochastic Multiperiod Inventory Problem via a Look-Ahead Optimization Approach," Mathematics of Operations Research, INFORMS, vol. 39(4), pages 1039-1056, November.
    10. DE WOLF, Daniel, 2003. "Using column generation to solve an industrial mixing problem," LIDAM Discussion Papers CORE 2003042, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    11. Amy Cohn & Michael Magazine & George Polak, 2009. "Rank‐Cluster‐and‐Prune: An algorithm for generating clusters in complex set partitioning problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 56(3), pages 215-225, April.
    12. Barry C. Smith & Ellis L. Johnson, 2006. "Robust Airline Fleet Assignment: Imposing Station Purity Using Station Decomposition," Transportation Science, INFORMS, vol. 40(4), pages 497-516, November.
    13. Tao Wu & Zhe Liang & Canrong Zhang, 2018. "Analytics Branching and Selection for the Capacitated Multi-Item Lot Sizing Problem with Nonidentical Machines," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 236-258, May.
    14. Richard Freling & H. Edwin Romeijn & Dolores Romero Morales & Albert P. M. Wagelmans, 2003. "A Branch-and-Price Algorithm for the Multiperiod Single-Sourcing Problem," Operations Research, INFORMS, vol. 51(6), pages 922-939, December.
    15. Awi Federgruen & Min Wang, 2015. "Inventory Models with Shelf-Age and Delay-Dependent Inventory Costs," Operations Research, INFORMS, vol. 63(3), pages 701-715, June.
    16. Marc Peeters & Zeger Degraeve, 2004. "The Co-Printing Problem: A Packing Problem with a Color Constraint," Operations Research, INFORMS, vol. 52(4), pages 623-638, August.
    17. Asimit, Alexandru V. & Bignozzi, Valeria & Cheung, Ka Chun & Hu, Junlei & Kim, Eun-Seok, 2017. "Robust and Pareto optimality of insurance contracts," European Journal of Operational Research, Elsevier, vol. 262(2), pages 720-732.
    18. Hekimoğlu, Mustafa & van der Laan, Ervin & Dekker, Rommert, 2018. "Markov-modulated analysis of a spare parts system with random lead times and disruption risks," European Journal of Operational Research, Elsevier, vol. 269(3), pages 909-922.
    19. Yael Grushka-Cockayne & Bert De Reyck & Zeger Degraeve, 2008. "An Integrated Decision-Making Approach for Improving European Air Traffic Management," Management Science, INFORMS, vol. 54(8), pages 1395-1409, August.
    20. Sung, Inkyung & Lee, Taesik, 2016. "Optimal allocation of emergency medical resources in a mass casualty incident: Patient prioritization by column generation," European Journal of Operational Research, Elsevier, vol. 252(2), pages 623-634.
    21. Noblesse, Ann M. & Boute, Robert N. & Lambrecht, Marc R. & Van Houdt, Benny, 2014. "Lot sizing and lead time decisions in production/inventory systems," International Journal of Production Economics, Elsevier, vol. 155(C), pages 351-360.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:29:y:2017:i:2:p:197-210. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.