A LINEARIZATION PROCEDURE FOR QUADRATIC AND CUBIC MIXED-INTEGER PROBLEMS

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.