从近似到精确的整数编程
Daniel Dadush1, Friedrich Eisenbrand2, Thomas Rothvoss3
1Centrum Wiskunde & Informatica (CWI), Amsterdam, The Netherlands.
概括
新的方法利用近似的整数编程来有效地解决精确的整数编程问题. 这一突破为复杂的问题提供了更快的算法,如背包和子集和.
科学领域:
- 计算数学 计算数学 计算数学
- 优化理论 优化理论
- 计算机科学 计算机科学
背景情况:
- 精确的整数编程在计算上具有挑战性.
- 准确整数编程的现有方法复杂且耗时.
- 大致整数编程提供了一个更快的替代方案,但缺乏直接应用到确切的问题.
研究的目的:
- 开发基于近似整数编程的精确整数编程的高效方法.
- 为了实现解决整数编程问题的新型复杂性结果.
- 提高解决特定问题的效率,如背包和子集和.
主要方法:
- 一种切割平面技术反复地减少了可行的集的体积.
- 用近似的整数编程来确定切割平面.
- 引入了一个新的不对称的近似卡拉西奥多里定理.
- 在方程标准形式的整数编程问题被简化为多个近似问题.
主要成果:
- 一个整数点可以在时间中找到,当提供组件剩余数时.
- 介绍了一个具有时间复杂性的通用整数编程算法,匹配最知名的边界.
- 带有多项式变量范围的Knapsack和子集和问题在时间内得到解决,改进了之前的边界.
结论:
- 开发的方法在解决整数编程问题的复杂性方面提供了显著的改进.
- 新的算法为诸如背包和子集和等问题提供了实际优势.
- 该研究引入了新的算法技术和优化理论结果.
相关概念视频
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
38
Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
38
Statically Indeterminate Problem Solving
355
Statically indeterminate problems are those where statics alone can not determine the internal forces or reactions. Consider a structure comprising two cylindrical rods made of steel and brass. These rods are joined at point B and restrained by rigid supports at points A and C. Now, the reactions at points A and C and the deflection at point B are to be determined. This rod structure is classified as statically indeterminate as the structure has more supports than are necessary for maintaining...
355
Accuracy, limits, and approximation
425
Accuracy, limits, and approximations are common in many fields, especially in engineering calculations. These concepts are imperative for ensuring that a given value is as close as possible to its true value.
Accuracy is defined as the closeness of the measured value to the true or actual value. In engineering mechanics, repeated measurements are taken during theoretical or experimental analyses to ensure that the result is precise and accurate.
The accuracy of any solution is based on the...
Accuracy is defined as the closeness of the measured value to the true or actual value. In engineering mechanics, repeated measurements are taken during theoretical or experimental analyses to ensure that the result is precise and accurate.
The accuracy of any solution is based on the...
425
Linear Approximation in Time Domain
59
Nonlinear systems often require sophisticated approaches for accurate modeling and analysis, with state-space representation being particularly effective. This method is especially useful for systems where variables and parameters vary with time or operating conditions, such as in a simple pendulum or a translational mechanical system with nonlinear springs.
For a simple pendulum with a mass evenly distributed along its length and the center of mass located at half the pendulum's length,...
For a simple pendulum with a mass evenly distributed along its length and the center of mass located at half the pendulum's length,...
59
Decision Making: P-value Method
5.2K
The process of hypothesis testing based on the P-value method includes calculating the P- value using the sample data and interpreting it.
First, a specific claim about the population parameter is proposed. The claim is based on the research question and is stated in a simple form. Further, an opposing statement to the claim is also stated. These statements can act as null and alternative hypotheses: a null hypothesis would be a neutral statement while the alternative hypothesis can...
First, a specific claim about the population parameter is proposed. The claim is based on the research question and is stated in a simple form. Further, an opposing statement to the claim is also stated. These statements can act as null and alternative hypotheses: a null hypothesis would be a neutral statement while the alternative hypothesis can...
5.2K
Linear Approximation in Frequency Domain
84
Linear systems are characterized by two main properties: superposition and homogeneity. Superposition allows the response to multiple inputs to be the sum of the responses to each individual input. Homogeneity ensures that scaling an input by a scalar results in the response being scaled by the same scalar.
In contrast, nonlinear systems do not inherently possess these properties. However, for small deviations around an operating point, a nonlinear system can often be approximated as linear....
In contrast, nonlinear systems do not inherently possess these properties. However, for small deviations around an operating point, a nonlinear system can often be approximated as linear....
84


