Author: "Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC)" - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC)"' showing total 369 results

Start Over Author "Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC)"

369 results on '"Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC)"'

1. Octal Games on Graphs: The game 0.33 on subdivided stars and bistars

Author: Sylvain Gravier, Laurent Beaudou, Julien Moncel, Eric Sopena, Aline Parreau, Pierre Coupechoux, Antoine Dailly, Université Clermont Auvergne [2017-2020] (UCA [2017-2020]), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Institut Fourier (IF ), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), ANR-14-CE25-0006,GAG,Jeux et graphes(2014), Université Clermont Auvergne (UCA), Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J), Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA), Institut Fourier (IF), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université Sciences et Technologies - Bordeaux 1-Université Bordeaux Segalen - Bordeaux 2, ANR-14-CE25-0006,GAG,Games and Graphs, Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université Clermont Auvergne ( UCA ), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes ( LAAS-ROC ), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] ( LAAS ), Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ) -Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ), Graphes, AlgOrithmes et AppLications ( GOAL ), Laboratoire d'InfoRmatique en Image et Systèmes d'information ( LIRIS ), Université Lumière - Lyon 2 ( UL2 ) -École Centrale de Lyon ( ECL ), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 ( UCBL ), Université de Lyon-Centre National de la Recherche Scientifique ( CNRS ) -Institut National des Sciences Appliquées de Lyon ( INSA Lyon ), Université de Lyon-Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Lumière - Lyon 2 ( UL2 ) -École Centrale de Lyon ( ECL ), Université de Lyon-Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ), Institut Fourier ( IF ), Centre National de la Recherche Scientifique ( CNRS ) -Université Grenoble Alpes ( UGA ), Laboratoire Bordelais de Recherche en Informatique ( LaBRI ), and Centre National de la Recherche Scientifique ( CNRS ) -École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université Sciences et Technologies - Bordeaux 1-Université Bordeaux Segalen - Bordeaux 2
Subjects: FOS: Computer and information sciences, Discrete Mathematics (cs.DM), General Computer Science, Octal, Combinatorial game theory, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [ MATH.MATH-CO ] Mathematics [math]/Combinatorics [math.CO], Theoretical Computer Science, Combinatorics, Octal Games, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Mathematics - Combinatorics, Mathematics, Heap (data structure), Connected component, Discrete mathematics, ComputingMilieux_PERSONALCOMPUTING, [ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM], 020207 software engineering, Graph, Octal game, Vertex (geometry), Stars, Subtraction Games, Combinatorial Games, 020201 artificial intelligence & image processing, Combinatorics (math.CO), Graphs, Computer Science - Discrete Mathematics
Abstract: International audience; Octal games are a well-defined family of two-player games played on heaps of counters, in which the players remove alternately a certain number of counters from a heap, sometimes being allowed to split a heap into two nonempty heaps, until no counter can be removed anymore. We extend the definition of octal games to play them on graphs: heaps are replaced by connected components and counters by vertices. Thus, an octal game on a path P_n is equivalent to playing the same octal game on a heap of n counters. We study one of the simplest octal games, called 0.33, in which the players can remove one vertex or two adjacent vertices without disconnecting the graph. We study this game on trees and give a complete resolution of this game on subdivided stars and bistars.
Published: 2018
Full Text: View/download PDF

2. A Study of Evacuation Planning for Wildfires

Author: Artigues , Christian, Hébrard , Emmanuel, Pencolé , Yannick, Schutt , Andreas, Stuckey , Peter, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Équipe DIagnostic, Supervision et COnduite (LAAS-DISCO), Data61 [Canberra] (CSIRO), Australian National University (ANU)-Commonwealth Scientific and Industrial Research Organisation [Canberra] (CSIRO), Department of Computing and Information Systems, University of Melbourne, European Project: 691161,H2020,H2020-MSCA-RISE-2015,GEO-SAFE(2016), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] ( LAAS ), Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes ( LAAS-ROC ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ) -Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Équipe DIagnostic, Supervision et COnduite ( LAAS-DISCO ), Data61 [Canberra] ( CSIRO ), Australian National University ( ANU ) -Commonwealth Scientific and Industrial Research Organisation [Canberra] ( CSIRO ), and European Project : 691161,H2020,H2020-MSCA-RISE-2015,GEO-SAFE ( 2016 )
Subjects: [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [ INFO.INFO-RO ] Computer Science [cs]/Operations Research [cs.RO]
Abstract: International audience; The GEO-SAFE project gathers researchers and fire emergency practitioners from EU and Australia with the aim to design innovative models and efficient response tools based on optimization methods for fighting wildfires. In this paper, we consider an evacuation planning problem issued from discussions with practitioners, where a wildfire is threatening a region with intermediate populated centres. As in earlier approaches in case of flood, we use a constraint optimization model involving malleable tasks to represent the evacuation of a population and a cumulative constraint per route segments. Indeed, in order to mitigate congestion risks, the authorities may delay the start of the evacuation but they may also affect the rate of evacuation by modulating the method used to raise the alarm. However, we consider a different objective: we maximize the minimum " safety margin " , weighted by the population, over every road segment. We introduce a new heuristic and a global flow constraint propa-gator. Moreover, we also propose an instance generator based on a random generation of road networks and basic fire propagation models. This generator produces challenging benchmarks even with very few evacuation tasks. Finally, we report the results of extensive computational experiments done using CP Optimizer.
Published: 2018

3. Algorithms for the Flexible Cyclic Jobshop Problem

Author: Idir Hamaz, Felix Quinton, Laurent Houssin, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes ( LAAS-ROC ), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] ( LAAS ), Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Toulouse III - Paul Sabatier ( UPS ), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique ( CNRS ) -Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), and Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique ( CNRS )
Subjects: Flexibility (engineering), 0209 industrial biotechnology, Schedule, Mathematical optimization, 021103 operations research, Job shop scheduling, Computer science, 0211 other engineering and technologies, Context (language use), 02 engineering and technology, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Cycle time, 020901 industrial engineering & automation, Feature (machine learning), Robot, Heuristics, [ INFO.INFO-RO ] Computer Science [cs]/Operations Research [cs.RO]
Abstract: International audience; This paper considers the cyclic jobshop problem in a flexible context. The aim is to find the minimum cycle time of a periodic schedule. The flexibility feature comes from the ability of the machines or robots to perform several kinds of tasks. Hence, the scheduling problem does not only concern starting time of tasks but also on which machines the tasks will be performed. We propose an exact method to solve this problem and two heuristics.
Published: 2018
Full Text: View/download PDF

4. Data Instance generator and optimization models for evacuation planning in the event of wildfire

Author: Artigues, Christian, Hébrard, Emmanuel, Pencolé, Yannick, Schutt, Andreas, Stuckey, Peter J., Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Équipe DIagnostic, Supervision et COnduite (LAAS-DISCO), Data61 [Canberra] (CSIRO), Australian National University (ANU)-Commonwealth Scientific and Industrial Research Organisation [Canberra] (CSIRO), Department of Computing and Information Systems, University of Melbourne, Gabriele Di Stefano, Alfredo Navarra, European Project: 691161,H2020,H2020-MSCA-RISE-2015,GEO-SAFE(2016), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] ( LAAS ), Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes ( LAAS-ROC ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ) -Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Équipe DIagnostic, Supervision et COnduite ( LAAS-DISCO ), Data61 [Canberra] ( CSIRO ), Australian National University ( ANU ) -Commonwealth Scientific and Industrial Research Organisation [Canberra] ( CSIRO ), European Project : 691161,H2020,H2020-MSCA-RISE-2015,GEO-SAFE ( 2016 ), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), and Université Fédérale Toulouse Midi-Pyrénées
Subjects: [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [ INFO.INFO-RO ] Computer Science [cs]/Operations Research [cs.RO]
Abstract: International audience; One critical part of decision support during the response phase to a wildfire is the ability to perform large-scale evacuation planning. While in practice most evacuation planning is principally designed by experts using simple heuristic approaches or scenario simulations, more recently optimization approaches to evacuation planning have been carried out, notably in the context of floodings. Evacuation planning in case of wildfires is much harder as wildfire propagations are inherently less predictable than floods. This paper present a new optimization model for evacuation planning in the event of wildfire aiming at maximizing the temporal safety margin between the evac-uees and the actual or potential wildfire front. As a first contribution, an open-source data instance generator based on road network generation via quadtrees and a basic fire propagation model is proposed to the community. As a second contribution we propose 0–1 integer programming and constraint programming formulations enhanced with a 1 simple compression heuristic that are compared on 240 problem instances build by the generator. The results show that the generated instances are computationally challenging and that the contraint programming framework obtains the best performance.
Published: 2018

5. Codes and subtraction and pursuit games in graphs

Author: Coupechoux , Pierre, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), INSA de Toulouse, Julien Moncel, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes ( LAAS-ROC ), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] ( LAAS ), Centre National de la Recherche Scientifique ( CNRS ) -Université Toulouse III - Paul Sabatier ( UPS ), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Institut National Polytechnique [Toulouse] ( INP ) -Centre National de la Recherche Scientifique ( CNRS ) -Université Toulouse III - Paul Sabatier ( UPS ), and Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Institut National Polytechnique [Toulouse] ( INP )
Subjects: [ INFO.INFO-GT ] Computer Science [cs]/Computer Science and Game Theory [cs.GT], Graph theory, Identifying colorings, Colorations identifiantes, Identifying codes, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Codes identifiants, Théorie des graphes, Firefighter, Game theory, Théorie des jeux, 0.33
Abstract: Identifying codes were introduced in 1998 by Karpovsky, Chakrabarty and Levitin. An identifying code is a subgraph such that each vertex is uniquely identified by the vertices in its neighborhood. There are several variants of these codes, including a colored version where the vertices are identified by the colors in their neighborhood. In this phd, we want to build an identifying coloring of a large cycle, given a fixed number of colors. We also studied identified codes in a certain class of oriented graphs: tournaments. We have also studied some topics in the game theory. The first one is a generalization of octal games, where we play on a graph instead of a heap. More precisely, the 0.33 game; each player can remove one or two vertices in a graph, with no disconnection allowed. The first player who cannot play loses. We studied this game in some graph classes: subdivided stars and subdivided bistars. The other game is called the Firefighter game. It's a one player game, where this one wants to contain a spreading fire in a graph. We solved a conjecture about this game, and introduced the online version of the game, for which we found some approximation results.; Les codes identifiants ont été introduits en 1998 par Karpovsky, Chakrabarty et Levitin. Un code identifiant est un sous-graphe tel que chaque sommet est identifié de manière unique par les sommets du code qui l'entourent. Il existe plusieurs variantes de ces codes, dont notamment une version colorée dans laquelle les sommets sont identifiés par les couleurs dans leur voisinage. Dans cette thèse, nous cherchons en particulier à construire un cycle le plus grand possible qui admette une coloration identifiante, étant donné un nombre de couleurs fixé. Nous avons aussi étudié le problème des codes identifiants sur une classe particulière de graphes orientés : les tournois. Dans une seconde partie, nous avons aussi étudié deux jeux particuliers. Le premier est une généralisation des jeux octaux - qui se jouent normalement sur un tas - aux graphes. Plus précisemment, le jeu 0.33 ; chaque joueur peut retirer un ou deux sommets voisins d'un graphe, sans déconnecter ce dernier. Le premier qui ne peut plus jouer perd. Nous avons été capable de caractériser les issues de ce jeu dans des classes de graphes particulières, les étoiles subdivisées et les bi-étoiles subdivisées. Le second jeu est appelé le jeu du Pompier (Firefighter). Il consiste à arrêter un feu qui se propage dans un graphe en protégeant des sommets à chaque tour. Nous avons résolu une conjecture sur ce jeu, et introduit la version online, pour laquelle nous avons pu donner des résultats d'approximation.
Published: 2018

