Approximation of Multi-Parametric Programming Problems

• Applicants: Professor Dr. Stefan Ruzika; Professor Dr. Clemens Thielen
• Subject Area: Mathematics ; Theoretical Computer Science
• Term: since 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 508981269

In parametric programming problems - which, in this proposal, 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 proposal 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 joint preliminary work of the applicants, 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.

• DFG Programme: Research Grants