Location, Order and Discrete Optimization

This talk considers discrete optimization problems with ordering requirements. These problems are formulated on general discrete sets in which there exists an implicit 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 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. In addition, we will discuss that in many cases of combinatorial problems if the sum objective is polynomialy solvable then the corresponding ordered median problem is also solvable in polynomial time. We will specialize on k-centrum integer optimization problems and on some problems on matroids.