Matlab 中的混合整数最近最优解
Mixed-Integer Nearest Optimal Solution in Matlab
是否可以找到最接近混合整数问题的最优解?例如,我想要下面的简化问题:
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)
到 return x=[0;0;1]
因为这是 0.16
的 objective 值最接近的整数解。相反,目前 returns
Intlinprog stopped because no point satisfies the constraints.
不一定要运行intlinprog
。如果 beq
较低,则理想情况下也需要工作,例如 0.14
.
您可以引入一些松弛变量以允许在需要时违反约束,如下所示:
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)))
是否可以找到最接近混合整数问题的最优解?例如,我想要下面的简化问题:
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)
到 return x=[0;0;1]
因为这是 0.16
的 objective 值最接近的整数解。相反,目前 returns
Intlinprog stopped because no point satisfies the constraints.
不一定要运行intlinprog
。如果 beq
较低,则理想情况下也需要工作,例如 0.14
.
您可以引入一些松弛变量以允许在需要时违反约束,如下所示:
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)))