Transcript Multi-objective optimization - DPCS@IN3-UOC

MOGISA Group
Modeling, Optimization, and Integrated
Management of Systems of Activities
Toulouse, France
November 2011
MOGISA
1
LAAS-CNRS


LAAS = Laboratory for Analysis and
Architecture of Systems

More than 650 persons:


Founded in 1967


Laboratory of the French National
Center for Scientific Research
(CNRS)


4 thematic research areas:


Associated to:




Université Paul Sabatier (UPS)
Institut National Polytechnique (INP)
Institut National des Sciences
Appliquées (INSA)
Institut Supérieur de l’Aéronautique
et de l’Espace (ISAE)
November 2011
MOGISA
Research scientists ( 100)
Faculty members ( 100)
Graduate, PhD students, and
postdocs ( 300)
Engineers, technicians, and
administrative clerks ( 100)



Micro and Nano Systems
(MINAS)
Modelling, Optimisation and
Control of Systems (MOCOSY)
Robotics and Artificial
Intelligence (RIA)
Critical Computer Systems
(SINC)
2
Decision and Optimization theme

Discrete and continuous optimization
Constraint satisfaction
Performance evaluation
Robust, non-linear, saturated control
Model-based diagnosis

3 research teams:







November 2011
DISCO (diagnosis, supervision)
MAC (control)
MOGISA (discrete optimization, discrete-event dynamic systems)
MOGISA
3
MOGISA: Members
(February 15, 2012)
11 research scientists – 8 PhD students – 1 post-docs
Head: ARTIGUES Christian (DR)
Research scientists













BRIAND Cyril (Pr)
ESQUIROL Patrick (Mcf)
HEBRARD Emmanuel (CR)
HOUSSIN Laurent (Mcf)
HUGUET Marie-José (Mcf)
JOZEFOWIEZ Nicolas (Mcf)
LOPEZ Pierre (DR)
MERCE Colette (Pr)
MONCEL Julien (Mcf)
NGUEVEU Sandra (Mcf)
November 2011
PhD Students (year of defence)








CHABAANE Nadia (2015)
BEN RAHHOU Touria (2013)
GAOUA Yacine (2014)
MALTA Leonardo (2015)
SARPONG Boadu (2013)
SIALA Mohamed (2014)
TANGPATTANAKUL
Panwadee (2013)
TROJET Mariem (2013)
 Post-doc
Secretary


SIMONIN Gilles
MOUCLIER Christèle
MOGISA
4
Scientific objectives

Research domains




Research topics





Operations Research
Artificial Intelligence (Constraints)
Control Theory (Discrete-Event Systems)
Discrete optimization & Constraint satisfaction
Supply chain management
Scheduling
Transportation
General stakes



November 2011
Advances (models, algorithms, general methods) for fundamental
problems
Tackling complex constraints and multiple objectives for real-world
applications
Coping with uncertainty and dynamics
MOGISA
5
Discrete Optimization and
Constraint Satisfaction

Objectives

General methods for solving:



NP-hard discrete optimization problems
min f(x) x  X
NP-complete satisfaction problems
 x, D(x)  C
Results

Tree search enhanced with learning mechanisms
Tree-based local search: discrepancy search improvements
Large neighborhood search embedding implicit enumeration
Constraint propagation-based cutting planes for integer programming

Applications to industrial problems





November 2011
Frequency assignment in telecommunications
Production scheduling, project management, supply chain management,
passenger transportation…
MOGISA
6
Discrete Optimization and
Constraint Satisfaction: trends

Robust discrete optimization



Problems computationally challenging and currently
intractable even for small instance problems
New constraint & integer programming approaches
Application for robust scheduling (facing to limits of
interval representation for uncertainty of data)

Multi-objective optimization




Exact methods
MIP as search components
Matheuristics (e.g., local branching)
Constraint propagation and satisfaction


November 2011
Methods hybridization, integration and cross-fertilization for discrete optimization pbs
From CP, SAT, MIP, Metaheuristics, Mach. Learning, Parameterized Complexity
MOGISA
7
Scheduling

Objectives


Integrating complex constraints from real-world applications and
tackling uncertainty
Results

Complexity results on open problems
Branch-and-bound methods for complex shop problems
New MIP formulations (OMSP, RCPSP)
Generalized resource constraint propagation
New approach to generate flexible solutions for robust scheduling

Applications to industrial problems






November 2011
wafer manufacturing
crew scheduling
MOGISA
8
Scheduling: trends

New challenges