6. GeoSafe – Evacuation planning problems

Author: Artigues, Christian, Hébrard, Emmanuel, Pencolé, Yannick, Schutt, Andreas, Stuckey, Peter, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Équipe DIagnostic, Supervision et COnduite (LAAS-DISCO), Data61 [Canberra] (CSIRO), Australian National University (ANU)-Commonwealth Scientific and Industrial Research Organisation [Canberra] (CSIRO), Department of Computing and Information Systems, University of Melbourne, European Project: 691161,H2020,H2020-MSCA-RISE-2015,GEO-SAFE(2016), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] ( LAAS ), Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes ( LAAS-ROC ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ) -Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Équipe DIagnostic, Supervision et COnduite ( LAAS-DISCO ), Data61 [Canberra] ( CSIRO ), Australian National University ( ANU ) -Commonwealth Scientific and Industrial Research Organisation [Canberra] ( CSIRO ), European Project : 691161,H2020,H2020-MSCA-RISE-2015,GEO-SAFE ( 2016 ), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), and Université Fédérale Toulouse Midi-Pyrénées
Subjects: [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [ INFO.INFO-RO ] Computer Science [cs]/Operations Research [cs.RO]
Abstract: This paper aims at identifying new challenging variants of the evacuation planning problems, especially in case of bush fires, based on exchanges with practitioners in the context of the GeoSafe project. A large amount of work has been carried out at NICTA mainly in the context of floodings, which can be easily transposed to evacuation in case of fires. .We present a state-of-the-art review of these papers and we provide new research directions for the GeoSafe project.
Published: 2018

7. Octal Games on Graphs: The game 0.33 on subdivided stars and bistars. Full proof of Theorem 22

Author: Beaudou , Laurent, Coupechoux , Pierre, Dailly , Antoine, Gravier , Sylvain, Moncel , Julien, Parreau , Aline, Sopena , Eric, Université Clermont Auvergne [2017-2020] (UCA [2017-2020]), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), Institut Fourier (IF ), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Clermont Auvergne ( UCA ), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes ( LAAS-ROC ), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] ( LAAS ), Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ) -Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ), Graphes, AlgOrithmes et AppLications ( GOAL ), Laboratoire d'InfoRmatique en Image et Systèmes d'information ( LIRIS ), Université Lumière - Lyon 2 ( UL2 ) -École Centrale de Lyon ( ECL ), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 ( UCBL ), Université de Lyon-Centre National de la Recherche Scientifique ( CNRS ) -Institut National des Sciences Appliquées de Lyon ( INSA Lyon ), Université de Lyon-Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Lumière - Lyon 2 ( UL2 ) -École Centrale de Lyon ( ECL ), Université de Lyon-Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ), Institut Fourier ( IF ), Centre National de la Recherche Scientifique ( CNRS ) -Université Grenoble Alpes ( UGA ), Laboratoire Bordelais de Recherche en Informatique ( LaBRI ), Centre National de la Recherche Scientifique ( CNRS ) -École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université Sciences et Technologies - Bordeaux 1-Université Bordeaux Segalen - Bordeaux 2, Université Clermont Auvergne (UCA), Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J), Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA), Institut Fourier (IF), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA), and Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université Sciences et Technologies - Bordeaux 1-Université Bordeaux Segalen - Bordeaux 2
Subjects: [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [ MATH.MATH-CO ] Mathematics [math]/Combinatorics [math.CO]
Abstract: We give a full proof of Theorem 22 of "Octal Games on Graphs: The game 0.33 on subdivided stars and bistars".
Published: 2018

8. OPTIMAL CONVERGENCE RATES FOR NESTEROV ACCELERATION

Author: Jean-François Aujol, Charles Dossal, Aude Rondepierre, Institut de Mathématiques de Bordeaux ( IMB ), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux ( UB ) -Institut Polytechnique de Bordeaux ( Bordeaux INP ) -Centre National de la Recherche Scientifique ( CNRS ), Institut de Mathématiques de Toulouse UMR5219 ( IMT ), Université Toulouse 1 Capitole ( UT1 ) -Université Toulouse - Jean Jaurès ( UT2J ) -Université Toulouse III - Paul Sabatier ( UPS ), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-PRES Université de Toulouse-Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Centre National de la Recherche Scientifique ( CNRS ), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes ( LAAS-ROC ), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] ( LAAS ), Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Toulouse III - Paul Sabatier ( UPS ), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique ( CNRS ) -Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique ( CNRS ), Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Institut de Mathématiques de Toulouse UMR5219 (IMT), Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UPS), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-PRES Université de Toulouse-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] (LAAS), Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UPS), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique [Toulouse] (INP)-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UPS), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique [Toulouse] (INP), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), and Université de Toulouse (UT)
Subjects: Lyapunov function, [ MATH.MATH-OC ] Mathematics [math]/Optimization and Control [math.OC], Work (thermodynamics), 0211 other engineering and technologies, Acceleration (differential geometry), 010103 numerical & computational mathematics, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, symbols.namesake, Convergence (routing), FOS: Mathematics, Applied mathematics, ODEs, 0101 mathematics, Mathematics - Optimization and Control, Mathematics, Lyapunov functions, 021103 operations research, Lojasiewicz property, Ode, Function (mathematics), Computer Science::Numerical Analysis, Rate of convergence, Optimization and Control (math.OC), symbols, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Convex function, optimization, Software, rate of convergence
Abstract: International audience; In this paper, we study the behavior of solutions of the ODE associated to Nesterov acceleration. It is well-known since the pioneering work of Nesterov that the rate of convergence $O(1/t^2)$ is optimal for the class of convex functions with Lipschitz gradient. In this work, we show that better convergence rates can be obtained with some additional geometrical conditions, such as \L ojasiewicz property. More precisely, we prove the optimal convergence rates that can be obtained depending on the geometry of the function $F$ to minimize. The convergence rates are new, and they shed new light on the behavior of Nesterov acceleration schemes. We prove in particular that the classical Nesterov scheme may provide convergence rates that are worse than the classical gradient descent scheme on sharp functions: for instance, the convergence rate for strongly convex functions is not geometric for the classical Nesterov scheme (while it is the case for the gradient descent algorithm). This shows that applying the classical Nesterov acceleration on convex functions without looking more at the geometrical properties of the objective functions may lead to sub-optimal algorithms.
Published: 2018
Full Text: View/download PDF

9. Technologies respectueuses de la vie privée pour le covoiturage

Author: Aïvodji, Ulrich Matchi, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes ( LAAS-ROC ), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] ( LAAS ), Centre National de la Recherche Scientifique ( CNRS ) -Université Toulouse III - Paul Sabatier ( UPS ), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Institut National Polytechnique [Toulouse] ( INP ) -Centre National de la Recherche Scientifique ( CNRS ) -Université Toulouse III - Paul Sabatier ( UPS ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Institut National Polytechnique [Toulouse] ( INP ), Équipe Tolérance aux fautes et Sûreté de Fonctionnement informatique ( LAAS-TSF ), Université Toulouse 3 Paul Sabatier (UT3 Paul Sabatier), M.J.HUGUET, Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ) -Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ), Équipe Tolérance aux fautes et Sûreté de Fonctionnement informatique (LAAS-TSF), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Université Paul Sabatier - Toulouse III, Marie-José Huguet, and Marc-Olivier Killijian
Subjects: [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Ridesharing, [ INFO ] Computer Science [cs], Privacy, Covoiturage, [ INFO.INFO-AU ] Computer Science [cs]/Automatic Control Engineering, Privacy enhancing technologies, Technologies renforçant la vie privée, Vie privée
Abstract: National audience; The emergence of mobile phones and connected objects has profoundly changed our daily lives. These devices, thanks to the multitude of sensors they embark, allow access to a broad spectrum of services. In particular, position sensors have contributed to the development of location-based services such as navigation, ridesharing, real-time congestion tracking. . . Despite the comfort offered by these services, the collection and processing of location data seriously infringe the privacy of users. In fact, these data can inform service providers about points of interests (home, workplace, sexual orientation), habits and social network of the users. In general, the protection of users’ privacy can be ensured by legal or technical provisions. While legal measures may discourage service providers and malicious individuals from infringing users’ privacy rights, the effects of such measures are only observable when the offense is already committed and detected. On the other hand, the use of privacy-enhancing technologies (PET) from the design phase of systems can reduce the success rate of attacks on the privacy of users. The main objective of this thesis is to demonstrate the viability of the usage of PET as a means of location data protection in ridesharing services. This type of location-based ser- vice, by allowing drivers to share empty seats in vehicles, helps in reducing congestion, CO2 emissions and dependence on fossil fuels. In this thesis, we study the problems of synchro- nization of itineraries and matching in the ridesharing context, with an explicit consideration of location data (origin, destination) protection constraints. The solutions proposed in this thesis combine multimodal routing algorithms with sev- eral privacy-enhancing technologies such as homomorphic encryption, private set intersection, secret sharing, secure comparison of integers. They guarantee privacy properties including anonymity, unlinkability, and data minimization. In addition, they are compared to conven- tional solutions, which do not protect privacy. Our experiments indicate that location data protection constraints can be taken into account in ridesharing services without degrading their performance.; L’émergence des téléphones mobiles et objets connectés a profondément changé notre vie quotidienne. Ces dispositifs, grâce à la multitude de capteurs qu’ils em- barquent, permettent l’accès à un large spectre de services. En particulier, les capteurs de position ont contribué au développent des services de localisation tels que la navigation, le covoiturage, le suivi de la congestion en temps réel. . . En dépit du confort offert par ces services, la collecte et le traitement des données de localisation portent de sérieuses atteintes à la vie privée des utilisateurs. En effet, ces données peuvent renseigner les fournisseurs de services sur les points d’intérêt (domicile, lieu de travail, orientation sexuelle), les habitudes ainsi que le réseau social des utilisateurs. D’une façon générale, la protection de la vie privée des utilisateurs peut être assurée par des dispositions légales ou techniques. Même si les mesures d’ordre légal peuvent dissuader les fournisseurs de services et les individus malveillants à enfreindre le droit à la vie privée des utilisateurs, les effets de telles mesures ne sont observables que lorsque l’infraction est déjà commise et détectée. En revanche, l’utilisation des technologies renforçant la protection de la vie privée (PET pour Privacy Enhancing Technologies) dès la phase de conception des systèmes permet de réduire le taux de réussite des attaques contre la vie privée des utilisateurs. L’objectif principal de cette thèse est de montrer la viabilité de l’utilisation des PET comme moyens de protection des données de localisation dans les services de covoiturage. Ce type de service de localisation, en aidant les conducteurs à partager les sièges vides dans les véhicules, contribue à réduire les problèmes de congestion, d’émissions et de dépendance aux combustibles fossiles. Dans cette thèse, nous étudions les problèmes de synchronisation d’itinéraires et d’appariement relatifs au covoiturage avec une prise en compte explicite des contraintes de protection des données de localisation (origine, destination). Les solutions proposées dans cette thèse combinent des algorithmes de calcul d’itinéraires multimodaux avec plusieurs techniques de protection de la vie privée telles que le chiffrement homomorphe, l’intersection sécurisée d’ensembles, le secret partagé, la comparaison sécurisée dentier. Elles garantissent des propriétés de protection de vie privée comprenant l’anonymat, la non-chainabilité et la minimisation des données. De plus, elles sont comparées à des so- lutions classiques, ne protégeant pas la vie privée. Nos expérimentations indiquent que les contraintes de protection des données privées peuvent être prise en compte dans les services de covoiturage sans dégrader leurs performances.
Published: 2018

10. Analytical Solutions for Impulsive Elliptic Out-of-Plane Rendezvous Problem via Primer Vector Theory

Author: Aude Rondepierre, Denis Arzelier, Romain Serra, Équipe Méthodes et Algorithmes en Commande ( LAAS-MAC ), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] ( LAAS ), Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ) -Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes ( LAAS-ROC ), Institut de Mathématiques de Toulouse UMR5219 ( IMT ), Centre National de la Recherche Scientifique ( CNRS ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -PRES Université de Toulouse-Université Paul Sabatier - Toulouse 3 ( UPS ) -Université Toulouse - Jean Jaurès ( UT2J ) -Université Toulouse 1 Capitole ( UT1 ), Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Institut de Mathématiques de Toulouse UMR5219 (IMT), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), and Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)
Subjects: [ MATH.MATH-OC ] Mathematics [math]/Optimization and Control [math.OC], 0209 industrial biotechnology, 02 engineering and technology, linear equations of motion, fuel optimal space trajectories, 020901 industrial engineering & automation, 0203 mechanical engineering, Control theory, Simple (abstract algebra), Applied mathematics, Boundary value problem, Electrical and Electronic Engineering, Mathematics, Space rendezvous, impulsive maneuvers, 020301 aerospace & aeronautics, Spacecraft, business.industry, Rendezvous, primer vector theory, Aerodynamics, Optimal control, Control and Systems Engineering, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Orbital rendezvous, business, Rendezvous problem
Abstract: International audience; This paper focuses on the fixed-time minimum-fuel out-of-plane rendezvous between close elliptic orbits of an active spacecraft, with a passive target spacecraft, assuming a linear impulsive setting. It is shown that the out-of-plane elliptic relative dynamics are simple enough to allow for an analytical solution of the problem reviewed. Indeed, the approach relies on the primer vector theory by writing down and directly solving the optimality necessary conditions. After analyzing the characteristics of the dynamics of the optimal primer vector candidates, the complete analytical optimal solution is obtained for arbitrary durations of the rendezvous and arbitrary boundary conditions.
Published: 2018
Full Text: View/download PDF

