Norm bounds and underestimators for unconstrained polynomial integer minimization View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2018-02

AUTHORS

Sönke Behrends, Ruth Hübner, Anita Schöbel

ABSTRACT

We consider the problem of minimizing a polynomial function over the integer lattice. Though impossible in general, we use a known sufficient condition for the existence of continuous minimizers to guarantee the existence of integer minimizers as well. In case this condition holds, we use sos programming to compute the radius of a p-norm ball which contains all integer minimizers. We prove that this radius is smaller than the radius known from the literature. Our numerical results show that the number of potentially optimal solutions is reduced by several orders of magnitude. Furthermore, we derive a new class of underestimators of the polynomial function. Using a Stellensatz from real algebraic geometry and again sos programming, we optimize over this class to get a strong lower bound on the integer minimum. Also our lower bounds are evaluated experimentally. They show a good performance, in particular within a branch and bound framework. More... »

PAGES

73-107

References to SciGraph publications

  • 2010. 50 Years of Integer Programming 1958-2008, From the Early Years to the State-of-the-Art in NONE
  • 2012. Mixed Integer Nonlinear Programming in NONE
  • 1997-07. Modifiedr-algorithm to find the global minimum of polynomial functions in CYBERNETICS AND SYSTEMS ANALYSIS
  • 2006-05. Minimizing Polynomials via Sum of Squares over the Gradient Ideal in MATHEMATICAL PROGRAMMING
  • 1960-06. L’algebre de Boole et ses applications en recherche operationnelle in TRABAJOS DE ESTADÍSTICA
  • 2000-02. Integer Optimization on Convex Semialgebraic Sets in DISCRETE & COMPUTATIONAL GEOMETRY
  • 2009. Sums of Squares, Moment Matrices and Optimization Over Polynomials in EMERGING APPLICATIONS OF ALGEBRAIC GEOMETRY
  • 2012-04. Sum of squares methods for minimizing polynomial forms over spheres and hypersurfaces in FRONTIERS OF MATHEMATICS IN CHINA
  • 2012. Handbook on Semidefinite, Conic and Polynomial Optimization in NONE
  • 2000. Handbook of Semidefinite Programming, Theory, Algorithms, and Applications in NONE
  • 2007. Ideals, Varieties, and Algorithms, An Introduction to Computational Algebraic Geometry and Commutative Algebra in NONE
  • 2005. Detecting Global Optimality and Extracting Solutions in GloptiPoly in POSITIVE POLYNOMIALS IN CONTROL
  • 2000. Squared Functional Systems and Optimization Problems in HIGH PERFORMANCE OPTIMIZATION
  • 2009-11-06. Nonlinear Integer Programming in 50 YEARS OF INTEGER PROGRAMMING 1958-2008
  • 1987-11. Class of global minimum bounds of polynomial functions in CYBERNETICS AND SYSTEMS ANALYSIS
  • 2014. Box-Constrained Mixed-Integer Polynomial Optimization Using Separable Underestimators in INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00186-017-0608-y

    DOI

    http://dx.doi.org/10.1007/s00186-017-0608-y

    DIMENSIONS

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


    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/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of G\u00f6ttingen", 
              "id": "https://www.grid.ac/institutes/grid.7450.6", 
              "name": [
                "Institute for Numerical and Applied Mathematics, University of G\u00f6ttingen, Lotzestr. 16\u201318, 37083, G\u00f6ttingen, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Behrends", 
            "givenName": "S\u00f6nke", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of G\u00f6ttingen", 
              "id": "https://www.grid.ac/institutes/grid.7450.6", 
              "name": [
                "Institute for Numerical and Applied Mathematics, University of G\u00f6ttingen, Lotzestr. 16\u201318, 37083, G\u00f6ttingen, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "H\u00fcbner", 
            "givenName": "Ruth", 
            "id": "sg:person.013177467112.78", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013177467112.78"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of G\u00f6ttingen", 
              "id": "https://www.grid.ac/institutes/grid.7450.6", 
              "name": [
                "Institute for Numerical and Applied Mathematics, University of G\u00f6ttingen, Lotzestr. 16\u201318, 37083, G\u00f6ttingen, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Sch\u00f6bel", 
            "givenName": "Anita", 
            "id": "sg:person.016135602505.17", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016135602505.17"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-0-387-09686-5_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005145396", 
              "https://doi.org/10.1007/978-0-387-09686-5_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4614-0769-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010074517", 
              "https://doi.org/10.1007/978-1-4614-0769-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4614-0769-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010074517", 
              "https://doi.org/10.1007/978-1-4614-0769-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/10556789908805762", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010748736"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4614-1927-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010863518", 
              "https://doi.org/10.1007/978-1-4614-1927-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4614-1927-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010863518", 
              "https://doi.org/10.1007/978-1-4614-1927-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10107-005-0672-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012083193", 
              "https://doi.org/10.1007/s10107-005-0672-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10107-005-0672-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012083193", 
              "https://doi.org/10.1007/s10107-005-0672-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10107-005-0672-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012083193", 
              "https://doi.org/10.1007/s10107-005-0672-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-68279-0_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013813721", 
              "https://doi.org/10.1007/978-3-540-68279-0_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-68279-0_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013813721", 
              "https://doi.org/10.1007/978-3-540-68279-0_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4615-4381-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014628929", 
              "https://doi.org/10.1007/978-1-4615-4381-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4615-4381-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014628929", 
              "https://doi.org/10.1007/978-1-4615-4381-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4757-3216-0_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014742978", 
              "https://doi.org/10.1007/978-1-4757-3216-0_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/10997703_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015075880", 
              "https://doi.org/10.1007/10997703_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf03006558", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023808751", 
              "https://doi.org/10.1007/bf03006558"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://app.dimensions.ai/details/publication/pub.1027557578", 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-0-387-35651-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027557578", 
              "https://doi.org/10.1007/978-0-387-35651-8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-0-387-35651-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027557578", 
              "https://doi.org/10.1007/978-0-387-35651-8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-68279-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030141941", 
              "https://doi.org/10.1007/978-3-540-68279-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-68279-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030141941", 
              "https://doi.org/10.1007/978-3-540-68279-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02733104", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037675001", 
              "https://doi.org/10.1007/bf02733104"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02733104", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037675001", 
              "https://doi.org/10.1007/bf02733104"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0166-218x(01)00341-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039547005"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jco.2006.07.002", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039598025"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.disopt.2012.11.003", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049049320"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-07557-0_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049086537", 
              "https://doi.org/10.1007/978-3-319-07557-0_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/10556789908805765", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049285622"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s11464-012-0187-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049425767", 
              "https://doi.org/10.1007/s11464-012-0187-4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/pl00009496", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051310884", 
              "https://doi.org/10.1007/pl00009496"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/pl00009496", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051310884", 
              "https://doi.org/10.1007/pl00009496"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01070233", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052605099", 
              "https://doi.org/10.1007/bf01070233"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01070233", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052605099", 
              "https://doi.org/10.1007/bf01070233"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/050646500", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062846773"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/130929187", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062871035"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s1052623400366802", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062883193"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s1052623403431779", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062883381"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/mnsc.31.12.1533", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064719979"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/moor.1050.0169", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064722829"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/opre.15.6.1171", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064727177"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/opre.21.1.221", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064728285"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.4153/cjm-2009-010-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1072268577"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.4153/cmb-2003-054-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1072272513"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/cdc.2011.6160623", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094297642"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/dimacs/060", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1097022580"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/surv/146", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098734667"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2018-02", 
        "datePublishedReg": "2018-02-01", 
        "description": "We consider the problem of minimizing a polynomial function over the integer lattice. Though impossible in general, we use a known sufficient condition for the existence of continuous minimizers to guarantee the existence of integer minimizers as well. In case this condition holds, we use sos programming to compute the radius of a p-norm ball which contains all integer minimizers. We prove that this radius is smaller than the radius known from the literature. Our numerical results show that the number of potentially optimal solutions is reduced by several orders of magnitude. Furthermore, we derive a new class of underestimators of the polynomial function. Using a Stellensatz from real algebraic geometry and again sos programming, we optimize over this class to get a strong lower bound on the integer minimum. Also our lower bounds are evaluated experimentally. They show a good performance, in particular within a branch and bound framework.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00186-017-0608-y", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1053187", 
            "issn": [
              "1432-2994", 
              "1432-5217"
            ], 
            "name": "Mathematical Methods of Operations Research", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "87"
          }
        ], 
        "name": "Norm bounds and underestimators for unconstrained polynomial integer minimization", 
        "pagination": "73-107", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "85a034101d500061b7b59c521f9ae140dd9b1c37987e673b8d8629194194afbd"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00186-017-0608-y"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1091906408"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00186-017-0608-y", 
          "https://app.dimensions.ai/details/publication/pub.1091906408"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T00:30", 
        "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/0000000001_0000000264/records_8695_00000601.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007%2Fs00186-017-0608-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/s00186-017-0608-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/s00186-017-0608-y'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00186-017-0608-y'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00186-017-0608-y'


     

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

    194 TRIPLES      21 PREDICATES      62 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00186-017-0608-y schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author N01f6a2613c1e48518db4a9a04792aa3a
    4 schema:citation sg:pub.10.1007/10997703_15
    5 sg:pub.10.1007/978-0-387-09686-5_7
    6 sg:pub.10.1007/978-0-387-35651-8
    7 sg:pub.10.1007/978-1-4614-0769-0
    8 sg:pub.10.1007/978-1-4614-1927-3
    9 sg:pub.10.1007/978-1-4615-4381-7
    10 sg:pub.10.1007/978-1-4757-3216-0_17
    11 sg:pub.10.1007/978-3-319-07557-0_17
    12 sg:pub.10.1007/978-3-540-68279-0
    13 sg:pub.10.1007/978-3-540-68279-0_15
    14 sg:pub.10.1007/bf01070233
    15 sg:pub.10.1007/bf02733104
    16 sg:pub.10.1007/bf03006558
    17 sg:pub.10.1007/pl00009496
    18 sg:pub.10.1007/s10107-005-0672-6
    19 sg:pub.10.1007/s11464-012-0187-4
    20 https://app.dimensions.ai/details/publication/pub.1027557578
    21 https://doi.org/10.1016/j.disopt.2012.11.003
    22 https://doi.org/10.1016/j.jco.2006.07.002
    23 https://doi.org/10.1016/s0166-218x(01)00341-9
    24 https://doi.org/10.1080/10556789908805762
    25 https://doi.org/10.1080/10556789908805765
    26 https://doi.org/10.1090/dimacs/060
    27 https://doi.org/10.1090/surv/146
    28 https://doi.org/10.1109/cdc.2011.6160623
    29 https://doi.org/10.1137/050646500
    30 https://doi.org/10.1137/130929187
    31 https://doi.org/10.1137/s1052623400366802
    32 https://doi.org/10.1137/s1052623403431779
    33 https://doi.org/10.1287/mnsc.31.12.1533
    34 https://doi.org/10.1287/moor.1050.0169
    35 https://doi.org/10.1287/opre.15.6.1171
    36 https://doi.org/10.1287/opre.21.1.221
    37 https://doi.org/10.4153/cjm-2009-010-4
    38 https://doi.org/10.4153/cmb-2003-054-7
    39 schema:datePublished 2018-02
    40 schema:datePublishedReg 2018-02-01
    41 schema:description We consider the problem of minimizing a polynomial function over the integer lattice. Though impossible in general, we use a known sufficient condition for the existence of continuous minimizers to guarantee the existence of integer minimizers as well. In case this condition holds, we use sos programming to compute the radius of a p-norm ball which contains all integer minimizers. We prove that this radius is smaller than the radius known from the literature. Our numerical results show that the number of potentially optimal solutions is reduced by several orders of magnitude. Furthermore, we derive a new class of underestimators of the polynomial function. Using a Stellensatz from real algebraic geometry and again sos programming, we optimize over this class to get a strong lower bound on the integer minimum. Also our lower bounds are evaluated experimentally. They show a good performance, in particular within a branch and bound framework.
    42 schema:genre research_article
    43 schema:inLanguage en
    44 schema:isAccessibleForFree true
    45 schema:isPartOf N08cb3cfcb53a4e3ab7b891f099cb1f09
    46 Nb4f404c8d08449e797a12072ba6da072
    47 sg:journal.1053187
    48 schema:name Norm bounds and underestimators for unconstrained polynomial integer minimization
    49 schema:pagination 73-107
    50 schema:productId N16fdd3e4a8a94ba0b95f1c22d15d2390
    51 N534765f927414d7fb940f229447b1d75
    52 Ne5719f789b854f3489e27cdc3980cc75
    53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091906408
    54 https://doi.org/10.1007/s00186-017-0608-y
    55 schema:sdDatePublished 2019-04-11T00:30
    56 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    57 schema:sdPublisher Nb887789178f64683934cd0de0139b08e
    58 schema:url http://link.springer.com/10.1007%2Fs00186-017-0608-y
    59 sgo:license sg:explorer/license/
    60 sgo:sdDataset articles
    61 rdf:type schema:ScholarlyArticle
    62 N01f6a2613c1e48518db4a9a04792aa3a rdf:first N3d8c277819f54f5387dcbae64fa1cd34
    63 rdf:rest Ne54614b8b14e44e5b7938302c9799b94
    64 N08cb3cfcb53a4e3ab7b891f099cb1f09 schema:volumeNumber 87
    65 rdf:type schema:PublicationVolume
    66 N16fdd3e4a8a94ba0b95f1c22d15d2390 schema:name readcube_id
    67 schema:value 85a034101d500061b7b59c521f9ae140dd9b1c37987e673b8d8629194194afbd
    68 rdf:type schema:PropertyValue
    69 N3d8c277819f54f5387dcbae64fa1cd34 schema:affiliation https://www.grid.ac/institutes/grid.7450.6
    70 schema:familyName Behrends
    71 schema:givenName Sönke
    72 rdf:type schema:Person
    73 N534765f927414d7fb940f229447b1d75 schema:name dimensions_id
    74 schema:value pub.1091906408
    75 rdf:type schema:PropertyValue
    76 N8afebe95c7a34ce9869dcb68af7274c5 rdf:first sg:person.016135602505.17
    77 rdf:rest rdf:nil
    78 Nb4f404c8d08449e797a12072ba6da072 schema:issueNumber 1
    79 rdf:type schema:PublicationIssue
    80 Nb887789178f64683934cd0de0139b08e schema:name Springer Nature - SN SciGraph project
    81 rdf:type schema:Organization
    82 Ne54614b8b14e44e5b7938302c9799b94 rdf:first sg:person.013177467112.78
    83 rdf:rest N8afebe95c7a34ce9869dcb68af7274c5
    84 Ne5719f789b854f3489e27cdc3980cc75 schema:name doi
    85 schema:value 10.1007/s00186-017-0608-y
    86 rdf:type schema:PropertyValue
    87 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    88 schema:name Mathematical Sciences
    89 rdf:type schema:DefinedTerm
    90 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    91 schema:name Pure Mathematics
    92 rdf:type schema:DefinedTerm
    93 sg:journal.1053187 schema:issn 1432-2994
    94 1432-5217
    95 schema:name Mathematical Methods of Operations Research
    96 rdf:type schema:Periodical
    97 sg:person.013177467112.78 schema:affiliation https://www.grid.ac/institutes/grid.7450.6
    98 schema:familyName Hübner
    99 schema:givenName Ruth
    100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013177467112.78
    101 rdf:type schema:Person
    102 sg:person.016135602505.17 schema:affiliation https://www.grid.ac/institutes/grid.7450.6
    103 schema:familyName Schöbel
    104 schema:givenName Anita
    105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016135602505.17
    106 rdf:type schema:Person
    107 sg:pub.10.1007/10997703_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015075880
    108 https://doi.org/10.1007/10997703_15
    109 rdf:type schema:CreativeWork
    110 sg:pub.10.1007/978-0-387-09686-5_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005145396
    111 https://doi.org/10.1007/978-0-387-09686-5_7
    112 rdf:type schema:CreativeWork
    113 sg:pub.10.1007/978-0-387-35651-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027557578
    114 https://doi.org/10.1007/978-0-387-35651-8
    115 rdf:type schema:CreativeWork
    116 sg:pub.10.1007/978-1-4614-0769-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010074517
    117 https://doi.org/10.1007/978-1-4614-0769-0
    118 rdf:type schema:CreativeWork
    119 sg:pub.10.1007/978-1-4614-1927-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010863518
    120 https://doi.org/10.1007/978-1-4614-1927-3
    121 rdf:type schema:CreativeWork
    122 sg:pub.10.1007/978-1-4615-4381-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014628929
    123 https://doi.org/10.1007/978-1-4615-4381-7
    124 rdf:type schema:CreativeWork
    125 sg:pub.10.1007/978-1-4757-3216-0_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014742978
    126 https://doi.org/10.1007/978-1-4757-3216-0_17
    127 rdf:type schema:CreativeWork
    128 sg:pub.10.1007/978-3-319-07557-0_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049086537
    129 https://doi.org/10.1007/978-3-319-07557-0_17
    130 rdf:type schema:CreativeWork
    131 sg:pub.10.1007/978-3-540-68279-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030141941
    132 https://doi.org/10.1007/978-3-540-68279-0
    133 rdf:type schema:CreativeWork
    134 sg:pub.10.1007/978-3-540-68279-0_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013813721
    135 https://doi.org/10.1007/978-3-540-68279-0_15
    136 rdf:type schema:CreativeWork
    137 sg:pub.10.1007/bf01070233 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052605099
    138 https://doi.org/10.1007/bf01070233
    139 rdf:type schema:CreativeWork
    140 sg:pub.10.1007/bf02733104 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037675001
    141 https://doi.org/10.1007/bf02733104
    142 rdf:type schema:CreativeWork
    143 sg:pub.10.1007/bf03006558 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023808751
    144 https://doi.org/10.1007/bf03006558
    145 rdf:type schema:CreativeWork
    146 sg:pub.10.1007/pl00009496 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051310884
    147 https://doi.org/10.1007/pl00009496
    148 rdf:type schema:CreativeWork
    149 sg:pub.10.1007/s10107-005-0672-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012083193
    150 https://doi.org/10.1007/s10107-005-0672-6
    151 rdf:type schema:CreativeWork
    152 sg:pub.10.1007/s11464-012-0187-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049425767
    153 https://doi.org/10.1007/s11464-012-0187-4
    154 rdf:type schema:CreativeWork
    155 https://app.dimensions.ai/details/publication/pub.1027557578 schema:CreativeWork
    156 https://doi.org/10.1016/j.disopt.2012.11.003 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049049320
    157 rdf:type schema:CreativeWork
    158 https://doi.org/10.1016/j.jco.2006.07.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039598025
    159 rdf:type schema:CreativeWork
    160 https://doi.org/10.1016/s0166-218x(01)00341-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039547005
    161 rdf:type schema:CreativeWork
    162 https://doi.org/10.1080/10556789908805762 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010748736
    163 rdf:type schema:CreativeWork
    164 https://doi.org/10.1080/10556789908805765 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049285622
    165 rdf:type schema:CreativeWork
    166 https://doi.org/10.1090/dimacs/060 schema:sameAs https://app.dimensions.ai/details/publication/pub.1097022580
    167 rdf:type schema:CreativeWork
    168 https://doi.org/10.1090/surv/146 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098734667
    169 rdf:type schema:CreativeWork
    170 https://doi.org/10.1109/cdc.2011.6160623 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094297642
    171 rdf:type schema:CreativeWork
    172 https://doi.org/10.1137/050646500 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062846773
    173 rdf:type schema:CreativeWork
    174 https://doi.org/10.1137/130929187 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062871035
    175 rdf:type schema:CreativeWork
    176 https://doi.org/10.1137/s1052623400366802 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062883193
    177 rdf:type schema:CreativeWork
    178 https://doi.org/10.1137/s1052623403431779 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062883381
    179 rdf:type schema:CreativeWork
    180 https://doi.org/10.1287/mnsc.31.12.1533 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064719979
    181 rdf:type schema:CreativeWork
    182 https://doi.org/10.1287/moor.1050.0169 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064722829
    183 rdf:type schema:CreativeWork
    184 https://doi.org/10.1287/opre.15.6.1171 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064727177
    185 rdf:type schema:CreativeWork
    186 https://doi.org/10.1287/opre.21.1.221 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064728285
    187 rdf:type schema:CreativeWork
    188 https://doi.org/10.4153/cjm-2009-010-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072268577
    189 rdf:type schema:CreativeWork
    190 https://doi.org/10.4153/cmb-2003-054-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072272513
    191 rdf:type schema:CreativeWork
    192 https://www.grid.ac/institutes/grid.7450.6 schema:alternateName University of Göttingen
    193 schema:name Institute for Numerical and Applied Mathematics, University of Göttingen, Lotzestr. 16–18, 37083, Göttingen, Germany
    194 rdf:type schema:Organization
     




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


    ...