<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>6104</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>2016-11-20</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Verifying Integer Programming Results</title>
    <abstract language="eng">Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from programming or algorithmic errors, motivating the desire for a way to produce independently verifiable certificates of claimed results. Due to the complex nature of state-of-the-art MILP solution algorithms, the ideal form of such a certificate is not entirely clear. This paper proposes such a certificate format, illustrating its capabilities and structure through examples. The certificate format is designed with simplicity in mind and is composed of a list of statements that can be sequentially verified using a limited number of simple yet powerful inference rules. We present a supplementary verification tool for compressing and checking these certificates independently of how they were created.  We report computational results on a selection of mixed-integer linear programming instances from the literature.  To this end, we have extended the exact rational version of the MIP solver SCIP to produce such certificates.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-61044</identifier>
    <identifier type="doi">10.1007/978-3-319-59250-3_13</identifier>
    <enrichment key="SourceTitle">F. Eisenbrand and J. Koenemann, eds., Integer Programming and Combinatorial Optimization: 19th International Conference, IPCO 2017</enrichment>
    <author>Kevin K. H. Cheung</author>
    <submitter>Ambros Gleixner</submitter>
    <author>Ambros Gleixner</author>
    <author>Daniel Steffy</author>
    <series>
      <title>ZIB-Report</title>
      <number>16-58</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>correctness, verification, proof, certificate, optimality, infeasibility, mixed-integer linear programming</value>
    </subject>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="projects" number="ASTfSCM">ASTfSCM</collection>
    <collection role="projects" number="MIP-ZIBOPT">MIP-ZIBOPT</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="Siemens">Siemens</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6104/ZR-16-58.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/6104/ZR-16-58-revised.pdf</file>
  </doc>
</export-example>
