### Refine

#### Year of publication

#### Document Type

- ZIB-Report (9)
- In Proceedings (5)
- Article (4)

#### Language

- English (18)

#### Is part of the Bibliography

- no (18)

#### Keywords

- Mixed Integer Programming (2)
- branch-and-bound (2)
- exact computation (2)
- mixed integer programming (2)
- Algorithm Analysis (1)
- Exact linear programming (1)
- IP (1)
- Iterative refinement (1)
- Linear Programming (1)
- Linear programming (1)

#### Institute

MIPLIB 2010
(2010)

This paper reports on the fifth version of the Mixed Integer Programming Library.
The MIPLIB 2010 is the first MIPLIB release that has been assembled by a large group from academia and from industry, all of whom work in integer programming. There was mutual consent that the concept of the library had to be expanded in order to fulfill the needs of the community. The new version comprises 361 instances sorted into several groups.
This includes the main benchmark test set of 87 instances, which
are all solvable by today's codes, and also the challenge test set with 164 instances, many of which are currently unsolved.
For the first time, we include scripts to run automated tests in a predefined way. Further, there is a solution checker to
test the accuracy of provided solutions using exact arithmetic.

We present an exact rational solver for mixed-integer linear programming
that avoids the numerical inaccuracies inherent in the floating-point
computations used by existing software. This allows the solver to be used
for establishing theoretical results and in applications where correct
solutions are critical due to legal and financial consequences. Our solver
is a hybrid symbolic/numeric implementation of LP-based branch-and-bound,
using numerically-safe methods for all binding computations in the search
tree. Computing provably accurate solutions by dynamically choosing the
fastest of several safe dual bounding methods depending on the structure of
the instance, our exact solver is only moderately slower than an inexact
floating-point branch-and-bound solver. The software is incorporated into
the SCIP optimization framework, using the exact LP solver QSopt_ex and the
GMP arithmetic library. Computational results are presented for a suite of
test instances taken from the MIPLIB and Mittelmann collections.

Fast computation of valid linear programming (LP) bounds serves as an
important subroutine for solving mixed-integer programming problems
exactly. We introduce a new method for computing valid LP bounds designed
for this application. The algorithm corrects approximate LP dual solutions
to be exactly feasible, giving a valid bound. Solutions are repaired by
performing a projection and a shift to ensure all constraints are
satisfied; bound computations are accelerated by reusing structural
information through the branch-and-bound tree. We demonstrate this method
to be widely applicable and faster than solving a sequence of exact LPs.
Several variations of the algorithm are described and computationally
evaluated in an exact branch-and-bound algorithm within the mixed-integer
programming framework SCIP.

We describe an iterative refinement procedure for computing extended precision or exact solutions to linear programming problems (LPs). Arbitrarily precise solutions can be computed by solving a sequence of closely related LPs with limited precision arithmetic. The LPs solved share the same constraint matrix as the original problem instance and are transformed only by modification of the objective function, right-hand side, and variable bounds. Exact computation is used to compute and store the exact representation of the transformed problems, while numeric computation is used for solving LPs. At all steps of the algorithm the LP bases encountered in the transformed problems correspond directly to LP bases in the original problem description.
We demonstrate that this algorithm is effective in practice for computing extended precision solutions and that this leads to direct improvement of the best known methods for solving LPs exactly over the rational numbers.

We present an exact rational solver for mixed-integer linear programming that avoids the numerical inaccuracies inherent in the floating-point computations used by existing software. This allows the solver to be used for establishing theoretical results and in applications where correct solutions are critical due to legal and financial consequences. Our solver is a hybrid symbolic/numeric implementation of LP-based branch-and-bound, using numerically-safe methods for all binding computations in the search tree. Computing provably accurate solutions by dynamically choosing the fastest of several safe dual bounding methods depending on the structure of the instance, our exact solver is only moderately slower than an inexact floating-point branch-and-bound solver. The software is incorporated into the SCIP optimization framework, using the exact LP solver QSopt_ex and the GMP arithmetic library. Computational results are presented for a suite of test instances taken from the MIPLIB and Mittelmann libraries and for a new collection of numerically difficult instances.

We investigate how the numerical properties of the LP relaxations evolve
throughout the solution procedure in a solver employing the branch-and-cut
algorithm. The long-term goal of this work is to determine whether the effect
on the numerical conditioning of the LP relaxations resulting from the
branching and cutting operations can be effectively predicted
and whether such predictions can be used to make better algorithmic
choices. In a first step towards this goal, we discuss here the numerical
behavior of an existing solver in order to determine whether our
intuitive understanding of this behavior is correct.

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.