Models and algorithms for nonlinear mixed integer problems (MINLP)

• Grant number: 13/21515-9
• Support Opportunities: Scholarships in Brazil - Doctorate
• Start date: January 01, 2014
• End date: June 30, 2017
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Marcia Aparecida Gomes Ruggiero
• Grantee: Daiane Gonçalves Ferreira
• Host Institution: Instituto de Matemática, Estatística e Computação Científica (IMECC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

Mathematical models of real problems in various areas require the optimization of a function with integer and continuous decision variables. The functions that represent the objective and the constraints can be linear (MILP: Mixed Integer Linear Programming) or nonlinear (MINLP: Mixed Integer Nonlinear Programming). The integer variables represent items that can not be fractionated, such as machinery, medical equipment, cutting patterns, professional and / or machines allocated to tasks. In decision-making problems, the formulation also involves binary variables. If the model involves only continuous variables, we have a non-linear programming problem, denoted here by NLP: Nonlinear Programming. The first procedures of resolution for MINLPs were based on solving MILP subproblems generated from the linearization of the functions involved. These subproblems allow to obtain bounds for the optimal value of the original problem which are properly used in techniques Branch-and-Bound. Clearly, this procedure is only numerically possible for small and medium sized problems. However, the growing advances in methods for solving MILP and NLP models have contributed to proposed new methods for problems with larger number of variables and constraints. MINLP problems where the functions involved are convex are easier to solve than the ones that involve non convex functions. The reason is quite simple since the relaxed version of the model, obtained by assuming that all variables are continuous, results in a nonlinear convex problems. For these convex NLP problems, a variety of exact methods can be used, such as Benders decomposition, branch-and-bound, branch-and-cut, outer approximation, among others. The aim of this work is to address problems formulated as MINLP with and without convexity assumption on the functions and we intend to develop a robust and efficient algorithm for solving these problems. The resolution process that we propose is a heuristic algorithm based on Inexact Restoration methods combined with Feasibility Pump technique. The Inexact Restoration methods were proposed for solving nonlinear problems with continuous variables. These methods involve two phases, Restoration (viability phase) and Optimality. The Feasibility Pump technique was proposed to obtain feasible solutions for optimization problems with integer variables, MILPs and MINLPs. The proposal in this work is to adapt the two phases of Inexact Restoration method in the context of problems with integer variables, MINLP, seeking advances in feasibility (Restoration phase) through the Feasibility Pump strategy. In the optimality phase, the integrality constraints will be relaxed, a merit function will be proposed and will be used in the resolution of a nonlinear problem with continuous variables. A master process should coordinate the subproblems to be solved at each stage. The final version of the algorithm employs a specific software for the various subproblems, such as MINOS and CPLEX in addition to the heuristics that will be proposed and implemented. All this computational design requires the use of suitable platforms for modeling, such as AMPL and AIMMS. The performance of the final algorithm will be analysed in a set of classical problems. After these tests, we will apply and analyze our algorithm on the resolution of MINLP models for a supply chain network design. (AU)

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

FERREIRA, Daiane Gonçalves. A hybrid heuristic for solving mixed integer nonlinear programming problems. 2017. Doctoral Thesis - Universidade Estadual de Campinas (UNICAMP). Instituto de Matemática, Estatística e Computação Científica Campinas, SP.