Titolo della tesi: Multiobjective integer and mixed-integer nonlinear programming: exact approaches and applications
Multiobjective optimization comes into play in many real world problems, e.g. finance, production planning, biology, medical imaging, transportation. Some of these applications require to include integer variables in the optimization model, in order to give a proper description of the problem. Thus, multiobjective integer and mixed integer optimization comes into play.
This thesis presents new exact approaches and applications in the field of multiobjective integer optimization. First of all, we present new theoretical results about the ε-constraint algorithm for biobjective nonlinear integer programming problems. It can be shown that, when certain assumptions are satisfied, the algorithm is able to retrieve the complete Pareto frontier.
Then, we leverage this theoretical result for building a biobjective model, used for solving the industrial problem that we named ''Best Allocation of Resource Size''. The problem consists of determining which set of item sizes or volumes to choose in order to carry out the production of certain products, likewise having certain sizes or volumes. This is done by analyzing the trade-off between the number of items chosen and a cost function, consisting of different cost factors, e.g. purchase cost and stock cost. More specifically, the solutions of the biobjective integer optimization problem are retrieved by means of the ε-constrained method and examined under an industrial point of view.
Then, the results concerning the exactness of the ε-constraint method for biobjective problems are extended to the triobjective case. In particular, an exact method able to retrieve all the nondominated points of triobjetive integer nonlinear optimization problems is devised. Such algorithm, named TrIntOpt, is then used to solve linear and nonlinear triobjective problems in order to determine sustainable and nutritionally adequate diet plans for elementary school cantines. More specifically, the model determines a five days lunch menu by taking into account constraints regarding nutritional factors and attractiveness, while minimizing the carbon dioxide, water and nitrogen footprint.
Finally, we also propose an algorithm for finding an approximation of the nondominated set of multiobjective mixed-integer convex quadratic optimization problems. The devised branch-and-bound algorithm, named DEIA-BB, solves dual formulations for computing linear outer approximations of subproblems at the nodes of the branch-and-bound tree, where the values of certain integer variables are fixed.
The pruning conditions defined and a tailored preprocessing phase allow the nodes to be quickly enumerated.
In addition to the enclosure of the nondominated set, DEIA-BB also returns a superset of the efficient assignments for the integer variables.