Exact Integer Programming

Overview

Available solvers for mixed-integer programs (MIPs) focus on finding close to optimal solutions for feasible instances. Users are aware that the answers are only accurate with respect to feasibility and optimality tolerances, but for many application, this is regarded to be acceptable.

This situation changes fundamentally when MIPs are used to study theoretical problems, when instances become pure feasibility questions (and are infeasible), and when wrong answers can have legal consequences. Examples for applications where inexact solvers are not adequate include combinatorial design theory, chip verification, and contracting by combinatorial auctions.

In this project, we develop and implement an approach for the exact solution of MIPs. By extending the constraint programming/MIP solver SCIP, we want to provide a tool, which is freely available to the scientific community, to compute exact optimal solutions or, perhaps even more important, exact certificates for infeasibility.

Übersicht

Verfügbare Löser für gemischt-ganzzahlige Programme (mixed-integer programs, MIPs) sind auf die schnelle Berechnung von annähernd optimalen Lösungen für zulässige Instanzen ausgelegt. Die Nutzer wissen, dass die Antworten nur im Rahmen von Zulässigkeits- und Optimalitätstoleranzen verlässlich sind, legen aber in vielen Fällen auf exakte Lösungen keinen besonderen Wert.

Die Lage ändert sich fundamental, wenn MIPs verwendet werden, um theoretische Fragen zu untersuchen, wenn Instanzen reine Zulässigkeitsprobleme sind (die unzulässig sind), und wenn falsche Antworten rechtliche Konsequenzen haben. Beispiele für solche Anwendungen sind die Designtheorie, die Chip-Verifikation, und die ertragsvergabe mittels kombinatorischer Auktionen.

Wir entwickeln und implementieren in diesem Projekt einen Ansatz zur exakten Lösung von MIPs. Auf Basis des Constraint Programming/MIP-Lösers SCIP wollen wir der wissenschaftlichen Gemeinschaft ein frei erhältliches Werkzeug zur Verfügung stellen, mit dem exakte Optimallösungen bzw., was vielleicht noch wichtiger ist, exakte Unzulässigkeitsbeweise berechnet werden können.

News

Software

Our objective is to design a framework that can exactly solve MIP instances that are given by rational data. For a feasible instance, a true optimum solution will be computed; for an infeasible instance, a provably correct infeasibility certificate will be issued. Based on the software SCIP (Solving Constraint Integer Programs) we want to provide a fully fledged production code which includes all state-of-the-art components of modern MIP solvers to achieve reasonable running times.

For more details, please visit our project website.

Publications

@InProceedings{AchtBertKochWolt08,
author = "Tobias Achterberg and Timo Berthold and Thorsten Koch and Kati Wolter",
title = "Constraint Integer Programming: A New Approach to Integrate {CP} and {MIP}",
booktitle = "Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 5th International Conference, CPAIOR 2008",
pages = "6--20",
year = "2008",
editor = "Laurent Perron and Michael A. Trick",
volume = "5015",
series = "Lecture Notes in Computer Science", publisher = "Springer"}

-- KatiWolter - 06 Sep 2010