67. Ordered interactions in combinatorial problems
Invited abstract in session TD-1: Data structures, stream Data structures.
Thursday, 14:30 - 16:00Room: L226
Authors (first author is the speaker)
| 1. | Alberto Torrejón Valenzuela
|
| Department of Statistics and Operations Research, University of Seville | |
| 2. | Justo Puerto
|
| Estadistica e I.O., Universidad de Sevilla | |
| 3. | Víctor Blanco
|
| Institute of Mathematics, Universidad de Granada |
Abstract
The application of ordered optimisation approaches to combinatorial problems has been widely studied in the literature. Examples of problems which involve straightforward sorting procedures are the well-known ordered location problems, ordered weighted average problems or ordered hub location problems, but it also covers other disciplines such as voting problems, portfolio optimisation, outlier detection or machine learning, among others.
The ordered description of these problems usually relies on a vector of weights that multiplies the ordered costs in the objective function. However, the range of problems that can be studied within an ordered framework is limited to the linearity of such models. By means of a quadratic approach to ordered optimisation, considering a matrix of weights instead of a vector, the number of problems to be modelled is considerably multiplied, allowing, among others, to minimise interaction between costs or to model more specific objective functions which require quadratic terms, such as the variance. On the other hand, introducing ordered interactions as a modeling feature increases the complexity of the problems at hand, which motivates the study of efficient resolution methods that allow the scalability of these problems.
The following work motivates this new approach, which allows a higher level of generalisation of several combinatorial problems, particularly location problems, providing a mathematical formalisation of this approach, describing exact models as solution methods, and performing empirical comparison between these different solutions methods.
Keywords
- Combinatorial Optimization
- Integer programming
- Routing, location and capacity planning
Status: accepted
Back to the list of papers