将非线性编程转化为线性编程时，大M法在约束中是怎么做的？

Question

我在论文中得到了一个关于这个约束的问题。这篇论文说为了把非线性编程模型变成LP，用了大M法。我得到大数M1是一个巨大的数字，但我不明白什么大数M1 真正做到了在约束条件上。你们能不能给我讲讲这个约束条件中大数M的用法呢，下面是约束条件中大数M的用法。1.

本文说这些约束条件是when K[m][i]=p[i]*x[m][i]。

maximize sum(m in M, i in I) (K[m][i]-c[i]*x[m][i]     
K[m][i]-M[1]*(1-x[m][i]) <= p[i]
K[m][i]+M[1]*(1-x[m][i]) >= p[i]
K[m][i]-M[1]*x[m][i] <= 0

原来在非线性编程中是这样的

maximize sum(m in M, i in I)(p[i]-c[i])*x[m][i]

所以，基本上，把非线性编程转化为线性编程，导致一些决策变量发生了一点变化，多了3个大数M的约束条件。

下面是另一个包含大数M的约束条件。

sum (j in J) b[i][j]*p[j]-p[i]<= M[1]*y[i]

它原来的样子是

p[i]<sum (j in J) b[i][j]*p[j], if y[i]==1

这里是最后一个大数M的约束条件。

(r[m][j]=p[j])*b[i][j]*x[m][i] >= -y[i]*m[1]

那是

(r[m][j]-p[j])*b[i][j]*x[m][i](1-y[i])>=0 

在非线性程序中。

我真的想知道大M在模型中做什么.如果有人给我一些见解，那将是非常感激的。

谢谢你。

Answer 1

如你所说，大M法是用来建立非线性约束模型的。

K[m][i] = p[i] * x[m][i]

万一 x 是一个二进制变量。假设是 M 是一个上界，在 K[m][i] 并且 K[m][i] 是一个非负变量，即。0 <= K[m][i] <= M. 也是 p 假设为非负数。

由于 x[m][i] 是二进制的，我们可以在可行的解里有两种情况。

1. x[m][i] = 0. 在这种情况下，积 p[i] * x[m][i] 为0，因此 K[m][i] 也应该是零。这是由约束条件 K[m][i] - M * x[m][i] <= 0 这就变成了 K[m][i] <= 0. 其他两个制约因素涉及 M 在这种情况下，成为多余的。例如，第一个约束条件减少为 K[m][i] <= p[i] + M 始终是真实的，因为 M 是一个上界，在 K[m][i] 和 p 是非负数。
2. x[m][i] = 1. 在这种情况下，乘积 p[i] * x[m][i] 只是 p[i] 而涉及M的前两个约束条件变成 K[m][i] <= p[i] 和 K[m][i] >= p[i] 相当于 K[m][i] = p[i]). 最后一个约束条件涉及 M 成为 K[m][i] <= M 这是多余的，因为 M 是一个上界，在 K[m][i].

因此，在这一过程中的作用 M 的值来 "启用和禁用 "某些约束条件。x.

Answer 2

为了建立逻辑约束的模型，你可以使用逻辑约束，也可以依靠大M?

https:/www.ibm.comsupportpagesdifference-between-using-indicator-constraints-and-big-m-formulation

我倾向于建议将逻辑约束作为默认选择。

在 https:/www.linkedin.compulsehow-opl-alex-fleischer

让我来举个例子

如何在CPLEX中用布尔型决策变量乘以决策变量？

// suppose we want b * x <= 7 

    dvar int x in 2..10;
    dvar boolean b;

    dvar int bx;

    maximize x;
    subject to
    {

    // Linearization  
    bx<=7;



    2*b<=bx;
    bx<=10*b;

    bx<=x-2*(1-b);
    bx>=x-10*(1-b);

    // if we use CP we could write directly
    // b*x<=7

    // or rely on logical constraints within CPLEX
    // (b==1) => (bx==x);
    // (b==0) => (bx==0);
    }