On aggregating binary relations using integer linear programming
This paper is concerned with the general problem of aggregating many binary relations in order to find out a consensus. The theoretical background we rely on is the Relational Analysis (RA) approach. The latter method represents binary relations (BRs) as adjacency matrices, models relational properties as linear equations and finds a consensus by maximizing a majority based criterion using 0-1 integer linear programming. Our contribution consists in a generalization of the theoretical results obtained in this framework. First, with regards to classical BRs on a single set, we provide new linear equations that correspond to relational properties that have not been covered yet such as semi-transitivity, quasi-transitivity or Ferrers relation. Second, we extend
the BR aggregation problem to the case of maps or functions which are interpreted as BRs on two different sets. These results allow the RA approach to be a more general framework for dealing with BR aggregation problems. We also analyze the relationships between different BR aggregation problems and several tasks addressed in the artificial intelligence and machine learning fields. In that case, preference aggregation, clustering, and bi-clustering tasks are studied and we thus emphasize the underlying theoretical foundations of such problems from the point of view of BRs and their aggregations.
The 11th International Symposium on Artificial Intelligence and Mathematics - ISAIM 2010, Fort Lauderdale, Florida, January 6-8, 2010