Parallel processors
Resource flexibility in production systems
Power management systems
Energy
7.0
6.0
1.0
MEM
5.0
1.0
3.1
6.3
2.0
4.1
2.1
4.2
2.2
4.3
2.3
1.1
5.1
1.2
5.2
1.3
5.3
1.4
5.4
1.1
3.0
6.2
7.1
4.0
ALU
6.1
1.2
CTL
1.3
1.4
7.0
7.1
7.0
7.1
ODD
2.0
0

1
2
3
2.1
4
5
2.2
6
7
2.3
8
9
New efficient (exact and approximate) methods for





November 2011
cyclic scheduling problems under resource constraints
scheduling under alternatives
multi-objective scheduling
mathematical models and constraint propagation
approaches for energy constraints & objectives
(max,+) algebra for solving and for performance
evaluation of schedules
MOGISA
3
9
Robust scheduling

Cooperation vs. Robustness (ROBOCOOP)




Robust scheduling for innovative projects



November 2011
Tasks are distributed among a set of agent
Agent schedules are robust
Distributed and reactive scheduling:
 Negotiation between Agents
 Convergence of negotiations in finite time
 Trade-off between global and local objectives
 Cooperation mechanisms
Problem
 Activity failure implies project failure
 Past project investments are definitively lost
 Alternative activities exist (flexibility): if an activity fails, but one
alternative activity succeeds, project can go on
Decision variables
 Determine which activities have to be launched and their start time
Objectives
 Investments minimization
 Risk of project failure minimization (robustness)
MOGISA
10
Land transportation

Objectives


Solving complex Vehicle Routing /
Passenger Transportation Problems
Results: New models and methods for


Generalized TSPs
Multi-objective VRPs







VRP with route balancing
Bi-objective TSPs with accessibility
VRPs on multi-graphs
Unusual objectives: stability
Large Arc Routing Problems
Applications
Waste collecting
November 2011

Railway tracks examination
MOGISA
11
Land transportation: trends

Goal



Challenges






Convergence toward more realistic problems
Optimization of individual/public transports
Multi-modality in passenger transportation and VRPs
Advance the use of multi-objective optimization
Problems with many constraints (“rich”)
Dynamicity
Take into account the human side of problems
Applications



November 2011
Door-to-door service network (ANR + DHL)
High-capacity and real-time on-demand
transportation
Multi-modal algorithms for GIS
MOGISA
12
Optimization in space

ROSETTA/MOST (Post-doc – CNES Contract)
 Scheduling of scientific experiences
 Data transfer management system
 Limited energy
November 2011
MOGISA
13
Optimization in space

Image-taking Scheduling of Earth observation
satellites (PhD thesis THEOS Operational Training
Program + Project CNES + Astrium/ONERA on
flexible scheduling)
November 2011
MOGISA
14
Optimization in space

Frequency allocation for satellite communications
(Collaboration with Thales AS)
November 2011
MOGISA
15
Contracts & collaborations

Industrial contracts : EADS, Airbus, Thales, Astrium, CNES,
SNCF, Amadeus
Academic projects

Local and National collaborations




November 2011
IMT, LARA/ENAC, CLLE/LTC
IBM/ILOG, INRIA Lille-Nord Europe, LAMSADE, LAGIS/ECL,
LAPS Bordeaux, LI Avignon, LI Tours, LIMOS, LISA Angers, LOSI
Troyes, LIP6,…
International collaborations : Spain, Canada, Belgium,
Germany, Tunisia, Algeria …
MOGISA
16
Other visibility

Involvement in life of ROADEF (French OR&DA society)
http://www.roadef.org/
http://www2.lifl.fr/PM2O/
http://challenge.roadef.org/
http://roadef2010.fr/



Reporting (CRSNG Canada, ECOS-Sud/Nord, FWO Belgium,
ANR, ANRT, “Régions”…)

Program committees of conferences (IESM, ILS, MISTA,
MOSIM, ROADEF, JFPDA, CIGI)
Conference organization : ROADEF 2010, JFPC 2012,
Odysseus 2015

November 2011
MOGISA
17
Publications 01/2005-12/2010






November 2011
40 journals with review board
2 books (editor)
80 refereed conferences with proceedings
11 book chapters
15 PhD thesis
2 “HDR”
MOGISA
18
What do we wish to develop ?

Multiobjective optimization




Optimization under uncertainties



Robust optimization
Stochastic programming
Collaborative logistics


November 2011
New methods
Parallelization to overcome computational
complexity
Applications
Intermodal transportation
Integrated systems
MOGISA
19
MOGISA Group
Modeling, Optimization, and Integrated
Management of Systems of Activities
November, 2011
November 2011
MOGISA
20