Probabilistic analysis of discrete optimization problems
Probabilistic analysis of discrete optimization problems
复制标题
离散优化问题的概率分析
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
René Beier
中科院分区：
文献类型：
--
作者：
René Beier
我们研究了在随机输入下进行硬优化问题的精确算法的性能。特别是，我们证明了各种结构属性，这些属性导致了两项适用于大量优化问题的一般平均案例分析。在第一部分中，我们研究了两个目标函数的二元优化问题的帕累托曲线的大小。帕累托最佳解决方案可以看作是多个目标之间的权衡。虽然在最坏的情况下，帕累托曲线的基数在变量的数量中是指数的，但当至少一个目标函数是线性并表现出足够的随机性时，我们证明了预期帕累托点的多项式上限。我们的分析涵盖了具有有限平均值的一般概率分布，并且以最通用的形式可以处理目标函数系数的不同概率分布。我们将此结果应用于约束的最短路径问题和背包问题。这两个问题都有算法可以非常有效地列举所有帕累托最佳解决方案，因此我们的多项式上限在帕累托曲线的大小上意味着这些算法的预期运行时间也是多项式的。例如，对于均匀的随机背包实例，我们获得了O（n4）的界限，其中n表示可用的项目数。在第二部分中，我们研究了背包核心算法的性能，这是实践中主要的算法概念。这个想法是将大多数变量固定在最佳分数解决方案规定的值中。减少的问题平均仅具有多聚体大小，并且使用Nemhauser/Ullmann算法解决。应用第一部分的分析，我们可以在预期的运行时间上证明O（npolylog n）的上限。此外，我们将分析扩展到一类更难的随机输入分布。最后，我们介绍了针对各种随机输入分布的背包实例的实验研究。我们研究了结构性属性，包括帕累托曲线的大小和完整性差距，并比较核心算法不同实现之间的运行时间。论文的最后一部分引入了一个半随机输入模型，以解决受约束的二进制优化问题，这使我们能够对大量优化问题进行平滑的分析，同时照顾个体问题的组合结构。我们的分析围绕着结构性特性，称为获胜者，失败者和可行性差距。这些差距描述了最佳解决方案对输入轻微扰动的敏感性，可用于绑定必要的准确性以及解决实例的复杂性。我们以自适应圆形方案的形式利用差距，以提高计算的准确性，直到找到最佳解决方案为止。应用于各种NP-HARD优化问题的应用来说明我们的技术的强度，我们获得了具有多项式平均案例/平滑复杂性的第一个算法。
We investigate the performance of exact algorithms for hard optimization problems under random inputs. In particular, we prove various structural properties that lead to two general average-case analyses applicable to a large class of optimization problems. In the first part we study the size of the Pareto curve for binary optimization problems with two objective functions. Pareto optimal solutions can be seen as trade-offs between multiple objectives. While in the worst case, the cardinality of the Pareto curve is exponential in the number of variables, we prove polynomial upper bounds for the expected number of Pareto points when at least one objective function is linear and exhibits sufficient randomness. Our analysis covers general probability distributions with finite mean and, in its most general form, can even handle different probability distributions for the coefficients of the objective function. We apply this result to the constrained shortest path problem and to the knapsack problem. There are algorithms for both problems that can enumerate all Pareto optimal solutions very efficiently, so that our polynomial upper bound on the size of the Pareto curve implies that the expected running time of these algorithms is polynomial as well. For example, we obtain a bound of O(n4) for uniformly random knapsack instances, where n denotes the number of available items. In the second part we investigate the performance of knapsack core algorithms, the predominant algorithmic concept in practice. The idea is to fix most variables to the values prescribed by the optimal fractional solution. The reduced problem has only polylogarithmic size on average and is solved using the Nemhauser/Ullmann algorithm. Applying the analysis of the first part, we can prove an upper bound of O(npolylog n) on the expected running time. Furthermore, we extend our analysis to a harder class of random input distributions. Finally, we present an experimental study of knapsack instances for various random input distributions. We investigate structural properties including the size of the Pareto curve and the integrality gap and compare the running time between different implementations of core algorithms. The last part of the thesis introduces a semi-random input model for constrained binary optimization problems, which enables us to perform a smoothed analysis for a large class of optimization problems while at the same time taking care of the combinatorial structure of individual problems. Our analysis is centered around structural properties, called winner, loser, and feasibility gap. These gaps describe the sensitivity of the optimal solution to slight perturbations of the input and can be used to bound the necessary accuracy as well as the complexity for solving an instance. We exploit the gaps in form of an adaptive rounding scheme increasing the accuracy of calculation until the optimal solution is found. The strength of our techniques is illustrated by applications to various NP-hard optimization problems for which we obtain the rst algorithms with polynomial average-case/smoothed complexity.