全二次混合整数问题:关于进化策略和数学编程的研究
1Computer Science Department, Reichman University, and The Galilee Research Institute - Migal, Upper Galilee, Israel guyz@migal.org.il.
Evolutionary computation
|September 10, 2025
概括
黑盒进化策略 (ES) 和白盒解决器在混合整数二次编程方面表现出竞争力. CPLEX 优异,除非 optima 得到显著的翻译,否则 ES 的表现会优于它.
科学领域:
- 优化优化 优化优化
- 计算数学 计算数学 计算数学
- 运营研究 运营研究
背景情况:
- 全二次混合整数 (MI) 程序是NP完整的,具有无边界的整数变量,使它们无法决定.
- 传统的白盒数学编程 (MP) 解决者与这些问题的复杂性作斗争.
研究的目的:
- 评估黑盒进化策略 (ES) 与白盒解决方案的有效性,以最大限度地减少MI凸二次目标和约束函数.
- 在不同的条件下分析解决器性能,包括赫斯形式,条件号码和无限性.
主要方法:
- 经验评估比较CPLEX (白框) 与MIES (黑框) 在全方位测试案例中.
- 调查的重点是更高的维度 (D=64),CPLEX经常超出时间.
- MIES使用了惩罚方法来处理约束.
主要成果:
- 在客观功能值方面,CPLEX和MI ES表现相似 (67%的相似性).
- 在没有遇到停机的情况下,CPLEX在98%的案例中超过或匹配MIES.
- 当翻译optima时,CPLEX性能显著下降 (81%较差),有利于MI ESs.
结论:
- 黑盒子和白盒子解决方案可以在全方位MI程序中竞争.
- 问题特征,如条件和分离性,不能直观地预测难度.
- 解决器的性能对无限场景中最佳的翻译非常敏感.
相关概念视频
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
292
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...
292
Mathematical Modeling: Problem Solving
280
Mathematical modeling transforms real-world scenarios into mathematical expressions, allowing for structured problem-solving and analysis. This process involves defining the situation, assigning variables to measurable quantities, selecting an appropriate model, and solving the resulting equation. Such models are invaluable in finance, providing precise methods to evaluate investments, loans, and repayment structures.A widely used example is the calculation of fixed monthly payments on a loan,...
280
Gaussian Elimination: Problem Solving
162
Systems of linear equations in several variables are pivotal in modeling complex scenarios involving multiple unknowns and constraints. Such systems are widely used in various fields to represent relationships where several conditions must be simultaneously satisfied. Each variable in the system corresponds to an unknown quantity, while each equation imposes a linear constraint, leading to a structured approach for analyzing and solving real-world problems.A system of three equations with three...
162
Application of Nonlinear Inequalities
214
A nonlinear inequality describes a comparison involving an expression that curves or behaves more complexly than a straight line. These inequalities often appear in forms that include squares, products, or variables in the denominator.To solve such an inequality, one starts by rewriting it so that zero appears on one side. For example, the inequality: can be factored as: This form makes it easier to identify the values that cause the expression to equal zero. In this case, the...
214
Quadratic Equations
304
A quadratic equation is an algebraic expression where a variable is raised to the second power and combined with its first power and a constant; all equated to zero. These equations are frequently used to model relationships involving area, motion, and optimization. The general representation of a quadratic equation iswhere a, b, and c are real values, and a is nonzero to ensure the presence of the squared term.One method for solving a quadratic equation involves rewriting it as a product of...
304
Quadratic Models
197
Quadratic models are mathematical representations used to describe relationships in which the rate of change changes at a constant rate. These models appear in a wide variety of natural and engineered systems, especially those involving motion, forces, and optimization. One common application is analyzing the vertical motion of objects influenced by gravity, such as a ball thrown into the air.In such scenarios, the object's height changes over time in a curved pattern, rising to a maximum point...
197


