mathematical-optimization - 建议 ILP 求解器的下限-6ren

mathematical-optimization - 建议 ILP 求解器的下限

转载作者：行者123 更新时间：2023-12-02 03:11:04

24

4

我有一个整数线性规划问题，我尝试过的求解器(CPLEX、CBC)需要很长时间才能解决，即使它们很早就找到了最优解。他们只是需要很长时间才能完全证明这一点。

很容易为我的最小化问题的目标值计算一个微不足道的下界，但在 CPLEX 的输出(最佳界列)中我可以看到它甚至在很长很长一段时间内都没有接近。它几乎立即找到了非常好的解决方案，但它错误地认为最佳解决方案可能会更好。

现在我不得不承认我真的不知道这些求解器是如何工作的，但看起来它们正在浪费时间尝试改进可笑的弱下限，寻找不可能乐观的解决方案。所以我的问题是:

是否可以告诉求解器目标的合理下限有助于它更快地运行？
如果是这样，哪些求解器可以接受作为附加输入提供的已知下限？

作为说明，我粘贴了示例运行中 CPLEX 输出的前几行(持续时间更长，目标没有任何进一步改进，最佳边界的改进缓慢得令人痛苦):

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap
      0     0     -388.6997   178                   -388.6997        9
*     0+    0                          297.0000     -388.6997        9  230.88%
*     0+    0                          275.0000     -388.6997        9  241.35%
      0     2     -388.6997   178      275.0000     -387.8106        9  241.02%
*    20+   20                          185.0000     -307.6363       80  266.29%
*    30+   30                          135.0000     -307.6363       90  327.88%
*    30+   30                           94.0000     -307.6363       90  427.27%
*    60+   60                           90.0000     -307.6363      120  441.82%
*   160+  126                           77.0000     -307.6363      272  499.53%
*   200+   93                           12.0000     -307.4836      325     ---
    300   182     -135.2988   107       12.0000     -268.6638      466     ---
   1200   934      -50.6022    85       12.0000     -206.2938     1480     ---
   2197  1755      -96.9612    93       12.0000     -189.8013     2470     ---
   3226  2600       -2.8316    87       12.0000     -179.9669     3480     ---
   4374  3521     -156.2442   110       12.0000     -170.4183     4567     ---
   5490  4421     -128.0871    97       12.0000     -167.3696     5623     ---
   6971  5603     -147.5022   108       12.0000     -162.4180     7055     ---
   8739  6997     -103.5374   113       12.0000     -156.3532     8673     ---

我希望我可以告诉求解器不要费心寻找目标值低于 10 的解决方案(因为我可以用更简单的方法证明这一点)，尤其是目标值为负的情况下(因为这在我的系统中是不可能的)型号)。

最佳答案

如果您有一个很好的下限，从一个可行的解决方案，您可以将其作为 MIP 开始提供给 CPLEX。

然后 CPLEX 将尝试改进该解决方案并忽略其分支定界算法中边界低于该解决方案的任何分支。

关于mathematical-optimization - 建议 ILP 求解器的下限，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40048946/

24

4

0

文章推荐： xslt - Visual Studio 2015 社区 - 缺少 "Show XSL Output"选项

文章推荐： amazon-web-services - 未找到字段值 - AppSync AWS

文章推荐： reactjs - 如何动态加载多选？ [ react 选择]

