IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v300y2022i2p743-754.html

Bilevel integer programming on a Boolean network for discovering critical genetic alterations in cancer development and therapy

Author

Listed:
  • Moon, Kyungduk
  • Lee, Kangbok
  • Chopra, Sunil
  • Kwon, Steve

Abstract

Boolean network is a modeling tool that describes a dynamic system with binary variables and their logical transition formulas. Recent studies in precision medicine use a Boolean network to discover critical genetic alterations that may lead to cancer or target genes for effective therapies to individuals. In this paper, we study a logical inference problem in a Boolean network to find all such critical genetic alterations in a minimal (parsimonious) way. We propose a bilevel integer programming model to find a single minimal genetic alteration. Using the bilevel integer programming model, we develop a branch and bound algorithm that effectively finds all of the minimal alterations. Through a computational study with eleven Boolean networks from the literature, we show that the proposed algorithm finds solutions much faster than the state-of-the-art algorithms in large data sets.

Suggested Citation

  • Moon, Kyungduk & Lee, Kangbok & Chopra, Sunil & Kwon, Steve, 2022. "Bilevel integer programming on a Boolean network for discovering critical genetic alterations in cancer development and therapy," European Journal of Operational Research, Elsevier, vol. 300(2), pages 743-754.
    • Handle: RePEc:eee:ejores:v:300:y:2022:i:2:p:743-754
    DOI: 10.1016/j.ejor.2021.10.019
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221721008687
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2021.10.019?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
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. Weber, Gerhard-Wilhelm & Defterli, Ozlem & Alparslan Gök, SIrma Zeynep & Kropat, Erik, 2011. "Modeling, inference and optimization of regulatory networks based on time series data," European Journal of Operational Research, Elsevier, vol. 211(1), pages 1-14, May.
    2. C. Audet & P. Hansen & B. Jaumard & G. Savard, 1997. "Links Between Linear Bilevel and Mixed 0–1 Programming Problems," Journal of Optimization Theory and Applications, Springer, vol. 93(2), pages 273-300, May.
    3. H. Paul Williams, 2009. "Modelling In Logic For Integer Programming," International Series in Operations Research & Management Science, in: Logic and Integer Programming, chapter 0, pages 71-103, Springer.
    4. Matteo Fischetti & Ivana Ljubić & Michele Monaci & Markus Sinnl, 2017. "A New General-Purpose Algorithm for Mixed-Integer Bilevel Linear Programs," Operations Research, INFORMS, vol. 65(6), pages 1615-1637, December.
    5. Liu, Shaonan & Wang, Mingzheng & Kong, Nan & Hu, Xiangpei, 2021. "An enhanced branch-and-bound algorithm for bilevel integer linear programming," European Journal of Operational Research, Elsevier, vol. 291(2), pages 661-679.
    6. H. Paul Williams, 2009. "Logic and Integer Programming," International Series in Operations Research and Management Science, Springer, number 978-0-387-92280-5, December.
    7. James T. Moore & Jonathan F. Bard, 1990. "The Mixed Integer Linear Bilevel Programming Problem," Operations Research, INFORMS, vol. 38(5), pages 911-921, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Sun, Xuting & Zhao, Xiaoyao & Chung, Sai-Ho & Ma, Hoi-Lam, 2025. "An interactive decision making framework design for the outsourcing cooperation between the service provider and the airline: An exact bilevel method," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 199(C).

    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. Liu, Shaonan & Kong, Nan & Parikh, Pratik & Wang, Mingzheng, 2023. "Optimal trauma care network redesign with government subsidy: A bilevel integer programming approach," Omega, Elsevier, vol. 119(C).
    2. George Kozanidis & Eftychia Kostarelou, 2023. "An Exact Solution Algorithm for Integer Bilevel Programming with Application in Energy Market Optimization," Journal of Optimization Theory and Applications, Springer, vol. 197(2), pages 573-607, May.
    3. Junlong Zhang & Osman Y. Özaltın, 2021. "Bilevel Integer Programs with Stochastic Right-Hand Sides," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1644-1660, October.
    4. R. Paulavičius & C. S. Adjiman, 2020. "New bounding schemes and algorithmic options for the Branch-and-Sandwich algorithm," Journal of Global Optimization, Springer, vol. 77(2), pages 197-225, June.
    5. James Hebden & Fabian Winkler, 2021. "Computation of Policy Counterfactuals in Sequence Space," Finance and Economics Discussion Series 2021-042r1, Board of Governors of the Federal Reserve System (U.S.), revised 01 Sep 2024.
    6. O’Neill, Sam & Wrigley, Paul & Bagdasar, Ovidiu, 2022. "A mixed-integer linear programming formulation for the modular layout of three-dimensional connected systems," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 201(C), pages 739-754.
    7. Böttger, T. & Grimm, V. & Kleinert, T. & Schmidt, M., 2022. "The cost of decoupling trade and transport in the European entry-exit gas market with linear physics modeling," European Journal of Operational Research, Elsevier, vol. 297(3), pages 1095-1111.
    8. Vishal Bansal & Sachin Jayaswal & Ankur Sinha, 2024. "Capacitated multiple allocation hub location problems under the risk of interdiction: model formulations and solution approaches," Annals of Operations Research, Springer, vol. 332(1), pages 213-251, January.
    9. Maenhout, Broos & Šůcha, Přemysl & Valdmanova, Viktorie & Tkadlec, Ondřej & Rozlivkova, Jana Thao, 2026. "A bilevel approach to integrated surgeon scheduling and surgery planning solved via branch-and-price," Omega, Elsevier, vol. 138(C).
    10. Johanna Burtscheidt & Matthias Claus, 2025. "Existence of solutions in bilevel stochastic linear programming with integer variables in the lower level problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 102(2), pages 435-468, December.
    11. Holger Heitsch & René Henrion & Thomas Kleinert & Martin Schmidt, 2022. "On convex lower-level black-box constraints in bilevel optimization with an application to gas market models with chance constraints," Journal of Global Optimization, Springer, vol. 84(3), pages 651-685, November.
    12. Martin Bichler & Stefan Waldherr, 2022. "Core Pricing in Combinatorial Exchanges with Financially Constrained Buyers: Computational Hardness and Algorithmic Solutions," Operations Research, INFORMS, vol. 70(1), pages 241-264, January.
    13. Tanınmış, Kübra & Aras, Necati & Altınel, İ. Kuban, 2022. "Improved x-space algorithm for min-max bilevel problems with an application to misinformation spread in social networks," European Journal of Operational Research, Elsevier, vol. 297(1), pages 40-52.
    14. Soares, Inês & Alves, Maria João & Henggeler Antunes, Carlos, 2021. "A deterministic bounding procedure for the global optimization of a bi-level mixed-integer problem," European Journal of Operational Research, Elsevier, vol. 291(1), pages 52-66.
    15. Claudio Contardo & Jorge A. Sefair, 2022. "A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 890-908, March.
    16. Fischetti, Matteo & Monaci, Michele & Sinnl, Markus, 2018. "A dynamic reformulation heuristic for Generalized Interdiction Problems," European Journal of Operational Research, Elsevier, vol. 267(1), pages 40-51.
    17. Jaroslav Pluskal & Radovan Šomplák & Dušan Hrabec & Vlastimír Nevrlý & Lars Magnus Hvattum, 2022. "Optimal location and operation of waste-to-energy plants when future waste composition is uncertain," Operational Research, Springer, vol. 22(5), pages 5765-5790, November.
    18. Ambrosius, Mirjam & Grimm, Veronika & Kleinert, Thomas & Liers, Frauke & Schmidt, Martin & Zöttl, Gregor, 2020. "Endogenous price zones and investment incentives in electricity markets: An application of multilevel optimization with graph partitioning," Energy Economics, Elsevier, vol. 92(C).
    19. Mattia, Sara & Rossi, Fabrizio & Smriglio, Stefano, 2026. "Robust shift scheduling with discretionary rest breaks," Omega, Elsevier, vol. 141(C).
    20. Stojkoski, Viktor & Hidalgo, César A., 2026. "Optimizing economic complexity," Research Policy, Elsevier, vol. 55(4).

    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:eee:ejores:v:300:y:2022:i:2:p:743-754. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.