Home > Research > Publications & Outputs > The stable set problem

Research

Associated organisational unit

Electronic data

  • nodal

    Rights statement: This is the author’s version of a work that was accepted for publication in Computers and Operations Research. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Computers and Operations Research, 123, 2020 DOI: 10.1016/j.cor.2020.105024

    Accepted author manuscript, 915 KB, PDF document

    Available under license: CC BY-NC-ND: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License

Links

Text available via DOI:

Keywords

View graph of relations

The stable set problem: clique and nodal inequalities revisited

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

The stable set problem: clique and nodal inequalities revisited. / Letchford, Adam; Rossi, Fabrizio; Smriglio, Stefano.
In: Computers and Operations Research, Vol. 123, 105024, 30.11.2020.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Letchford, A, Rossi, F & Smriglio, S 2020, 'The stable set problem: clique and nodal inequalities revisited', Computers and Operations Research, vol. 123, 105024. https://doi.org/10.1016/j.cor.2020.105024

APA

Letchford, A., Rossi, F., & Smriglio, S. (2020). The stable set problem: clique and nodal inequalities revisited. Computers and Operations Research, 123, Article 105024. https://doi.org/10.1016/j.cor.2020.105024

Vancouver

Letchford A, Rossi F, Smriglio S. The stable set problem: clique and nodal inequalities revisited. Computers and Operations Research. 2020 Nov 30;123:105024. Epub 2020 Jun 17. doi: 10.1016/j.cor.2020.105024

Author

Letchford, Adam ; Rossi, Fabrizio ; Smriglio, Stefano. / The stable set problem : clique and nodal inequalities revisited. In: Computers and Operations Research. 2020 ; Vol. 123.

Bibtex

@article{761901ae0ff44661a394297e4eca0e67,
title = "The stable set problem: clique and nodal inequalities revisited",
abstract = "The stable set problem is a fundamental combinatorial optimisation problem, that is known to be very difficult in both theory and practice. Some of the solution algorithms in the literature are based on 0-1 linear programming formulations. We examine an entire family of such formulations, based on so-called clique and nodal inequalities. As well as proving some theoretical results, we conduct extensive computational experiments. This enables us to derive guidelines on how to choose the right formulation for a given instance.",
keywords = "combinatorial optimisation, integer programming",
author = "Adam Letchford and Fabrizio Rossi and Stefano Smriglio",
note = "This is the author{\textquoteright}s version of a work that was accepted for publication in Computers and Operations Research. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Computers and Operations Research, 123, 2020 DOI: 10.1016/j.cor.2020.105024",
year = "2020",
month = nov,
day = "30",
doi = "10.1016/j.cor.2020.105024",
language = "English",
volume = "123",
journal = "Computers and Operations Research",
issn = "0305-0548",
publisher = "Elsevier Ltd",

}

RIS

TY - JOUR

T1 - The stable set problem

T2 - clique and nodal inequalities revisited

AU - Letchford, Adam

AU - Rossi, Fabrizio

AU - Smriglio, Stefano

N1 - This is the author’s version of a work that was accepted for publication in Computers and Operations Research. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Computers and Operations Research, 123, 2020 DOI: 10.1016/j.cor.2020.105024

PY - 2020/11/30

Y1 - 2020/11/30

N2 - The stable set problem is a fundamental combinatorial optimisation problem, that is known to be very difficult in both theory and practice. Some of the solution algorithms in the literature are based on 0-1 linear programming formulations. We examine an entire family of such formulations, based on so-called clique and nodal inequalities. As well as proving some theoretical results, we conduct extensive computational experiments. This enables us to derive guidelines on how to choose the right formulation for a given instance.

AB - The stable set problem is a fundamental combinatorial optimisation problem, that is known to be very difficult in both theory and practice. Some of the solution algorithms in the literature are based on 0-1 linear programming formulations. We examine an entire family of such formulations, based on so-called clique and nodal inequalities. As well as proving some theoretical results, we conduct extensive computational experiments. This enables us to derive guidelines on how to choose the right formulation for a given instance.

KW - combinatorial optimisation

KW - integer programming

U2 - 10.1016/j.cor.2020.105024

DO - 10.1016/j.cor.2020.105024

M3 - Journal article

VL - 123

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

M1 - 105024

ER -