5

我正在尝试做一些在逻辑上应该可以做的事情。但是，我不确定如何在线性规划领域做到这一点。我正在使用 ZMPL/SCIP，但这对大多数人来说应该是可读的。

set I := {1,2,3,4,5};
param u[I] := <1> 10, <2> 20, <3> 30, <4> 40, <5> 50;

var a;
var b;

subto bval:
  b == 2;

subto works:
  a == u[2];

#subto does_not_work:
#  a == u[b];

我试图确保变量a等于b. u因此，例如，我确保b == 2然后尝试设置约束 that a == u[b]，但这不起作用。它抱怨我正在尝试使用变量进行索引。但是，我能够做到a == u[2]，这a等于20.

有没有办法u在变量指定的索引处轻松访问？感谢您的任何帮助/指导。

编辑：我认为共识是这是不可能的，因为它不再成为 LP。在这种情况下，任何人都可以想出另一种写法，以便根据 的值b，我可以从集合中获取关联的值u吗？这将不得不避免直接索引它。

解决方案：根据 Ram 的回复，我尝试了一下，发现它绝对是一个可行的线性解决方案。谢谢，拉姆！这是 ZMPL 中的示例解决方案代码：

set I := {1,2,3,4,5};
param u[I] := <1> 10, <2> 20, <3> 30, <4> 40, <5> 50;

var a;
var b;
var y[I] binary;

subto bval:
  b == 4;

subto only_one:
  sum <i> in I : y[i] == 1;

subto trick:
  b == (sum <i> in I : y[i] * i);

subto aval:
  (sum <i> in I : u[i]*y[i]) == a;
4

1 回答 1

4

是的，您可以通过引入一些额外的 0/1 变量（指标变量）来重写和线性化约束。这些技巧在整数编程中并不少见。

英语中的约束

b可以取 1 到 5 的值。b = {1..5}

并且根据 b 的值，变量a应该变成u[b]

指标变量

让我们介绍 5 个Y变量 - Y1..Y5（每个可能的 b 值一个）

在任何给定时间，其中只有一个可以为真。

 Y1 + Y2 + Y3 + Y4 + Y5 = 1
 All Y's are binary {0,1}

这是诀窍。我们引入一个线性约束以确保相应的 Y 变量将取值为 1，仅当 b 为该值时。

b - 1xY1 - 2xY2 - 3xY3 - 4xY4 - 5xY5 = 0

（例如，如果 b 为 3，则上述约束将强制 Y3 为 1。）

现在，我们想要a取值 u[b]。

 a = u[1]xY1 + u[2]xY2 + u[3]xY3 + u[4]xY4 + u[5]xY5

由于 u[1] ...u[5] 是事先已知的常数，因此上述约束也是线性的。

这是整数编程中这些 IF-THEN 条件的参考。其中许多技巧都涉及到 Big-M，尽管在这种情况下我们不需要它。

希望能帮助你前进。

于 2013-07-21T19:40:54.480 回答