An efficient linearization approach for mixed-integer problems. (English) Zbl 0982.90034

Summary: M. Oral and O. Kettani previously developed a linearization technique [Management Sci. 36, 115-119 (1990; Zbl 0694.90073) and Oper. Res. 40, S109–S116 (1992; Zbl 0771.90072)] for solving quadratic and cubic mixed-integer problems. For a quadratic problem with \(n\) 0-1 variables, their method would introduce \(n\) additional continuous variables and \(n\) auxiliary constraints. For a cubic problem with \(n\) 0-1 variables, their method would introduce \(3n\) additional continuous variables and \(3n\) auxiliary constraints. This linearization approach of Oral and Kettani has been accepted as the most efficient linearization technique published, requiring the least number of additional continuous variables and auxiliary constraints. However, their method is difficult to extend for linearizing higher order polynomial terms that appear in mixed-integer problems, and in addition, all constraints should be kept as linear. This note proposes a new general model for linearizing various orders of mixed-integer problems which cannot be solved by Oral and Kettani’s model when the order is higher than three. Some computational results show that the proposed model is more efficient than Oral-Kettani’s method because it uses less additional variables and auxiliary constraints to linearize the same size of mixed-integer problems. In addition, the proposed model can be easily applied to polynomial mixed-integer terms that appear in the objective function and/or constraints.


90C11 Mixed integer programming


Full Text: DOI


[2] Glover, F.; Woolsey, E., Converting the 0-1 polynomial programming problem to a 0-1 linear program, Operations Research, 22, 180-182 (1974) · Zbl 0272.90049
[3] Glover, F., Improved linear integer programming formulations of nonlinear integer problems, Management Science, 2, 455-460 (1975) · Zbl 0318.90044
[4] Glover, F., An improved MIP formulation for products of discrete and continuous variables, Journal of Information and Optimization Sciences, 5, 69-71 (1984) · Zbl 0534.90065
[5] Kettani, O.; Oral, M., Equivalent formulations of nonlinear integer problems for efficient optimization, Management Science, 36, 115-119 (1990) · Zbl 0694.90073
[6] Li, H. L.; Chang, C. T., An approximate approach of global optimization for polynomial programming problems, European Journal of Operational Research, 107, 625-632 (1998) · Zbl 0943.90079
[7] Løkketangen, A.; Glover, F., Tabu search for zero/one mixed integer programming with advanced level strategies and learning, International Journal of Operations and Quantitative Management, 1, 89-108 (1995)
[8] Løkketangen, A.; Glover, F., Solving zero-one mixed integer programming problems using tabu search, European Journal of Operational Research, 106, 624-658 (1998) · Zbl 0991.90091
[10] Oral, M.; Kettani, O., A Linearization procedure for quadratic and cubic mixed-integer problem, Operations Research, 40, 109-116 (1992)
[11] Sherali, H. D.; Tuncbilek, C. H., A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique, Journal of Global Optimization, 2, 101-112 (1992) · Zbl 0787.90088
[12] Sherali, H. D.; Adams, W. P.; Driscoll, P. J., Exploiting special structures in constructing a hierarchy of relaxations for 0-1 mixed integer problems, Operations Research, 46, 396-405 (1998) · Zbl 0979.90090
[13] Water, L. J., Reduction of integer polynomial programming problems to zero-one linear programming problems, Operations Research, 15, 1171-1174 (1967)
[14] Zangwill, W. I., Media selection by decision programming, Journal of Advertising Research, 5, 30-36 (1965)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.