11. Exact values for three domination-like problems in circular and infinite grid graphs of small height

Author: Bouznif, Marwane, Darlay, Julien, Moncel, Julien, Preissmann, Myriam, OC ( G-SCOP_OC ), Laboratoire des sciences pour la conception, l'optimisation et la production ( G-SCOP ), Université Joseph Fourier - Grenoble 1 ( UJF ) -Institut polytechnique de Grenoble - Grenoble Institute of Technology ( Grenoble INP ) -Institut National Polytechnique de Grenoble ( INPG ) -Centre National de la Recherche Scientifique ( CNRS ) -Université Grenoble Alpes ( UGA ) -Université Joseph Fourier - Grenoble 1 ( UJF ) -Institut polytechnique de Grenoble - Grenoble Institute of Technology ( Grenoble INP ) -Institut National Polytechnique de Grenoble ( INPG ) -Centre National de la Recherche Scientifique ( CNRS ) -Université Grenoble Alpes ( UGA ), Innovation 24 & LocalSolver, Bouygues-Bouygues, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes ( LAAS-ROC ), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] ( LAAS ), Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Toulouse III - Paul Sabatier ( UPS ), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique ( CNRS ) -Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique ( CNRS ), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Optimisation Combinatoire (G-SCOP_OC ), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] (LAAS), Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UPS), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique [Toulouse] (INP)-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UPS), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique [Toulouse] (INP), OC (G-SCOP_OC), and Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)
Subjects: ACM : G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory/G.2.2.1: Graph labeling, FOS: Computer and information sciences, ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory/G.2.2.4: Path and circuit problems, ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory/G.2.2.1: Graph labeling, Discrete Mathematics (cs.DM), [ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM], 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, locating-dominating code, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory/G.2.2.0: Graph algorithms, 01 natural sciences, grid, ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory, identifying code, ACM : G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory/G.2.2.4: Path and circuit problems, 010201 computation theory & mathematics, graph algorithm, ACM : G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory/G.2.2.0: Graph algorithms, 0202 electrical engineering, electronic engineering, information engineering, ACM : G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory, locating-total-dominating code, Computer Science - Discrete Mathematics
Abstract: International audience; In this paper we study three domination-like problems, namely identifying codes, locating-dominating codes, and locating-total-dominating codes. We are interested in finding the minimum cardinality of such codes in circular and infinite grid graphs of given height. We provide an alternate proof for already known results, as well as new results. These were obtained by a computer search based on a generic framework, that we developed earlier, for the search of a minimum labeling satisfying a pseudo-d-local property in rotagraphs.
Published: 2017
Full Text: View/download PDF

12. Blossom: an Anytime Algorithm for Computing Optimal Decision Trees

Author: Demirović, Emir, Hebrard, Emmanuel, Jean, Louis, Delft University of Technology (TU Delft), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Jolibrain, Barbara Engelhardt, Emma Brunskill, Kyunghyun Cho, and ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019)
Subjects: Decision Trees, Search, [INFO]Computer Science [cs]
Abstract: International audience; We propose a simple algorithm to learn optimal decision trees of bounded depth. This algorithm is essentially an anytime version of the state-ofthe-art dynamic programming approach. It has virtually no overhead compared to heuristic methods and is comparable to the best exact methods to prove optimality on most data sets. Experiments show that whereas existing exact methods hardly scale to deep trees, this algorithm learns trees comparable to standard heuristics without computational overhead, and can significantly improve their accuracy when given more computation time, even for deep trees.
Published: 2023

13. Fast and Robust Resource-Constrained Scheduling with Graph Neural Networks

Author: Teichteil-Königsbuch, Florent, Povéda, Guillaume, González de Garibay Barba, Guillermo, Luchterhand, Tim, Thiébaux, Sylvie, Airbus central R&T, AI research, Airbus Group [Madrid], Université de Toulouse (UT), Institut National des Sciences Appliquées (INSA), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Équipe Robotique et InteractionS (LAAS-RIS), Australian National University (ANU), Airbus R&T, ARC grant DP220103815, and European Project: 101070149,TUPLES
Subjects: Machine Learning, Optimisation in Hindsight, Scheduling, Stochastic Durations, Graph Neural Networks, Resource Constrained Project Scheduling, Constraint Programming, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract: International audience; Resource-Constrained Project Scheduling Problems (RCPSPs) are NP-complete, which makes it challenging to efficiently solve large instances and robustify solutions in the presence of uncertainty. To remedy this, we learn to efficiently mimic the solutions produced by Constraint Programming (CP) solver, using a Graph Neural Network (GNN) architecture designed to capture the structure of RCPSPs. Since the GNN solution may violate constraints, we ensure schedule feasibility at inference time by extracting the task ordering from the GNN schedule and post-processing it with the well-known Schedule Generation Scheme (SGS). We find that SIREN, the resulting algorithm, produces schedules that are of higher quality than those produced by the CP solver within the same computation time budget. The speed and solution quality of SIREN make it suitable as a component of an on-line scenario-based optimisation procedure for RCPSPs with stochastic durations. This leads to the SERENE system, which robustly selects, in real-time, the best next tasks to start in order to minimise the average makespan over the scenarios. Empirically, SERENE achieves better average makespan over different realisations of uncertainty than deterministic algorithms that continuously reschedule on the basis of either the worst, best or average task durations.
Published: 2023

14. Improving Fairness Generalization Through a Sample-Robust Optimization Method

Author: Julien Ferry, Ulrich Aïvodji, Sébastien Gambs, Marie-José Huguet, Mohamed Siala, Ecole de Technologie Supérieure [Montréal] (ETS), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Université du Québec à Montréal = University of Québec in Montréal (UQAM), ANR-11-LABX-0040,CIMI,Centre International de Mathématiques et d'Informatique (de Toulouse)(2011), and ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019)
Subjects: Fairness, Artificial Intelligence, Generalization, Distributionally Robust Optimization, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Supervised Learning, Software, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract: International audience; Unwanted bias is a major concern in machine learning, raising in particular significant ethical issues when machine learning models are deployed within high-stakes decision systems. A common solution to mitigate it is to integrate and optimize a statistical fairness metric along with accuracy during the training phase. However, one of the main remaining challenges is that current approaches usually generalize poorly in terms of fairness on unseen data. We address this issue by proposing a new robustness framework for statistical fairness in machine learning. The proposed approach is inspired by the domain of Distributionally Robust Optimization and works in ensuring fairness over a variety of samplings of the training set. Our approach can be used to quantify the robustness of fairness but also to improve it when training a model. We empirically evaluate the proposed method and show that it effectively improves fairness generalization. In addition, we propose a simple yet powerful heuristic application of our framework that can be integrated into a wide range of existing fair classification techniques to enhance fairness generalization. Our extensive empirical study using two existing fair classification methods demonstrates the efficiency and scalability of the proposed heuristic approach.
Published: 2023
Full Text: View/download PDF

15. Efficient exact A* algorithm for the single unit hydro unit commitment problem

Author: Heintzmann, Alexandre, Artigues, Christian, Bendotti, Pascale, Ngueveu, Sandra Ulrich, Rottner, Cécile, EDF Labs, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), and Institut National Polytechnique (Toulouse) (Toulouse INP)
Subjects: [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract: The Hydro Unit Commitment problem (HUC) specific to hydroelectric units is part of the electricity production planning problem, called Unit Commitment Problem (UCP). More specifically, the studied case is that of the HUC with a single unit, denoted 1-HUC. The unit is located between two reservoirs. The horizon is discretized in time periods. The unit operates at a finite number of points defined as pairs of the generated power and the corresponding water flow. Several constraints are considered. Each reservoir has an initial volume, as well as window resource constraints, defined by a minimum and maximum volume per time period. At each time period, there is an additional positive, negative or zero intake of water in the reservoirs. The case of a price-taker revenue maximization problem is considered. An efficient exact A* variant, so called HA*, is proposed to solve the 1-HUC accouting for window constraints, with a reduced search space and a dedicated optimistic heuristic. This variant is compared to a classical Resource Constrained Shortest Path Problem (RCSPP) algorithm and an MILP formulation solved with CPLEX. Results show that the proposed algorithm outperforms both concurrent alternatives in terms of computational time in average on a set of realistic instances, meaning that HA* exhibits a more stable behavior with more instances solved.
Published: 2023

16. Constraint programming for the robust two-machine flow-shop scheduling problem with budgeted uncertainty

Author: Juvin, Carla, Houssin, Laurent, Lopez, Pierre, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), and Institut Supérieur de l'Aéronautique et de l'Espace (ISAE-SUPAERO)
Subjects: Mixed-Integer Linear Programming, Uncertainty Budget, Robust Optimization, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Flow-Shop Scheduling, Constraint Programming
Abstract: International audience; This paper addresses the robust two-machine permutation flow-shop scheduling problem considering non-deterministic operation processing times associated with an uncertainty budget. The objective is to minimize the makespan of the schedule. Exact solution methods incorporated within the framework of a twostage robust optimization are proposed to solve the problem. We first prove that under particular conditions the robust two-machine permutation flow-shop scheduling problem can be solved in polynomial time by the well-known Johnson's algorithm usually dedicated to the deterministic version. Then we tackle the general problem, for which we propose a column and constraint generation algorithm. We compare two versions of the algorithm. In the first version, a mixed-integer linear programming formulation is used for the master problem. In the second version, we use a constraint programming model for the master problem. To the best of our knowledge, the use of constraint programming for a master problem in a two-stage robust optimization problem is innovative. The experimental results show the very good performance of the method based on the constraint programming formulation. We also notice that Johnson's algorithm is surprisingly efficient for the robust version of the general problem.
Published: 2023

