linear-programming - 可以通过变量索引一个集合吗？

Question

我正在尝试做一些逻辑上应该可以做的事情。但是，我不确定如何在线性规划领域内做到这一点。我正在使用 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然后我尝试设置约束 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;

Answer 1

是的，您可以通过引入一些额外的 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] 是事先已知的常数，因此上述约束也是线性的。

这是 one reference关于整数规划中的这些 IF-THEN 条件。许多这些技巧都涉及到 Big-M，尽管在这种情况下我们不需要它。

希望能帮助你前进。