一类多参数混合整数线性规划问题的近似解法

摘要

约束函数矩阵是含有不确定参数的多参数混合整数线性规划问题, 由于参数对整个约束矩阵的影响不确定, 使得其很少被研究.针对这类问题, 本文应用 McCormick 松弛处理约束函数中的双线性项, 提出一种基于分支技巧与对偶理论的算法.数值实验结果表明该算法是有效的.%Because left-hand side uncertainty refers to uncertainty affecting the entries of the constraint matrices, the multi-parametric mixed integer linear programming problem with uncertain parameter in the light-hand side of the constraints remain least studied. The McCormick relaxation is used to handle the bilinear term in the constraint function, and an algorithm is proposed to address the problems. The algorithm is based on the branch technique and the dual principle. The numerical examples illustrate the effectiveness of the proposed.