Verifying Integer Programming Results
C++ HTML Makefile
Switch branches/tags
Nothing to show
Permalink
Failed to load latest commit information.
code add make test Nov 23, 2016
experiments format instance-wise results table in supplementary information Nov 23, 2016
README.md
cert_spec_v1_0.html Add files via upload Nov 20, 2016

README.md

VIPR. Verifying Integer Programming Results

About

VIPR is new a software project to verify, in exact rational arithmetic, the correctness of results computed by mixed-integer linear programming solvers. It is based on an elementary file format for LP-based branch-and-cut certificates proposed in the article

Kevin K.H. Cheung, Ambros Gleixner, and Daniel E. Steffy: Verifying Integer Programming Results, ZIB-Report 16-58, November 2016, urn:nbn:de:0297-zib-61044.

This repository contains a detailed technical specification of the certificate file format, software to check, display, and compress certificate files, and supplementary information on the computational experiments conducted for the article above.

Software

VIPR currently comes with three C++ programs:

  • viprchk: A program that verifies mixed-integer linear programming certificate files specified in the .vipr file format.
  • viprttn: A program that tightens and improves .vipr files, potentially reducing their size and allowing for easier checking.
  • vipr2html: A program that converts .vipr certificate files to a human readable HTML format (not recommended for large files).

The code should compile with most modern compilers supporting the C++11 standard. Directory code provides a basic makefile. We have successfully built the tools with GNU g++ version 5.4.0 under Ubuntu 16.04.4. It depends on the GNU Multiple Precision library.

File format specification .vipr

A conceptual description of the verified integer programming result (.vipr) file format is given in the article above. A more detailed technical specification is provided here.

A small example is given as paper_eg3.vipr. Certificates for large MIP instances from the literature can be found as part of the supplementary information of the article.

Developers

Software for generating .vipr certificates

We have created an extension of the exact rational version of the SCIP optimization software that is able to produce certificates of MIP results. It is currently under active development and is available by request from the authors of this project. It will be included in future releases of the SCIP software.