## 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

**V) CHIP: a constraint programming
Technology for solving highly Complex Problems**

*Doctor Idir Gouachi, COSYTEC SA, Orsay, Paris (France) *

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