8

是否有可能找到最接近混合整数问题的最优解？例如，我想要下面的简化问题：

f = [1;1;1];
intcon = 1:3;

Aeq = [0.99,0.97,0.15];
beq = 0.16;
lb = zeros(3,1);
ub = [1;1;1]; 

x = intlinprog(f,intcon,[],[],Aeq,beq,lb,ub)

返回x=[0;0;1]，因为这是 的目标值最接近的整数解0.16。相反，目前它返回

Intlinprog 停止，因为没有点满足约束。

不一定要运行intlinprog。理想情况下，如果beq低也需要工作，例如0.14.

4

1 回答 1

6

您可以在需要时引入一些松弛变量以允许违反某些约束，如下所示：

largeValue = 100; % choose some large value to penalise the constraint violation
f_ = [f; largeValue; largeValue]; % penalise both slack variables
Aeq_ = [Aeq, 1, -1]; % add a positive and negative slack variable to the constraint
beq_ = beq;
lb_ = [lb; 0; 0]; % limit the constraint to a positive number
ub_ = [ub; inf; inf];

x_ = intlinprog(f_,intcon,[],[],Aeq_,beq_,lb_,ub_); % solve the adapted problem
x = x_(1:3) % extract the solution of the original problem

评论

  • 我添加了两个（正）松弛变量，一个用于正约束违规，另一个用于负约束违规。

  • 您应该以较大的值惩罚松弛变量，否则违反您的约束超过严格必要的限制是有益的。更通用的方法是根据 和 中的值确定一个好的惩罚值f，Aeq例如

    largeValue = 2*max(abs(f))/min(abs(Aeq(Aeq ~= 0)))
于 2017-07-30T10:11:34.573 回答