Solving Combinatorial Integral Approximation problems with pycombina

Adrian Bürger

Karlsruhe University of Applied Sciences, University of Freiburg

Tuesday, May 08, 2018, 11:00 - 12:00

"Room 01-012, Georges-Köhler-Allee 102, Freiburg 79110, Germany"

For solving Mixed-Integer Non-linear Programs (MINLPs) on a time scale suitable for Model Predictive Control (MPC) applications, it is typically less favorable to solve the exact MINLP by application of a general MINLP solver, but to decompose the original MINLP into a sequence of subproblems of which each one is less hard to solve. It has been proposed to decompose the MINLP problem into two Non-Linear Programs (NLPs) and one Mixed-Integer Linear Program (MILP), of which the MILP is a Combinatorial Integral Approximation (CIA) problem that can either be solved using a general MILP solver or by a tailored branch-and-bound method.

With pycombina, we provide a fast implementation of a branch-and-bound algorithm that can solve CIA problems under consideration of SOS1-, maximum-switching- and minimum-uptime-constraints. While the algorithm is implemented in C++, a Python interface is provided to facilitate simple usage. Additional pre-processing heuristics for CIA problems are presented that aim to reduce a problem's complexity. Finally, the performance of the implementations and methods are compared on a numerical example.