A Linearization Procedure for Quadratic and Cubic Mixed-Integer Problems

Muhittin Oral and Ossama Kettani
Additional contact information
Muhittin Oral: Université Laval, Quebec, Canada
Ossama Kettani: Université Laval, Quebec, Canada

Operations Research, 1992, vol. 40, issue 1-supplement-1, S109-S116

Abstract: 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.

Keywords: mathematics; combinatorics: equivalent formulations; programming; integer: linearization (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.40.1.S109 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:40:y:1992:i:1-supplement-1:p:s109-s116

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().