Computational study of separation algorithms for clique inequalities View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-05

AUTHORS

Francesca Marzi, Fabrizio Rossi, Stefano Smriglio

ABSTRACT

Clique inequalities appear in linear descriptions of many combinatorial optimisation problems. In general, they form an exponential family and, in addition, the associated separation problem is strongly NP-hard, being equivalent to a maximum weight clique problem. Therefore, most of the known (both exact and heuristic) separation procedures follow the decomposition scheme of a maximum clique algorithm. We introduce a new heuristic, aimed at constructing a collection of (violated) clique inequalities covering all the edges of the underlying graph. We present an extensive computational experience showing that this closely approximates the results of an exact separation oracle while being faster than standard heuristics. More... »

PAGES

1-15

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00500-019-03769-y

DOI

http://dx.doi.org/10.1007/s00500-019-03769-y

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1111751111


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of L'Aquila", 
          "id": "https://www.grid.ac/institutes/grid.158820.6", 
          "name": [
            "DISIM, University of L\u2019Aquila, Via Vetoio, Coppito, 67010, L\u2019Aquila, AQ, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Marzi", 
        "givenName": "Francesca", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of L'Aquila", 
          "id": "https://www.grid.ac/institutes/grid.158820.6", 
          "name": [
            "DISIM, University of L\u2019Aquila, Via Vetoio, Coppito, 67010, L\u2019Aquila, AQ, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rossi", 
        "givenName": "Fabrizio", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of L'Aquila", 
          "id": "https://www.grid.ac/institutes/grid.158820.6", 
          "name": [
            "DISIM, University of L\u2019Aquila, Via Vetoio, Coppito, 67010, L\u2019Aquila, AQ, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Smriglio", 
        "givenName": "Stefano", 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1057/jors.1992.71", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002544722", 
          "https://doi.org/10.1057/jors.1992.71"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02579273", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010850152", 
          "https://doi.org/10.1007/bf02579273"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02579273", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010850152", 
          "https://doi.org/10.1007/bf02579273"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0377-2217(99)00015-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022119318"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.dss.2008.10.009", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025633426"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0377-2217(00)00064-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026295535"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/pl00011381", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035954766", 
          "https://doi.org/10.1007/pl00011381"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02392825", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036532220", 
          "https://doi.org/10.1007/bf02392825"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10107-002-0335-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042660742", 
          "https://doi.org/10.1007/s10107-002-0335-9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1051732087", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-97881-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051732087", 
          "https://doi.org/10.1007/978-3-642-97881-4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-97881-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051732087", 
          "https://doi.org/10.1007/978-3-642-97881-4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01580121", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051792805", 
          "https://doi.org/10.1007/bf01580121"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01580121", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051792805", 
          "https://doi.org/10.1007/bf01580121"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0167-6377(90)90057-c", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052413170"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0167-6377(90)90057-c", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052413170"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4613-3279-4_18", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053233073", 
          "https://doi.org/10.1007/978-1-4613-3279-4_18"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0166-218x(99)00050-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053583242"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/mnsc.39.6.657", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064721077"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.3138/infor.48.1.053", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1071013419"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.3138/infor.52.4.185", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1071013520"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.dam.2017.02.005", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1084069174"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/trsc.2017.0750", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1090763606"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-66158-2_7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1091294293", 
          "https://doi.org/10.1007/978-3-319-66158-2_7"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2019-05", 
    "datePublishedReg": "2019-05-01", 
    "description": "Clique inequalities appear in linear descriptions of many combinatorial optimisation problems. In general, they form an exponential family and, in addition, the associated separation problem is strongly NP-hard, being equivalent to a maximum weight clique problem. Therefore, most of the known (both exact and heuristic) separation procedures follow the decomposition scheme of a maximum clique algorithm. We introduce a new heuristic, aimed at constructing a collection of (violated) clique inequalities covering all the edges of the underlying graph. We present an extensive computational experience showing that this closely approximates the results of an exact separation oracle while being faster than standard heuristics.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00500-019-03769-y", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.6850096", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": [
      {
        "id": "sg:journal.1050238", 
        "issn": [
          "1432-7643", 
          "1433-7479"
        ], 
        "name": "Soft Computing", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "9", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "23"
      }
    ], 
    "name": "Computational study of separation algorithms for clique inequalities", 
    "pagination": "1-15", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "4949ca6312bd173bdd5d013ed2ace323b910996f378d1cecac57d3c99c4e6b29"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00500-019-03769-y"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1111751111"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00500-019-03769-y", 
      "https://app.dimensions.ai/details/publication/pub.1111751111"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T13:55", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000371_0000000371/records_130811_00000006.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs00500-019-03769-y"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00500-019-03769-y'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00500-019-03769-y'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00500-019-03769-y'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00500-019-03769-y'


 

This table displays all metadata directly associated to this object as RDF triples.

142 TRIPLES      21 PREDICATES      47 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00500-019-03769-y schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nd9bc33515c834c1ab995b1db8d939c69
4 schema:citation sg:pub.10.1007/978-1-4613-3279-4_18
5 sg:pub.10.1007/978-3-319-66158-2_7
6 sg:pub.10.1007/978-3-642-97881-4
7 sg:pub.10.1007/bf01580121
8 sg:pub.10.1007/bf02392825
9 sg:pub.10.1007/bf02579273
10 sg:pub.10.1007/pl00011381
11 sg:pub.10.1007/s10107-002-0335-9
12 sg:pub.10.1057/jors.1992.71
13 https://app.dimensions.ai/details/publication/pub.1051732087
14 https://doi.org/10.1016/0167-6377(90)90057-c
15 https://doi.org/10.1016/j.dam.2017.02.005
16 https://doi.org/10.1016/j.dss.2008.10.009
17 https://doi.org/10.1016/s0166-218x(99)00050-5
18 https://doi.org/10.1016/s0377-2217(00)00064-3
19 https://doi.org/10.1016/s0377-2217(99)00015-6
20 https://doi.org/10.1287/mnsc.39.6.657
21 https://doi.org/10.1287/trsc.2017.0750
22 https://doi.org/10.3138/infor.48.1.053
23 https://doi.org/10.3138/infor.52.4.185
24 schema:datePublished 2019-05
25 schema:datePublishedReg 2019-05-01
26 schema:description Clique inequalities appear in linear descriptions of many combinatorial optimisation problems. In general, they form an exponential family and, in addition, the associated separation problem is strongly NP-hard, being equivalent to a maximum weight clique problem. Therefore, most of the known (both exact and heuristic) separation procedures follow the decomposition scheme of a maximum clique algorithm. We introduce a new heuristic, aimed at constructing a collection of (violated) clique inequalities covering all the edges of the underlying graph. We present an extensive computational experience showing that this closely approximates the results of an exact separation oracle while being faster than standard heuristics.
27 schema:genre research_article
28 schema:inLanguage en
29 schema:isAccessibleForFree false
30 schema:isPartOf N4b054647497c4ebf9f15d358e00a6dcc
31 Nd22d5b22311345f688365fffa887ca0e
32 sg:journal.1050238
33 schema:name Computational study of separation algorithms for clique inequalities
34 schema:pagination 1-15
35 schema:productId N00559e8538984bf38ed6d94ce638c628
36 N0c75f93c6ca04d17b419fd4a8b81c90a
37 N8b5b2ee5645e43c9844d2eea819f9a17
38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1111751111
39 https://doi.org/10.1007/s00500-019-03769-y
40 schema:sdDatePublished 2019-04-11T13:55
41 schema:sdLicense https://scigraph.springernature.com/explorer/license/
42 schema:sdPublisher N2aeb748362254d7ebf2dbc54b0b0ee2c
43 schema:url https://link.springer.com/10.1007%2Fs00500-019-03769-y
44 sgo:license sg:explorer/license/
45 sgo:sdDataset articles
46 rdf:type schema:ScholarlyArticle
47 N00559e8538984bf38ed6d94ce638c628 schema:name doi
48 schema:value 10.1007/s00500-019-03769-y
49 rdf:type schema:PropertyValue
50 N0ab3707f4cc44b3bbe0a2b503e5eb939 schema:affiliation https://www.grid.ac/institutes/grid.158820.6
51 schema:familyName Smriglio
52 schema:givenName Stefano
53 rdf:type schema:Person
54 N0c75f93c6ca04d17b419fd4a8b81c90a schema:name readcube_id
55 schema:value 4949ca6312bd173bdd5d013ed2ace323b910996f378d1cecac57d3c99c4e6b29
56 rdf:type schema:PropertyValue
57 N2aeb748362254d7ebf2dbc54b0b0ee2c schema:name Springer Nature - SN SciGraph project
58 rdf:type schema:Organization
59 N4b054647497c4ebf9f15d358e00a6dcc schema:issueNumber 9
60 rdf:type schema:PublicationIssue
61 N8b5b2ee5645e43c9844d2eea819f9a17 schema:name dimensions_id
62 schema:value pub.1111751111
63 rdf:type schema:PropertyValue
64 Nae281dd975eb402786c249a1a24dc0cb rdf:first Ndfd4d6eca2d9425398379c32b491684e
65 rdf:rest Nde4728d648d54153aa814e3b35a3811d
66 Nd22d5b22311345f688365fffa887ca0e schema:volumeNumber 23
67 rdf:type schema:PublicationVolume
68 Nd9bc33515c834c1ab995b1db8d939c69 rdf:first Necdd8690e35a4101b185b45315c835ca
69 rdf:rest Nae281dd975eb402786c249a1a24dc0cb
70 Nde4728d648d54153aa814e3b35a3811d rdf:first N0ab3707f4cc44b3bbe0a2b503e5eb939
71 rdf:rest rdf:nil
72 Ndfd4d6eca2d9425398379c32b491684e schema:affiliation https://www.grid.ac/institutes/grid.158820.6
73 schema:familyName Rossi
74 schema:givenName Fabrizio
75 rdf:type schema:Person
76 Necdd8690e35a4101b185b45315c835ca schema:affiliation https://www.grid.ac/institutes/grid.158820.6
77 schema:familyName Marzi
78 schema:givenName Francesca
79 rdf:type schema:Person
80 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
81 schema:name Information and Computing Sciences
82 rdf:type schema:DefinedTerm
83 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
84 schema:name Computation Theory and Mathematics
85 rdf:type schema:DefinedTerm
86 sg:grant.6850096 http://pending.schema.org/fundedItem sg:pub.10.1007/s00500-019-03769-y
87 rdf:type schema:MonetaryGrant
88 sg:journal.1050238 schema:issn 1432-7643
89 1433-7479
90 schema:name Soft Computing
91 rdf:type schema:Periodical
92 sg:pub.10.1007/978-1-4613-3279-4_18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053233073
93 https://doi.org/10.1007/978-1-4613-3279-4_18
94 rdf:type schema:CreativeWork
95 sg:pub.10.1007/978-3-319-66158-2_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091294293
96 https://doi.org/10.1007/978-3-319-66158-2_7
97 rdf:type schema:CreativeWork
98 sg:pub.10.1007/978-3-642-97881-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051732087
99 https://doi.org/10.1007/978-3-642-97881-4
100 rdf:type schema:CreativeWork
101 sg:pub.10.1007/bf01580121 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051792805
102 https://doi.org/10.1007/bf01580121
103 rdf:type schema:CreativeWork
104 sg:pub.10.1007/bf02392825 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036532220
105 https://doi.org/10.1007/bf02392825
106 rdf:type schema:CreativeWork
107 sg:pub.10.1007/bf02579273 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010850152
108 https://doi.org/10.1007/bf02579273
109 rdf:type schema:CreativeWork
110 sg:pub.10.1007/pl00011381 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035954766
111 https://doi.org/10.1007/pl00011381
112 rdf:type schema:CreativeWork
113 sg:pub.10.1007/s10107-002-0335-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042660742
114 https://doi.org/10.1007/s10107-002-0335-9
115 rdf:type schema:CreativeWork
116 sg:pub.10.1057/jors.1992.71 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002544722
117 https://doi.org/10.1057/jors.1992.71
118 rdf:type schema:CreativeWork
119 https://app.dimensions.ai/details/publication/pub.1051732087 schema:CreativeWork
120 https://doi.org/10.1016/0167-6377(90)90057-c schema:sameAs https://app.dimensions.ai/details/publication/pub.1052413170
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1016/j.dam.2017.02.005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1084069174
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1016/j.dss.2008.10.009 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025633426
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1016/s0166-218x(99)00050-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053583242
127 rdf:type schema:CreativeWork
128 https://doi.org/10.1016/s0377-2217(00)00064-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026295535
129 rdf:type schema:CreativeWork
130 https://doi.org/10.1016/s0377-2217(99)00015-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022119318
131 rdf:type schema:CreativeWork
132 https://doi.org/10.1287/mnsc.39.6.657 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064721077
133 rdf:type schema:CreativeWork
134 https://doi.org/10.1287/trsc.2017.0750 schema:sameAs https://app.dimensions.ai/details/publication/pub.1090763606
135 rdf:type schema:CreativeWork
136 https://doi.org/10.3138/infor.48.1.053 schema:sameAs https://app.dimensions.ai/details/publication/pub.1071013419
137 rdf:type schema:CreativeWork
138 https://doi.org/10.3138/infor.52.4.185 schema:sameAs https://app.dimensions.ai/details/publication/pub.1071013520
139 rdf:type schema:CreativeWork
140 https://www.grid.ac/institutes/grid.158820.6 schema:alternateName University of L'Aquila
141 schema:name DISIM, University of L’Aquila, Via Vetoio, Coppito, 67010, L’Aquila, AQ, Italy
142 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...