Hybrid-precision algorithms in a safe and verified MIP framework

by Ambros Gleixner (HTW Berlin; Zuse Institute Berlin)

Thursday Mar 9, 2023, 10:30 AM → 11:30 AM America/Chicago

Conference Room 1407 (Building 240)

Location: Hybrid, Bldg. 240, Conference Room 1407

Zoom Link: Please contact the host.

Abstract

The presence of floating-point roundoff errors compromises the results of virtually all fast mixed-integer programming solvers available today. In this talk we present recent advances in our endeavour to craft a performant mixed-integer optimizer that is not only free from roundoff errors, but produces certificates of optimality that can be verified independently of the solving process. Key to most efficient techniques is the combination of different levels of arithmetic precision and the use of directed rounding. We highlight several methods that follow this paradigm and present advances in exact LP solving and the safe generation of Gomory mixed-integer cuts via mixed-integer rounding. Our computational experiments are based on an extension of the open-source solver SCIP and the certificate language VIPR. This is joint work with Sander Borst, Leon Eifler, Fabian Frickenstein, and Jules Nicolas-Thouvenin.

Biography

Ambros Gleixner is Professor for Discrete Mathematics and Operations Research at HTW Berlin and Head of the research group Mathematical Optimization Methods at Zuse Institute Berlin (ZIB). His research focuses on computational aspects of mixed-integer linear and nonlinear programming. Having received both his diploma and Ph.D. degree in mathematics from the TU Berlin in Germany, he has been leading the development of the optimization framework SCIP since 2015, which today provides the fastest open-source MIP and MINLP solver. Motivated by this, his main interest is the design of structure-specific algorithms that help to improve general-purpose solvers both in terms of efficiency and accuracy

This seminar is part of an informal seminar series organized by Argonne National Laboratory, Northwestern University, and University of Chicago.

Agenda

09:15 am – 10:15 am: Individual Meetings
10:15 am – 10:30 am: Seminar preparation
10:30 am – 11:30 am: Seminar
11:30 am – 01:30 pm: Lunch break
01:30 pm – 03:30 pm: (Parallel) Individual Meetings
01:30 pm – 03:50 pm: (Parallel) Group Discussion
03:50 pm – 04:00 pm: Closing