IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v29y2017i2p197-210.html

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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. Peter C. Fishburn, 1976. "Utility Independence on Subsets of Product Sets," Operations Research, INFORMS, vol. 24(2), pages 245-255, April.
    6. 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.
    7. 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.
    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. Giorgio Fagiolo & Javier Reyes & Stefano Schiavo, 2010. "The evolution of the world trade web: a weighted-network analysis," Journal of Evolutionary Economics, Springer, vol. 20(4), pages 479-514, August.
    2. Valerio de Carvalho, J. M., 2002. "LP models for bin packing and cutting stock problems," European Journal of Operational Research, Elsevier, vol. 141(2), pages 253-273, September.
    3. 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.
    4. François Vanderbeck, 2000. "Exact Algorithm for Minimising the Number of Setups in the One-Dimensional Cutting Stock Problem," Operations Research, INFORMS, vol. 48(6), pages 915-926, December.
    5. 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.
    6. 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).
    7. Korte, Johanna P. & Yorke-Smith, Neil, 2025. "An aircraft and schedule integrated approach to crew scheduling for a point-to-point airline," Journal of Air Transport Management, Elsevier, vol. 124(C).
    8. 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.
    9. Gamvros, Ioannis & Raghavan, S., 2012. "Multi-period traffic routing in satellite networks," European Journal of Operational Research, Elsevier, vol. 219(3), pages 738-750.
    10. Enrique Campos-Nañez & Alfredo Garcia & Chenyang Li, 2008. "A Game-Theoretic Approach to Efficient Power Management in Sensor Networks," Operations Research, INFORMS, vol. 56(3), pages 552-561, June.
    11. Hadi W. Purnomo & Jonathan F. Bard, 2007. "Cyclic preference scheduling for nurses using branch and price," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(2), pages 200-220, March.
    12. 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.
    13. Manafzadeh Dizbin, Nima & Tan, Barış, 2020. "Optimal control of production-inventory systems with correlated demand inter-arrival and processing times," International Journal of Production Economics, Elsevier, vol. 228(C).
    14. 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.
    15. Alfandari, Laurent & Plateau, Agnès & Scheplerc, Xavier, 2014. "A Branch-and-Price-and-Cut Approach for Sustainable Crop Rotation Planning," ESSEC Working Papers WP1408, ESSEC Research Center, ESSEC Business School.
    16. 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.
    17. repec:cep:stiecm:em/2012/559 is not listed on IDEAS
    18. 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.
    19. 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).
    20. Alfandari, Laurent & Plateau, Agnès & Schepler, Xavier, 2015. "A branch-and-price-and-cut approach for sustainable crop rotation planning," European Journal of Operational Research, Elsevier, vol. 241(3), pages 872-879.
    21. 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.

    More about this item

    Keywords

    ;
    ;
    ;

    Statistics

    Access and download statistics

    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.