6. Digraph3 Archives
Raymond BISDORFF, Emeritus Professor of Applied Mathematics and Computer Science
R. Bisdorff 2013-2023
The Digraph3 Archives gather historical case studies and example digraphs compiled before 2006 and concerning the early development of python modules implementing tools and methods of the Rubis decision aiding approach (see [BISD-2008]).
A first collection of pages is devoted to the problem of enumerating non isomorphic kernels in symmetric digraphs like the Petersen, the Coxeter and the Chvátal graph for instance (see Computing the non isomorphic MISs of the 12-cycle graph). A second collection concerns the early development of the Rubis best choice algorithm (see Computing a first choice recommendation). And, a third collection finally illustrates the concepts of hyperkernels and prekernels in digraphs (see On computing digraph kernels).
More than 15 years later now, the historical discussions and illustrations of outranking digraphs, with potential best choice recommendations, appear rather confuse and controversial. It is worthwhile noticing that the concept of outranking digraph has meanwhile become much more accurate both, from a logical as well as, from an epistemic perspective (see [BISD-2013]).
In our present terms, the outranking concept is indeed modelled as a hybrid object. On the one hand, it is a bipolar-valued digraph object, modelling pairwise outranking relations between potential decision alternatives. On the other hand, the same concept models preferential situations, observed between decision alternatives that are assessed on multiple incommensurable performance criteria, as gathered in what we call a performance tableau object.
Such bipolar-valued outranking digraphs are specifically characterised by the fact that they verify a weakly completeness property and the coduality principle, i.e. not outranking situations necessarily correspond to the corresponding strictly outranked situations. Contrary, hence, to the historical outranking digraph examples shown below, we nowadays model a potential incomparability situation not via the absence of an outranking, but as an indeterminate situation (see Coping with missing data and indeterminateness). With this more accurate epistemic modelling, the strict outranking kernel concept gains great effectiveness for computing best choice recommendations from a given outranking digraph (see On computing digraph kernels).
Bisdorff R., Meyer P. and Roubens M.(2008) “RUBIS: a bipolar-valued outranking method for the choice problem”. 4OR, A Quarterly Journal of Operations Research Springer-Verlag, Volume 6, Number 2 pp. 143-165. (Online) Electronic version: DOI: 10.1007/s10288-007-0045-5 (downloadable preliminary version PDF file 271.5Kb).