解二次背包问题的一个线性化方法
|
摘要
讨论了二次背包问题(QKP)的一种线性化方法.利用文献中的相关结论,通过增加变量和线性约束,将(QKP)的二次0-1规划模型等价转化为一个线性混合整数规划模型,再利用计算线性混合整数规划的软件(如Ilog-cplex或Lingo)求解,从而解决原问题.对所构造问题实例的计算,验证了求解(QKP)方法的有效性.
In this paper,the linearization method for the Quadratic knapsack problem(QKP)was discassed.Using the relevant conclusions in the literature,the linearization strategies are to reformulate the quadratic 0-1programming model as equivalent linear mixed integer programming model by additional variables and linear constraints,and then calculated using linear mixed integer programming software(such as Ilog-cplex or Lingo)to solve,so as to solve the original problem.The numerical example is also presented to show that the proposed method for(QKP)is very efficient.
In this paper,the linearization method for the Quadratic knapsack problem(QKP)was discassed.Using the relevant conclusions in the literature,the linearization strategies are to reformulate the quadratic 0-1programming model as equivalent linear mixed integer programming model by additional variables and linear constraints,and then calculated using linear mixed integer programming software(such as Ilog-cplex or Lingo)to solve,so as to solve the original problem.The numerical example is also presented to show that the proposed method for(QKP)is very efficient.
引文
[1]GALLO G,HAMMER P L,SIMEONE B.Quadratic knapsack problems[J].Mathematical programming,1980,12:132-149.
[2]MICHELON P,VEILLEUX L.Lagrangean methods for the 0-1quadric knapsack problem[J].European Journal of Operational Research,1996,92:326-341.
[3]BILLIONNET A,FAYE A,SOUTIF E.A new upper bound for the 0-1quadratic knapsack problem[J].European Journal of Operational Research,1999,112:664-672.
[4]CAPRARA A,PISINGER D,TOTH P.Exact solution of the quadratic knapsack problem[J].INFORMS Journal on Computing,1999,11:125-137.
[5]GLOVER F,WOOLSEY E.Converting the 0-1polynomial programming problem to a 0-1linear program[J].Operations Research,1974,22(1):180-182.
[6]BILLIONNET A,CALMELS F.Linear programming for the 0-1quadratic knapsack problem[J].European Journal of Operational Research,1996,92:310-325.
[7]CHAOVALITWONGSE W,PARDALOS P M,PROKOPYEV O A.A new linearization technique for multi-quadratic 0-1programming problems[J].Operations Research Letters,2004,32:517-522.
[8]SHERALI H D,SMITH J C.An improved linearization strategy for zero-one quadratic programming problems[J].Optimization Letters,2007(1):33-47.
[9]任燕,陈伟.对带有盒约束的二次整数规划的一种线性化方法[J].运筹学学报,2010,14(1):66-75.
[2]MICHELON P,VEILLEUX L.Lagrangean methods for the 0-1quadric knapsack problem[J].European Journal of Operational Research,1996,92:326-341.
[3]BILLIONNET A,FAYE A,SOUTIF E.A new upper bound for the 0-1quadratic knapsack problem[J].European Journal of Operational Research,1999,112:664-672.
[4]CAPRARA A,PISINGER D,TOTH P.Exact solution of the quadratic knapsack problem[J].INFORMS Journal on Computing,1999,11:125-137.
[5]GLOVER F,WOOLSEY E.Converting the 0-1polynomial programming problem to a 0-1linear program[J].Operations Research,1974,22(1):180-182.
[6]BILLIONNET A,CALMELS F.Linear programming for the 0-1quadratic knapsack problem[J].European Journal of Operational Research,1996,92:310-325.
[7]CHAOVALITWONGSE W,PARDALOS P M,PROKOPYEV O A.A new linearization technique for multi-quadratic 0-1programming problems[J].Operations Research Letters,2004,32:517-522.
[8]SHERALI H D,SMITH J C.An improved linearization strategy for zero-one quadratic programming problems[J].Optimization Letters,2007(1):33-47.
[9]任燕,陈伟.对带有盒约束的二次整数规划的一种线性化方法[J].运筹学学报,2010,14(1):66-75.