Ontology type: schema:ScholarlyArticle
1989-05
AUTHORSIlan Adler, Mauricio G. C. Resende, Geraldo Veiga, Narendra Karmarkar
ABSTRACTThis paper describes the implementation of power series dual affine scaling variants of Karmarkar's algorithm for linear programming. Based on a continuous version of Karmarkar's algorithm, two variants resulting from first and second order approximations of the continuous trajectory are implemented and tested. Linear programs are expressed in an inequality form, which allows for the inexact computation of the algorithm's direction of improvement, resulting in a significant computational advantage. Implementation issues particular to this family of algorithms, such as treatment of dense columns, are discussed. The code is tested on several standard linear programming problems and compares favorably with the simplex codeMinos 4.0. More... »
PAGES297-335
http://scigraph.springernature.com/pub.10.1007/bf01587095
DOIhttp://dx.doi.org/10.1007/bf01587095
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1014973872
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/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
},
{
"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"
}
],
"author": [
{
"affiliation": {
"alternateName": "Department of Industrial Engineering and Operations Research, University of California, 94720, Berkeley, CA, USA",
"id": "http://www.grid.ac/institutes/grid.47840.3f",
"name": [
"Department of Industrial Engineering and Operations Research, University of California, 94720, Berkeley, CA, USA"
],
"type": "Organization"
},
"familyName": "Adler",
"givenName": "Ilan",
"id": "sg:person.014157407520.34",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014157407520.34"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Industrial Engineering and Operations Research, University of California, 94720, Berkeley, CA, USA",
"id": "http://www.grid.ac/institutes/grid.47840.3f",
"name": [
"Department of Industrial Engineering and Operations Research, University of California, 94720, Berkeley, CA, USA"
],
"type": "Organization"
},
"familyName": "Resende",
"givenName": "Mauricio G. C.",
"id": "sg:person.014552653433.70",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014552653433.70"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Industrial Engineering and Operations Research, University of California, 94720, Berkeley, CA, USA",
"id": "http://www.grid.ac/institutes/grid.47840.3f",
"name": [
"Department of Industrial Engineering and Operations Research, University of California, 94720, Berkeley, CA, USA"
],
"type": "Organization"
},
"familyName": "Veiga",
"givenName": "Geraldo",
"id": "sg:person.016062445136.04",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016062445136.04"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "AT&T Bell Laboratories, 07974, Murray Hill, NJ, USA",
"id": "http://www.grid.ac/institutes/grid.469490.6",
"name": [
"AT&T Bell Laboratories, 07974, Murray Hill, NJ, USA"
],
"type": "Organization"
},
"familyName": "Karmarkar",
"givenName": "Narendra",
"id": "sg:person.012767743421.72",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012767743421.72"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/bf02592024",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1046429529",
"https://doi.org/10.1007/bf02592024"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02592025",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1018061985",
"https://doi.org/10.1007/bf02592025"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01589349",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1043123060",
"https://doi.org/10.1007/bf01589349"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01840454",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1045683978",
"https://doi.org/10.1007/bf01840454"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02579150",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1035950209",
"https://doi.org/10.1007/bf02579150"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01840455",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1038753043",
"https://doi.org/10.1007/bf01840455"
],
"type": "CreativeWork"
}
],
"datePublished": "1989-05",
"datePublishedReg": "1989-05-01",
"description": "This paper describes the implementation of power series dual affine scaling variants of Karmarkar's algorithm for linear programming. Based on a continuous version of Karmarkar's algorithm, two variants resulting from first and second order approximations of the continuous trajectory are implemented and tested. Linear programs are expressed in an inequality form, which allows for the inexact computation of the algorithm's direction of improvement, resulting in a significant computational advantage. Implementation issues particular to this family of algorithms, such as treatment of dense columns, are discussed. The code is tested on several standard linear programming problems and compares favorably with the simplex codeMinos 4.0.",
"genre": "article",
"id": "sg:pub.10.1007/bf01587095",
"isAccessibleForFree": false,
"isPartOf": [
{
"id": "sg:journal.1047630",
"issn": [
"0025-5610",
"1436-4646"
],
"name": "Mathematical Programming",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "1-3",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
"volumeNumber": "44"
}
],
"keywords": [
"family of algorithms",
"linear programming",
"significant computational advantages",
"Karmarkar's algorithm",
"standard linear programming problem",
"implementation issues",
"linear programming problem",
"algorithm",
"inexact computation",
"computational advantages",
"programming problem",
"linear program",
"continuous trajectories",
"programming",
"implementation",
"continuous version",
"dual affine",
"computation",
"code",
"issues",
"version",
"advantages",
"trajectories",
"affine",
"variants",
"direction",
"improvement",
"dense columns",
"inequality form",
"program",
"approximation",
"form",
"order approximation",
"second-order approximation",
"family",
"column",
"treatment",
"paper",
"problem"
],
"name": "An implementation of Karmarkar's algorithm for linear programming",
"pagination": "297-335",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1014973872"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/bf01587095"
]
}
],
"sameAs": [
"https://doi.org/10.1007/bf01587095",
"https://app.dimensions.ai/details/publication/pub.1014973872"
],
"sdDataset": "articles",
"sdDatePublished": "2022-08-04T16:50",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/article/article_182.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/bf01587095"
}
]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/bf01587095'
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/bf01587095'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01587095'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf01587095'
This table displays all metadata directly associated to this object as RDF triples.
144 TRIPLES
21 PREDICATES
70 URIs
56 LITERALS
6 BLANK NODES