Ontology type: schema:ScholarlyArticle
2019-05
AUTHORSFrancesca Marzi, Fabrizio Rossi, Stefano Smriglio
ABSTRACTClique 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... »
PAGES1-15
http://scigraph.springernature.com/pub.10.1007/s00500-019-03769-y
DOIhttp://dx.doi.org/10.1007/s00500-019-03769-y
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1111751111
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
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