IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v40y1992i1-supplement-1ps109-s116.html
   My bibliography  Save this article

A Linearization Procedure for Quadratic and Cubic Mixed-Integer Problems

Author

Listed:
  • Muhittin Oral

    (Université Laval, Quebec, Canada)

  • Ossama Kettani

    (Université Laval, Quebec, Canada)

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.

Suggested Citation

  • Muhittin Oral & Ossama Kettani, 1992. "A Linearization Procedure for Quadratic and Cubic Mixed-Integer Problems," Operations Research, INFORMS, vol. 40(1-supplem), pages 109-116, February.
    • Handle: RePEc:inm:oropre:v:40:y:1992:i:1-supplement-1:p:s109-s116
    DOI: 10.1287/opre.40.1.S109
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.40.1.S109
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.40.1.S109?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Oral, Muhittin & Kettani, Ossama & Cinar, Unver, 2001. "Project evaluation and selection in a network of collaboration: A consensual disaggregation multi-criterion approach," European Journal of Operational Research, Elsevier, vol. 130(2), pages 332-346, April.
    2. Cherif, Mohamed Sadok & Chabchoub, Habib & Aouni, Belaid, 2008. "Quality control system design through the goal programming model and the satisfaction functions," European Journal of Operational Research, Elsevier, vol. 186(3), pages 1084-1098, May.
    3. Richard J. Forrester & Warren P. Adams & Paul T. Hadavas, 2010. "Concise RLT forms of binary programs: A computational study of the quadratic knapsack problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 57(1), pages 1-12, February.
    4. Oral, Muhittin, 2010. "E-DEA: Enhanced data envelopment analysis," European Journal of Operational Research, Elsevier, vol. 207(2), pages 916-926, December.
    5. Shahzad Bhatti & Michael Lim & Ho-Yin Mak, 2015. "Alternative fuel station location model with demand learning," Annals of Operations Research, Springer, vol. 230(1), pages 105-127, July.
    6. Aouni, Belaid & Ben Abdelaziz, Foued & Martel, Jean-Marc, 2005. "Decision-maker's preferences modeling in the stochastic goal programming," European Journal of Operational Research, Elsevier, vol. 162(3), pages 610-618, May.
    7. Kharrat, Aida & Chabchoub, Habib & Aouni, Belaid & Smaoui, Soulef, 2007. "Serial correlation estimation through the imprecise Goal Programming model," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1839-1851, March.
    8. Stefan Helber & Daniel Böhme & Farid Oucherif & Svenja Lagershausen & Steffen Kasper, 2016. "A hierarchical facility layout planning approach for large and complex hospitals," Flexible Services and Manufacturing Journal, Springer, vol. 28(1), pages 5-29, June.
    9. Scott Kolodziej & Pedro Castro & Ignacio Grossmann, 2013. "Global optimization of bilinear programs with a multiparametric disaggregation technique," Journal of Global Optimization, Springer, vol. 57(4), pages 1039-1063, December.
    10. Fishburn, Peter C. & LaValle, Irving H., 1996. "Binary interactions and subset choice," European Journal of Operational Research, Elsevier, vol. 92(1), pages 182-192, July.
    11. Allouche, Mohamed Anis & Aouni, Belaïd & Martel, Jean-Marc & Loukil, Taïcir & Rebaï, Abdelwaheb, 2009. "Solving multi-criteria scheduling flow shop problem through compromise programming and satisfaction functions," European Journal of Operational Research, Elsevier, vol. 192(2), pages 460-467, January.
    12. Lakhal, Salem & Martel, Alain & Kettani, Ossama & Oral, Muhittin, 2001. "On the optimization of supply chain networking decisions," European Journal of Operational Research, Elsevier, vol. 129(2), pages 259-270, March.
    13. Crama, Y. & Pascual J., R. & Torres, A., 2004. "Optimal procurement decisions in the presence of total quantity discounts and alternative product recipes," European Journal of Operational Research, Elsevier, vol. 159(2), pages 364-378, December.
    14. Sina Abbasi & Ilias Vlachos & Shabnam Rekabi & Mohammad Talooni, 2023. "Designing the Distribution Network of Essential Items in the Critical Conditions of Earthquakes and COVID-19 Simultaneously," Sustainability, MDPI, vol. 15(22), pages 1-23, November.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:40:y:1992:i:1-supplement-1:p:s109-s116. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.