AmPaPro – Approximation of Multi-Parametric Programming Problems
The project AMPaPro is funded by the Deutsche Forschungsgemeinschaft (DFG) from 01 March 2024 to 28 February 2027.
In parametric programming problems – which, in this project, subsume the classes of parametric linear and (mixed) integer programming problems as well as parametric combinatorial optimization problems – the objective function and/or the feasible set depend on one or several unknown parameters. The task then consists of solving the problem for each possible combination of parameter values. For most parametric programming problems, however, specifying an optimal solution for each combination of parameter values requires an enormous number of solutions. Consequently, these are usually very difficult to solve exactly and the applicability of exact solution algorithms is often severely limited. This particularly holds for multi-parametric problems, where several parameters are involved.
Hence, this project aims at developing efficient approximation methods for one- and multi-parametric programming problems that are applicable under weak assumptions and produce approximations with provably good approximation quality and small cardinality. In addition, the field of parametric programming will be widened by performing the first systematic investigation concerning problems with non-linear parameter dependencies and/or multiple objectives. Building on preliminary work (e.g., in project MultiApprox), general approximation methods for parametric programming problems will be designed and a rigorous structural theory of approximations of (multi-) parametric programming problems will be available upon completion of this project. Since parametric programming has numerous links to other fields such as non-parametric (discrete) optimization, multi-objective optimization, and sensitivity analysis, this will not only constitute an important advancement in the area of parametric programming, but also a significant contribution to the general state-of-the-art in mathematical programming.
Partners
- RPTU Kaiserslautern-Landau – Optimization Group – Prof. Dr. Stefan Ruzika
- Technical University of Munich – Professorship Optimization and Sustainable Decision Making – Prof. Dr. Clemens Thielen
Funded by
