COSI-Summer School

on Decision Aiding

Courses

 

I) On the theory of multicriteria games
Mohammed Said Radjef, University of Bejaia (Algeria) [pdf, pdf]

 

II) Interval Global Optimization [pdf]
Professor Frédéric Messine, ENSEEIHT-IRI, UMR-CNRS 5505, Toulouse (France)

 

 

III ) Bridging the gap between data warehouses and data mining [pdf, pdf]
Professor Mokrane Bouzeghoub, PRiSM, CNRS-University of Versailles, Paris (France)
Professor Jean-Marc Petit, INSA-Lyon (France)

 

IV) Constraint programming and Satisfiability : a comparative survey [pdf]

Doctor Youssef Hamadi, Microsoft Research Cambridge, United Kingdom

 

V) CHIP: a constraint programming Technology for solving highly Complex Problems [contacter par mail Idir Gouachi]
Doctor Idir Gouachi, COSYTEC SA, Orsay, Paris (France)

 

---

I) On the theory of multicriteria games

Mohammed Said Radjef, University of Bejaia (Algeria)

The classical game theory is the study of behaviours and decision making processes of several rational agents (players), that interact in the same environment with different objectives, often conflicting. Every agent tries to act on the environment so as to acquire the greatest possible profit.
On the other hand, practical problems have shown that the different objectives of a decision maker cannot always be represented by a unique utility function (real valued function). Multicriteria Decision Aid Methods are then developed and applied in different domains, where a decision making have to be performed, no longer with respect to a unique criterion, but to several evaluation criteria.
The confluence of the two theories (game theory and multicriteria optimization) gives rise to another theory, namely “Mulricriteria game theory”. It allows the study of real world conflicting situations, between two or more than two persons having more than one objective. The first studies on multicriteria games began since the fifties: Blackwell (1956), Shapley (1959), but their real development has not been effective without the development of the two theories over the last decades. Some recent results and applications of multicriteria games will be surveyed.

Keywords: Decision making, preference, multiple criteria, game.

Lecture outline

I)- Decision theory
- Introduction
- Choice and preference

II)- Decision analysis with many agents
- What is a game?
- Solution concepts
- Practical example

III- Decision in presence of many criteria
- Example
- Multicriteria decision aid methods

IV)- Multicriteria games
- Example
- Some solution concepts
- State of the art and research directions

---

II) Interval Global Optimization

Professor Frédéric Messine, ENSEEIHT-IRI, UMR-CNRS 5505, Toulouse (France)

Nowadays, there are a lot of interests to determine the exact solution of optimization problems. In the continuous case, classical methods based on descent algorithms can fail in this task if the problems owns some different minima. Indeed, the convergence of such methods is based on the initial point which is given by the user. In order to improve these algorithms some Meta-Heuristics were introduced such as Taboo Search Algorithm. These kinds of method are particularly well adapted when all the optima are in a small region. Thus, starting from a local minimum, these methods will perform some other researches relatively close to it. In order to cover the initial domain of research some stochastic methods, such as genetic algorithms, were introduced. Their intrinsic simplicities made them really attractive and popular. One of their main interests, is that they permit to solve black-box type problems.
However, all these methods cannot completely answer to the optimization problem: where is the exact solution? Have we found a local minima or the global one?
Consequently, some exact methods were developed for particular cases. For example, for the linear case or the quadratic case. For more general problems, the Branch and Bound techniques were introduced and developed. Considering continuous problems, these bisection techniques were associated with interval analysis. In the second part of this course, I will present in some details these particular exact interval methods which permit to compute bounds for a function considered over a box. Some acceleration techniques will be also presented for problems with or without constraints. The third and last part of this course will be dedicated to the use of these interval Branch and Bound Algorithms for the design of electrical machines; I will do this work in collaboration with the LEEI-UMR-CNR 5828 of Toulouse. This application will perfectly illustrate and validate this exact algorithmic approach.
Keywords: descent algorithms, meta-heuristic algorithm, global optimization, stochastic global optimization, interval analysis, constraint propagation techniques, Branch and Bound, electrical machines.

Lecture outline:

Part 1: Interests of Global Optimization versus Standard Optimization

