An implementation of Karmarkar's algorithm for linear programming View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1989-05

AUTHORS

Ilan Adler, Mauricio G. C. Resende, Geraldo Veiga, Narendra Karmarkar

ABSTRACT

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. More... »

PAGES

297-335

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf01587095

DOI

http://dx.doi.org/10.1007/bf01587095

DIMENSIONS

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


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/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

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/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

Subject Predicate Object
1 sg:pub.10.1007/bf01587095 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N48812153c2b9419893c8fc88041fe033
4 schema:citation sg:pub.10.1007/bf01589349
5 sg:pub.10.1007/bf01840454
6 sg:pub.10.1007/bf01840455
7 sg:pub.10.1007/bf02579150
8 sg:pub.10.1007/bf02592024
9 sg:pub.10.1007/bf02592025
10 schema:datePublished 1989-05
11 schema:datePublishedReg 1989-05-01
12 schema: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.
13 schema:genre article
14 schema:isAccessibleForFree false
15 schema:isPartOf N37cc5359ea694f0687428b77a32d4f52
16 Nd62e26db551d4c558fd7a990dd4754b6
17 sg:journal.1047630
18 schema:keywords Karmarkar's algorithm
19 advantages
20 affine
21 algorithm
22 approximation
23 code
24 column
25 computation
26 computational advantages
27 continuous trajectories
28 continuous version
29 dense columns
30 direction
31 dual affine
32 family
33 family of algorithms
34 form
35 implementation
36 implementation issues
37 improvement
38 inequality form
39 inexact computation
40 issues
41 linear program
42 linear programming
43 linear programming problem
44 order approximation
45 paper
46 problem
47 program
48 programming
49 programming problem
50 second-order approximation
51 significant computational advantages
52 standard linear programming problem
53 trajectories
54 treatment
55 variants
56 version
57 schema:name An implementation of Karmarkar's algorithm for linear programming
58 schema:pagination 297-335
59 schema:productId N42fcac36d3664231aa6285687fd9889e
60 N4b8070fac86243d58c3a61396c8c4a87
61 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014973872
62 https://doi.org/10.1007/bf01587095
63 schema:sdDatePublished 2022-08-04T16:50
64 schema:sdLicense https://scigraph.springernature.com/explorer/license/
65 schema:sdPublisher N607938c8c25643549ec67b49a67d1554
66 schema:url https://doi.org/10.1007/bf01587095
67 sgo:license sg:explorer/license/
68 sgo:sdDataset articles
69 rdf:type schema:ScholarlyArticle
70 N0430283eb5234e6aa6fa06071e6e224f rdf:first sg:person.016062445136.04
71 rdf:rest Nf858f84c909748fca5892bb99b20b9fc
72 N37cc5359ea694f0687428b77a32d4f52 schema:issueNumber 1-3
73 rdf:type schema:PublicationIssue
74 N42fcac36d3664231aa6285687fd9889e schema:name doi
75 schema:value 10.1007/bf01587095
76 rdf:type schema:PropertyValue
77 N48812153c2b9419893c8fc88041fe033 rdf:first sg:person.014157407520.34
78 rdf:rest N6819f1bbe52e490582115f822c021cca
79 N4b8070fac86243d58c3a61396c8c4a87 schema:name dimensions_id
80 schema:value pub.1014973872
81 rdf:type schema:PropertyValue
82 N607938c8c25643549ec67b49a67d1554 schema:name Springer Nature - SN SciGraph project
83 rdf:type schema:Organization
84 N6819f1bbe52e490582115f822c021cca rdf:first sg:person.014552653433.70
85 rdf:rest N0430283eb5234e6aa6fa06071e6e224f
86 Nd62e26db551d4c558fd7a990dd4754b6 schema:volumeNumber 44
87 rdf:type schema:PublicationVolume
88 Nf858f84c909748fca5892bb99b20b9fc rdf:first sg:person.012767743421.72
89 rdf:rest rdf:nil
90 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
91 schema:name Information and Computing Sciences
92 rdf:type schema:DefinedTerm
93 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
94 schema:name Computation Theory and Mathematics
95 rdf:type schema:DefinedTerm
96 sg:journal.1047630 schema:issn 0025-5610
97 1436-4646
98 schema:name Mathematical Programming
99 schema:publisher Springer Nature
100 rdf:type schema:Periodical
101 sg:person.012767743421.72 schema:affiliation grid-institutes:grid.469490.6
102 schema:familyName Karmarkar
103 schema:givenName Narendra
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012767743421.72
105 rdf:type schema:Person
106 sg:person.014157407520.34 schema:affiliation grid-institutes:grid.47840.3f
107 schema:familyName Adler
108 schema:givenName Ilan
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014157407520.34
110 rdf:type schema:Person
111 sg:person.014552653433.70 schema:affiliation grid-institutes:grid.47840.3f
112 schema:familyName Resende
113 schema:givenName Mauricio G. C.
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014552653433.70
115 rdf:type schema:Person
116 sg:person.016062445136.04 schema:affiliation grid-institutes:grid.47840.3f
117 schema:familyName Veiga
118 schema:givenName Geraldo
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016062445136.04
120 rdf:type schema:Person
121 sg:pub.10.1007/bf01589349 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043123060
122 https://doi.org/10.1007/bf01589349
123 rdf:type schema:CreativeWork
124 sg:pub.10.1007/bf01840454 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045683978
125 https://doi.org/10.1007/bf01840454
126 rdf:type schema:CreativeWork
127 sg:pub.10.1007/bf01840455 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038753043
128 https://doi.org/10.1007/bf01840455
129 rdf:type schema:CreativeWork
130 sg:pub.10.1007/bf02579150 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035950209
131 https://doi.org/10.1007/bf02579150
132 rdf:type schema:CreativeWork
133 sg:pub.10.1007/bf02592024 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046429529
134 https://doi.org/10.1007/bf02592024
135 rdf:type schema:CreativeWork
136 sg:pub.10.1007/bf02592025 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018061985
137 https://doi.org/10.1007/bf02592025
138 rdf:type schema:CreativeWork
139 grid-institutes:grid.469490.6 schema:alternateName AT&T Bell Laboratories, 07974, Murray Hill, NJ, USA
140 schema:name AT&T Bell Laboratories, 07974, Murray Hill, NJ, USA
141 rdf:type schema:Organization
142 grid-institutes:grid.47840.3f schema:alternateName Department of Industrial Engineering and Operations Research, University of California, 94720, Berkeley, CA, USA
143 schema:name Department of Industrial Engineering and Operations Research, University of California, 94720, Berkeley, CA, USA
144 rdf:type schema:Organization
 




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


...