17. Fast and reliable computation of the instantaneous orbital collision probability

Author: Masson, Matthieu, Arzelier, Denis, Bréhard, Florent, Joldes, Mioara, Salvy, Bruno, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon), and ANR-20-CE48-0014,NuSCAP,Sûreté numérique pour les preuves assistées par ordinateur(2020)
Subjects: [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Laplace transform, [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], debris risk management, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, Holonomic Functions, Error bounds, Saddle-point approximation, Integration algorithm, [INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering, probability of collision, Numerical accuracy, Cancellation Problem, Power series approximation, [INFO.INFO-MS]Computer Science [cs]/Mathematical Software [cs.MS]
Abstract: International audience; Due to the increasing number of objects in Low Earth orbit, the fast and reliable estimation of the collision risk is an important challenge for spacecraft owners/operators. Among the available risk indicators, we focus on computing the instantaneous probability of collision, which can be modeled as the integral of a three-dimensional Gaussian probability density function over a Euclidean ball. We propose an efficient and accurate method for evaluating this integral. It is based on the combination of two complementary strategies. For the first one, convergent series and numerical error bounds are computed. These bounds provide a tradeoff between the accuracy needed and the number of terms to compute. The second one, using divergent series, approximates the value of the integral with a good accuracy in most cases with only a few terms computed. Based on those two methods, a hybrid algorithm is tested on cases borrowed from the literature and compared against existing methods. Several numerical results and comparisons confirm both the efficiency and robustness of our approach.
Published: 2023

18. Reasoning about Connectivity Constraints

Author: Bessiere, C., Emmanuel Hebrard, Katsirelos, G., Walsh, T., Agents, Apprentissage, Contraintes (COCONUT), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J), Unité de Mathématiques et Informatique Appliquées de Toulouse (MIAT INRA), Institut National de la Recherche Agronomique (INRA), National ICT Australia [Sydney] (NICTA), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Agents, Apprentissage, Contraintes ( COCONUT ), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier ( LIRMM ), Université de Montpellier ( UM ) -Centre National de la Recherche Scientifique ( CNRS ) -Université de Montpellier ( UM ) -Centre National de la Recherche Scientifique ( CNRS ), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes ( LAAS-ROC ), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] ( LAAS ), Centre National de la Recherche Scientifique ( CNRS ) -Université Toulouse III - Paul Sabatier ( UPS ), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Institut National Polytechnique [Toulouse] ( INP ) -Centre National de la Recherche Scientifique ( CNRS ) -Université Toulouse III - Paul Sabatier ( UPS ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Institut National Polytechnique [Toulouse] ( INP ), Unité de Mathématiques et Informatique Appliquées de Toulouse ( MIAT INRA ), Institut National de la Recherche Agronomique ( INRA ), National ICT Australia [Sydney] ( NICTA ), University of New South Wales [Sydney] ( UNSW ), Qiang Yang, Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ) -Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), and Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS )
Subjects: [SDV]Life Sciences [q-bio], [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], [ INFO.INFO-AI ] Computer Science [cs]/Artificial Intelligence [cs.AI], [ INFO.INFO-RO ] Computer Science [cs]/Operations Research [cs.RO]
Abstract: International audience; Many problems in computational sustainability involve constraints on connectivity. When designing a new wildlife corridor, we need it to be geographically connected. When planning the harvest of a forest, we need new areas to harvest to be connected to areas that have already been harvested so we can access them easily. And when town planning, we need to connect new homes to the existing utility infrastructure. To reason about connectivity, we propose a new family of global connectivity constraints. We identify when these constraints can be propagated tractably, and give some efficient, typically linear time propagators for when this is the case. We report results on several benchmark problems which demonstrate the efficiency of our propagation algorithms and the promise offered by reasoning globally about connectivity.
Published: 2015

19. Approche hybride multi-étape pour la résolution du problème de job-shop flexible robuste avec budget d'incertitude

Author: Juvin, Carla, Houssin, Laurent, Lopez, Pierre, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut Supérieur de l'Aéronautique et de l'Espace (ISAE-SUPAERO), Rennes School of Business, and ANR-18-CE10-0007,PER4MANCE,Planification Et Répartition Flexible du travail entre les OpérateuRs des chaînes d'asseMblage AéroNautiques : une approChe systémique pour gérer les risques Ergonomiques et économiques(2018)
Subjects: programmation linéaire en nombres entiers, optimisation robuste multi-étape, Problème d'ordonnancement jop-shop flexible, budget d'incertitude, programmation par contraintes, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract: National audience; Dans ce travail, nous nous intéressons à la conception de méthodes exactes pour résoudre le problème d'ordonnancement de type job-shop flexible robuste. Nous proposons pour cela une optimisation robuste en deux étapes, la première étape s’occupant de l’affectation des opérations et de leur séquencement sur les machines, la seconde déterminant la date de début des opérations. Deux modèles robustes, basés sur des formulations de programmation linéaire en nombres entiers mixtes et de programmation par contraintes, sont présentés, de même qu’un algorithme de génération de colonnes et de contraintes. Des résultats expérimentaux permettent de tirer des conclusions sur la performance des méthodes proposées.
Published: 2023

20. Hybrid Methods to Solve the Two-Stage Robust Flexible Job-Shop Scheduling Problem with Budgeted Uncertainty

Author: Carla Juvin, Laurent Houssin, Pierre Lopez, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut Supérieur de l'Aéronautique et de l'Espace (ISAE-SUPAERO), and ANR-18-CE10-0007,PER4MANCE,Planification Et Répartition Flexible du travail entre les OpérateuRs des chaînes d'asseMblage AéroNautiques : une approChe systémique pour gérer les risques Ergonomiques et économiques(2018)
Subjects: Flexible Job-Shop Scheduling, Mixed Integer Linear Programming, Uncertainty Budget, Robust Optimization, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Constraint Programming
Abstract: International audience; This paper addresses the robust flexible job-shop scheduling problem considering uncertain operation processing times associated with an uncertainty budget. Exact solution methods based on mixed integer linear programming and constraint programming are proposed to solve the problem. Such solutions are hybridized in the framework of a two-stage robust optimization, and a column and constraint generation algorithm is used to solve representative instances. The experimental results show the advantages of a two-stage approach where constraint programming and integer programming are mixed to solve a master problem and a subproblem, respectively.
Published: 2023

21. Comparing modeling alternatives for solving a non-linear single Hydro Unit Commitment problem

Author: Alexandre Heintzmann, Christian Artigues, Pascale Bendotti, Sandra Ulrich Ngueveu, Cécile Rottner, EDF Labs, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), ANR-18-CE10-0007,PER4MANCE,Planification Et Répartition Flexible du travail entre les OpérateuRs des chaînes d'asseMblage AéroNautiques : une approChe systémique pour gérer les risques Ergonomiques et économiques(2018), and ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019)
Subjects: [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract: A wide range of real world optimization problems involves continuous decisions and non-linearities. Each non-linear component of such problems can be modeled either linearly or non-linearly, considering or not additional integer variables. This results into different modeling choices that can drastically impact the solution time and quality. In this paper, we evaluate representative modeling alternatives, including common models from the literature as well as new models featuring less common functions. The single Hydro Unit Commitment problem (1-HUC) is a non-linear use case considered. The non-linearities involved come from the power produced. The power is defined as a two-dimensional non-convex and non-concave function of the water flow and head decision variables, the latter being itself a one-dimensional concave function of the turbined volume. We consider both the general problem and a common special case, assuming that the water head is fixed. Several available solvers are used for each non-linear model and the best virtual solver is retained to focus on the model capabilities rather than on the solver performance. Based on the numerical experiments, three models stand out as the most efficient in terms of computational time, solution quality and feasibility, sometimes in a counter-intuitive manner. For each of these models, a solver is highlighted as the most adequate.
Published: 2023

22. Two-phase Branch & Cut for the Symmetric Weight Matrix Knapsack polytope

Author: Heintzmann, Alexandre, Bendotti, Pascale, Rottner, Cécile, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), and EDF Labs
Subjects: Branch & Cut, Polyedral study, Polytope, [INFO]Computer Science [cs], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Knapsack problem
Abstract: In this paper, we define a new variant of the knapsack problem, the Symmetric Weight Matrix Knapsack Problem (SMKP). The (SMKP) is the core structure of the Hydro Unit Commitment being a production scheduling problem relative to hydroelectric units. The (SMKP) is proven to be NP-hard. The main contribution is a polyedral study of the (SMKP) and a dedicated two-phase Branch & Cut scheme. The polyedral study focuses on inequalities with 0-1 coefficients. Necessary facet-defining conditions are described, through a new structure called pattern encoding the symmetries of the (SMKP). A special case of patterns is identified where these conditions are necessary and sufficient. A two-phase Branch & Cut scheme is defined to exploit the symmetries on the pattern inequalities. As a pre-processing step, the first phase aims to produce patterns verifying these conditions. The second phase separates the inequalities associated to the patterns produced in the first phase at the nodes of a Branch & Cut tree. Experimental results demonstrate the efficiency of the proposed scheme in particular with respect to default CPLEX.
Published: 2023

23. Exploiting Fairness to Enhance Sensitive Attributes Reconstruction

Author: Ferry, Julien, Aïvodji, Ulrich, Gambs, Sébastien, Huguet, Marie-José, Siala, Mohamed, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Ecole de Technologie Supérieure [Montréal] (ETS), Université du Québec à Montréal = University of Québec in Montréal (UQAM), ANR-11-LABX-0040,CIMI,Centre International de Mathématiques et d'Informatique (de Toulouse)(2011), ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), and Université Fédérale Toulouse Midi-Pyrénées
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, constraint programming, Computer Science - Cryptography and Security, Computer Science - Artificial Intelligence, reconstruction attack, fairness, privacy, Machine Learning (cs.LG), [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], Artificial Intelligence (cs.AI), machine learning, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Cryptography and Security (cs.CR)
Abstract: International audience; In recent years, a growing body of work has emerged on how to learn machine learning models under fairness constraints, often expressed with respect to some sensitive attributes. In this work, we consider the setting in which an adversary has black-box access to a target model and show that information about this model's fairness can be exploited by the adversary to enhance his reconstruction of the sensitive attributes of the training data. More precisely, we propose a generic reconstruction correction method, which takes as input an initial guess made by the adversary and corrects it to comply with some user-defined constraints (such as the fairness information) while minimizing the changes in the adversary's guess. The proposed method is agnostic to the type of target model, the fairness-aware learning method as well as the auxiliary knowledge of the adversary. To assess the applicability of our approach, we have conducted a thorough experimental evaluation on two state-of-the-art fair learning methods, using four different fairness metrics with a wide range of tolerances and with three datasets of diverse sizes and sensitive attributes. The experimental results demonstrate the effectiveness of the proposed approach to improve the reconstruction of the sensitive attributes of the training set.
Published: 2023

