0

每个人。我为我的研究制定了一些公式。我想问有没有什么工具可以解决这个问题。我调查了一些工具，例如 GLPK、一些 MATLAB 工具箱……但我的公式似乎是非线性的。我在网上找到了一些资料，它是整数规划的一种特殊情况，称为 0-1 整数规划。

我的疑问是：我可以像下面的公式那样将二进制变量放在指数中吗？解决这个问题时是否可以使用“product(pi)”？我调查了一些例子，但我没有发现这两种用法。

变量是 Xc,n,m,s,i。并且，Lc,n, Tmax, Tm, Pm,s,i, Dc,n,k, Bm 都是已知数。

谁能给我一些关于这个问题的建议？谢谢阅读！

我更新了图片，并尝试将 AMPL 语言用于我的公式。

在此处输入图像描述

    #AMPL model language

    #known numbers
    param L{c in 0..C, n in 0..N}; 
    param Tmax;
    param T{m in 0..M};
    param P{m in 0..M, s in 0..S, i in 0..I};
    param D{c in 0..C, n in 0..N, k in 0..K};

    #binary variable
    var X{c in 0..C, n in 0..N, m in 0..M, s in 0..S, i in 0..I} binary;

    #objective function
    maximize answer: sum{c in 0..C} r[c];

    #two subjections
    subject to s1{s in 0..S, i in 0..I}:  
    sum{c in 0..C}sum{n in 0..N}sum{m in 0..M} X[c,n,m,s,i] <= 1; 

    subject to s2{c in 0..C, n in 0..N}: 
    L[c,n]+Tmax >= sum{m in 0..M}sum{s in 0..S}sum{i in 0..I}T[m]*X[c,n,m,s,i] >= L[c,n]; 

    #where (I am not sure is it wright to write like this? Can somebody give me a hint?)
    V[c,n]=prod{k in 0..N}(prod{m in 0..M}prod{s in 0..S}prod{i in 0..I} P[m,s,i])^X[c,n,m,s,i])^D{c,n,k};
    r[c]=prod{n in 0..N}V[c,n]*(sum{m in 0..M}sum{s in 0..S}sum{i in 0..I}T[m]*X[c,n,m,s,i]);

使用逻辑约束进行修改以从指数中删除变量 X：

    ### model_c.mod ###
    set C;
    set N;
    set M;
    set S;
    set I;
    set K;

    param Tmax;  #known numbers
    param L{c in C, n in N};
    param T{m in M};
    param P{m in M, s in S, i in I};
    param D{c in C, n in N, k in K};

    var X{c in C, n in N, m in M, s in S, i in I} binary;  #binary variable
    var Y{c in C, n in N};

    maximize answer: 
    (sum{c in C}(prod{n in N}(prod{k in K}Y[c,n]^D[c,n,k])*(sum{m in M}sum{s in S}sum{i in I}T[m]*X[c,n,m,s,i]))); #objective function

    subject to s1{c in C, n in N, m in M, s in S, i in I}: 
    Y[c,n]=Y[c,n]*((P[m,s,i]-1)*X[c,n,m,s,i]+1);

    subject to s2{s in S, i in I}: 
    sum{c in C}sum{n in N}sum{m in M} X[c,n,m,s,i] <= 1;

    subject to s3{c in C, n in N}: 
    L[c,n]+Tmax >= sum{m in M}sum{s in S}sum{i in I}T[m]*X[c,n,m,s,i] >= L[c,n];

    ### model_c.dat ###
    data;   
    set C:= count1, count2;
    set N:= frame1, frame2;
    set M:= M1, M2;
    set S:= sub1, sub2;
    set I:= i1, i2;
    set K:= k1, k2;

    param Tmax:=30;


    param L: frame1 frame2:=
    count1     2      3
    count2     4      5;


    param T:=  M1 10
       M2 20;


    param P:=
    [*,*,i1]: sub1 sub2 :=
        M1   0.9 0.8
        M2   0.7 0.6

    [*,*,i2]: sub1 sub2 :=
        M1   0.9 0.8
        M2   0.7 0.6;


    param D:=
    [*,*,k1]: frame1 frame2 :=
        count1 1 0
        count2 0 1 

    [*,*,k2]: frame1 frame2 :=
        count1 1 0
        count2 1 1;
4

2 回答 2

1

我不知道，但也许看看 SCIP 和/或 opti 工具箱。（或 YALMIP）。（或硬币。）

以我的经验，在 Matlab 中构建是相当麻烦的。也许创建一个 .lp/.mps/.whatever 输出文件并从 Matlab 启动一个解析文件的 .exe 会更容易。

于 2014-05-14T15:04:34.020 回答
1

在我看来，实际上您的模型可以在没有指数项的情况下重新表述：这些项 $P^x$ 实际上归结为一个逻辑约束，对于 $x=0$ 或 $P$ 对于 $x=1 等于 $1$美元。

所以我的建议是引入一些辅助变量 $y$ 来代替指数项，然后设置逻辑约束。

生成的模型仍然是一个巨大的 MINLP：您可能需要像 Couenne（免费）或 Baron（商业）这样的求解器。

更新：

实际上更容易说：

y_(m,s,i) = (P_(m,s,i) -1)x_(c,n,m,s,i) + 1

然后在定义 V_(c,n) 的巨大乘积中使用 y。如您所见，对于 x=0，您得到 1，对于 x=1，您得到 P。

通过这种方式，您不需要任何条件约束。

无论如何，下次我建议你在 mathoverflow 上发布这种问题。

于 2014-05-14T20:32:16.933 回答