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

Document Type : conference paper

Authors

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

Abstract

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.

Keywords

Main Subjects

References

Anjos, M. F., & Vannelli, A. (2008). Computing globally optimal solutions for single-row layout problems using semidefinite programming and cutting planes. INFORMS Journal on Computing, 20(4), 611-617.
 
Bertacco, L., Fischetti, M., & Lodi, A. (2007). A feasibility pump heuristic for general mixed-integer problems. Discrete Optimization, 4(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 Computation, 2(1), 83-98.. 2(1): p. 83-98.
 
Buchberger, B. (2001). Gröbner bases and systems theory. Multidimensional systems and signal processing, 12(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 Engineering, 72, 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 engineering, 21(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 Optimization, 25, 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 Computation, 212(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 Industries, 30, 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 Optimization, 69(2), 443-459.
 
Fletcher, R., & Leyffer, S. (1994). Solving mixed integer nonlinear programs by outer approximation. Mathematical programming, 66(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 Optimization, 12(4), 1349-1366.
 
Gupta, O. K., & Ravindran, A. (1985). Branch and bound experiments in convex nonlinear integer programming. Management science, 31(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 optimization, 7(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 Systems, 63, 609-617.3.
 
Kim, S., & Kojima, M. (2017). Binary quadratic optimization problems that are difficult to solve by conic relaxations. Discrete Optimization, 24, 170-183.
 
Kirst, P., Rigterink, F., & Stein, O. (2017). Global optimization of disjunctive programs. Journal of Global Optimization, 69(2), 283-307.
       
Kraemer, K., Kossack, S., & Marquardt, W. (2007). An efficient solution method for the MINLP optimization of chemical processes. Computer Aided Chemical Engineering, 24, 105.8.
 
Lasserre, J. B. (2001). Global optimization with polynomials and the problem of moments. SIAM Journal on optimization, 11(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 Optimization, 12(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 Optimization, 12(4), 1587-1611.
 
Quesada, I., & Grossmann, I. E. (1992). An LP/NLP based branch and bound algorithm for convex MINLP optimization problems. Computers & chemical engineering, 16(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 Optimization, 32(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 production, 39, 168-179.
 
Westerlund, T., & Pettersson, F. (1995). An extended cutting plane method for solving convex MINLP problems. Computers & Chemical Engineering, 19, 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.
 

Files

History

  • Receive Date: 14 September 2018
  • Accept Date: 14 September 2018

Share

How to cite

Statistics