Approximation of Multi-Parametric Programming Problems

多参数规划问题的逼近

• 批准号: 508981269
• 负责人: Professor Dr. Stefan Ruzika
• 金额: --
• 依托单位: Professur für Komplexe Netzwerke
• 依托单位国家: 德国
• 项目类别: Research Grants
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/508981269?language=en
• 关键词: Approximation; Multi; Parametric; Programming; Problems

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.

在参数规划问题中-在这个建议中，它从属于参数线性和（混合）整数规划问题以及参数组合优化问题的类别-目标函数和/或可行集取决于一个或多个未知参数。然后，该任务包括解决每个可能的参数值组合的问题。然而，对于大多数参数规划问题，为每个参数值组合指定最优解需要大量的解。因此，这些问题通常很难精确求解，精确解算法的适用性往往受到严重限制。这特别适用于多参数问题，其中涉及多个参数。因此，这项建议的目的是开发有效的近似方法的一个和多参数规划问题，适用于弱假设下，并产生近似可证明良好的近似质量和小基数。此外，参数编程领域将通过执行第一次系统的调查有关的问题与非线性参数依赖性和/或多个目标拓宽。在申请人的联合初步工作的基础上，将设计参数规划问题的一般近似方法，并且在该项目完成后将提供（多）参数规划问题的近似的严格结构理论。由于参数规划与其他领域有许多联系，如非参数（离散）优化，多目标优化和灵敏度分析，这不仅构成了参数规划领域的重要进步，而且对数学规划的一般国家的最先进的显着贡献。