首页 文章

MIP GAP无法正确设置

提问于
浏览 次
0

我正在IBM ILOG Cplex中解决MIP问题 . 我已将相对MIP GAP和绝对MIP间隙设置为0，但是在引擎日志中报告的间隙高于0.当我按默认值运行模型时（1.0E-4,1.0E-6），差距在引擎日志中报告的值高于1.0E-4（有时甚至是6％） . 令人惊讶的是，即使计算时间很短（低于1秒） . 我想除了mip gap之外还需要其他设置来将其设置为零以获得目标函数的最佳值 . 另一件事是我的其他设置是默认设置 . 如果有人能帮助我，我感激不尽 .

这是我的一次运行的结果（相对MIP GAP设置为0，但报告的差距为1.13％，如您所见）：

Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer     Best Node    ItCnt     Gap

      0     0    15619.2777    30                  15619.2777      204         
      0     0    21532.4345    31                    Cuts: 92      300         
      0     0    22240.7958    65                    Cuts: 50      389         
      0     0    22374.7172    46                    Cuts: 63      452         
      0     0    22428.5062    28                    Cuts: 31      475         
      0     0    22447.7754    48                    Cuts: 28      517         
      0     0    22486.3137    39                    Cuts: 34      542         
      0     0    22486.3137    40                    Cuts: 13      557         
      0     0    22486.3137    30                 ZeroHalf: 4      558         
      0     0    22486.3137    28                    Cuts: 15      583         
*     0+    0                        23225.6696    22486.3137      583    3.18%
      0     2    22486.3137    28    23225.6696    22486.3137      583    3.18%
Elapsed real time =   0.36 sec. (tree size =  0.01 MB, solutions = 1)
*    26    20      integral     0    22743.1173    22486.3137     1126    1.13%

GUB cover cuts applied:  2
Clique cuts applied:  23
Cover cuts applied:  9
Implied bound cuts applied:  105
Flow cuts applied:  1
Mixed integer rounding cuts applied:  30
Zero-half cuts applied:  74
Gomory fractional cuts applied:  3

Root node processing (before b&c):
  Real time             =    0.31
Parallel b&c, 4 threads:
  Real time             =    0.25
  Sync time (average)   =    0.02
  Wait time (average)   =    0.06
                          -------
Total (root+branch&cut) =    0.56 sec.

事先感谢您的帮助 .

c++ cplex

1 回答

  • 0

    正如Tim在评论中所说，日志文件的最后一行实际上显示了最终解决方案（上限和下限），而不是树日志部分的最后一行 .

    这是一个例子：

    似乎问题如下：

    • CPLEX报告最佳解决方案，默认差距为10e-4，但报告为1.13％

    • 您已经找到了一个更好的解决方案，您已经检查过它是否可行

    对于第一个项目，CPLEX实际上并未报告差距为1.13％ . 在搜索过程中报告的差距为1.13％ .

    它返回一个应遵循默认容差的解决方案的事实证明，使用您的配方，最佳值不能低于报告的值 .

    既然您确信有更好的可行解决方案，那么您有几个选择 .

    • 尝试在开始优化之前将已知解决方案注入CPLEX . 一种方法是使用goals . 这可能有点复杂，所以你可能想...

    • 打印模型并手动评估您声明的解决方案对于您输入的约束（推荐方法）是否可行 .

    • 添加一个约束条件，即目标函数值应小于或等于您的解决方案的目标值增加少量（10e-3左右应该可以） . 如果您的解决方案适用于配方，您应该得到它，否则有一个错误，解决方案是不可行的 . 我不喜欢这种方法，因为如果有多种最佳解决方案，你可以得到有趣的结果，但通常它的工作原理） .

    总而言之，尝试调试模型并告诉我们 . 这是一个相当复杂的模型，很容易错过一些东西（即添加一个你不想添加的约束） .

    如果所有这些都失败了，你仍然发现自己想知道发生了什么，你可能想要将你的模型提交给IBM's official forum . 如果解算器中确实存在错误，他们会照顾它并让你知道 .

    我希望这有帮助

    回复于

相关问题