On discrete optimization with ordering |
| |
Authors: | Elena Fernández Justo Puerto Antonio M. Rodríguez-Chía |
| |
Affiliation: | 1. Dpt. d’Estadística i Investigació Operativa, Universitat Politècnica de Catalunya, Barcelona, Spain 2. Dpt. Estadística e Investigación Operativa, Universidad de Sevilla, Sevilla, Spain 3. Dpt. Estadística e Investigación Operativa, Universidad de Cádiz, Cadiz, Spain
|
| |
Abstract: | This paper studies discrete optimization problems with ordering requirements. These problems are formulated on general discrete sets in which there exists an ordering on their elements together with a cost function that evaluates each element of a given subset depending on its ordering relative to the remaining elements in the set. It is proven that ordered sequences over the original ground set define an independence system. The simplest such ordering problem, that consists of finding the ordered sequence of maximum weight, and its restriction to sets of a fixed cardinality are studied. In both cases, the polyhedral structure of the corresponding feasible sets is analyzed. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|