IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v123y2000i2p346-371.html
   My bibliography  Save this article

The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations

Author

Listed:
  • Macambira, Elder Magalhaes
  • de Souza, Cid Carvalho

Abstract

No abstract is available for this item.

Suggested Citation

  • Macambira, Elder Magalhaes & de Souza, Cid Carvalho, 2000. "The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations," European Journal of Operational Research, Elsevier, vol. 123(2), pages 346-371, June.
    • Handle: RePEc:eee:ejores:v:123:y:2000:i:2:p:346-371
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(99)00262-3
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Dijkhuizen, G. & Faigle, U., 1993. "A cutting-plane approach to the edge-weighted maximal clique problem," European Journal of Operational Research, Elsevier, vol. 69(1), pages 121-130, August.
    2. Park, Kyungchul & Lee, Kyungsik & Park, Sungsoo, 1996. "An extended formulation approach to the edge-weighted maximal clique problem," European Journal of Operational Research, Elsevier, vol. 95(3), pages 671-682, 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. Seyedmohammadhossein Hosseinian & Dalila B. M. M. Fontes & Sergiy Butenko, 2020. "A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 747-762, July.
    2. Seyedmohammadhossein Hosseinian & Dalila B. M. M. Fontes & Sergiy Butenko, 2018. "A nonconvex quadratic optimization approach to the maximum edge weight clique problem," Journal of Global Optimization, Springer, vol. 72(2), pages 219-240, October.
    3. Michael M. Sørensen, 2004. "b-Tree Facets for the Simple Graph Partitioning Polytope," Journal of Combinatorial Optimization, Springer, vol. 8(2), pages 151-170, June.
    4. Leonardo Lamorgese & Carlo Mannino, 2015. "An Exact Decomposition Approach for the Real-Time Train Dispatching Problem," Operations Research, INFORMS, vol. 63(1), pages 48-64, February.
    5. Hunting, Marcel & Faigle, Ulrich & Kern, Walter, 2001. "A Lagrangian relaxation approach to the edge-weighted clique problem," European Journal of Operational Research, Elsevier, vol. 131(1), pages 119-131, May.
    6. Rinaldi, Marco & Viti, Francesco, 2017. "Exact and approximate route set generation for resilient partial observability in sensor location problems," Transportation Research Part B: Methodological, Elsevier, vol. 105(C), pages 86-119.
    7. Carvalho, Filipa D. & Almeida, M. Teresa, 2011. "Upper bounds and heuristics for the 2-club problem," European Journal of Operational Research, Elsevier, vol. 210(3), pages 489-494, May.
    8. Alidaee, Bahram & Glover, Fred & Kochenberger, Gary & Wang, Haibo, 2007. "Solving the maximum edge weight clique problem via unconstrained quadratic programming," European Journal of Operational Research, Elsevier, vol. 181(2), pages 592-597, September.
    9. Sørensen, Michael M., 2005. "Polyhedral Computations for the Simple Graph Partitioning Problem," CORAL Working Papers L-2005-02, University of Aarhus, Aarhus School of Business, Department of Business Studies.
    10. Wu, Qinghua & Hao, Jin-Kao, 2013. "A hybrid metaheuristic method for the Maximum Diversity Problem," European Journal of Operational Research, Elsevier, vol. 231(2), pages 452-464.
    11. Daehan Won & Hasan Manzour & Wanpracha Chaovalitwongse, 2020. "Convex Optimization for Group Feature Selection in Networked Data," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 182-198, January.
    12. Sorensen, Michael M., 2004. "New facets and a branch-and-cut algorithm for the weighted clique problem," European Journal of Operational Research, Elsevier, vol. 154(1), pages 57-70, April.
    13. 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.
    14. Lourenco, Lidia Lampreia & Pato, Margarida Vaz, 2007. "The effect of strengthened linear formulations on improving the lower bounds for the part families with precedence constraints problem," European Journal of Operational Research, Elsevier, vol. 183(1), pages 181-196, November.
    15. Borgwardt, S. & Schmiedl, F., 2014. "Threshold-based preprocessing for approximating the weighted dense k-subgraph problem," European Journal of Operational Research, Elsevier, vol. 234(3), pages 631-640.
    16. San Segundo, Pablo & Coniglio, Stefano & Furini, Fabio & Ljubić, Ivana, 2019. "A new branch-and-bound algorithm for the maximum edge-weighted clique problem," European Journal of Operational Research, Elsevier, vol. 278(1), pages 76-90.
    17. Juan Francisco Monge, 2017. "Cardinality constrained portfolio selection via factor models," Papers 1708.02424, arXiv.org.

    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. Sorensen, Michael M., 2004. "New facets and a branch-and-cut algorithm for the weighted clique problem," European Journal of Operational Research, Elsevier, vol. 154(1), pages 57-70, April.
    2. San Segundo, Pablo & Coniglio, Stefano & Furini, Fabio & Ljubić, Ivana, 2019. "A new branch-and-bound algorithm for the maximum edge-weighted clique problem," European Journal of Operational Research, Elsevier, vol. 278(1), pages 76-90.
    3. Sinha, Ankur & Das, Arka & Anand, Guneshwar & Jayaswal, Sachin, 2023. "A general purpose exact solution method for mixed integer concave minimization problems," European Journal of Operational Research, Elsevier, vol. 309(3), pages 977-992.
    4. Sinha, Ankur & Das, Arka & Anand, Guneshwar & Jayaswal, Sachin, 2021. "A General Purpose Exact Solution Method for Mixed Integer Concave Minimization Problems," IIMA Working Papers WP 2021-03-01, Indian Institute of Management Ahmedabad, Research and Publication Department.
    5. Seyedmohammadhossein Hosseinian & Dalila B. M. M. Fontes & Sergiy Butenko, 2020. "A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 747-762, July.
    6. Hunting, Marcel & Faigle, Ulrich & Kern, Walter, 2001. "A Lagrangian relaxation approach to the edge-weighted clique problem," European Journal of Operational Research, Elsevier, vol. 131(1), pages 119-131, May.
    7. Wu, Qinghua & Hao, Jin-Kao, 2015. "A review on algorithms for maximum clique problems," European Journal of Operational Research, Elsevier, vol. 242(3), pages 693-709.
    8. Seyedmohammadhossein Hosseinian & Dalila B. M. M. Fontes & Sergiy Butenko, 2018. "A nonconvex quadratic optimization approach to the maximum edge weight clique problem," Journal of Global Optimization, Springer, vol. 72(2), pages 219-240, October.
    9. Sinha, Ankur & Das, Arka & Anand, Guneshwar & Jayaswal, Sachin, 2021. "A General Purpose Exact Solution Method for Mixed Integer Concave Minimization Problems (revised as on 12/08/2021)," IIMA Working Papers WP 2021-03-01, Indian Institute of Management Ahmedabad, Research and Publication Department.
    10. Alberto Caprara & David Pisinger & Paolo Toth, 1999. "Exact Solution of the Quadratic Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 11(2), pages 125-137, May.
    11. Park, Kyungchul & Lee, Kyungsik & Park, Sungsoo, 1996. "An extended formulation approach to the edge-weighted maximal clique problem," European Journal of Operational Research, Elsevier, vol. 95(3), pages 671-682, December.
    12. W. David Pisinger & Anders Bo Rasmussen & Rune Sandvik, 2007. "Solution of Large Quadratic Knapsack Problems Through Aggressive Reduction," INFORMS Journal on Computing, INFORMS, vol. 19(2), pages 280-290, May.
    13. Lourenco, Lidia Lampreia & Pato, Margarida Vaz, 2007. "The effect of strengthened linear formulations on improving the lower bounds for the part families with precedence constraints problem," European Journal of Operational Research, Elsevier, vol. 183(1), pages 181-196, November.
    14. Yi Chu & Boxiao Liu & Shaowei Cai & Chuan Luo & Haihang You, 2020. "An efficient local search algorithm for solving maximum edge weight clique problem in large graphs," Journal of Combinatorial Optimization, Springer, vol. 39(4), pages 933-954, May.
    15. Michael M. Sørensen, 2004. "b-Tree Facets for the Simple Graph Partitioning Polytope," Journal of Combinatorial Optimization, Springer, vol. 8(2), pages 151-170, June.
    16. Carvalho, Filipa D. & Almeida, M. Teresa, 2011. "Upper bounds and heuristics for the 2-club problem," European Journal of Operational Research, Elsevier, vol. 210(3), pages 489-494, May.
    17. Zhou, Yi & Hao, Jin-Kao & Goëffon, Adrien, 2017. "PUSH: A generalized operator for the Maximum Vertex Weight Clique Problem," European Journal of Operational Research, Elsevier, vol. 257(1), pages 41-54.
    18. Richard J. Forrester & Warren P. Adams & Paul T. Hadavas, 2010. "Concise RLT forms of binary programs: A computational study of the quadratic knapsack problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 57(1), pages 1-12, February.
    19. Dilson Lucas Pereira & Abilio Lucena & Alexandre Salles da Cunha & Luidi Simonetti, 2022. "Exact Solution Algorithms for the Chordless Cycle Problem," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 1970-1986, July.

    More about this item

    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:123:y:2000:i:2:p:346-371. 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.