2

我正在尝试解决一个问题，即有一组对象需要在特定时间在各个点之间移动。

我已经能够在线性规划方面形式化大多数约束，即：

object1FirstDepartureTime > X
object1FirstArrivalTime < Y
object1FirstArrivalTime - object1FirstDepartureTime > Z
object1SecondDepartureTime - object1FirstArrivalTime > A

对于所有对象及其所有到达/离开，依此类推。目标函数将是在运输中花费最少或最多的时间。

我遇到的问题是一个额外的限制：某些物体在旅行期间需要由其他物体陪伴。例如，object1 可以伴随 object2、object3 或 object4。这些对象本身具有一定的到达或离开限制。我想让我的（也许是混合整数）线性程序负责拾取伴随的对象。但是在尝试将其形式化时，我无法找到一种保持线性的方法。我想到了混合整数约束，例如

object2GoWIthObject1 + object3GoWithObject1 + object4GoWithObject1 < 2
object2GoWIthObject1, object3GoWithObject1, object4GoWithObject1 are all less than 2
object2GoWIthObject1, object3GoWithObject1, object4GoWithObject1 are all integers

但我不知道如何表达诸如“如果对象 2 伴随对象 1，它将在时间 X 与对象 1 离开并在时间 Y 到达”之类的约束。这似乎是非线性的，因为我会将布尔变量（如果对象 2 伴随对象 1）乘以旅行时间。

当然，我可以为每个“if...then...”语句创建不同的线性问题，但是有 60 个伴随路径和 10 个伴随对象，这将导致 10^60 个线性程序要解决，这不是好的。

如果有人对如何形式化这个线性规划问题有任何直觉，以便做出“X 会伴随 Y”的决定吗？可以用问题本身来表达，我将不胜感激！

4

2 回答 2

2

是的，您可以修改公式来处理您的约束。有许多涉及“Big-M”和新 0-1 的标准技巧来实现这一点。（韩的回答正确地表明了这一点。）

为了适应您的特定非线性约束，您将引入新的 0-1 变量（如您的“GoWith”变量），然后在您的公式中添加额外的线性约束。

让我们按照您的要求：如果对象 2 伴随对象 1，它将在时间 X 与对象 1 离开并在时间 Y 到达

Start1 >= X 
Arrive1 <= Y

是对象 1 已有的约束。

让我们引入二进制变量Z12，如果 Object2 与 Object1 一起旅行，则 Z12 为 1，否则 Z12 = 0。

所以，

If Z12 = 1, then Start2 > X
If Z12 = 1 then Arrive2 < Y

我们可以将其重写为：

Start2 - X >= 0 if Z12 =1
Start2 - X >= -M if Z12 =0, where M is a large number.

将它们组合成一个线性约束：

Start2 - X >= M(Z12-1)

当 Z12 为 1 时，此约束是有约束力的，否则很容易满足。

同样，为了使 Object2 的到达与 Object1 的到达相匹配，您可以编写：

Arrive2 < Y if Z12=1
Arrive2 < M if Z12=0

变成

Arrive2 < Y + M(1-Z12), a linear constraint.

通过类似地引入二进制变量 Z13、Z14 等，您可以在一个线性公式中处理所有约束。

更多用于 IP 制定的“技巧”可在以下网址找到： http ://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/new15.pdf

于 2012-01-10T07:48:59.790 回答
0

一种方法是像这样使用 big-M 方法：

object1FirstDepartureTime - object2FirstDepartureTime > -M * object2GoWIthObject1
object1FirstDepartureTime - object2FirstDepartureTime < M * object2GoWIthObject1

M 是一个足够大的常数。big-M 方法的问题在于它会导致较差的 LP 松弛。

于 2011-12-21T20:16:49.540 回答