Search

Showing total 11 results
Start Over Search Limiters Available in Library Collection Topic combinatorial search Publisher hal ccsd
11 results

1. On the numerical integration of rate independent single crystal behavior at large strain

Author

Clément Keller, Abdelwaheb Dogui, Olivier Débordes, Laurent Duchene, Mohamed Ben Bettaieb, ArGEnCo Department, MS2F Division (ArGEnCo), Université de Liège, Matériaux et Structures (M&S), Laboratoire de Mécanique et d'Acoustique [Marseille] (LMA ), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Génie Mécanique [Monastir] (LGM / ENIM), École Nationale d’Ingénieurs de Monastir (ENIM), ERMECA (ERMECA), Groupe de physique des matériaux (GPM), Centre National de la Recherche Scientifique (CNRS)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Normandie Université (NU), Université de Monastir - University of Monastir (UM)-Université de Monastir - University of Monastir (UM), Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche sur les Matériaux Avancés (IRMA), Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Normandie Université (NU)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Centre National de la Recherche Scientifique (CNRS)-Université de Rouen Normandie (UNIROUEN), and Normandie Université (NU)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Non-linear hardening, Constitutive equation, Perturbation (astronomy), 02 engineering and technology, Slip (materials science), [SPI.MECA.SOLID]Engineering Sciences [physics]/Mechanics [physics.med-ph]/Solid mechanics [physics.class-ph], 01 natural sciences, Homogenization (chemistry), 0203 mechanical engineering, Fixed-point iteration, FCC single crystal, Schmid's law, [PHYS.MECA.SOLID]Physics [physics]/Mechanics [physics]/Solid mechanics [physics.class-ph], Applied mathematics, Combinatorial search, General Materials Science, 0101 mathematics, Mathematics, business.industry, Mechanical Engineering, Structural engineering, Numerical integration, 010101 applied mathematics, 020303 mechanical engineering & transports, Mechanics of Materials, Finite strain theory, Finite strain, business
Abstract

International audience; This paper presents a new numerical algorithm for the integration of the constitutive equations of a single crystal for finite rate-independent elastoplastic strains. The algorithm addressed in this paper is dedicated to face-centered-cubic (FCC) crystal structures. Its first feature is a much more efficient and more accurate integration scheme of the constitutive equations compared to previous attempts. This scheme is based on a fully implicit integration procedure, yet it may be transformed easily into an explicit scheme. Determining the set of active slip systems is performed by the use of a combinatorial search procedure, and the determination of the slip rates of the different active slip systems is based on the fixed point method. The second feature of this algorithm stems from the original method used to solve the ambiguity of the possible non-uniqueness of the set of active slip systems. A robust method, based on a small positive perturbation of the critical shear stresses, is proposed to overcome this difficulty. It is worth mentioning that the algorithm developed in this paper is not limited to one particular hardening law or to FCC crystal structures. Rather, it can be used and extended to various hardening laws and crystal structures (e.g. BCC or HCP...) in a straightforward manner. The authors demonstrate the performance of the proposed algorithm and illustrate its accuracy and efficiency through various numerical simulations at the single crystal and polycrystal scales. The predicted results obtained from those simulations were compared with those obtained using other numerical techniques and algorithms (i.e., a pseudo-inversion technique and an explicit algorithm). Our numerical predictions are also compared with some numerical and experimental results from other papers. The response of the polycrystal was computed by using the proposed algorithm combined with Taylor's homogenization scheme, which is used to compute the overall polycrystalline behavior. The paper ends with a statistical study of the influence of the perturbation technique on the response prediction for a single crystal and a polycrystal.

Published
2012

2. A pipeline to create predictive functional networks: application to the tumor progression of hepatocellular carcinoma

Author