24. Learning Hybrid Interpretable Models: Theory, Taxonomy, and Methods

Author: Ferry, Julien, Laberge, Gabriel, Aïvodji, Ulrich, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), École Polytechnique de Montréal (EPM), Ecole de Technologie Supérieure [Montréal] (ETS), ANR-11-LABX-0040,CIMI,Centre International de Mathématiques et d'Informatique (de Toulouse)(2011), and ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, Rule Sets, Rule Lists, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Statistics - Machine Learning, Machine Learning (stat.ML), Interpretability, Black-box, Hybrid Models, Machine Learning (cs.LG)
Abstract: A hybrid model involves the cooperation of an interpretable model and a complex black box. At inference, any input of the hybrid model is assigned to either its interpretable or complex component based on a gating mechanism. The advantages of such models over classical ones are two-fold: 1) They grant users precise control over the level of transparency of the system and 2) They can potentially perform better than a standalone black box since redirecting some of the inputs to an interpretable model implicitly acts as regularization. Still, despite their high potential, hybrid models remain under-studied in the interpretability/explainability literature. In this paper, we remedy this fact by presenting a thorough investigation of such models from three perspectives: Theory, Taxonomy, and Methods. First, we explore the theory behind the generalization of hybrid models from the Probably-Approximately-Correct (PAC) perspective. A consequence of our PAC guarantee is the existence of a sweet spot for the optimal transparency of the system. When such a sweet spot is attained, a hybrid model can potentially perform better than a standalone black box. Secondly, we provide a general taxonomy for the different ways of training hybrid models: the Post-Black-Box and Pre-Black-Box paradigms. These approaches differ in the order in which the interpretable and complex components are trained. We show where the state-of-the-art hybrid models Hybrid-Rule-Set and Companion-Rule-List fall in this taxonomy. Thirdly, we implement the two paradigms in a single method: HybridCORELS, which extends the CORELS algorithm to hybrid modeling. By leveraging CORELS, HybridCORELS provides a certificate of optimality of its interpretable component and precise control over transparency. We finally show empirically that HybridCORELS is competitive with existing hybrid models, and performs just as well as a standalone black box (or even better) while being partly transparent.
Published: 2023

25. Interpretable Machine Learning Models via Maximum Boolean Satisfiability

Author: Hu, Hao, Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées, INSA de Toulouse, Marie-José Huguet, Mohamed Siala, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), and Université de Toulouse (UT)
Subjects: Machine Learning, Decision Tress, Diagrammes de décision, Arbres de décision, Boolean Satisfiability, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Decision Diagrams, Satisfaisabilité booléenne, Apprentissage
Abstract: National audience; Interpretable Machine Learning models receive growing interest due to the increasing concerns in understanding the reasoning behind some crucial decisions made by modern Artificial Intelligent systems. Due to their structure, especially with small sizes, these interpretable models are inherently understandable for humans. Compared to classical heuristic methods to learn these models, recent exact methods offer more compact models or better prediction quality. In this thesis, we propose two novel exact methods via Maximum Boolean Satisfiability (MaxSAT) to learn optimal interpretable machine learning models.Our contribution starts with an original MaxSAT-based exact method to learnoptimal decision trees. This method optimizes the empirical accuracy to avoidoverfitting and also enriches the constraints to restrict the tree depth. Additionally,we integrate this MaxSAT-based method in AdaBoost, which is a classical Boostingmethod to improve the generalization performance. The experimental results showthe competitive prediction quality of this MaxSAT-based method compared to state-of-the-art heuristics and other exact methods. Additionally, clear improvements inprediction performance are observed after the integration in AdaBoost.Our second contribution is an original MaxSAT-based exact method to optimize binary decision diagrams. We introduce an initial Boolean Satisfiability (SAT) encoding to model binary decision diagrams in limited depth with perfect empirical accuracy. Next, we present how to adapt the SAT-based model into MaxSAT approach. Finally, we present a pre-processing for selecting some important features to increase the scalability of our MaxSAT-based method to optimize binary decision diagrams. The experimental results show clear advances of our MaxSAT-based method in prediction quality, compared to state-of-the-art heuristic methods. We also observe a huge shrink in encoding size and model size in comparison between our approach and state-of-the-art exact method without losing the prediction performance. In addition, great reductions in encoding size are displayed after the application of pre-processing, which boosts the scalability.; Les modèles d’apprentissage interprétables reçoivent un intérêt croissant en raisonde l’augmentation des préoccupations pour comprendre le raisonnement menantaux décisions cruciales prises par les systèmes modernes d’intelligence artificielle.En raison de leur structure, en particulier pour des petites tailles, ces modèlesinterprétables sont intrinsèquement compréhensibles pour les humains. Par rapportaux méthodes heuristiques classiques pour apprendre ces modèles, les méthodesexactes récentes offrent des modèles plus compacts ou atteingnent une meilleurequalité de prédiction. Dans cette thèse, nous proposons deux nouvelles méthodesexactes basées sur la Satisfiabilité Booléenne Maximale (MaxSAT) pour apprendredes modèles d’apprentissage interprétables optimaux.Notre contribution commence par une méthode exacte originale basée sur MaxSATpour apprendre des arbres de décision optimaux. Cette méthode optimise la précision empirique pour éviter le surapprentissage et prend également en compte des contraintes pour restreindre la profondeur de l’arbre. De plus, nous intégrons cette méthode basée sur MaxSAT à la méthode AdaBoost, qui est une méthode standard de Boosting pour améliorer les performances de généralisation. Les résultats expérimentaux montrent une qualité de prédiction compétitive de cette méthode basée sur MaxSAT par rapport à des méthodes heuristiques et exactes de l’état de l’art. En plus, des améliorations des performances de prédiction sont observées après intégration dans AdaBoost.Notre deuxième contribution est une méthode exacte originalebasée sur MaxSAT pour optimiser les diagrammes de décision binaire. Nous introduisons tout d’abord un encodage de Satisfiabilité Booléenne (SAT) pour modéliser des diagrammes de décision binaire de profondeur limitée avec une parfaite précision. Puis, nous présentons comment adapter le modèle en Satisfiabilité Booléenne Maximale. Finalement, nous présentons un pré-traitement pour la sélection de certaines caractéristiques importantes afin d’augmenter le passage à l’échelle de notre méthode MaxSAT pour optimiser les diagrammes de décision binaire. Les résultats expérimentaux montrent des avancées de notre méthode MaxSAT sur la qualité de prédiction, par rapport aux méthodes heuristiques. Nous observons également une réduction importante sur la taille d’encodage et la taille du modèle dans les comparaisons entre notre approche et une méthode exacte de l’état de l’art, sans perdre en performance de prédiction. De plus, une grande réduction sur la taille d’encodage est mise en évidence après application du pré-traitement, ce qui renforce le passage à l’échelle.
Published: 2022

26. Cooperative project scheduling with controllable processing times: a game theory framework

Author: Jean-Charles Billaut, Cyril Briand, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Université Toulouse III - Paul Sabatier (UT3), Laboratoire d'Informatique Fondamentale et Appliquée de Tours (LIFAT), Université de Tours-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J), Centre National de la Recherche Scientifique (CNRS)-Université de Tours-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes ( LAAS-ROC ), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] ( LAAS ), Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ) -Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ), Laboratoire d'Informatique de l'Université de Tours ( LI ), Université de Tours-Polytech'Tours, Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), and Université de Tours (UT)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL)
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Project network, 021103 operations research, Operations research, business.industry, Computer science, Stochastic game, 0211 other engineering and technologies, 0102 computer and information sciences, 02 engineering and technology, Schedule (project management), [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Minimax, 01 natural sciences, symbols.namesake, [ INFO.INFO-CC ] Computer Science [cs]/Computational Complexity [cs.CC], 010201 computation theory & mathematics, Nash equilibrium, symbols, Artificial intelligence, Project management, business, Game theory, [ INFO.INFO-RO ] Computer Science [cs]/Operations Research [cs.RO], Implementation theory
Abstract: International audience; This paper considers a project-scheduling environment assuming that the activities of the project network are distributed among a set of actors (or agents). Activity durations are modeled as time intervals and are controllable, meaning that every actor is allowed to shorten the duration of some activities by adding extra-money. For performing the project, actors have to collaborate with each other intending to satisfy a desired project duration. In this work, every actor's payoff corresponds to a given ratio of the total customer's payment, which itself depends on the ability of the actors to achieve the project in time, provided daily penalty costs are applied in case of tardiness. This problem can be modeled as a game, where players (actors) have to select a strategy (a duration vector for their activities) intending to maximize their profit. In this paper, the focus is put on the modeling of this project game, and on the connections between various decision problems, arising either in decision or game theory. We also study the particular case where each activity is assigned to one specific agent and a polynomial-time algorithm is proposed for finding Nash equilibrium with the smallest project makespan.
Published: 2011
Full Text: View/download PDF

27. Validated Numerics

Author: Joldes, Mioara, Centre National de la Recherche Scientifique (CNRS), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), and ANR-20-CE48-0014,NuSCAP,Sûreté numérique pour les preuves assistées par ordinateur(2020)
Subjects: Interval Arithmetic, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Newton method, D-finite functions, Finite precision evaluation, Rigorous computing, Chebyshev series
Abstract: International audience; My lecture will survey some classical and recent validated computing algorithms based on the theory of set-valued analysis, in suitable functional spaces, as well as by combining symbolic and numerical computations. These techniques are illustrated with some applications which appear in practical space mission analysis and design. This is only a short summary of the talk.
Published: 2022
Full Text: View/download PDF

28. An Efficient Approach to Data Transfer Scheduling for Long Range Space Exploration

Author: Hébrard, Emmanuel, Artigues, Christian, Lopez, Pierre, Lusson, Arnaud, Chien, Steve, Maillard, Adrien, Rabideau, Gregg, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Jet Propulsion Laboratory (JPL), NASA-California Institute of Technology (CALTECH), ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), and ANR-18-CE10-0007,PER4MANCE,Planification Et Répartition Flexible du travail entre les OpérateuRs des chaînes d'asseMblage AéroNautiques : une approChe systémique pour gérer les risques Ergonomiques et économiques(2018)
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract: International audience; Long range space missions, such as Rosetta, require robust plans of data-acquisition activities and of the resulting data transfers. In this paper we revisit the problem of assigning priorities to data transfers in order to maximize safety margin of onboard memory. We propose a fast sweep algorithm to verify the feasibility of a given priority assignment and we introduce an efficient exact algorithm to assign priorities on a single downlink window. We prove that the problem is NP-hard for several windows, and we propose several randomized heuristics to tackle the general case. Our experimental results show that the proposed approaches are able to improve the plans computed for the real mission by the previously existing method, while the sweep algorithm yields drastic accelerations.
Published: 2022
Full Text: View/download PDF

29. Learning constraints through partial queries

