1

如何重写程序

maximize max(2x, 3y)
s.t 0 <= x, y <= 1

那么LP / MILP可以解决它吗？

我的实际目标函数是 在此处输入图像描述

我是 LP 新手，我不太了解如何使用“二元约束”。

我正在学习PuLP和GLPK。
在我的生产代码中，我将使用CPLEX或Gurobi。
这两个支持开箱即用的“最大化最大值”？

4

2 回答 2

2

“最大化最大值”本质上是非凸的。您需要在此处使用 MIP 技巧。并且您必须能够获得最大对象的下限和上限才能做到这一点。任何有限界都可以，但更清晰的界会提供更紧密的松弛，这可能会更快地解决并且在数值上更好。

假设您有以下问题，它比您给出的问题更普遍：

maximize max(3x, 2y)
s.t.  0 <= x <= A, 0 <= y <= B.

请注意，它的下界和上3x界都是微不足道的。类似地，下界为 ，上界为。现在您引入两个二进制变量和，并且您要求其中一个是。 对应于从的选择并且对应于从的选择。然后你写03A2y02Bc_1c_21c_13xmaxc_22ymax

maximize z_1 + z_2
s.t.  z_1 <= 3A c_1
      z_1 <= 3x
      z_2 <= 2B c_2
      z_2 <= 2y
      c_1 + c_2 = 1
      0 <= x <= A, 0 <= y <= B
      c_1, c_2 binary

第一个约束“关闭” z_1，因此如果最大值达到 ，它的贡献为零2y。在达到最大值的情况下，第二个约束限制z_1为。3x3x

于 2014-02-10T02:34:19.693 回答
1

如果目标是最小化，您可以使用如下辅助变量：

minimize z
s.t. z >= 2x, z >= 3y, 0 <= x, y <= 1

如果它是一个最大化，下面应该工作，其中

M是一个足够大的数字；

u_{1,2}_{1,2}是一组辅助变量，表示对 2x 和 3y 进行排序的“排列”。

maximize (z_1_2 + z_2_2)
s.t. 
z_1 = 2x
z_2 = 3y

z_1 = z_1_1 + z_1_2
z_2 = z_2_1 + z_2_2

u_1_1 + u_1_2=1
u_2_1 + u_2_2=1
u_1_1 + u_2_1=1
u_1_2 + u_2_2=1

z_1_1 <= M*u_1_1
z_1_2 <= M*u_1_2
z_2_1 <= M*u_2_1
z_2_2 <= M*u_2_2

z_1_1 + z_2_1 <= z_2_1 + z_2_2


0 <= x, y <= 1
u_{1,2}_{1,2} in {0,1}   //u_i_k are binary variables.

与 sum 不同，一堆数字的 min 和 max 不是线性形式，我认为 CPLEX 或 MILP 通常对此没有特殊形式。在这个特定示例中，较少数量的二进制辅助变量可能就足够了（而u_{1,2}_{1,2}不是你的案子最大的项目）。

于 2014-02-10T01:47:00.883 回答