r - 求解 R 中混合模型方程的积分
我正在使用混合效应模型，并且由于我的方法的特殊性我需要解决下面模型的积分，然后制作图表获得的估计值。换句话说，我需要求解下面的积分: 其中，di^2 是我模型中的 Var3，dh 是混合效应模型对应
r - 求解 R 中的不定方程组
我有一个方程组，我想用数值方法求解它。给定起始种子，我想得到一个接近的解决方案。让我解释。我有一个常量向量，X，值: X <- (c(1,-2,3,4)) 和一个向量 W 的权重: W <- (c(
r - 求解 R 中的非线性方程组
假设我有以下方程组: a * b = 5 sqrt(a * b^2) = 10 如何求解 R 中 a 和 b 的这些方程？我想这个问题可以说是一个优化问题，具有以下功能......？ fn <- f
r - 求解 R 中的微分方程组
我在 R 中有一个简单的通量模型。它归结为两个微分方程，对模型中的两个状态变量进行建模，我们将它们称为 A和 B .它们被计算为四个分量通量的简单差分方程 flux1-flux4 , 5 个参数 p1
r - 求解 R 中函数的逆
R有什么办法吗？求解给定单变量函数的反函数？动机是我以后告诉R使用值向量作为反函数的输入，以便它可以吐出反函数值。例如，我有函数 y(x) = x^2 ，逆是 y = sqrt(x) .有没有办法R
excel - 求解 x 的方程
我在字符串中有以下方程 y = 18774x + 82795 求解x我会这样做:- x = (y-82795) / 18774 我知道y的值但是方程一直在变化，并且始终采用字符串格式是否可以简单地
haskell - 求解(两个以上)线性不等式系统
如果我用 diophantine(2*x+3*y-5*z-77) 我收到了这个结果。 {(t_0, -9*t_0 - 5*t_1 + 154, -5*t_0 - 3*t_1 + 77)} 到目前为止还
r - 求解 ODE - 只有正解
我正在尝试求解仅限于正解的 ODE，即: dx/dt=f(x) x>=0。在 MATLAB 中这很容易实现。 R 是否有任何变通方法或包来将解决方案空间限制为仅正值？这对我来说非常重要，不幸的是没
antlr - 求解 ANTLR 相互左递归规则
下面的 ANTLR 文法中的 'expr' 规则显然是相互左递归的。作为一个 ANTLR 新手，我很难解决这个问题。我已经阅读了 ANTLR 引用书中的“解决非 LL(*) 冲突”，但我仍然没有看到解
r - 求解 R 中的简单方程
我有一个关于在 R 中求解函数的可能性的非常基本的问题，但知道答案确实有助于更好地理解 R。我有以下等式: 0=-100/(1+r)+(100-50)/(1+r)^2+(100-50)/(1+r)^
java - 求解 N 个皇后时出现数组索引越界异常
我正在编写使用递归回溯来解决 8 个皇后问题的代码(将 n 个国际象棋皇后放在 n × n 的棋盘上，这样皇后就不会互相攻击)。我的任务是创建两个方法:编写一个公共(public)solveQuee
r - 求解 R 中的线性方程组
我不知道在以下情况下如何进行，因为最后一个方程没有所有 4 个变量。所以使用了等式下面的代码，但这是错误的......有谁知道如何进行？方程: 3a + 4b - 5c + d = 10 2a +
math - 求解 AVL 树中节点数的递归关系？
假设我们有这个递归关系，它出现在 AVL 树的分析中: F1 = 1 F2 = 2 Fn = Fn - 1 + Fn - 2 + 1(其中 n ≥ 3) 你将如何解决这个递归以获得 F(n) 的封闭形
c - 求解 Maple 中的变量
在Maple中，有谁知道是否存在一个函数来求解变量？例如，我正在尝试求解 r 的 solve4r=(M-x^y)*(r^(-1)) mod (p-1)。所以我知道 M、x、y 和 p 的值，但不知道
c# - 求解 WAV 文件中的振幅和频率
我也问过这个here在声音设计论坛上，但问题是沉重的计算机科学/数学，所以它实际上可能属于这个论坛: 因此，通过读取文件中的二进制文件，我能够成功地找到关于 WAV 文件的所有信息，除了 big si
java - 求解 boolean 表达式时如何思考？
我有以下问题: 设 a 和 b 为 boolean 变量。是否可以设置 a 和 b 的值以使以下表达式的计算结果为 false？ b or (((not a) or (not a)) or (a or
c - 求解 C 中的超越方程
我需要用 C 求解这个超越方程: x = 2.0 - 0.5sen(x) 我试过这个: double x, newx, delta; x = 2.0 - 0.5; newx = sin(x); del
c++ - OpenCV 求解 PnPRansac
我在 Windows 上使用 OpenCV 3.1。一段代码: RNG rng; // random number generator cv::Mat rVec = (cv::Mat_(3, 1)
python - 求解 3 个变量的隐式二次系统
我正在尝试求解一个包含 3 个变量和数量可变的方程的方程组。基本上，系统的长度在 5 到 12 个方程之间，无论有多少个方程，我都试图求解 3 个变量。看起来像这样: (x-A)**2 + (y-
algorithm - 求解 ODE 算法的有限差分法
我正在尝试为有限差分法设计一种算法，但我有点困惑。所讨论的 ODE 是 y''-5y'+10y = 10x，其中 y(0)=0 且 y(1)=100。所以我需要一种方法来以某种方式获得将从关系中乘以“

首页

博学

6Ren·AI

商城

mathematical-optimization - 建议 ILP 求解器的下限