<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>8951</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2023-01-19</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Strengthening SONC Relaxations with Constraints Derived from Variable Bounds</title>
    <abstract language="eng">Nonnegativity certificates can be used to obtain tight dual bounds for polynomial optimization problems. Hierarchies of certificate-based relaxations ensure convergence to the global optimum, but higher levels of such hierarchies can become very computationally expensive, and the well-known sums of squares hierarchies scale poorly with the degree of the polynomials. This has motivated research into alternative certificates and approaches to global optimization. We consider sums of nonnegative circuit polynomials (SONC) certificates, which are well-suited for sparse problems since the computational cost depends on the number of terms in the polynomials and does not depend on the degrees of the polynomials. We propose a method that guarantees that given finite variable domains, a SONC relaxation will yield a finite dual bound. This method opens up a new approach to utilizing variable bounds in SONC-based methods, which is particularly crucial for integrating SONC relaxations into branch-and-bound algorithms. We report on computational experiments with incorporating SONC relaxations into the spatial branch-and-bound algorithm of the mixed-integer nonlinear programming framework SCIP. Applying our strengthening method increases the number of instances where the SONC relaxation of the root node yielded a finite dual bound from 9 to 330 out of 349 instances in the test set.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-89510</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <author>Ksenia Bestuzheva</author>
    <submitter>Ksenia Bestuzheva</submitter>
    <author>Helena Völker</author>
    <author>Ambros Gleixner</author>
    <collection role="msc" number="14Q99">None of the above, but in this section</collection>
    <collection role="msc" number="68-04">Explicit machine computation and programs (not the theory of computation or programming)</collection>
    <collection role="msc" number="90C26">Nonconvex programming, global optimization</collection>
    <collection role="msc" number="90C57">Polyhedral combinatorics, branch-and-bound, branch-and-cut</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="bestuzheva">Bestuzheva, Ksenia</collection>
    <collection role="persons" number="helena.mueller">Müller, Helena</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/8951/zr.pdf</file>
  </doc>
  <doc>
    <id>570</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2000-01-31</completedDate>
    <publishedDate>2000-01-31</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Symbolic Integration of Exact PDEs</title>
    <abstract language="eng">An algorithm is described to decide if a given polynomial differential expression $\Delta$ of multivariate functions is exact, i.e. whether there exists a first integral $P$ such that $D_xP = \Delta$ for any one of a set of variables $x$ and to provide the integral $P$. A generalization is given to allow integration in the case that the exactness is prohibited by terms which contain only functions of not all the independent variables.</abstract>
    <identifier type="serial">00-02</identifier>
    <identifier type="opus3-id">571</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-5702</identifier>
    <enrichment key="SourceTitle">Appeared in: J. Symb. Comp. 30 (2000) 619-629</enrichment>
    <author>Thomas Wolf</author>
    <series>
      <title>ZIB-Report</title>
      <number>00-02</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>symbolic integration</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>partial differential equations</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="34-04">Explicit machine computation and programs (not the theory of computation or programming)</collection>
    <collection role="msc" number="35-04">Explicit machine computation and programs (not the theory of computation or programming)</collection>
    <collection role="msc" number="35D99">None of the above, but in this section</collection>
    <collection role="msc" number="35N10">Overdetermined systems with variable coefficients</collection>
    <collection role="msc" number="68-04">Explicit machine computation and programs (not the theory of computation or programming)</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/570/ZR-00-02.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/570/ZR-00-02.pdf</file>
  </doc>
  <doc>
    <id>4223</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2013-08-30</completedDate>
    <publishedDate>2013-08-30</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">HUHFA: A Framework for Facet Classification</title>
    <abstract language="eng">Usually complete linear descriptions of polytopes consist of&#13;
an enormous number of facet-defining inequalities already&#13;
for very small problem sizes. In this paper, we describe a method&#13;
for dividing the inequalities into equivalence classes without resorting to a normal form. Within each&#13;
class, facets are related by certain symmetries and it is sufficient&#13;
to list one representative of each class to give a complete&#13;
picture of the structural properties of a polytope. We propose an algorithm&#13;
for the classification and illustrate its efficiency on a broad range of combinatorial optimization problems including the Traveling Salesman and the Linear Ordering Problem.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-42230</identifier>
    <author>Olga Heismann</author>
    <submitter>Olga Heismann</submitter>
    <author>Achim Hildenbrandt</author>
    <author>Francesco Silvestri</author>
    <author>Gerhard Reinelt</author>
    <author>Ralf Borndörfer</author>
    <series>
      <title>ZIB-Report</title>
      <number>13-45</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>facet classification</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>symmetry</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>polyhedral structure</value>
    </subject>
    <collection role="msc" number="52B15">Symmetry properties of polytopes</collection>
    <collection role="msc" number="68-04">Explicit machine computation and programs (not the theory of computation or programming)</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="MATHEON-B22">MATHEON-B22</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/4223/ZR 13-45.pdf</file>
  </doc>
</export-example>