Arnaud Poret, Nathalie Théret, Lokmane Chebouba, Maxime Folschette, Vincent Legagneux, Carito Guziolowski, Institut de recherche en santé, environnement et travail (Irset), Université d'Angers (UA)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-École des Hautes Études en Santé Publique [EHESP] (EHESP)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Structure Fédérative de Recherche en Biologie et Santé de Rennes ( Biosit : Biologie - Santé - Innovation Technologique ), Dynamics, Logics and Inference for biological Systems and Sequences (Dyliss), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-GESTION DES DONNÉES ET DE LA CONNAISSANCE (IRISA-D7), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Laboratoire des Sciences du Numérique de Nantes (LS2N), Université de Nantes - Faculté des Sciences et des Techniques, Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), BioComputing, Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189 (CRIStAL), Ecole Centrale de Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Ecole Centrale de Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Combinatoire et Bioinformatique (COMBI), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Nantes - Faculté des Sciences et des Techniques, Institut Français de Bioinformatique - UMS CNRS 3601 (IFB-CORE), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Centre National de la Recherche Scientifique (CNRS), École Centrale de Nantes (ECN), Laboratoire de Recherche en Intelligence Artificielle [Alger] (LRIA), Université des Sciences et de la Technologie Houari Boumediene [Alger] (USTHB), Université Bretagne Loire, Université d'Angers (UA)-Université de Rennes (UR)-École des Hautes Études en Santé Publique [EHESP] (EHESP)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Structure Fédérative de Recherche en Biologie et Santé de Rennes ( Biosit : Biologie - Santé - Innovation Technologique ), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), 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)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Combinatoire et Bioinformatique (LS2N - équipe COMBI), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Institut Français de Bioinformatique (IFB-CORE), Institut National de Recherche en Informatique et en Automatique (Inria)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Université des Sciences et de la Technologie Houari Boumediene = University of Sciences and Technology Houari Boumediene [Alger] (USTHB), Folschette, Maxime, Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National de la Recherche Agronomique (INRA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique)-Université de Nantes - Faculté des Sciences et des Techniques, Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), and Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Computer science, Hepatocellular carcinoma, computer.software_genre, Workflow, 0302 clinical medicine, Databases, Genetic, Gene expression, Gene Regulatory Networks, lcsh:QH301-705.5, ComputingMilieux_MISCELLANEOUS, [INFO.INFO-BI] Computer Science [cs]/Bioinformatics [q-bio.QM], chemistry.chemical_classification, 0303 health sciences, Biological data, Liver Neoplasms, [SDV.BBM.MN]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Molecular Networks [q-bio.MN], Signaling and regulatory knowledge, 030220 oncology & carcinogenesis, KEGG, Disease Progression, Graph (abstract data type), lcsh:R858-859.7, Data mining, [INFO.INFO-MO] Computer Science [cs]/Modeling and Simulation, Research Article, Carcinoma, Hepatocellular, Stability (learning theory), Complex system, Context (language use), [SDV.CAN]Life Sciences [q-bio]/Cancer, lcsh:Computer applications to medicine. Medical informatics, 03 medical and health sciences, [SDV.CAN] Life Sciences [q-bio]/Cancer, Humans, Combinatorial search, Gene, 030304 developmental biology, Biomolecule, Computational Biology, Pipeline (software), [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, chemistry, [SDV.BBM.MN] Life Sciences [q-bio]/Biochemistry, Molecular Biology/Molecular Networks [q-bio.MN], lcsh:Biology (General), Data and network integration, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Transcriptome, computer, Discrete modeling
Abstract

BackgroundIntegrating genome-wide gene expression patient profiles with regulatory knowledge is a challenging task because of the inherent heterogeneity, noise and incompleteness of biological data. From the computational side, several solvers for logic programs are able to perform extremely well in decision problems for combinatorial search domains. The challenge then is how to process the biological knowledge in order to feed these solvers to gain insights in a biological study. It requires formalizing the biological knowledge to give a precise interpretation of this information; currently, very few pathway databases offer this possibility.ResultsThe presented work proposes an automatic pipeline to extract automatically regulatory knowledge from pathway databases and generate novel computational predictions related to the state of expression or activity of biological molecules. We applied it in the context of hepatocellular carcinoma (HCC) progression, and evaluate the precision and the stability of these computational predictions. Our working base is a graph of 3,383 nodes and 13,771 edges extracted from the KEGG database, in which we integrate 209 differentially expressed genes between low and high aggressive HCC across 294 patients. Our computational model predicts the shifts of expression of 146 initially non-observed biological components. Our predictions were validated at 88% using a larger experimental dataset and cross-validation techniques. In particular, we focus on the protein complexes predictions and show for the first time that NFKB1/BCL-3 complexes are activated in aggressive HCC. In spite of the large dimension of the reconstructed models, our analyses over the computational predictions discover a well constrained region where KEGG regulatory knowledge constrains gene expression of several biomolecules. These regions can offer interesting windows to perturb experimentally such complex systems.ConclusionThis new pipeline allows biologists to develop their own predictive models based on a list of genes. It facilitates the identification of new regulatory biomolecules using knowledge graphs and predictive computational methods. Our workflow is implemented in an automatic python pipeline which is publicly available at https://github.com/LokmaneChebouba/key-pipe and contains as testing data all the data used in this paper.

Published
2020

3. Minimal NMR distance information for rigidity of protein graphs

Author

Leo Liberti, Benjamin Bardiaux, Michael Nilges, Thérèse E. Malliavin, Bradley Worley, Bruce R. Donald, Carlile Lavor, Instituto de Matemática, Estatística e Computação Científica [Brésil] (IMECC), Universidade Estadual de Campinas (UNICAMP), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Duke University [Durham], Bioinformatique structurale, Institut Pasteur [Paris]-Centre National de la Recherche Scientifique (CNRS), C.L. would like to thank the Brazilian research agencies CNPq, FAPESP and B.D. would like to thank the NIH grants R01 GM-118543 and R01 GM-078031 for their financial support., We are also thankful to Angela Gronenborn and Michael Souza, for discussions that clarify some ideas in the paper, and to anonymous referees that made very important comments to this work., Bioinformatique structurale - Structural Bioinformatics, Universidade Estadual de Campinas = University of Campinas (UNICAMP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), and Institut Pasteur [Paris] (IP)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Computational complexity theory, Nuclear Magnetic Resonance, 0211 other engineering and technologies, Structure (category theory), Rigidity (psychology), 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Topology, 01 natural sciences, Article, Cardinality, Protein structure, Distance Geometry, Discrete Mathematics and Combinatorics, Molecule, Combinatorial search, Mathematics, Quantitative Biology::Biomolecules, [SDV.BBM.BS]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Structural Biology [q-bio.BM], Applied Mathematics, Solution set, 021107 urban & regional planning, [SDV.BBM.BP]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Biophysics, [SDV.BBM.BS]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Biomolecules [q-bio.BM], Vertex orders, 010201 computation theory & mathematics, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Molecular structure
Abstract

International audience; Nuclear Magnetic Resonance (NMR) experiments provide distances between nearby atoms of a protein molecule. The corresponding structure determination problem is to determine the 3D protein structure by exploiting such distances. We present a new order on the atoms of the protein, based on information from the chemistry of proteins and NMR experiments, which allows us to formulate the problem as a combinatorial search. Additionally, this order tells us what kind of NMR distance information is crucial to understand the cardinality of the solution set of the problem and its computational complexity.

Published
2019

4. Optimal Sensor Network Design to Monitor the Energy Performances of a Process Plant

Author

Jean-Paul Gourlia, Cong-Toan Tran, Marie-Ann Evans, Hala Rameh, Assaad Zoughaib, Centre Efficacité Énergétique des Systèmes (CES), MINES ParisTech - École nationale supérieure des mines de Paris, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), and Paris Saclay Efficacité Energétique (PS2E)