Author: Christian Bessiere, Clément Carbonnel, Anton Dries, Emmanuel Hebrard, George Katsirelos, Nina Narodytska, Claude-Guy Quimper, Kostas Stergiou, Dimosthenis C. Tsouros, Toby Walsh, Agents, Apprentissage, Contraintes (COCONUT), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Nokia Bell Labs, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Mathématiques et Informatique Appliquées (MIA Paris-Saclay), AgroParisTech-Université Paris-Saclay-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), VMware, Université Laval [Québec] (ULaval), University of Western Macedonia [Kozani] (UoWM), University of New South Wales [Sydney] (UNSW), and ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019)
Subjects: Linguistics and Language, Active learning, Artificial Intelligence, Constraint acquisition, Constraint programming, Language and Linguistics, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract: International audience; Learning constraint networks is known to require a number of membership queries exponential in the number of variables. In this paper, we learn constraint networks by asking the user partial queries. That is, we ask the user to classify assignments to subsets of the variables as positive or negative. We provide an algorithm, called QuAcq2, that, given a negative example, elucidates a constraint of the target network in a number of queries logarithmic in the size of the example. The whole constraint network can then be learned with a polynomial number of partial queries. We give information theoretic lower bounds for learning some simple classes of constraint networks and show that our generic algorithm is optimal in some cases. We provide a version of QuAcq2 with a cutoff mechanism that controls the time to generate a query. Our experiments illustrate the good behavior of QuAcq2 in practice, especially in the case where QuAcq2 is executed to learn the missing constraints in a partially filled constraint model. Our experiments also show that QuAcq2 requires significantly fewer queries to learn a network than its predecessor QuAcq1.
Published: 2023
Full Text: View/download PDF

30. Leveraging Integer Linear Programming to Learn Optimal Fair Rule Lists

Author: Aïvodji, Ulrich, Ferry, Julien, Gambs, Sébastien, Huguet, Marie-José, Siala, Mohamed, Ecole de Technologie Supérieure [Montréal] (ETS), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Université du Québec à Montréal = University of Québec in Montréal (UQAM), ANR-11-LABX-0040,CIMI,Centre International de Mathématiques et d'Informatique (de Toulouse)(2011), ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), Huguet, Marie-Jose, Centre International de Mathématiques et d'Informatique (de Toulouse) - - CIMI2011 - ANR-11-LABX-0040 - LABX - VALID, and Artificial and Natural Intelligence Toulouse Institute - - ANITI2019 - ANR-19-P3IA-0004 - P3IA - VALID
Subjects: [INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], Machine Learning, Fairness, Rule Lists, [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], Interpretability, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract: International audience; Fairness and interpretability are fundamental requirements for the development of responsible machine learning. However, learning optimal interpretable models under fairness constraints has been identified as a major challenge. In this paper, we investigate and improve on a state-of-the-art exact learning algorithm, called CORELS, which learns rule lists that are certifiably optimal in terms of accuracy and sparsity. Statistical fairness metrics have been integrated incrementally into CORELS in the literature. This paper demonstrates the limitations of such an approach for exploring the search space efficiently before proposing an Integer Linear Programming method, leveraging accuracy, sparsity and fairness jointly for better pruning. Our thorough experiments show clear benefits of our approach regarding the exploration of the search space.
Published: 2022

31. Fast convergence of inertial dynamics with Hessian-driven damping under geometry assumptions

Author: Aujol, Jean-François, Dossal, Charles, Hoàng, Văn Hào, Labarrière, Hippolyte, Rondepierre, Aude, Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées, Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), and ANR-19-CE23-0017,MaSDOL,Mathématiques de l'optimisation déterministe et stochastique liées à l'apprentissage profond(2019)
Subjects: Lyapunov analysis, Lojasiewicz property, Optimization and Control (math.OC), FOS: Mathematics, ODEs, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Hessian-driven damping, Convex optimization
Abstract: First-order optimization algorithms can be considered as a discretization of ordinary differential equations (ODEs) \cite{su2014differential}. In this perspective, studying the properties of the corresponding trajectories may lead to convergence results which can be transfered to the numerical scheme. In this paper we analyse the following ODE introduced by Attouch et al. in \cite{attouch2016fast}: \begin{equation*} \forall t\geqslant t_0,~\ddot{x}(t)+\frac{\alpha}{t}\dot{x}(t)+\beta H_F(x(t))\dot{x}(t)+\nabla F(x(t))=0,\end{equation*} where $\alpha>0$, $\beta>0$ and $H_F$ denotes the Hessian of $F$. This ODE can be derived to build numerical schemes which do not require $F$ to be twice differentiable as shown in \cite{attouch2020first,attouch2021convergence}. We provide strong convergence results on the error $F(x(t))-F^*$ and integrability properties on $\|\nabla F(x(t))\|$ under some geometry assumptions on $F$ such as quadratic growth around the set of minimizers. In particular, we show that the decay rate of the error for a strongly convex function is $O(t^{-\alpha-\varepsilon})$ for any $\varepsilon>0$. These results are briefly illustrated at the end of the paper.
Published: 2022

32. Solving the Time-Discrete Winter Runway Scheduling Problem: A Column Generation and Constraint Programming Approach

Author: Christian Artigues, Rainer Kolisch, M. Pohl, Technische Universität Munchen - Université Technique de Munich [Munich, Allemagne] (TUM), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, and Technical University of Munich (TUM)
Subjects: Mathematical optimization, Information Systems and Management, General Computer Science, Discretization, Computer science, Heuristic (computer science), 0211 other engineering and technologies, 02 engineering and technology, Management Science and Operations Research, Industrial and Manufacturing Engineering, 0502 economics and business, Constraint programming, Column generation, Clique, 050210 logistics & transportation, 021103 operations research, Binary Independence Model, Job shop scheduling, Scheduling, 05 social sciences, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Modeling and Simulation, Airport operations, Runway
Abstract: International audience; We address the runway scheduling problem under consideration of winter operations. During snowfall, runways have to be temporarily closed in order to clear them from snow, ice and slush. We propose an integrated optimization model to simultaneously plan snow removal for multiple runways and to assign runways and takeoff and landing times to aircraft. For this winter runway scheduling problem, we present a time-discrete binary model formulation using clique inequalities and an equivalent constraint programming model. To solve the winter runway scheduling problem optimally, we propose an exact solution methodology. Our start heuristic based on constraint programming generates a feasible initial start solution. We use a column generation scheme, which we initialize with a heuristic solution, to identify all variables of the binary program which are required to solve it optimally. Finally, we apply a branch-and-bound procedure to our resulting binary program. Additionally, we present an enhanced time discretization method to balance model size and solution quality. We apply our algorithm to realistic instances from a large international airport. An analysis of resulting model sizes proves the ability of our approach to significantly reduce the number of required variables and constraints of the time-discrete binary program. We also show that our method computes optimal schedules in a short amount of time and often outperforms a time-continuous formulation as well as a pure constraint programming approach.
Published: 2022
Full Text: View/download PDF

33. A project scheduling problem with periodically aggregated resource-constraints

Author: Morin, Pierre-Antoine, Artigues, Christian, Haït, Alain, Kis, Tamás, Spieksma, Frits C.R., Combinatorial Optimization 1, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut Supérieur de l'Aéronautique et de l'Espace (ISAE-SUPAERO), Institute for Computer Science and Control [Budapest] (SZTAKI), Hungarian Academy of Sciences (MTA), Eindhoven University of Technology [Eindhoven] (TU/e), ANR-18-CE10-0007,PER4MANCE,Planification Et Répartition Flexible du travail entre les OpérateuRs des chaînes d'asseMblage AéroNautiques : une approChe systémique pour gérer les risques Ergonomiques et économiques(2018), and ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019)
Subjects: Computational complexity, General Computer Science, Mixed-integer linear programming, Modeling and Simulation, Project scheduling, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Management Science and Operations Research, Periodic aggregation of resource-constraints
Abstract: International audience; We consider the so-called periodically aggregated resource-constrained project scheduling problem. This problem, introduced by Morin et al. 2017, is a variant of the well-known resource-constrained project scheduling problem that allows for a more flexible usage of the resource constraints. While the start and completion times of the activities can be arbitrary moments in time, the limitations on the resource usage are considered on average over aggregated periods of parameterized length. This paper presents new theoretical and experimental results for this problem. First, we settle the complexity status of the problem by proving NP-hardness of a number of special cases of the problem. Second, we propose a new mixed-integer programming formulation of the problem by disaggregating the precedence constraints over the periods. A theoretical comparison shows that the new formulation dominates the previously proposed one in terms of relaxation strength. Finally, we carry out computational experiments on instances from the literature to compare the merits of the different formulations.
Published: 2022
Full Text: View/download PDF

34. Modélisation et résolution de problèmes d'ordonnancement au sein du solveur d'optimisation mathématique LocalSolver

