Home // ADVCOMP 2013, The Seventh International Conference on Advanced Engineering Computing and Applications in Sciences // View article

Reliable Outer Bounds for the Dual Simplex Algorithm with Interval Right-hand Side

Authors:
Christoph Fuenfzig
Dominique Michelucci
Sebti Foufou

Keywords: verified simplex algorithm; interval arithmetic; tableau form; OpenMP parallelization

Abstract:
In this article, we describe the reliable computation of outer bounds for linear programming problems occuring in linear relaxations derived from the Bernstein polynomials. The computation uses interval arithmetic for the Gauss-Jordan pivot steps on a simplex tableau. The resulting errors are stored as interval right hand sides. Additionally, we show how to generate a start basis for the linear programs of this type. We give details of the implementation using OpenMP and comment on numerical experiments.

Pages: 49 to 54

Copyright: Copyright (c) IARIA, 2013

Publication date: September 29, 2013

Published in: conference

ISSN: 2308-4499

ISBN: 978-1-61208-290-5

Location: Porto, Portugal

Dates: from September 29, 2013 to October 3, 2013