Subjects
Observability, Computer science, Sensor network, Distributed computing, media_common.quotation_subject, Control engineering, 02 engineering and technology, 021001 nanoscience & nanotechnology, Concentrator, 7. Clean energy, Reduction (complexity), [SPI]Engineering Sciences [physics], 020401 chemical engineering, Combinatorial search, Parallel computing, [SPI.GPROC]Engineering Sciences [physics]/Chemical and Process Engineering, 0204 chemical engineering, 0210 nano-technology, Function (engineering), Wireless sensor network, Energy (signal processing), Efficient energy use, media_common
Abstract

International audience; Nowadays, there’s an increased interest in industry for the energy audit, whose objective is identifying opportunities to improve energy efficiency. The analysis of the energy performances, for industrial processes, requires the knowledge of the physical quantities involved in the energy and mass balances, and therefore, the establishment of a sensor network. Many studies were conducted to solve this problem. However rare are those which helped reducing the computing time substantially for medium and large size problems. This paper introduces a methodology for finding the optimal sensor network to be installed in a process plant. Using a parallelized combinatorial search associated with a verification function, the proposed sequential methodology identifies a suboptimal set of possible sensor networks to be adopted, in ascending order of number of sensors. This methodology is tested on a starch concentrator (medium size problem), showing an effective reduction of computational time.