Author: Blaise, Léa, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, INSA Toulouse, and Christian Artigues(artigues@laas.fr)
Subjects: solveur, propagation de contraintes, local search, [INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering, ordonnancement disjonctif, packing, constraint propagation, disjunctive scheduling, recherche locale, solver
Abstract: National audience; Solving a scheduling problem consists in organizing the realization of tasks in the course of time: determining their distribution on the various available resources as well as their execution dates. Scheduling problems are encountered in all domains of industry and services, and are often studied in the literature. This thesis focuses on disjunctive scheduling and/or packing problems, with or without flexibility on the resources. All the algorithmic contributions of this thesis have been implemented within the mathematical optimization solver LocalSolver, whose resolution techniques combine exact methods, such as linear, nonlinear and constraint programming, and heuristics, such as local search and constructive algorithms.This thesis addresses two main issues related to the treatment of this type of scheduling problems by LocalSolver. The first objective is to easily allow users to model many disjunctive scheduling problems. By taking advantage of LocalSolver's set-based modeling formalism, we propose generic formulations, adaptable to different disjunctive scheduling problem families, in order to simply express the concepts of tasks, precedence relations, or non-overlap constraints on the tasks assigned to the same disjunctive resource. These generic formulations are based on the combined use of two types of decision variables offered by LocalSolver: integer variables, representing the start dates and durations of tasks, and list variables, representing their order on the various disjunctive resources.The second objective of the thesis is to improve the performance of LocalSolver on the considered scheduling problems, by integrating different resolution algorithms, as generic as possible, to the local search component of the solver. The genericity of the contributions is crucial: indeed, we do not aim at improving the performance of the solver on a single problem, nor even only on scheduling problems, but on all problems presenting certain characteristic structures often encountered in disjunctive scheduling or in packing.The algorithmic contributions of this thesis can be grouped into three main categories: initialization algorithms, local search moves, and a constraint propagation algorithm. We present two constructive initialization algorithms for set and list variables, which help the solver to immediately find a feasible solution to problems such as the Aircraft Landing or Assembly Line Balancing Problems, and thus accelerate the search for good quality solutions. We also present several local search moves, based on the detection of specific structures in the model (non-overlap constraints, precedence relations, packing constraints). We also present a solution repair algorithm by constraint propagation, integrated into the solver's local search component, and called after each local move leading to an infeasible solution. Our algorithm differs from classical constraint propagation in several ways. For example, it only propagates domain reductions that exclude the current values of the va! riables, and can make arbitrary decisions when it encounters a constraint that can be repaired in different ways. We prove that in some cases the algorithm has properties that ensure that the propagation will succeed if the solution can be repaired. This algorithm overcomes the difficulties encountered by local search on tightly constrained scheduling problems (moving from a good solution to another requires making changes on a large number of variables). The integration of these local moves and this repair algorithm into LocalSolver's local search component brings significant performance gains on various problems (Job Shop and variants, Unit Commitment, Assembly Line Balancing, or Bin Packing).; Résoudre un problème d'ordonnancement consiste à organiser la réalisation de tâches au cours du temps : déterminer leur répartition sur les différentes ressources disponibles ainsi que leurs dates d'exécution. Les problèmes d'ordonnancement se rencontrent dans tous les domaines de l'industrie et des services, et sont très étudiés dans la littérature. Le travail de cette thèse se concentre sur les problèmes d’ordonnancement de type disjonctif et/ou packing, avec ou sans flexibilité des ressources. L'ensemble des contributions algorithmiques de la thèse ont été implémentées au sein du solveur d'optimisation mathématique LocalSolver, dont les techniques de résolution combinent des méthodes exactes, telles que la programmation linéaire, non linéaire et par contraintes, et heuristiques, comme la recherche locale et des algorithmes constructifs.Le travail de cette thèse répond à deux problématiques principales, liées au traitement de ce type de problèmes d'ordonnancement par LocalSolver. Le premier objectif se dégageant de ces problématiques consiste à permettre aux utilisateurs du solveur de modéliser simplement un grand nombre de problèmes d'ordonnancement disjonctif. En tirant profit de la richesse du formalisme de modélisation ensembliste de LocalSolver, on propose des formulations génériques, adaptables à différentes familles de problèmes d'ordonnancement disjonctif, permettant d'exprimer simplement les notions de tâches, de relations de précédence, ou encore de contraintes de non-chevauchement des tâches affectées à une même ressource disjonctive. Les formulations génériques ainsi choisies reposent sur l'utilisation combinée de deux types de variables de décision offertes par LocalSolver : les variables entières, permettant de modéliser les dates de début et durées de tâches, ! et les variables de listes, représentant leur ordre sur les différentes ressources disjonctives.Le second objectif de la thèse consiste à améliorer les performances de LocalSolver sur les problèmes d'ordonnancement étudiés, en intégrant différents algorithmes de résolution les plus génériques possibles à la composante de recherche locale du solveur. Cette généricité des contributions est cruciale : en effet, on ne cherche pas à améliorer les performances du solveur sur un unique problème, ni même seulement sur les problèmes d'ordonnancement, mais sur tous les problèmes présentant des structures caractéristiques de l'ordonnancement disjonctif ou du packing.Les contributions algorithmiques de cette thèse peuvent être regroupées en trois grandes catégories : des algorithmes d'initialisation, des mouvements de recherche locale, et un algorithme de propagation de contraintes. On présente deux algorithmes constructifs d'initialisation des variables ensemblistes (sets et listes), aidant le solveur à trouver une solution réalisable immédiatement sur des problèmes comme ceux de l'Aircraft Landing ou de l'Assembly Line Balancing, et accélérant ainsi la recherche de solutions de bonne qualité sur ces problèmes. On présente également des mouvements de recherche locale, reposant sur la détection de structures spécifiques dans le modèle (contraintes de non-chevauchement des tâches, relations de précédence, contraintes de packing). On présente également un algorithme de réparation de solutions par propagation de contraintes, appelé au cours de la recherche locale après chaque mouvement conduisant à une solution in! faisable. Notre algorithme diffère de la propagation classique de la programmation par contraintes par plusieurs points. Par exemple, il ne propage que les réductions de domaine excluant la valeur courante des variables, et peut prendre des décisions arbitraires lorsqu'il rencontre une contrainte pouvant être réparée de différentes manières. On démontre que dans certains cas l’algorithme présente des propriétés lui assurant de trouver une réparation s'il en existe une. Cet algorithme permet de pallier les difficultés rencontrées par la recherche locale sur les problèmes d'ordonnancement aux contraintes très serrées (passer d'une bonne solution à une autre nécessite de réaliser des changements sur un grand nombre de variables). L'intégration de ces mouvements et de cet algorithme de réparation au sein de la recherche locale de LocalSolver apporte des gains de performance importants sur divers problèmes (Job Shop et variantes, Unit Commitment, Assemb! ly Line Balancing, ou encore Bin Packing).
Published: 2022

35. Logic-based Benders Decomposition for preemptive Flexible Job-Shop Scheduling

Author: Juvin, Carla, Houssin, Laurent, Lopez, Pierre, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut Supérieur de l'Aéronautique et de l'Espace (ISAE-SUPAERO), ANR-18-CE10-0007,PER4MANCE,Planification Et Répartition Flexible du travail entre les OpérateuRs des chaînes d'asseMblage AéroNautiques : une approChe systémique pour gérer les risques Ergonomiques et économiques(2018), and Lopez, Pierre
Subjects: [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], Benders decomposition, Preemption, Flexible job-shop scheduling, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract: International audience; In this paper, we address the preemptive flexible job-shop scheduling problem (pFJSSP). We propose three exact methods to solve the pFJSSP with makespan minimization objective: a Mixed Integer Linear Programming (MILP) formulation, a Constraint Programming (CP) formulation, and a Logic-Based Benders Decomposition (LBBD) algorithm.
Published: 2022

36. Exact methods for mono-objective and Bi-Objective Multi-Vehicle Covering Tour Problems

Author: Sandra Ulrich Ngueveu, Roberto Roberti, Nicolas Jozefowiez, Estèle Glize, Operations Analytics, Amsterdam Business Research Institute, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Vrije Universiteit Amsterdam [Amsterdam] (VU), Laboratoire de Conception, Optimisation et Modélisation des Systèmes (LCOMS), and Université de Lorraine (UL)
Subjects: Bi-objective optimization, Column generation, Combinatorial optimization, Multi-vehicle Covering Tour Problem, Vehicle routing problems, Mathematical optimization, Information Systems and Management, General Computer Science, Computer science, 0211 other engineering and technologies, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Management Science and Operations Research, Upper and lower bounds, Industrial and Manufacturing Engineering, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], 0502 economics and business, Bi objective, 050210 logistics & transportation, 021103 operations research, 05 social sciences, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Modeling and Simulation
Abstract: International audience; The Multi-vehicle Covering Tour Problem and the Bi-Objective Multi-vehicle Covering Tour Problem have been studied for more than thirty years. Both problems have several practical applications in industry. In this paper, we propose an effective exact method for the Multi-vehicle Covering Tour Problem based on column generation techniques. The effectiveness of the exact method is owed to tailored dominance rules and completion bounds. To validate our approach, we conducted extensive computational experiments on instances from literature. The comparison with state-of-the-art methods shows the effectiveness of the proposed method. In particular, seven open instances are closed to optimality for the first time, and the best lower bounds of the six open instances are improved. The exact method for the Multi-vehicle Covering Tour Problem is also embedded in a-constraint exact method to solve its bi-objective counterpart. Computational results show that the lower bound set provided by this bi-objective exact method is stronger than those provided by the state-of-the-art method from the literature.
Published: 2020
Full Text: View/download PDF

37. Stepping Stone to Smarter Supervision Systems: A Human-centered Multidisciplinary Framework

Author: Mailliez, Mélody, Chevroton, Hugo, Briand, Cyril, Truillet, Philippe, Lemercier, Céline, Laboratoire de Psychologie Sociale : contextes et régulation (LPS (URP_4471)), Université Paris Cité (UPCité), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Etude de L’Interaction Personne SystèmE (IRIT-ELIPSE), Institut de recherche en informatique de Toulouse (IRIT), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Cognition, Langues, Langage, Ergonomie (CLLE-LTC), École Pratique des Hautes Études (EPHE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université Toulouse - Jean Jaurès (UT2J), and Université de Toulouse (UT)-Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)
Subjects: [SCCO.PSYC]Cognitive science/Psychology, [INFO]Computer Science [cs]
Published: 2022

38. Two-stage stochastic/robust scheduling using permutable operation groups

Author: Rivière, Louis, Artigues, Christian, Fargier, Hélène, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Argumentation, Décision, Raisonnement, Incertitude et Apprentissage (IRIT-ADRIA), Institut de recherche en informatique de Toulouse (IRIT), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Institut National des Sciences Appliquées : INSA Lyon, Université de Lyon, ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), Sciencesconf.org, CCSD, and Artificial and Natural Intelligence Toulouse Institute - - ANITI2019 - ANR-19-P3IA-0004 - P3IA - VALID
Subjects: [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Stochastic optimisation, Permutable operation groups, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract: International audience; This paper considers a single machine scheduling problem with release dates, due dates,precedence constraints and aiming for the minimization of the maximum lateness or the sumof completion times over a sampled set of release dates scenarios, either in a stochastic orrobust setting. The standard 2-stage approach for stochastic and robust scheduling on a singlemachine considers first-stage decisions that output a full ordering (sequence) of the jobs (J-SEQ) on the machine and second-stage decisions that set the job start times in accordancewith the information of a given scenario.. In this paper, we study the performances of analternative 2-stage solution method based on groups of permutable jobs. The method, initiallypresented in [1], considers first-stage decisions that output only a partial ordering in the formof a sequence of groups of permutable jobs (G-SEQ). Given a scenario, the second stage policyorders the jobs inside each group according to the earliest realized release date first heuristic.We introduce a constraint programming approach to compute an optimal G-SEQ solutionbut show that in a limited time, it provides poor quality solutions on the largest instancescompared to a standard J-SEQ solution approach. We then design several heuristics that usea portion of the time limit to obtain good quality J-SEQ starting solutions and then switch toG-SEQ solutions via greedy or local search. The best G-SEQ heuristics outperform all of thestandard J-SEQ approaches under the same time limit.
Published: 2022

39. Ordonnancement des contacts Search And Rescue dans une constellation de satellites de géopositionnement

Author: Artigues, Christian, Gallois, Léonie, Houssin, Laurent, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut Supérieur de l'Aéronautique et de l'Espace (ISAE-SUPAERO), INSA Lyon, ANR-18-CE10-0007,PER4MANCE,Planification Et Répartition Flexible du travail entre les OpérateuRs des chaînes d'asseMblage AéroNautiques : une approChe systémique pour gérer les risques Ergonomiques et économiques(2018), and ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019)
Subjects: [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], programmation en nombres entiers, constellation de satellites, ordonnancement
Abstract: International audience; Ordonnancement des contacts Search And Rescue dans une constellation de satellites de géopositionnement
Published: 2022

40. Concilier l'équité statistique et la précision en apprentissage machine interprétable grâce à la PLNE

Author: Ferry, Julien, Aïvodji, Ulrich, Gambs, Sebastien, Huguet, Marie-José, Siala, Mohamed, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Ecole de Technologie Supérieure [Montréal] (ETS), Université du Québec à Montréal = University of Québec in Montréal (UQAM), INSA Lyon, and Sciencesconf.org, CCSD
Subjects: [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], optimisation, équité, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], apprentissage, interprétabilité, recherche opérationnelle
Abstract: International audience; L'interprétabilité et l'équité sont deux propriétés de plus en plus recherchées en apprentissage machine. Toutefois, l'apprentissage de modèles interprétables optimaux et respectant des contraintes d'équité statistique a été identifié comme l'un des grands défis techniques à l'interprétabilité. En effet, les contraintes d'équité modifient l'espace des solutions admissibles, rendant plus difficile son exploration.FairCORELS est un algorithme d'apprentissage supervisé permettant l'apprentissage de modèles de type listes de règles certifiés optimaux et respectant des contraintes d'équité. FairCORELS est basé sur CORELS, un algorithme de branch-and-bound permettant l'apprentissage de listes de règles optimales. En raison des contraintes d'équité imposées dans FairCORELS, certaines structures de données utilisées dans CORELS ne peuvent plus être utilisées, et l'exploration de l'espace de recherche est alors plus difficile.Nous proposons une approche basée sur la PLNE tirant profit des contraintes d'équité, et de leur interaction avec la précision, pour élaguer l'espace de recherche efficacement et guider son exploration. Les expérimentations menées montrent que l'approche proposée accélère la convergence et permet l'apprentissage de modèles équitables optimaux.
Published: 2022

