標題: A NEW GLOBAL APPROACH FOR 0-1 POLYNOMIAL PROGRAMS
作者: LI, HL
交大名義發表
資訊管理與財務金融系 註:原資管所+財金所
National Chiao Tung University
Department of Information Management and Finance
公開日期: 1-Mar-1994
摘要: Given a 0-1 polynomial expression SIGMA(k=1)N-1 SIGMA(m=k+1)N x(k)x(m), where x(k) and x(m) are 0-1 variables, the famous Glover and Woolsey method required to use N(N - 1)/2 additional continuous variables and 2N(N - 1) linear constraints to transform this expression into a linear form. This paper proposes a method which first reformulates the above expression as a new expression SIGMA(k=1)N x(k)y(k), y(k) = SIGMA(m=k+1)N x(m); then to transform the expression into a linear form where x(k) and y(k) are separated. The proposed transformation method only required to use 2(N - 1) additional continuous variables and 8(N - 1) linear constraints. Based on the new transformation, a 0-1 polynomial program can be more effectively solved to obtain a global optimum.
URI: http://hdl.handle.net/11536/2603
ISSN: 0305-0548
期刊: COMPUTERS & OPERATIONS RESEARCH
Volume: 21
Issue: 3
起始頁: 319
結束頁: 327
Appears in Collections:Articles