On the m-clique free interval subgraphs polytope: polyhedral analysis and applications

Mohammed-Albarra Hassan (), Imed Kacem (), Sébastien Martin () and Izzeldin M. Osman ()
Additional contact information
Mohammed-Albarra Hassan: Université de Lorraine
Imed Kacem: Université de Lorraine
Sébastien Martin: Université de Lorraine
Izzeldin M. Osman: Sudan University of Science and Technology

Journal of Combinatorial Optimization, 2018, vol. 36, issue 3, No 19, 1074-1101

Abstract: Abstract In this paper we study the m-clique free interval subgraphs. We investigate the facial structure of the polytope defined as the convex hull of the incidence vectors associated with these subgraphs. We also present some facet-defining inequalities to strengthen the associated linear relaxation. As an application, the generalized open-shop problem with disjunctive constraints (GOSDC) is considered. Indeed, by a projection on a set of variables, the m-clique free interval subgraphs represent the solution of an integer linear program solving the GOSDC presented in this paper. Moreover, we propose exact and heuristic separation algorithms, which are exploited into a Branch-and-cut algorithm for solving the GOSDC. Finally, we present and discuss some computational results.

Keywords: Interval graph; Polyhedral analysis; Branch-and-cut; Clique (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-0291-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:36:y:2018:i:3:d:10.1007_s10878-018-0291-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-018-0291-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().