- Principle of standard descent methods
- Examples of difficulties to find the exact solution
- Improvements of these methods yielding Meta-Heuristic Methods
- Introduction to Global Optimization via some examples of Stochastic Approaches
- Exact Methods adapted to particular problems. For examples, Linear Programming, Quadratic Programming, Convex Programming

Part 2: Interval Branch and Bound Methods

- Branch and Bound principle
- Interval Analysis
- Computations of bounds via a Taylor expansion
- Affine arithmetic and extensions
- Interval constraint propagation techniques
- Some improvements via heuristics
- Some acceleration routines based on monotonicity and convexity tests
- Interval Newton Algorithm

Part 3: Application to the Design of Electrical Motors

- Inverse problem of design
- Combinatorial analytical models
- Comparisons of local and exact solutions on three examples
- Presentation of some realizations

---

III ) Bridging the gap between data warehouses and data mining

Professor Mokrane Bouzeghoub, PRiSM, CNRS-University of Versailles, Paris (France)
Professor Jean-Marc Petit, INSA-Lyon (France)

Dramatic advances in data capture, processing power, data transmission, and storage capabilities are enabling organizations to integrate their various databases into data warehouses. Data warehousing is defined as a process of centralized data management and retrieval and represents an ideal vision of maintaining a central repository of all organizational data. Centralization of data is needed to maximize user access and analysis. Dramatic technological advances are making this vision a reality for many companies. In this setting, high level OLAP queries against the data warehouse may be posed providing accurate and integrated data to end-users. In order to go one step beyond, datamarts can be built on top of the data warehouse from which data mining techniques can be applied to discover interesting nuggets of information hidden in the data. Generally, data mining (sometimes called knowledge discovery) is the process of analyzing data from different perspectives and summarizing it into useful information - information that turn out to be useful for decision makers. Data mining is the process of finding correlations or patterns in large databases and lies at the intersection of databases, statistics and machine learning.

Keywords: databases, data quality, OLAP queries, DBMS, knowledge discovery in databases, data mining

Lecture outline:

Part 1: Data warehouses

- Datawarehousing systems : achitectures and functionalities
- Data warehouses in decision support systems : roles and goals
- Data warehouse systems and other data integration systems
- OLAP technologies and servers
- Data warehouse design and deployment
- ETL tools and data warehouse maintenance
- Data quality in data warehousing : metrics, techniques and impact on decision support systems

Part 2: Knowledge discovery in databases (KDD)
- Data warehouses: a pre requisite
  - Beyond OLAP queries
- KDD process
- Data mining: an important step
  - Main techniques
  - Focus on association rules and frequent pattern enumeration
- Data mining systems
- Data mining and database systems: Is there an intersection?

---

IV) Constraint programming and Satisfiability : a comparative survey

Doctor Youssef Hamadi, Microsoft Research Cambridge, United Kingdom

Propositional Satisfiability (SAT) and Constraint Programming (CP) have developed as two relatively independent threads of research cross-fertilizing occasionally. These two approaches to problem solving have a lot in common as evidenced by similar ideas underlying the branch and prune algorithms that are most successful at solving both kinds of problems. They also exhibit differences in the way they are used to state and solve problems since SAT’s approach is, in general, a black-box approach, while CP aims at being tunable and programmable. This survey overviews the two areas in a comparative way, emphasizing the similarities and differences between the two and the points where we feel that one technology can benefit from ideas or experience acquired from the other.

Keywords: Artificial intelligence, Constraint programming, Satisfiability

Lecture outline :
- SAT and CP philosophies
- Respective strengths
- SAT and CP integration
- SMT and the future of CP
- Conclusion

---

In the last fifteen years, many successful industrial applications have been implemented using the CHIP system. CHIP is a Constraint Programming system designed to tackle real world constrained problems with a short-term development time and a good efficiency. Constraint programming appears as a suitable technology for many areas in fields of production planning, scheduling and ressources allocation.
This course gives a brief overview of the CHIP system, and introduces some important notions of the Constraint Programming and how these notions are used in CHIP. The first part of the course details the CHIP Constraints through applications examples.The second part presents a complete operational application folloed by a demonstration.

Keywords: Combinatory Optimisation, Artificial Intelligence (AI), Constraint Programming (CP), Operational Research (OR).

Lecture outline:

- CHIP Architecture
- Presentation of syntactic constraints
- Presentation of global constraints: second generation constraints
- Presentation of an operational application
- Demonstration
- Conclusion