Simple and Fast Implementation of Exact Optimization Algorithms with SCIL
Prof. Dr. Ernst Althaus; Universität Mainz
Prof. Dr. Christoph Buchheim; Technische Universität Dortmund
SCIL is a software that allows a simple implementation of exact algorithms for difficult optimization problems. It is based on efficient Branch-and-Cut procedures, but compared to other approaches it also supports symbolic constraints instead of linear inequalities.
The project's goal is further development of SCIL. We focus on the integration of new separation methods that will lead to a considerable speedup and to the development of new modelling possibilities. An important point is the ability to use polynomial objective functions and logic constraints. Moreover SCIL should be extended such that numerically exact optimal solutions could be computed - an important feature, e.g., for automatic verification of hybrid systems.
In order to ensure a practice-oriented development, another part of the project focuses on solving difficult practical optimization problems that are particularly well suited as applications for SCIL.
- C. Buchheim, A. Wiegele and L. Zheng. "Exact Algorithms for the Quadratic Linear Ordering Problem", INFORMS Journal on Computing, Vol. 22. 2010, pp. 168-177. [More]
- C. Buchheim, F. Liers and M. Oswald. "Speeding up IP-based Algorithms for Constrained Quadratic 0-1 Optimization", Mathematical Programming (Series B), Vol. 124. 2010, pp. 513-535. [More]
- F. Baumann, C. Buchheim and F. Liers. "Exact Bipartite Crossing Minimization under Tree Constraints". 9th International Symposium on Experimental Algorithms SEA 2010. 2010. pp. 118-128. [More]
- F. Baumann and C. Buchheim. "Submodular Formulations for Range Assignment Problems". International Symposium on Combinatorial Optimization ISCO 2010. 2010. pp. 239-246. [More]
- E. Althaus and D. Dumitriu. "Fast and Accurate Bounds on Linear Programs". 8th International Symposium on Experimental Algorithms (SEA). 2009. pp. 40-50. [More]