Global optimization of mixed-integer polynomial programming problems: A new method based on Grobner Bases theory

Document Type : conference paper


School of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran


Mixed-integer polynomial programming (MIPP) problems are one class of mixed-integer nonlinear programming (MINLP) problems where objective function and constraints are restricted to the polynomial functions. Although the MINLP problem is NP-hard, in special cases such as MIPP problems, an efficient algorithm can be extended to solve it. In this research, we propose an algorithm for global optimization of the MIPP problems, in which, first, the MIPP is reformulated as a multi-parametric programming by considering integer variables as parameters. Then, the optimality conditions of resulting parametric programming give a parametric polynomial equations system (PES) that is solved analytically by Grobner Bases (GB) theory. After solving PES, the parametric optimal solution as a function of the relaxed integer variables is obtained. A simple discrete optimization problem is resulted for any non-imaginary parametric solution of PES, which the global optimum solution of MIPP is determined by comparing their optimal value. Some numerical examples are provided to clarify proposed algorithm and extend it for solving the MINLP problems. Finally, a performance analysis is conducted to demonstrate the practical efficiency of the proposed method.


Main Subjects

Anjos, M. F., & Vannelli, A. (2008). Computing globally optimal solutions for single-row layout problems using semidefinite programming and cutting planes. INFORMS Journal on Computing20(4), 611-617.
Bertacco, L., Fischetti, M., & Lodi, A. (2007). A feasibility pump heuristic for general mixed-integer problems. Discrete Optimization4(1), 63-76.
Boege, W., Gebauer, R., & Kredel, H. (1986). Some examples for solving systems of algebraic equations by calculating Groebner bases. Journal of Symbolic Computation2(1), 83-98.. 2(1): p. 83-98.
Buchberger, B. (2001). Gröbner bases and systems theory. Multidimensional systems and signal processing12(3-4), 223-251.
Cafaro, V. G., Cafaro, D. C., Méndez, C. A., & Cerdá, J. (2015). MINLP model for the detailed scheduling of refined products pipelines with flow rate dependent pumping costs. Computers & Chemical Engineering72, 210-221.2.   
Cardoso, M. F., Salcedo, R. L., de Azevedo, S. F., & Barbosa, D. (1997). A simulated annealing approach to the solution of MINLP problems. Computers & chemical engineering21(12), 1349-1364.
Chang, Y. J., & Wah, B. W. (1994, November). Polynomial programming using groebner bases. In Computer Software and Applications Conference, 1994. COMPSAC 94. Proceedings., Eighteenth Annual International (pp. 236-241). IEEE.
Crama, Y., & Rodríguez-Heck, E. (2017). A class of valid inequalities for multilinear 0–1 optimization problems. Discrete Optimization25, 28-47.
Deep, K., Singh, K. P., Kansal, M. L., & Mohan, C. (2009). A real coded genetic algorithm for solving integer and mixed integer optimization problems. Applied Mathematics and Computation212(2), 505-518.
de Lira-Flores, J., Vázquez-Román, R., López-Molina, A., & Mannan, M. S. (2014). A MINLP approach for layout designs based on the domino hazard index. Journal of Loss Prevention in the Process Industries30, 219-227.
Eronen, V. P., Kronqvist, J., Westerlund, T., Mäkelä, M. M., & Karmitsa, N. (2017). Method for solving generalized convex nonsmooth mixed-integer nonlinear programming problems. Journal of Global Optimization69(2), 443-459.
Fletcher, R., & Leyffer, S. (1994). Solving mixed integer nonlinear programs by outer approximation. Mathematical programming66(1-3), 327-349.
Goemans, M. X., & Williamson, D. P. (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM)42(6), 1115-1145.
Gu, J., Xiao, X., & Zhang, L. (2016). A subgradient-based convex approximations method for DC programming and its applications. Journal of Industrial & Management Optimization12(4), 1349-1366.
Gupta, O. K., & Ravindran, A. (1985). Branch and bound experiments in convex nonlinear integer programming. Management science31(12), 1533-1546.
Hägglöf, K., Lindberg, P. O., & Svensson, L. (1995). Computing global minima to polynomial optimization problems using Gröbner bases. Journal of global optimization7(2), 115-125.
Kaur, S., Kumbhar, G., & Sharma, J. (2014). A MINLP technique for optimal placement of multiple DG units in distribution systems. International Journal of Electrical Power & Energy Systems63, 609-617.3.
Kim, S., & Kojima, M. (2017). Binary quadratic optimization problems that are difficult to solve by conic relaxations. Discrete Optimization24, 170-183.
Kirst, P., Rigterink, F., & Stein, O. (2017). Global optimization of disjunctive programs. Journal of Global Optimization69(2), 283-307.
Kraemer, K., Kossack, S., & Marquardt, W. (2007). An efficient solution method for the MINLP optimization of chemical processes. Computer Aided Chemical Engineering24, 105.8.
Lasserre, J. B. (2001). Global optimization with polynomials and the problem of moments. SIAM Journal on optimization11(3), 796-817.23.        
Li, J., Yu, N., Liu, Z., & Shu, L. (2016). Optimal rebate strategies in a two-echelon supply chain with nonlinear and linear multiplicative demands. Journal of Industrial & Management Optimization12(4), 1587-1611.
Li, J., Yu, N., Liu, Z., & Shu, L. (2016). Optimal rebate strategies in a two-echelon supply chain with nonlinear and linear multiplicative demands. Journal of Industrial & Management Optimization12(4), 1587-1611.
Quesada, I., & Grossmann, I. E. (1992). An LP/NLP based branch and bound algorithm for convex MINLP optimization problems. Computers & chemical engineering16(10-11), 937-947.
Sherali, H. D., & Desai, J. (2005). A global optimization RLT-based approach for solving the hard clustering problem. Journal of Global Optimization32(2), 281-306.
Su, L., L. Tang, and I.E. Grossmann, Computational strategies for improved MINLP algorithms. Computers & Chemical Engineering, 2015. 75: p. 40-48.
Tokos, H., Pintarič, Z. N., & Yang, Y. (2013). Bi-objective optimization of a water network via benchmarking. Journal of cleaner production39, 168-179.
Westerlund, T., & Pettersson, F. (1995). An extended cutting plane method for solving convex MINLP problems. Computers & Chemical Engineering19, 131-136.
Yan, L., K. Shen, and S. Hu, Solving mixed integer nonlinear programming problems with line-up competition algorithm. Computers & chemical engineering, 2004. 28(12): p. 2647-2657.