IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v10y2005i1d10.1007_s10878-005-1859-8.html
   My bibliography  Save this article

Computational Comparison Studies of Quadratic Assignment Like Formulations for the In Silico Sequence Selection Problem in De Novo Protein Design

Author

Listed:
  • H. K. Fung

    (Princeton University)

  • S. Rao

    (Princeton University)

  • C. A. Floudas

    (Princeton University)

  • O. Prokopyev

    (University of Florida)

  • P. M. Pardalos

    (University of Florida)

  • F. Rendl

    (Universität Klagenfurt)

Abstract

In this paper an O(n2) mathematical formulation for in silico sequence selection in de novo protein design proposed by Klepeis et al. (2003, 2004), in which the number of additional variables and linear constraints scales with the square of the number of binary variables, is compared to three O(n) formulations. It is found that the O(n2) formulation is superior to the O(n) formulations on most sequence search spaces. The superiority of the O(n2) formulation is due to the reformulation linearization techniques (RLTs), since the O(n2) formulation without RLTs is found to be computationally less efficient than the O(n) formulations. In addition, new algorithmic enhancing components of RLTs with inequality constraints, triangle inequalities, and Dead-End Elimination (DEE) type preprocessing are added to the O(n2) formulation. The current best O(n2) formulation, which is the original formulation from Klepeis et al. (2003, 2004) plus DEE type preprocessing, is proposed for in silico sequence search. For a test problem with a search space of 3.4×1045 sequences, this new improved model is able to reduce the required CPU time by 67%.

Suggested Citation

  • H. K. Fung & S. Rao & C. A. Floudas & O. Prokopyev & P. M. Pardalos & F. Rendl, 2005. "Computational Comparison Studies of Quadratic Assignment Like Formulations for the In Silico Sequence Selection Problem in De Novo Protein Design," Journal of Combinatorial Optimization, Springer, vol. 10(1), pages 41-60, August.
    • Handle: RePEc:spr:jcomop:v:10:y:2005:i:1:d:10.1007_s10878-005-1859-8
    DOI: 10.1007/s10878-005-1859-8
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-005-1859-8
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-005-1859-8?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 search for a different version of it.

    References listed on IDEAS

    as
    1. Oral, Muhittin & Kettani, Ossama, 1992. "Reformulating nonlinear combinatorial optimization problems for higher computational efficiency," European Journal of Operational Research, Elsevier, vol. 58(2), pages 236-249, April.
    2. Fred Glover, 1975. "Improved Linear Integer Programming Formulations of Nonlinear Integer Problems," Management Science, INFORMS, vol. 22(4), pages 455-460, December.
    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. Joonghyun Ryu & Deok-Soo Kim, 2013. "Protein structure optimization by side-chain positioning via beta-complex," Journal of Global Optimization, Springer, vol. 57(1), pages 217-250, September.
    2. Andrew C. Trapp & Oleg A. Prokopyev, 2010. "Solving the Order-Preserving Submatrix Problem via Integer Programming," INFORMS Journal on Computing, INFORMS, vol. 22(3), pages 387-400, August.

    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. Sven Mallach, 2018. "Compact linearization for binary quadratic problems subject to assignment constraints," 4OR, Springer, vol. 16(3), pages 295-309, September.
    2. Yokoyama, Ryohei & Kitano, Hiroyuki & Wakui, Tetsuya, 2017. "Optimal operation of heat supply systems with piping network," Energy, Elsevier, vol. 137(C), pages 888-897.
    3. Christodoulos Floudas & Xiaoxia Lin, 2005. "Mixed Integer Linear Programming in Process Scheduling: Modeling, Algorithms, and Applications," Annals of Operations Research, Springer, vol. 139(1), pages 131-162, October.
    4. Gupta, Renu & Bandopadhyaya, Lakshmisree & Puri, M. C., 1996. "Ranking in quadratic integer programming problems," European Journal of Operational Research, Elsevier, vol. 95(1), pages 231-236, November.
    5. Osman, Hany & Demirli, Kudret, 2010. "A bilinear goal programming model and a modified Benders decomposition algorithm for supply chain reconfiguration and supplier selection," International Journal of Production Economics, Elsevier, vol. 124(1), pages 97-105, March.
    6. Verbiest, Floor & Cornelissens, Trijntje & Springael, Johan, 2019. "A matheuristic approach for the design of multiproduct batch plants with parallel production lines," European Journal of Operational Research, Elsevier, vol. 273(3), pages 933-947.
    7. Biswas, Debajyoti & Alfandari, Laurent, 2022. "Designing an optimal sequence of non‐pharmaceutical interventions for controlling COVID-19," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1372-1391.
    8. Sven Mallach, 2021. "Inductive linearization for binary quadratic programs with linear constraints," 4OR, Springer, vol. 19(4), pages 549-570, December.
    9. Ricardo M. Lima & Ignacio E. Grossmann, 2017. "On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study," Computational Optimization and Applications, Springer, vol. 66(1), pages 1-37, January.
    10. Jih-Jeng Huang, 2016. "Resource decision making for vertical and horizontal integration problems in an enterprise," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 67(11), pages 1363-1372, November.
    11. Andrés Gómez & Oleg A. Prokopyev, 2021. "A Mixed-Integer Fractional Optimization Approach to Best Subset Selection," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 551-565, May.
    12. Dimitris Bertsimas & Ryan Cory-Wright, 2022. "A Scalable Algorithm for Sparse Portfolio Selection," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1489-1511, May.
    13. Wakui, Tetsuya & Akai, Kazuki & Yokoyama, Ryohei, 2022. "Shrinking and receding horizon approaches for long-term operational planning of energy storage and supply systems," Energy, Elsevier, vol. 239(PD).
    14. Parreño, Francisco & Álvarez-Valdés, Ramón & Martí, Rafael, 2021. "Measuring diversity. A review and an empirical analysis," European Journal of Operational Research, Elsevier, vol. 289(2), pages 515-532.
    15. Martina Fischetti & Michele Monaci, 2016. "Proximity search heuristics for wind farm optimal layout," Journal of Heuristics, Springer, vol. 22(4), pages 459-474, August.
    16. Gabrielli, Paolo & Gazzani, Matteo & Martelli, Emanuele & Mazzotti, Marco, 2018. "Optimal design of multi-energy systems with seasonal storage," Applied Energy, Elsevier, vol. 219(C), pages 408-424.
    17. Sun, Xuting & Chung, Sai-Ho & Choi, Tsan-Ming & Sheu, Jiuh-Biing & Ma, Hoi Lam, 2020. "Combating lead-time uncertainty in global supply chain's shipment-assignment: Is it wise to be risk-averse?," Transportation Research Part B: Methodological, Elsevier, vol. 138(C), pages 406-434.
    18. Bretthauer, Kurt M. & Ross, Anthony & Shetty, Bala, 1999. "Nonlinear integer programming for optimal allocation in stratified sampling," European Journal of Operational Research, Elsevier, vol. 116(3), pages 667-680, August.
    19. Feng, Wei & Feng, Yiping & Zhang, Qi, 2021. "Multistage robust mixed-integer optimization under endogenous uncertainty," European Journal of Operational Research, Elsevier, vol. 294(2), pages 460-475.
    20. Fu, Zhexi & Chow, Joseph Y.J., 2022. "The pickup and delivery problem with synchronized en-route transfers for microtransit planning," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 157(C).

    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:spr:jcomop:v:10:y:2005:i:1:d:10.1007_s10878-005-1859-8. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.