Published
2017

5. Localisation of humans, objects and robots interacting on load-sensing floors

Author

François Charpillet, Mihai Andries, Olivier Simonin, Lifelong Autonomy and interaction skills for Robots in a Sensing ENvironment (LARSEN), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Complex Systems, Artificial Intelligence & Robotics (LORIA - AIS), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Robots coopératifs et adaptés à la présence humaine en environnements dynamiques (CHROMA), 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)-CITI Centre of Innovation in Telecommunications and Integration of services (CITI), 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)-Institut National de Recherche en Informatique et en Automatique (Inria)-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), Inria CORDI-S, Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), and Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)

Subjects
Engineering, Ubiquitous computing, Feature extraction, 02 engineering and technology, Tracking (particle physics), 01 natural sciences, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, 0202 electrical engineering, electronic engineering, information engineering, Intelligent systems, Combinatorial search, Computer vision, Sensor arrays, Electrical and Electronic Engineering, Instrumentation, Ambient intelligence, business.industry, Identification of persons, Home automation, 010401 analytical chemistry, Probabilistic logic, Intelligent decision support system, 0104 chemical sciences, Video tracking, Robot, 020201 artificial intelligence & image processing, Artificial intelligence, business, Force sensors
Abstract

International audience; Localisation, tracking and recognition of objects and humans are basic tasks that are of high value in applications of ambient intelligence. Sensing floors were introduced to address these tasks in a non-intrusive way. To recognize the humans moving on the floor, they are usually first localized, and then a set of gait features are extracted (stride length, cadence, pressure profile over a footstep). However, recognition generally fails when several people stand or walk together, preventing successful tracking. This paper presents a detection, tracking and recognition technique which uses objects' weight. It continues working even when tracking individual persons becomes impossible. Inspired by computer vision, this technique processes the floor pressure-image by segmenting the blobs containing objects, tracking them, and recognizing their contents through a mix of inference and combinatorial search. The result lists the probabilities of assignments of known objects to observed blobs. The concept was successfully evaluated in daily life activity scenarii, involving multi-object tracking and recognition on low resolution sensors, crossing of user trajectories, and weight ambiguity. This technique can be used to provide a probabilistic input for multi-modal object tracking and recognition systems.

Published
2016

6. Consistent Neighborhood Search for Combinatorial Optimization

Author

Michel Vasquez, Nicolas Zufferey, Laboratoire de Génie Informatique et Ingénierie de Production (LGI2P), IMT - MINES ALES (IMT - MINES ALES), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Centre Universitaire d'Informatique (CUI), and University of Geneva [Switzerland]

Subjects
Incremental heuristic search, Mathematical optimization, 021103 operations research, Article Subject, ddc:332/658, Computer science, 0211 other engineering and technologies, Best-first search, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Iterative deepening depth-first search, 01 natural sciences, 010201 computation theory & mathematics, Search algorithm, Combinatorial search, Beam search, Guided Local Search, Metaheuristic
Abstract

Many optimization problems (from academia or industry) require the use of a local search to find a satisfying solution in a reasonable amount of time, even if the optimality is not guaranteed. Usually, local search algorithms operate in a search space which contains complete solutions (feasible or not) to the problem. In contrast, in Consistent Neighborhood Search (CNS), after each variable assignment, the conflicting variables are deleted to keep the partial solution feasible, and the search can stop when all the variables have a value. In this paper, we formally propose a new heuristic solution method, CNS, which has a search behavior between exhaustive tree search and local search working with complete solutions. We then discuss, with a unified view, the great success of some existing heuristics, which can however be considered within the CNS framework, in various fields: graph coloring, frequency assignment in telecommunication networks, vehicle fleet management with maintenance constraints, and satellite range scheduling. Moreover, some lessons are given in order to have guidelines for the adaptation of CNS to other problems.

Published
2012

7. The Grand Challenge of Computer Go: Monte Carlo Tree Search and Extensions

Author

