这可以用混合整数线性规划来形式化吗？-Java 学习之路

我试图解决一个问题，其中有一组对象需要在特定时间点之间移动 .

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

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？”的决定 . 可以在问题本身表达，我非常感激！

2 回答

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

为了适应您的特定非线性约束，您将引入新的0-1变量（如"GoWith"变量），然后在您的配方中添加额外的线性约束 .

让我们按照您的要求： If object 2 accompanies object 1, it will depart at time X with object 1 and arrive at time Y
```
Start1 >= X 
Arrive1 <= Y
```
是对象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等，您可以在一个线性公式中处理所有约束 .

更多"tricks"用于IP配方可在以下网址找到：http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/new15.pdf
回复于 2024-05-05T03:55:17+08:00

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

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

M是足够大的常数 . big-M方法的问题在于它导致LP松弛不良 .

回复于 2024-05-05T03:55:17+08:00

这可以用混合整数线性规划来形式化吗？

2 回答

相关问题