这可以用混合整数线性规划来形式化吗？
我正在尝试解决一个问题，其中有一组对象需要在特定时间在不同的点之间移动。
我已经能够将线性规划中的大多数约束形式化，即：
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...“创建不同的线性问题。语句，但是有60ish的伴随路径和10ish的伴随对象，这将导致10^60个线性程序需要求解，这是不好的。
如果有人对如何形式化这个线性规划问题有任何直觉，以便“X将伴随Y?”可以在问题本身中表达出来，我将非常感激！
回答 2
Stack Overflow用户
发布于 2012-01-10 15:49:00
是的，您可以修改公式以处理您的约束。有许多涉及"Big-M“和新的0-1的标准技巧来实现这一点。(韩的回应恰如其分地暗示了这一点。)
为了适应特定的非线性约束，您需要引入新的0-1变量(如"GoWith“变量)，然后在公式中添加额外的线性约束。
让我们看看你声明的需求：如果对象2伴随着对象1，它将在时间X离开对象1，并在时间Y到达
Start1 >= X
Arrive1 <= Y 是您对Object 1已有的约束。
让我们引入二进制变量 Z12 ，如果Object2与Object1一起旅行，它是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
Stack Overflow用户
发布于 2011-12-22 04:16:50
一种方法是使用big-M方法，如下所示：
object1FirstDepartureTime - object2FirstDepartureTime > -M * object2GoWIthObject1
object1FirstDepartureTime - object2FirstDepartureTime < M * object2GoWIthObject1M是一个足够大的常数。big-M方法的问题是它导致了很差的LP松弛。
https://stackoverflow.com/questions/8473107
复制相似问题
腾讯云开发者
