1

我试图了解 CPLEX 中指标约束的使用。我已指定要在 CPLEX Interactive Optimizer 中解决的简单整数规划问题。由于各种原因,我无法使用任何 CPLEX API 来完成此任务。

真正的问题是一个简单的最大覆盖集问题,但有大量变量。有许多类型的 THING,它们可以在一个或多个 BOXES 中找到。我想在我的解决方案中最大化 THING 类型的数量,同时将 BOXES 的数量保持在一个约束之下。所有变量都是二进制文件。

真正的问题显然要大得多。我在这里制作了一个简单的版本,限制为 3 BOXES。

MAXIMIZE
obj: THING1 + THING2 + THING3 + THING4 + THING5 + THING6 + THING7 + THING8 + THING9 + THING10
SUBJECT TO
nboxes: BOX1 + BOX2 + BOX3 + BOX4 + BOX5 + BOX6 <=3
box1_indicator: BOX1 = 1 -> THING1 + THING2 + THING3 = 3
box2_indicator: BOX2 = 1 -> THING4 + THING5 + THING6 = 3
box3_indicator: BOX3 = 1 -> THING7 + THING8 + THING9 = 3
box4_indicator: BOX4 = 1 -> THING10 + THING1 = 2
box5_indicator: BOX5 = 1 -> THING1 + THING5 + THING9 + THING10 = 4
box6_indicator: BOX6 = 1 -> THING3 + THING4 = 3
thing1_indicator: THING1 = 1 -> BOX1 + BOX4 + BOX5 >=1
thing2_indicator: THING2 = 1 -> BOX1 >=1
thing3_indicator: THING3 = 1 -> BOX1 + BOX6 >=1
thing4_indicator: THING4 = 1 -> BOX2 + BOX6 >=1
thing5_indicator: THING5 = 1 -> BOX2 + BOX5 >=1
thing6_indicator: THING6 = 1 -> BOX2 >=1
thing7_indicator: THING7 = 1 -> BOX3 >=1
thing8_indicator: THING8 = 1 -> BOX3 >=1
thing9_indicator: THING9 = 1 -> BOX3 + BOX5 >=1
thing10_indicator: THING10 = 1 -> BOX4 + BOX5 >=1

BINARIES
THING1
THING2
THING3
THING4
THING5
THING6
THING7
THING8
THING9
THING10
BOX1
BOX2
BOX3
BOX4
BOX5
BOX6

END

我的第一个问题是:这种仅使用指标约束的问题表述是否有效?在我的真实示例中,它可以愉快地与 CPLEX 一起运行,我还没有发现它会产生意想不到的解决方案。回答这个问题是以下问题的先决条件。

我的第二个问题是:我想引入一个约束,我只想要对 THING1 进行两次采样的解决方案。我替换了指标约束

   thing1_indicator: THING1 = 1 -> BOX1 + BOX4 + BOX5 >=1

   thing1_indicator: THING1 = 1 -> BOX1 + BOX4 + BOX5 >=2

在我真正的问题中,这个约束的 RHS 似乎被忽略了。CPLEX 毫无怨言地读取和优化,返回的解决方案将 THING1 的值设为 1,但(例如)将具有 BOX1 = 1、BOX4 = 0、BOX5 = 0。

这让我担心要么我完全错过了在 LP 格式程序中使用指标约束的要点,要么是处理指标约束的优先级导致了这个问题。

我想到的另一件事是 CPLEX 的预求解例程可能会在某处删除约束,但我认为在深入研究预求解输出之前我会检查明显的情况。

4

1 回答 1

1

您可以将这些写为可以由 cplex 处理的线性约束。约束 box1_indicator 可以写成

box1_indicator: THING1 + THING2 + THING3 - 3 * BOX1 >= 0

如果 BOX1 为 1,则约束变为THING1 + THING2 + THING3 >= 3并且只有当总和恰好为 3 时才能满足。如果 BOX1 为零,则约束变为THING1 + THING2 + THING3 >= 0始终为真。

同样地

thing1_indicator: BOX1 + BOX4 + BOX5 - THING1 >= 0
于 2013-09-22T20:32:19.743 回答