GIUV2013-049
Our group's research focuses on the development of models and algorithms for the optimisation of different Combinatorial Optimisation problems. These problems appear naturally in manufacturing processes, logistics, service localisation, activity planning, etc., and are characterised by wanting to optimise one or more objectives from a large number of solutions that grows exponentially with the size of the problem. It is, therefore, necessary for the decision-maker to have efficient algorithms to help in making decisions. However, the possible contributions we can make in the area of mathematical programming are also important.From a mathematical point of view, the optimisation problems posed are all difficult Combinatorial Optimisation problems. Given their combinatorial nature, solving these problems presents great difficulty. This is reflected in the fact that they belong to the NP-Hard category. As regards solving them, this means that unless P=NP, which seems highly unlikely, there will be no algorithms that guarantee that optimal solutions can be obtained in polynomial time in the size of the problems. However, the economic and social implications of decisions based on the...Our group's research focuses on the development of models and algorithms for the optimisation of different Combinatorial Optimisation problems. These problems appear naturally in manufacturing processes, logistics, service localisation, activity planning, etc., and are characterised by wanting to optimise one or more objectives from a large number of solutions that grows exponentially with the size of the problem. It is, therefore, necessary for the decision-maker to have efficient algorithms to help in making decisions. However, the possible contributions we can make in the area of mathematical programming are also important.From a mathematical point of view, the optimisation problems posed are all difficult Combinatorial Optimisation problems. Given their combinatorial nature, solving these problems presents great difficulty. This is reflected in the fact that they belong to the NP-Hard category. As regards solving them, this means that unless P=NP, which seems highly unlikely, there will be no algorithms that guarantee that optimal solutions can be obtained in polynomial time in the size of the problems. However, the economic and social implications of decisions based on the optimisation of these problems require exact solving methods to be designed that provide solutions and whose optimality can be shown in acceptable computation times. Given the dimensions of the instances that are usually posed in practice, this is only possible through a thorough study of both the structure and properties of these problems. To carry out this analysis, it is often necessary to resort to techniques that are typical of polyhedral combinatorics, such as the study of the polyhedra that characterize the sets of solutions to problems, as well as techniques for separating valid inequalities. Characterising the polyhedra associated with these problems is one of the fields of greatest relevance and technical difficulty in mathematical programming. Metaheuristic procedures are a category of approximate methods that are designed to solve difficult optimisation problems, in which classic heuristics are not effective. Metaheuristics provide a general framework for creating new hybrid algorithms combining different concepts derived from artificial intelligence (tabu search), biological evolution (evolutionary algorithms) and statistical mechanisms (simulated tempering).We have worked on numerous optimisation problems, both in the academic field and in industrial applications, for which we have designed efficient problem-solving methods based on these methods. We develop heuristic methods to solve difficult optimisation problems. We basically address two types of problems: those for which the restrictions and the objective to be optimised are explicitly known (type 1) and those that we will call "with partial information" in which the description of the problem is not explicit and some of its elements (objective function or restrictions) are obtained indirectly (type 2). In the first type, knowledge about the characteristics of the problem is exploited to design specific problem-solving methods. In the second type generic optimisation methods applicable to large families of problems are proposed. To this end, we are working on the design of a generic procedure that allows us to extract information on certain attributes of the problem during the search process and, using artificial intelligence techniques, we will exploit this information to find the best possible solution.
[Read more][Hide]
[Read more][Hide]
- Modelos y algoritmos para problemas de optimizacion combinatoria
- Models and algorithms for combinatorial optimization problems.Development of models and algorithms for combinatorial optimisation problems.
| Name | Nature of participation | Entity | Description |
|---|---|---|---|
| RAFAEL MARTI CUNQUERO | Director | Universitat de València | |
| Research team | |||
| ISAAC PLANA ANDANI | Member | Universitat de València | |
| JOSE MARIA SANCHIS LLOPIS | Collaborator | Universitat Politècnica de València | tenured university professor |
- -
- -
- Statistics and Operational Research
- Optimización, algoritmos
