2017
R. Bisdorff, Algorithmic Decision Theory for solving complex decision problems. Distinguished ILIAS Interdisciplinary Lab for Intelligent and Adaptive Systems Lecture IV, FSTC, University of Luxembourg, 3 May, 2017 (handout: PDF file 1.1 MB).
Today's decision makers in fields ranging from engineering to psychology, from medicine to economics and/or homeland security are faced with remarkable new technologies, huge amounts of information to help them in reaching good decisions, and the ability to share information at unprecedented speeds and quantities. These tools and resources should lead to better decisions. Yet, the tools bring with them daunting new problems: the massive amounts of data available are often incomplete, unreliable and/or distributed and there is great uncertainty in them; interoperating/distributed decision makers and decision making devices need to be coordinated; many sources of data need to be fused into a good decision; information sharing under new cooperation/competition arrangements raises security problems. When faced with such issues, there are few highly efficient algorithms available to support decision makers. The objective of Algorithmic Decision Theory (ADT) is to improve the ability of decision makers to perform well when facing these new challenges and problems through the use of methods from theoretical computer science, in particular algorithmic methods. The primary goal of ADT is hence to explore and develop algorithmic approaches for solving decision problems arising in a variety of applications areas. Examples include, but are not limited to:
- Computational tractability/intractability of social consensus and multiple criteria compromise functions;
- Improvement of decision support and recommender systems;
- Development of automatic decision devices including on-line decision procedures;
- Robust decision making;
- Learning for multi-agent systems and other on-line decision devices.
This presentation will focus more specifically on multiple criteria decision aiding methodology, the actual research field of the author.
2016
R. Bisdorff, Computing linear rankings from trillions of pairwise outranking situations. DA2PL'2016 From Multiple Criteria Decision Aid to Preference Learning, Mini-EURO Conference, Paderborn (Germany), 7-8 November, 2016 ((see Programme, paper PDF file 451.4 kB, handout: PDF file 464.9.8 kB).
We illustrate in this presentation a sparse HPC implementation for outranking digraphs of huge orders, up to several millions of decision alternatives. The proposed outranking digraph model is based on a quantiles equivalence class decomposition of the underlying multicriteria performance tableau. When locally ranking each of these ordered components, we may readily obtain an overall linear ranking of big sets of decision alternatives. For the local rankings, both, Copeland's as well as the Net-Flows ranking rules, appear to give the best compromise between, on the one side, the fitness of the overall ranking with respect to the given global outranking relation and, on the other side, computational tractability for very big outranking digraphs modelling up to several trillions of pairwise outranking situations.
R. Bisdorff, A sparse outranking digraph model for HPC-ranking of big performance tableaux. EURO 2016 28th European Conference on Operational Research, Poznan (Poland), 3-6 July, 2016 (see handout: PDF file 471.8 kB).
In the context of the ongoing GDRI-Algodec "Algorithmic Decision Theory", supported o.a. by the CNRS (France) and the FNR (Luxembourg), we develop multicriteria ranking HPC algorithms for large sets of potential decision alternatives: up to several thousand of alternatives evaluated on multiple incommensurable ordinal performance criteria. By using Python3.5 multiprocessing resources and the Digraph3 multicriteria software library, we could linearly rank without ties on the UL HPC gaia-80 machine with 120 single threaded cores and a CPU memory of 2.0 TB, in about two hours (2h17') a huge set of 1'732'051 decision alternatives evaluated on 13 performance criteria by balancing economic, ecological and societal decision objectives. Data input is, on the one side, a 1'732'051 x 13 performance tableau of size 2.6GB, and on the other side, a theoretical outranking space consisting of three trillions (3 x 1012) of pairwise outranking situations. A "small" set of 1000 decision alternatives, on a standard laptop with 8caores, may thus be ranked typically in less than 2 seconds.
R. Bisdorff, Ranking big performance tableaux with multiple incommensurable criteria and missing data. ORBEL30 30th Belgian Conference on Operations Research, Louvain-la-Neuve, 28-29 January, 2016 (see Programme, extended abstract: PDF file 254.7 kB, handout: PDF file 499.3 kB).
In the context of the ongoing GDRI-Algodec "Algorithmic Decision Theory", supported o.a. by the CNRS (France) and the FNR (Luxembourg), we develop multicriteria ranking HPC algorithms for large sets of potential decision alternatives: up to several thousand of alternatives evaluated on multiple incommensurable ordinal performance criteria. This research is motivated by the development of a visualization tool - a heat map - for performance tables showing the decision alternatives linearly ordered form the best to the worst, and the individual performances colored by quantiles equivalence classes.
2015
R. Bisdorff, On boosting Kohler's ranking-by-choosing rule with a quantiles preordering. ORBEL29 29th Belgian Conference on Operations Research, Antwerp, 5-6 February, 2015 (see Programme, extended abstract: PDF file 129.4 kB, handout: PDF file 536.0 kB).
Several ranking methods, like Tideman's rule, have been proposed for ranking decision actions with multiple incommensurable performance criteria. Of these, Kohler's rule is by far the fastest ranking heuristic, yet also the less satisfactory in terms of ordinal correlation with a corresponding pairwise outranking relation. We show that preordering the decision actions to be ranked along quantiles, and then locally applying Kohler's rule on each equivalence class, greatly enhances this correlation without adding any essential algorithmic complexity. The combination of both, hence, becomes efficient for tackling large scale multiple criteria ranking problems.
2014
R. Bisdorff, On confident outrankings with multiple criteria of uncertain significance. DA2PL'2014 from Multiple Criteria Decision Aid to Preference Learning, Ecole Centrale Paris, 20-21 November, 2014 (see Programme, downladable presentation: PDF file 479.8 kB).
When modelling preferences following the outranking approach, the sign of the majority margins do sharply distribute validation and invalidation of pairwise outranking situations. How can we be confident in the resulting outranking digraph, when we acknowledge the usual imprecise knowledge of criteria significance weights and a small majority margin? To answer this question, we propose to model the significance weights as random variables following more less widespread distributions around an average weight value that corresponds to the given deterministic weight. As the bipolarly valued random credibility of an outranking statement results from a simple sum of positive or negative independent and similarly distributed random variables, we may apply the CLT for computing likelihoods that a given majority margin is indeed positive, respectively negative. To test the effective convergence of the CLT likelihoods, we apply Monte Carlo simulations of outranking digraph constructions. Our computational results confirm a satisfactory convergence even for a random performance tableau with only seven criteria.
R. Bisdorff, On ranking-by-choosing with bipolar outranking digraphs of large orders. Conference Graphs & Decisions, GDRI "Algorithmic Decision Theory", Luxembourg, 27-29 October, 2014 ( downladable presentation: PDF file 489.6 kB).
Ranking-by-choosing decision alternatives with possibly a small number of ties, when dealing with pairwise bipolarly-valued outranking situations, is a computational difficult problem that could until now only be genuinely solved for tiny outranking digraph orders; up to 40 alternatives. In this lecture we present a HPC two-stages decomposition of large outranking digraphs, which allows us to solve such ranking-by-choosing problems for larger outranking digraph orders; up to several thousands of decision alternatives. In a first stage, all alternatives are sorted into a prefixed set of multiple criteria quantile classes. Each resulting quantile equivalence class is then, in a second stage, locally ranked-by-choosing on the basis of the restricted outranking digraph. Operational results will be illustrated with Monte Carlo simulations of large scale Cost-Benefit performance tableaux.
R. Bisdorff, On weakly ordering by choosing from valued pairwise outranking situations. ORBEL28, 28th Annual Conference of the Belgian Operations Research Society, Mons, January 30-31, 2014 (see Programme, downladable presentation: PDF file 319.0 kB).
Polarised outrankings with considerable performance differences (weighted majority margins with vetoes and counter-vetoes) appear as weakly complete (and reflexive) relations (Bisdorff 2013). Constructing weak orderings (rankings with potential ties) from such outranking relations consists in computing, hence, a transitive closure of the given outranking relation. Determining optimal transitive closures is a computational difficult problem ( (Hudry 2013). However, global heuristic scoring methods based on average ranks (like Borda scores) or average net flows like in the PROMETHEE approach, may easily deliver such a transitive closure. Now, weak orderings may also naturally result from the iterated application of a certain choice procedure, an approach called "ranking-by-choosing" (Bouyssou 2004). In this contribution we shall present such a new ranking-by-choosing approach based on the Rubis best choice method (Bisdorff et al. 2008). A practical application concerns the weak ordering of 41 German universities following from the Spiegel magazine's on-line 50000 students survey from 2004 (see survey data and final ranking).
2013
R. Bisdorff, On measuring and testing the ordinal correlation between valued outranking relations. International Year Of Statistics Conference www.iys2013.lu, Luxembourg, November 26th - 27th, 2013 (See presentation handout (PDF 383.7 kB)).
We generalize Kendall's rank correlation measure τ to valued binary relations. Motivation for this work comes from the need to measure the level of approximation that is required when replacing a given valued outranking relation with a convenient crisp ordering recommendation.
A. Olteanu, P. Meyer and R. Bisdorff, Descriptive profiles for sets of alternatives in MCDA. 3rd International Conference on Algorithmic Decision Theory ADT 20113, Université Libre de Bruxelles, November 13th - 15th, 2013 (See presentation handout (PDF 1.6 MB)).
In the context of Multiple Criteria Decision Aid, a decision-maker may be faced at any time with the task of analysing one or several sets of alternatives, irrespective of the decision he is about to make. As in this case the alternatives may express contrasting gains and losses on the criteria on which they are evaluated, and while the sets that are presented to the decision-maker may potentially be large, the task of analysing them becomes a difficult one. Therefore the need to reduce these sets to a more concise representation is very important. Classically, profiles that describe sets of alternatives may be found in the context of the sorting problem, however they are either given beforehand by the decision-maker or determined from a set of assignment examples. We would therefore like to extend such profiles, as well as propose new ones, in order to characterise any set of alternatives. For each of them, we present several approaches for extracting them, which we then compare with respect to their performance.
A. Olteanu and R. Bisdorff, Mining preferential datasets in MCDA. European Conference on Data Analysis 2013, University of Luxembourg, July 10th - 12th, 2013 (See presentation handout (PDF 1.3 MB)).
We shortly present first the field of multiple criteria decision aid and its preference modelling tradition, before introducing clustering procedures that group decision alternatives, not on the basis of their similarity or dissimilarity, but, instead, on the basis of their being indifferent or not. In order to illustrate the approach, we present a real large scale case study that concerns preferential clustering of 22000 toxic chemicals release practices in the US.
R. Bisdorff, The Electre like outranking approach to MCDA. Invited lectures, 11th MCDA|M Summer School, Helmut-Schmidt-Universität, Hamburg, July 22nd - August 2nd, 2013. See lecture I handout (PDF 435.0 kB) and lecture II handout (PDF 342.1 kB).
2012
R. Bisdorff, Algorithmic Decision Theory. Invited speaker, ICOCBA2012 International Conference on "Optimization, Computing and Busisness Analytics", 45th Annual Convention of the Operational Research Society of India, Kolkata, December 20-22, 2012 (See Conference web site and presentation (PDF 1.3 MB)).
Today's decision makers in fields ranging from engineering to psychology to medicine to economics to homeland security are faced with remarkable new technologies, huge amounts of information to help them in reaching good decisions, and the ability to share information at unprecedented speeds and quantities. These tools and resources should lead to better decisions. Yet, the tools bring with them daunting new problems: the massive amounts of data available are often incomplete or unreliable or distributed and there is great uncertainty in them; interoperating/distributed decision makers and decision making devices need to be coordinated; many sources of data need to be fused into a good decision; information sharing under new cooperation/competition arrangements raises security problems. When faced with such issues, there are few highly efficient algorithms available to support decisions. The objective of Algorithmic Decision Theory (ADT) is to improve the ability of decision makers to perform in the face of these new challenges and problems through the use of methods of theoretical computer science, in particular algorithmic methods. The primary goal of ADT is to explore and develop algorithmic approaches to decision problems arising in a variety of applications areas. Examples include, but are not limited to: - Computational tractability/intractability of consensus functions; - Improvement of decision support and recommender systems; - Development of automatic decision devices including on-line decision procedures; - Robust Decision Making;- Learning for Multi-Agent Systems and other on-line decision devices.
R. Bisdorff, On measuring and testing the ordinal correlation between bipolar outranking relations. Algodec Workshop DA2PL'2012 "From Multiple Criteria Decision Aid to Preference Learning", University of Mons, November 15-16, 2012 (See Program, downloadable presentation PDF file 408.6 kB).
We generalize Kendall's rank correlation measure τ to bipolarly valued relations. Motivation for this work comes from the need to measure the level of ordinal approximation that is required when replacing a given bipolar outranking with a convenient weak ordering recommendation.
R. Bisdorff, On polarizing outranking relations with large performance differences. ORBEL26, 26th Annual Conference of the Belgian Operations Research Society, Bruxelles, February 2-3, 2012 (see Programme and downladable presentation: PDF file 119.6 kB).
We introduce a bipolarly extended veto principle – a positive, as well as negative, large performance differences polarization – which allows us to extend the definition of the classical outranking relation in such a way that the identity between its asymmetric part and its codual relation is preserved.
2011
R. Bisdorff, P. Meyer and A. Olteanu A Clustering Approach using Weighted Similarity Majority Margins. BNAIC 2011, The 23rd Benelux Conference on Artificial Intelligence Gent November 3-4 2011 (see Programme and downladable presentation: PDF file 218.6 kB).
We propose a meta-heuristic algorithm for clustering objects that are described on multiple incommensurable attributes defined on different scale types. We make use of a bipolar-valued dual similarity-dissimilarity relation and perform the clustering process by first finding a set of cluster cores and then building a final partition by adding the objects left out to a core in a way which best fits the initial bipolar-valued similarity relation.
R. Bisdorff, Aide à la Décision Concentrée sur l'Expertise Humaine. Journée en hommage à Jean-Pierre Barthélemy, TELECOM ParisTech, Société Française de Classification, 21 juin 2011 (see Programme and downladable presentation: PDF file 495.5 kB).
Au printemps 1993, lors d'une réunion du groupe EURO-MCDA à Chania (Crète), Jean-Pierre Barthélemy m'a convaincu de l'intérêt qu'il peut y avoir en aide à la décision de s'intéresser très particulièrement à l'expertise décisionnelle humaine. Deux projets industriels superbes allaient s'en suivre. Le premier, appelé « Systèmes cognitifs en industrie » (1993-1995), donna lieu à la conception d'un laboratoire cognitif d'aide, d'un côté, à la formulation et délimitation (« l'art de la découpe ») et, de l'autre côté, à l'extraction des stratégies cognitives de résolution mises en oeuvre par un opérateur expert dans un problème hebdomadaire d'ordonnancement d'une installation complexe de patentage-laitonnage de fils d'acier. Fort de ces premiers résultats encourageants, le second projet, le fameux projet Brite-Euram COMAPS (1997-2000), donna lieu à la conception d'un système général d'archivage, de vérification (« check as you decide »), et de maintenance en temps réel d'une expertise décisionnelle quotidienne en industrie manufacturi&egarve;re. Très en avance sur son temps, le projet COMAPS marqua en fait la naissance d'un courant spécifique de l'aide à la décision.
R. Bisdorff, Starting a new COST Action called: The Internet of Decisions. Last workshop of the COST Action IC0602 “Algorithmic Decision Theory”, Manchester Business School, April 14-15, 2011 (see Programme and downladable presentation: PDF file 90.1 kB).
There is a need to change from systems thinking to infrastructural thinking about decision support systems (DSSs). Decision makers (citizens, policy makers, business managers) do not benefit nor add value to the data and data infrastructures on Inter/intranet because of lack of DSS Infrastructure (DSSI). Reasons are heterogeneity and non-interoperability, lack of standards and easily reconfigurable and adaptable DSSs as well as scattered scientific and industrial communities. Main objectives of the new COST Action are:
- to support development of new distributed inter-operable DSSI (e.g. standards, policies, ontologies, opensource software, discovery and work flow tools), and
- to develop decision fusion and aiding methodologies especially for spatial data handling, and easily scalable and interoperable DSSs,
- and to link dispersed research and practice communities.
Benefits are an integrated European development of DSSI, and fair conditions for industry to add value to data for decision makers.
R. Bisdorff, K-Sorting with multiple ordinal criteria. 25th ORBEL Conference, University of Ghent, February 10-11, 2011 (see Programme and downladable presentation: PDF file 2.1 MB).
We present a new k-sorting algorithm based on the bipolar extension of the classic Electre Tri approach. By the way we present the latest software tool from the Decision Deck project.
2010
R. Bisdorff and Michel Zam, Agile MCDA Modelling: D4 meets XMCDA. 7thDecision Deck Workshop, Université Paris-Dauphine, October 6, 2010 (see Programme and downladable presentation: PDF file 2.1 MB).
We show needs and opportunities for using the XMCDA standard within D4. What is the right granularity of practical XMCDA formulated problems? Does XMCDA need UML profiling and stereotyping mechanisms?
R. Bisdorff, The Decision Deck Project. ECP MCD{A|M} Summer School 2010, 25thEcole Centrale Paris, June 27- July 9, 2010 (see Programme and downladable presentation: PDF file 1.5 MB).
In this presentation we present the Decision Deck Project. After a historical review of the ongoing 6 initiaves (de client, d3, MCDA web services, XMCDA, diviz and d4), main focus is given to the XMCDA standard encoding of MCD{A|M} data, the MCDA web services, and the diviz server.
R. Bisdorff, On a bipolar foundation of the outranking concept. URPDM-2010, 25th Mini EURO Conference Uncertainty and Robustness in Planning and Decision Making. University of Coimbra (Portugal), April 14-16, 2010 (see Programme and downladable presentation: PDF file 100.8 kB).
In this paper we introduce a bipolarly extended veto principle which allows us to extend the definition of the classic outranking relation in such a way that the identity between the asymmetric part and bipolar codual of the latter outranking relation is given.
R. Bisdorff, G. Godinet and M. Zam, The D4 Platform. 6th Descision Deck Workshop, University of Coimbra (Portugal), April 13-14, 2010 (see Programme and downladable presentation: PDF file 1.4 MB).
In this presentation we show the actuial state of the development of D4, the Distributed Designer for Decision Deck Applications.
R. Bisdorff, Enumerating chordless circuits in directed graphs. ORBEL24-2010, 24th Annual Conference of the Belgian Operational Research Society (ORBEL aka Sogesci-B.V.W.B.). Liège (BE), January 28-29, 2010 (see Programme extract and downladable presentation: PDF file 208.8 kB ).
We introduce and discuss an algorithm using O(p) time and O(n(n+m)) space for enumerating the m >= 0 chordless circuits in a digraph of order n and containing p pre-chordless-circuits. Running it on random digraphs yields some statistical insight into its practical performance.
R. Bisdorff, ROAD development perspectives. UGR GreatRoad, 3rd meeting of the network on Operational Research and Decision Aid of the Unversity of the Great Region. Luxembourg (LU), January 21, 2010 (downladable presentation: PDF file 86.6 kB ).
2009
R. Bisdorff, P. Meyer and Th. Veneziano, Inverse analysis from a Condorcet robustness denotation of valued outranking relations. ADT 2009, 1st Conference on Algorithmic Decision Theory. Venice (IT), October 21-23, 2009 (see Programme extract and downladable presentation: PDF file 140.0 kB ).
In this presentation we develop an indirect approach for assessing criteria significance weights from the robustness of the significance that a decision maker acknowledges for his pairwise outranking statements in a Multiple Criteria Decision Aiding process. The main result consists in showing that with the help of a mixed integer linear programming model this kind of a priori knowledge is sufficient for estimating adequate numerical significance weights.
R. Bisdorff and M. Zam, D4: rationale, concept and implementation of a distributed MCDA application designer. Presentation at the 5th Decision Deck Workshop Brest (FR), September 17-18, 2009 (see Programme extract and downloadable presentation: PDF file 331.1 kB).
Content:
R. Bisdorff and P. Meyer, The Decision Deck Project. Invited session at the 23rd European Conference on Operational Research Bonn (DE), July 5-8, 2009 (see Program extract).
R. Bisdorff, P. Meyer and Th. Veneziano, XMCDA: a standard XML encoding of MCDA data. Invited presentation at the 23rd European Conference on Operational Research Bonn (DE), July 5-8, 2009 (downloadable presentation: PDF file 331.1 kB)
XMCDA is a structured XML proposal for encoding objects and data from the field of Multiple Criteria Decision Analysis (MCDA). Its main objectives are to allow different MCDA algorithms to interact and to be easily callable from within a common software platform like Decision Deck diviz. We present this XML standard and detail the underlying data types via illustrative coding examples.
R. Bisdorff, Random outranking digraphs. Joint International Meeting of the Canadian Operational Research Socity (CORS) and the Institute for Operations Research & Management Sciences (INFORMS), Toronto (CA) June 14-17 2009 (downloadable presentation: PDF file 342.4 kB).
In order to advance the empirical knowledge concerning outranking digraph instances, we presented a model of outranking digraphs generated from random performance tableaux. Comparison with standard random digraphs illustrates the specific characteristics of genuine outranking digraphs. Our results are meaningful for discussing algorithmic complexity issues when exploiting outranking relations for selecting, ranking and sorting decision problems.
R. Bisdorff, Generating random performance tableaux. 4th DECISION-DECK Workshop, Mons (BE), March 30-31 2009 (downloadable presentation: PDF file 250.7 kB).
In this presentation we wanted to illustrate the use of the Decision Deck Universal MCDA Modelling Language XMCDA and the D3 server at the University of Luxembourg for generating random multiple criteria performance tableaux. Such random generators are useful on the one hand for the necessary testing of implemented MCDA methods, especially the Decision Deck webservices, and on the other hand, in the study of the general statistical properties of random outranking digraphs.
R. Bisdorff, Random outranking digraphs. ORBEL'09 - the 23rd Belgian Conference on Operations Research, Leuven (BE) February 5-7 2009 (downloadable presentation: PDF file 375.2 kB).
In order to advance the empirical knowledge concerning outranking digraph instances, we presented a model of outranking digraphs generated from random cost benefit performance tableaux.
This Web Site, designed by Raymond Bisdorff, is licensed under a Creative Commons Attribution 3.0 Luxembourg License. Best seen with Firefox