Levente Kocsis, Marc Schoenauer, David Silver, Olivier Teytaud, Csaba Szepesvári, Sylvain Gelly, Michèle Sebag, Machine Learning and Optimisation (TAO), Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Paris-Sud - Paris 11 (UP11)-Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec, Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Microsoft Research - Inria Joint Centre (MSR - INRIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Microsoft Research Laboratory Cambridge-Microsoft Corporation [Redmond, Wash.], OASE, National University of Tainan, Taiwan (OASE), National Taiwan University [Taiwan] (NTU), Department of Electrical Engineering and Computer Science (Institut Montefiore), Université de Liège, LPDS, Computer and Automation Research Institute [Budapest] (MTA SZTAKI ), University of Alberta, Department of Computing Science [Edmonton], Grid'5000, Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
Hardware architecture, Theoretical computer science, General Computer Science, Computer science, Monte Carlo tree search, ComputingMilieux_PERSONALCOMPUTING, 02 engineering and technology, Tree (data structure), State space search, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, Combinatorial search, 020201 artificial intelligence & image processing, State (computer science), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Computer Go
Abstract

International audience; The ancient oriental game of Go has long been considered a grand challenge for artificial intelligence. For decades, com- puter Go has defied the classical methods in game tree search that worked so successfully for chess and checkers. How- ever, recent play in computer Go has been transformed by a new paradigm for tree search based on Monte-Carlo meth- ods. Programs based on Monte-Carlo tree search now play at human-master levels and are beginning to challenge top professional players. In this paper we describe the leading algorithms for Monte-Carlo tree search and explain how they have advanced the state of the art in computer Go.

Published
2012

8. NILS: a Neutrality-based Iterated Local Search and its application to Flowshop Scheduling

Author

Arnaud Liefooghe, Laetitia Jourdan, Sébastien Verel, Clarisse Dhaenens, Marie-Eleonore Marmion, Laboratoire d'Informatique Fondamentale de Lille (LIFL), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS), Parallel Cooperative Multi-criteria Optimization (DOLPHIN), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Groupe SCOBI, Modèles Discrets pour les Systèmes Complexes (Laboratoire I3S - MDSC), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Peter Merz and Jin-Kao Hao, Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)

Subjects
FOS: Computer and information sciences, Mathematical optimization, 021103 operations research, Computer science, business.industry, Iterated local search, Computer Science - Artificial Intelligence, 0211 other engineering and technologies, Computer Science - Neural and Evolutionary Computing, 02 engineering and technology, Tabu search, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], Local optimum, Artificial Intelligence (cs.AI), 0202 electrical engineering, electronic engineering, information engineering, Combinatorial search, Beam search, 020201 artificial intelligence & image processing, Local search (optimization), Guided Local Search, Neural and Evolutionary Computing (cs.NE), business, Hill climbing
Abstract

International audience; This paper presents a new methodology that exploits specific characteristics from the fitness landscape. In particular, we are interested in the property of neutrality, that deals with the fact that the same fitness value is assigned to numerous solutions from the search space. Many combinatorial optimization problems share this property, that is generally very inhibiting for local search algorithms. A neutrality-based iterated local search, that allows neutral walks to move on the plateaus, is proposed and experimented on a permutation flowshop scheduling problem with the aim of minimizing the makespan. Our experiments show that the proposed approach is able to find improving solutions compared with a classical iterated local search. Moreover, the tradeoff between the exploitation of neutrality and the exploration of new parts of the search space is deeply analyzed.

Published
2011

9. GPU-based Approaches for Multiobjective Local Search Algorithms. A Case Study: the Flowshop Scheduling Problem

Author

Thé Van Luong, Nouredine Melab, El-Ghazali Talbi, Parallel Cooperative Multi-criteria Optimization (DOLPHIN), Laboratoire d'Informatique Fondamentale de Lille (LIFL), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria), and Peter Merz and Jin-Kao Hao

Subjects
Mathematical optimization, Iterated local search, Computer science, business.industry, [SCCO.COMP]Cognitive science/Computer science, Best-first search, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Tabu search, 010201 computation theory & mathematics, Search algorithm, 0202 electrical engineering, electronic engineering, information engineering, Beam search, Combinatorial search, 020201 artificial intelligence & image processing, Guided Local Search, Local search (optimization), business, Algorithm
Abstract

