Computing k different solutions to the assignment problem
| Autor: | Enrico Malaguti, Rosa Medina Durán |
|---|---|
| Přispěvatelé: | Malaguti E., Medina Duran R. |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
Ranking solution
Mathematical optimization 021103 operations research General Computer Science Matching (graph theory) Computer science 0211 other engineering and technologies General Engineering 02 engineering and technology Set (abstract data type) Assignment problem 0202 electrical engineering electronic engineering information engineering Portfolio 020201 artificial intelligence & image processing Semi-assignment Element (category theory) Computational experiment |
| Popis: | Assignment problems are about the best way of matching the elements of a first set with the elements of a second set. In Semi-Assignment problems, more than one element of the first set can be assigned to each element of the second. In many situations, a solution to the same Assignment or Semi-Assignment problem has to be implemented more than once, and for a fairness reason it may not be desirable to always implement the same solution. Another common situation is when more than a single solution to the (Semi-)Assignment has to be generated, so as to give the decision maker a portfolio of options to choose in. This can happen because not all the problem constraints could be considered in the problem formulation, and the decision maker may want to choose between alternative solutions. In both cases, one is interested in defining several alternative solutions to the problem, still optimizing their cost. In this paper we discuss two specific situations for which we present optimization algorithms. The algorithms are computationally tested on a set of instances from the literature and from a real world application. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|