Many real-world problems in the areas of Applied Sciences, Engineering and Economics, are modeled involving integer and 0-1 variables, in order to reflect discrete quantities, logical relationships or decisions.
When nonlinear functions are necessary to model the
nonlinear context of the problem, we are in the field of
Mixed-Integer Nonlinear Programming (MINLP).
MINLP problems combine all the difficulties of both Mixed Integer Programs (MIP) and NonLinear Programs (NLP), which are among the class of theoretically difficult problems (NP-complete).
Therefore, the design of efficient solution methods for MINLP problems is a big challenge for people working in Operations Research.
The research activity will be devoted to
- the study and the definition of new optimization methodologies to deal with specific combinatorial and MINLP problems,
- the definition and the use of new algorithms for handling real-world revenue management problems.
The challenging nature of mixed integer programming problems increasingly calls for
- the definition of new ways to compute bounds on the solution,
- the development of efficient and easy-to-use solution methods.
From the methodological point of view, the research activity will be carried out along the following new approaches:
- MINLPs with special structure in either the objective function and/or the constraints.
A key feature to define efficient branch-and-bound methods for this class of problems is to solve appropriate optimization problems for the computation of bounds on the solution.
Similarly to what has been done in [5, 8, 12], we plan to study specific continuous relaxation of the original problem that should be efficiently solved to global optimality by an ad-hoc
defined optimization algorithm. The smart combination of this optimization algorithm with a suitably defined enumeration strategy should lead to the definition of effective branch-and-bound algorithms.
- Maximum clique problem.
Starting from a nonconvex continuous formulation of the problem, we plan to study and define new ways to compute bounds on the solution, based both on relaxing the feasible set and on modifying the objective function. By implementing the approaches defined, we will have an insight on the efficiency of the bounds proposed.
- Revenue Management problems.
Starting from a known formulation, that is the state of art for Network-Based Revenue Management problems (see [16]), we plan to investigate new formulations based on decomposition with the aim of solving hard instances of Sales Based Integer Program. The main idea would be to optimally allocate the capacity to the markets by transforming the market subproblems into a piecewise linear objective function. We should get advantages from a significant reduction of the problem size and the possibility of deriving a concave objective function as an approximation.
- Penalty approaches for defining new easier-to-handle subproblems.
The idea of lifting the violation of (some of) the continuous constraints within the objective function has been recently used in the context of integer nonconvex quadratic programming problems with linear equality constraints [4]. Being inspired by the classical penalty approaches in the nonlinear context, our aim is that of defining exact reformulations that could be more efficiently handled from a practical point of view.
For the references: See "Descrizione delle attività e dei compiti dei partecipanti"