International audience; Multiobjective local search algorithms are efficient methods to solve complex problems in science and industry. Even if these heuristics allow to significantly reduce the computational time of the solution search space exploration, this latter cost remains exorbitant when very large problem instances are to be solved. As a result, the use of GPU computing has been recently revealed as an efficient way to accelerate the search process. This paper presents a new methodology to design and implement efficiently GPU-based multiobjective local search algorithms. The experimental results show that the approach is promising especially for large problem instances.

Published
2011

10. Large Neighborhood Local Search Optimization on Graphics Processing Units

Author

The Van Luong, Nouredine Melab, El-Ghazali Talbi, Parallel Cooperative Multi-criteria Optimization (DOLPHIN), Laboratoire d'Informatique Fondamentale de Lille (LIFL), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, and Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
021103 operations research, Theoretical computer science, Computer science, business.industry, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], 0211 other engineering and technologies, Graphics processing unit, 02 engineering and technology, CUDA, 0202 electrical engineering, electronic engineering, information engineering, Combinatorial search, Combinatorial optimization, 020201 artificial intelligence & image processing, Local search (optimization), Graphics, Heuristics, business, Metaheuristic
Abstract

International audience; Local search (LS) algorithms are among the most powerful techniques for solving computationally hard problems in combinatorial optimization. These algorithms could be viewed as ``walks through neighborhoods'' where the walks are performed by iterative procedures that allow to move from a solution to another one in the solution space. In these heuristics, designing operators to explore large promising regions of the search space may improve the quality of the obtained solutions at the expense of a highly computationally process. Therefore, the use of graphics processing units (GPUs) provides an efficient complementary way to speed up the search. However, designing applications on GPU is still complex and error-prone. We provide a methodology to design and implement large neighborhood LS algorithms on GPU. Finding efficient mappings of the neighborhood structures onto the GPU threads organization is a challenging issue dealt with in this paper. The work has been experimented for binary problems by deploying multiple neighborhood structures. The obtained results are convincing both in terms of efficiency, quality and robustness of the provided solutions at run time.

Published
2010

11. Enhancing Set Constraint Solvers with Lexicographic Bounds

Author

Carmen Gervet, Andrew Sadler, UMR 228 Espace-Dev, Espace pour le développement, Institut de Recherche pour le Développement (IRD)-Université de Perpignan Via Domitia (UPVD)-Avignon Université (AU)-Université de La Réunion (UR)-Université de Montpellier (UM)-Université de Guyane (UG)-Université des Antilles (UA), and Université de Guyane (UG)-Université des Antilles (UA)-Institut de Recherche pour le Développement (IRD)-Université de Perpignan Via Domitia (UPVD)-Avignon Université (AU)-Université de La Réunion (UR)-Université de Montpellier (UM)

Subjects
Mathematical optimization, Control and Optimization, Computer Networks and Communications, 02 engineering and technology, Management Science and Operations Research, Solver, modelling languages, Constraint Programming, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], Constraint (information theory), Set (abstract data type), Cardinality, Combinatorial design, Artificial Intelligence, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, Constraint programming, Combinatorial search, 020201 artificial intelligence & image processing, Finite set, Software, Information Systems, Mathematics
Abstract

International audience; Since their beginning in constraint programming, set solvers have been applied to a wide range of combinatorial search problems, such as bin-packing, set partitioning, circuit design, and Combinatorial Design Problems. In this paper we present and evaluate a new means towards improving the practical reasoning power of Finite Set (FS) constraint solvers to better address such set problems with a particular attention to the challenging symmetrical set problems often cast as Combinato-rial Design Problems (CDPs). While CDPs find a natural formulation in the language of sets, in constraint programming literature, alternative models are often used due to a lack of efficiency of traditional FS solvers. We first identify the main structural components of CDPs that render their modeling suitable to set languages but their solving a technical challenge. Our new prototype solver extends the traditional subset variable domain with lexicographic bounds that better approximate a set domain by satisfying the cardinality restrictions applied to the variable , and allow for active symmetry breaking using ordering constraints. Our contribution includes the formal and practical framework of the new solver implemented on top of a traditional set solver, and an empirical evaluation on benchmark CDPs.

Published
2008