A LINEARIZATION PROCEDURE FOR QUADRATIC AND CUBIC MIXED-INTEGER PROBLEMS
成果类型：
Article
署名作者：
ORAL, M; KETTANI, O
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.40.1.S109
发表日期：
1992
页码：
S109-S116
关键词：
摘要：
Several techniques of linearization have appeared in the literature. The technique of F. Glover, which seems to be the most efficient, linearizes a binary quadratic integer problem of n variables by introducing n new continuous variables and 4n auxiliary linear constraints. The new technique proposed in this paper is not only useful in linearizing binary quadratic and cubic integer problems, but also applicable to the case of quadratic and to a certain class of cubic mixed-integer problems. It is shown that the new technique further reduces the number of auxiliary linear constraints from 4n to n, while keeping the number of new continuous variables at n for the binary quadratic integer problem of n variables. And, it requires, in the case of a certain class of cubic mixed-integer problems having 2n of 0-1 variables, only 3n auxiliary linear constraints and the same number of new continuous variables. The analytical superiority of the new linearization technique has also been observed, in terms of the number of iterations and execution times, through a computational experiment conducted on a set of randomly generated binary quadratic integer problems.