[ro] PhD Proposal in Discrete Optimization at the LAAS-CNRS
Forum 'Emplois' - Sujet créé le 2012-02-14
PhD Proposal in Discrete Optimization at the LAAS-CNRS Lab of Toulouse (France) - http://www.laas.fr
__________________________________________________________________________________________
*Subject* Solving multiagent combinatorial optimization problems: centralized and decentralized approaches
*Duration* September 2012 - September 2015
*Deadline for Application* 23 March 2012
*General context*
This thesis is funded by the EDSYS Doctoral School on the basis of a Doctoral contract (from 1374,21€ to 1651,90 € per month net)
*How to Apply*
Please send a CV, a covering letter, your scores and ranking during the last two years of academic studies, and a letter(s) of recommendation
to briand@laas.fr and huguet@laas.fr.
*Description*
In many applicative fields, decision processes involve a set of agents; each one having their own decision autonomy and managing their own constraints and objectives. Agents need to cooperate together to fulfil a global objective, providing their local objective is also optimized or, at least, kept close to a given satisfying value. In the literature, such a decision framework is often referred as "multiagent combinatorial optimization". In the context of multiobjective optimization, seeking a "fair" strategy that satisfies agents' objectives and, which also remains acceptable in a global viewpoint, has been considered in several papers (e.g. [1]). In the context of game theory, some authors also take an interest in finding a stable strategy (Nash equilibrium), which optimizes the global objective (e.g. [2, 3]), aiming at measuring the so-called price of stability.
The selected applicant will investigate the complexity of such problems for various classical OR problems, and propose centralized or decentralized algorithms for solving them. Concerning decentralized algorithms, he/she will take benefit from some already existing approaches connected to the field of Distributed Constraint Optimization (see [3, 4, 5]).
Required skills
Applicants should have an outstanding academic record and a master's degree in computer science. They should have good programming skills, an interest in, as well as a good understanding of, Combinatorial Optimization, and should be knowledgeable in at least some of the methods that will be investigated: Constraint Programming, Integer Programming, and Game Theory. Prior knowledge of French is an advantage, although not mandatory.
*Working environment*
The student will work on this project in collaboration with Marie-José Huguet and Cyril Briand, and more generally with members of the MOGISA group (http://www.laas.fr/MOGISA-EN/) at LAAS. The scientific activities of the group are focused on scheduling, transportation, discrete optimization, and constraint satisfaction.
*References*
1. Briand C., Lehaux T, "The multi-agent project scheduling problem : the fair share of stress", 12th International Workshop devoted to Project Management and Scheduling (PMS 2010), Tours (France), 26-28 April 2010.
2. Briand C., Billaut J.-C, "Cooperative project scheduling with controllable processing times: a game theory framework", Emerging Technologies and Factory Automation (ETFA 2011), Toulouse (France), 5-9 September 2011.
3. Briand, C., Agnetis, A., & Billaut, J.-C. (2011), 'The multiagent project scheduling problem: complexity of finding a minimum-makespan Nash equilibrium', to be presented to the 13th International Conference on Project Management and Scheduling, Leuven, Belgium.
4. Anton Chechetka and Katia Sycara, "An Any-space Algorithm for Distributed Constraint Optimization", Proceedings of AAAI Spring Symposium on Distributed Plan and Schedule Management, March", 2006.
5. Jonathan Gaudreault, Jean-Marc Frayret, and Gilles Pesant. 2009. Distributed search for supply chain coordination. Comput. Ind. 60, 6 (August 2009), 441-451.
6. William Yeoh, Ariel Felner, and Sven Koenig. 2008. BnB-ADOPT: an asynchronous branch-and-bound DCOP algorithm. In Proceedings of the 7th International Joint Conference on autonomous agents and multiagent systems - Volume 2 (AAMAS '08), Vol. 2. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 591-598.
__________________________________________________________________________________________
*Subject* Solving multiagent combinatorial optimization problems: centralized and decentralized approaches
*Duration* September 2012 - September 2015
*Deadline for Application* 23 March 2012
*General context*
This thesis is funded by the EDSYS Doctoral School on the basis of a Doctoral contract (from 1374,21€ to 1651,90 € per month net)
*How to Apply*
Please send a CV, a covering letter, your scores and ranking during the last two years of academic studies, and a letter(s) of recommendation
to briand@laas.fr and huguet@laas.fr.
*Description*
In many applicative fields, decision processes involve a set of agents; each one having their own decision autonomy and managing their own constraints and objectives. Agents need to cooperate together to fulfil a global objective, providing their local objective is also optimized or, at least, kept close to a given satisfying value. In the literature, such a decision framework is often referred as "multiagent combinatorial optimization". In the context of multiobjective optimization, seeking a "fair" strategy that satisfies agents' objectives and, which also remains acceptable in a global viewpoint, has been considered in several papers (e.g. [1]). In the context of game theory, some authors also take an interest in finding a stable strategy (Nash equilibrium), which optimizes the global objective (e.g. [2, 3]), aiming at measuring the so-called price of stability.
The selected applicant will investigate the complexity of such problems for various classical OR problems, and propose centralized or decentralized algorithms for solving them. Concerning decentralized algorithms, he/she will take benefit from some already existing approaches connected to the field of Distributed Constraint Optimization (see [3, 4, 5]).
Required skills
Applicants should have an outstanding academic record and a master's degree in computer science. They should have good programming skills, an interest in, as well as a good understanding of, Combinatorial Optimization, and should be knowledgeable in at least some of the methods that will be investigated: Constraint Programming, Integer Programming, and Game Theory. Prior knowledge of French is an advantage, although not mandatory.
*Working environment*
The student will work on this project in collaboration with Marie-José Huguet and Cyril Briand, and more generally with members of the MOGISA group (http://www.laas.fr/MOGISA-EN/) at LAAS. The scientific activities of the group are focused on scheduling, transportation, discrete optimization, and constraint satisfaction.
*References*
1. Briand C., Lehaux T, "The multi-agent project scheduling problem : the fair share of stress", 12th International Workshop devoted to Project Management and Scheduling (PMS 2010), Tours (France), 26-28 April 2010.
2. Briand C., Billaut J.-C, "Cooperative project scheduling with controllable processing times: a game theory framework", Emerging Technologies and Factory Automation (ETFA 2011), Toulouse (France), 5-9 September 2011.
3. Briand, C., Agnetis, A., & Billaut, J.-C. (2011), 'The multiagent project scheduling problem: complexity of finding a minimum-makespan Nash equilibrium', to be presented to the 13th International Conference on Project Management and Scheduling, Leuven, Belgium.
4. Anton Chechetka and Katia Sycara, "An Any-space Algorithm for Distributed Constraint Optimization", Proceedings of AAAI Spring Symposium on Distributed Plan and Schedule Management, March", 2006.
5. Jonathan Gaudreault, Jean-Marc Frayret, and Gilles Pesant. 2009. Distributed search for supply chain coordination. Comput. Ind. 60, 6 (August 2009), 441-451.
6. William Yeoh, Ariel Felner, and Sven Koenig. 2008. BnB-ADOPT: an asynchronous branch-and-bound DCOP algorithm. In Proceedings of the 7th International Joint Conference on autonomous agents and multiagent systems - Volume 2 (AAMAS '08), Vol. 2. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 591-598.