41. A CP model for interactive project scheduling in space industry

Author: Hugo Chevroton, Cyrille Briand, Philippe Truillet, Melody Mailliez, Céline Lemercier, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Etude de L’Interaction Personne SystèmE (IRIT-ELIPSE), Institut de recherche en informatique de Toulouse (IRIT), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université Toulouse III - Paul Sabatier (UT3), Laboratoire de Psychologie Sociale : contextes et régulation (LPS (URP_4471)), Université Paris Cité (UPCité), Cognition, Langues, Langage, Ergonomie (CLLE), École Pratique des Hautes Études (EPHE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Toulouse Mind & Brain Institut (TMBI), INSA Lyon, Université de Lyon, and Sciencesconf.org, CCSD
Subjects: [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], constraint programming, [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], decision aid, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], scheduling, human machine interaction, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract: International audience; As modern production environments tend to be increasingly complex and stressful for production process supervisors, providing interactive decision support tools (DSTs) is seen as a relevant way to help humans better organize and monitor operations, in the face of production uncertainties. Consideration of the actual needs and capabilities of supervisors in the DST development process thus seems to be a prerequisite for the development of usable, accepted and effective tools. The results presented in this paper synthesize the findings of an ongoing multidisciplinary project taking interest in human-centered design of DSTs related to production supervision. This work was conducted in partnership with a major French company specialized in space technologies, which provided our case study.
Published: 2022

42. Décomposition de Benders basée sur la logique pour le problème de job-shop flexible préemptif

Author: Juvin, Carla, Houssin, Laurent, Lopez, Pierre, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut Supérieur de l'Aéronautique et de l'Espace (ISAE-SUPAERO), INSA Lyon, and Sciencesconf.org, CCSD
Subjects: [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], préemption, méthodes exactes, [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], Job shop flexible, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], décomposition de Benders, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract: International audience; On s'intéresse au problème d'ordonnancement de production du type job-shop flexible préemptif. Trois approches sont proposées pour le résoudre : la programmation linéaire en nombres entiers, la programmation par contraintes et la décomposition de Benders basée sur la logique.
Published: 2022

43. Une variante de la méthode de Benders adverse pour le problème de lot-sizing robuste avec budget d'incertitude

Author: Portoleau, Tom, Guillaume, Romain, Artigues, Christian, Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT), Université Toulouse - Jean Jaurès (UT2J), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), INSA Lyon, and Sciencesconf.org, CCSD
Subjects: [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], Benders adverse, Budget d'incertitude, Production sous incertitude, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract: International audience; Dans ce papier nous présentons une variante de la méthode de Benders adverse pour résoudre un problème d’optimisation robuste pour le lot-sizing avec budget d’incertitude sur la demande cumulée. Nous rappelons d’abord l’approche classique avant de détailler cette variante qui se base sur une représentation compacte de scénarios dans un type de graphe particulier. Nous concluons avec des résultats expérimentaux comparant les deux approches, qui indiquent que notre variante peut être plus intéressante que l’approche classique lorsque le budget d’incertitude est bas.
Published: 2022

44. Heuristiques de linéarisation par morceaux de fonctions à deux variables avec minimisation du nombre de morceaux sous contrainte de tolérance

Author: Duguet, Aloïs, Ngueveu, Sandra Ulrich, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), INSA Lyon, and Sciencesconf.org, CCSD
Subjects: [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], MINLP, linéaire par morceaux, garantie d'approximation, [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], Linéarisation, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], heuristique
Abstract: International audience; Heuristiques de linéarisation par morceaux de fonctions à deux variables avec minimisation du nombre de morceaux sous contrainte de tolérance
Published: 2022

45. Comparaison de différents modèles pour résoudre le problème non-linéaire Hydro Unit Commitment

Author: Heintzmann, Alexandre, Artigues, Christian, Bendotti, Pascale, Ngueveu, Sandra Ulrich, Rottner, Cécile, EDF Labs, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), INSA Lyon, ANR-18-CE10-0007,PER4MANCE,Planification Et Répartition Flexible du travail entre les OpérateuRs des chaînes d'asseMblage AéroNautiques : une approChe systémique pour gérer les risques Ergonomiques et économiques(2018), and Sciencesconf.org, CCSD
Subjects: [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], MINLP, programmation non linéaire, Hydro Unit Commitment, [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract: International audience; Les systèmes physiques réels possèdent dans certains cas des non-linéarités dont il faut tenir compte lors de la résolution de problèmes d'optimisations associés. Il existe un grand nombre de possibilité pour modéliser ces problèmes, ayant une précision, et demandant des temps de calculs différents.Le Hydro Unit Commitment fait parti des problèmes non-linéaires, faisant intervenir deux non-linéarités. Plusieurs modèles sont présentés pour modéliser le HUC, et sont comparés sur un jeu d'instance varié.Le but est d'identifier les modèles pertinants, en terme de temps de calcul, précision et faisabilité, et les charactéristiques des instances qui ont un impact sur la résolution des différents modèles proposés.
Published: 2022

46. Optimizing Binary Decision Diagrams with MaxSAT for Classification

Author: Hao Hu, Marie-José Huguet, Mohamed Siala, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), and Huguet, Marie-Jose
Subjects: [INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], FOS: Computer and information sciences, Computer Science - Machine Learning, Artificial Intelligence (cs.AI), Computer Science - Artificial Intelligence, General Medicine, Machine Learning (cs.LG), [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract: The growing interest in explainable artificial intelligence (XAI) for critical decision making motivates the need for interpretable machine learning (ML) models. In fact, due to their structure (especially with small sizes), these models are inherently understandable by humans. Recently, several exact methods for computing such models are proposed to overcome weaknesses of traditional heuristic methods by providing more compact models or better prediction quality. Despite their compressed representation of Boolean functions, Binary decision diagrams (BDDs) did not gain enough interest as other interpretable ML models. In this paper, we first propose SAT-based models for learning optimal BDDs (in terms of the number of features) that classify all input examples. Then, we lift the encoding to a MaxSAT model to learn optimal BDDs in limited depths, that maximize the number of examples correctly classified. Finally, we tackle the fragmentation problem by introducing a method to merge compatible subtrees for the BDDs found via the MaxSAT model. Our empirical study shows clear benefits of the proposed approach in terms of prediction quality and intrepretability (i.e., lighter size) compared to the state-of-the-art approaches., Comment: This is the preprint version of the paper accepted in AAAI'22
Published: 2022

47. Efficient and Validated Numerical Evaluation of Abelian Integrals

Author: Bréhard, Florent, Brisebarre, Nicolas, Joldeş, Mioara, Tucker, Warwick, Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Arithmetic and Computing (ARIC), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), School of Mathematics [Australia], Monash University [Melbourne], ANR-20-CE48-0014,NuSCAP,Sûreté numérique pour les preuves assistées par ordinateur(2020), Brisebarre, Nicolas, and Sûreté numérique pour les preuves assistées par ordinateur - - NuSCAP2020 - ANR-20-CE48-0014 - AAPG2020 - VALID
Subjects: [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], limit cycles, [INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC], [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, Abelian integral, [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], Newton-like operator, [MATH.MATH-DS] Mathematics [math]/Dynamical Systems [math.DS], rigorous numerics, Hilbert's 16th problem, [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], 2020 AMS classification: Primary: 34C07, Secondary: 37G15, 37M20, 42A10, 42A15, 65G20, [INFO.INFO-NA] Computer Science [cs]/Numerical Analysis [cs.NA], ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, [INFO.INFO-AO] Computer Science [cs]/Computer Arithmetic, trigonometric polynomial interpolation
Abstract: Abelian integrals play a key role in the infinitesimal version of Hilbert's 16th problem. Being able to evaluate such integrals - with guaranteed error bounds - is a fundamental step in computer-aided proofs aimed at this problem. Using interpolation by trigonometric polynomials and quasi-Newton-Kantorovitch validation, we develop a validated numerics method for computing Abelian integrals in a quasi-linear number of arithmetic operations. Our approach is both effective, as exemplified on two practical perturbed integrable systems, and amenable to an implementation in a formal proof assistant, which is key to provide fully reliable computer-aided proofs.
Published: 2022

48. Stochastic Differential Equations for modeling first order optimization methods

Author: Dambrine, Marc, Dossal, Ch, Puig, Bénédicte, Rondepierre, Aude, Rondepierre, Aude, Laboratoire de Mathématiques et de leurs Applications [Pau] (LMAP), Université de Pau et des Pays de l'Adour (UPPA)-Centre National de la Recherche Scientifique (CNRS), Institut de Mathématiques de Toulouse UMR5219 (IMT), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), and Université de Toulouse (UT)
Subjects: SDEs, geometry, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], optimization, Lyapunov functions, rate of convergence
Abstract: In this article, a family of SDEs are derived as a tool to understand the behavior of numerical optimization methods under random evaluations of the gradient. Our objective is to transpose the introduction of continuous version through ODEs to understand the asymptotic behavior of discrete optimization scheme to the stochastic setting. We consider a continuous version of the stochastic gradient scheme and of a stochastic inertial system. This article first studies the quality of the approximation of the discrete scheme by a SDE when the step size tends to 0. Then, it presents new asymptotic bounds on the values F (X(t)) − F * where X(t) is a solution of the SDE and F * = min F , when F is convex and under integrability conditions on the noise. Results are provided under two sets of hypotheses : first considering C 2 and convex functions and then adding some geometrical properties of F. All these results give an insight on the behavior of these inertial and perturbed algorithms in the setting of stochastic algorithms.
Published: 2022

49. Approximation à précision numérique prédéfinie d'une classe de problèmes d'optimisation non-linéaires non-convexes séparables

Author: Contardo, Claudio, Ngueveu, Sandra Ulrich, Sciencesconf.org, CCSD, Université du Québec à Montréal = University of Québec in Montréal (UQAM), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), and INSA Lyon
Subjects: MINLP, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], piecewise linear approximation, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract: International audience; Approximation à précision numérique prédéfinie d'une classe de problèmes d'optimisation non-linéaires non-convexes séparables
Published: 2022

50. Logic-Based Benders Decomposition for the Preemptive Flexible Job-Shop Scheduling Problem

Author: Carla Juvin, Laurent Houssin, Pierre Lopez, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), and Institut Supérieur de l'Aéronautique et de l'Espace (ISAE-SUPAERO)
Subjects: constraint programming, preemption, History, mixed-integer programming, General Computer Science, Polymers and Plastics, Benders decomposition, Modeling and Simulation, Flexible job-shop scheduling, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Management Science and Operations Research, Business and International Management, Industrial and Manufacturing Engineering
Abstract: In this paper, we focus on exact methods to solve the preemptive Flexible Job-Shop Scheduling Problem with makespan and total completion time minimisation objective functions. Mathematical and constraint programming models enable the resolution of this problem for small instances. However, as an NP-hard problem, the cost of solving grows rapidly when considering larger instances. In this regard, we propose a logic-based Benders decomposition that relies on an efficient branch-and-bound procedure to solve the subproblem representing a pure (non-flexible) preemptive job-shop scheduling problem. Computational experiments are carried out and show the very good performance of our proposals.
Published: 2022
Full Text: View/download PDF

Catalog

Books, media, physical & digital resources

See catalog results

Searchworks

Select search scope, currently: Articles Catalog books, media & more in Jio Institute collections Articles journal articles & other e-resources

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Journal

Database

Publisher

369 results on '"Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC)"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources