Search

Showing total 20 results
Start Over Topic 021103 operations research
20 results

1. Property Model Methodology: A Landing Gear Operational Use Case

Author

Thomas Razafimahefa, Pascal Paper, François Guérin, Patrice Micouin, Roland Becquet, Louis Fabre, Micouin, Patrice, Laboratoire des Sciences de l'Information et des Systèmes (LSIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Arts et Métiers Paristech ENSAM Aix-en-Provence-Centre National de la Recherche Scientifique (CNRS), Airbus Helicopters, Aeroport International de Marseille-Provence, MathWorks, and Centre National de la Recherche Scientifique (CNRS)-Arts et Métiers Paristech ENSAM Aix-en-Provence-Université de Toulon (UTLN)-Aix Marseille Université (AMU)

Subjects
[SPI.OTHER]Engineering Sciences [physics]/Other, 021103 operations research, Process (engineering), Computer science, [SPI.OTHER] Engineering Sciences [physics]/Other, media_common.quotation_subject, 0211 other engineering and technologies, Software requirements specification, 02 engineering and technology, 01 natural sciences, Conceptual framework, 0103 physical sciences, Systems engineering, Quality (business), Function (engineering), 010301 acoustics, Implementation, Lead time, Reliability (statistics), media_common
Abstract

International audience; Relevant for engineering a wide range of technological systems, Property Model Methodology (PMM) is applied in this paper to the development process of a helicopter function in the frame of the ARP4754A/ED79A. After a short presentation of the method, the case study is presented: "to retract and to extend airborne the landing gear system". Then, each stage of the PMM development process is illustrated by examples from the case study: (1) Modeling the top level requirements specification, (2) Validating the requirements specification by proof and simulation, (3) Modeling the architectural design, Refining the top level requirements into requirements specified to the different subsystems contributing to the function and Modeling the terminal subsystems detailed designs (4) Validating the requirements specified to the contributing subsystems by proof or simulation, (5) Verifying the design models by simulation and finally (6-8) Verifying physical implementations by test on the basis of all validation and verification scenarios accumulated throughout the development. At end, lessons learnt and industrial perspectives are summarized highlighting how PMM is a methodology adapted to the challenges facing to systems engineering by the globalization of development processes and showing how PMM can provide a powerful conceptual framework to support digital continuity within globalized Design Organizations. Modeling, simulation, proof and test generation activities are supported by the MATLAB and Simulink products. Introduction The aeronautic industry has to deliver more and more complicated systems in term of functions while maintaining high level of quality and safety/reliability. In the same time, competition is driving aircraft manufacturers to strongly improve their costs (including non-recurring costs) and development lead time. At the age of globalization, these systems are designed and produced by large, multicultural, geographically distributed teams belonging to different industrial organizations. This evolution introduces additional complexities (the complexity of a goal-oriented process refers to its propensity to fail [Suh, 2005]). To face these challenges, classical systems engineering approaches

Published
2018

2. A generic exact solver for vehicle routing and related problems

Author

Eduardo Uchoa, Artur Alves Pessoa, Ruslan Sadykov, François Vanderbeck, Universidade Federal Fluminense [Rio de Janeiro] (UFF), Reformulations based algorithms for Combinatorial Optimization (Realopt), 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é de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-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)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), 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), Atoptima, We would like to thank Teobaldo Bulhoes and Guillaume Marques for a large part of the implementation of the Julia–JuMP interface to the solver, Teobaldo Bulhoes, Guillaume Marques and Eduardo Queiroga for implementing, over that interface, the models corresponding to the examples of this paper, and Laurent Facq for a general support of the computing environment. Experiments presented in this paper were carried out using the PlaFRIM (Federative Platform for Research in Computer Science and Mathematics), created under the Inria PlaFRIM development action with support from Bordeaux INP, LABRI and IMB and other entities: Conseil Régional d’Aquitaine, Université de Bordeaux, CNRS and ANR in accordance to the 'Programme d’Investissements d’Avenir'. This study was financed in part by the Conselho Nacional de Científico e Tecnológico (CNPq), grant 313601/2018-6 (Produtividade 1B), and by the Funda¸c˜ao de Amparo à Pesquisa do Estado do Rio de Janeiro (FAPERJ), grant E-26/202.887/2017 (Cientista do Estado)., Plafrim, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-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)-Institut de Mathématiques de Bordeaux (IMB), 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é Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, and 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)

Subjects
Mathematical optimization, 021103 operations research, Bin packing problem, General Mathematics, Column generation, 0211 other engineering and technologies, Integer programming, Rule-based system, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], 010103 numerical & computational mathematics, 02 engineering and technology, Solver, 01 natural sciences, Vehicle routing problem, Path (graph theory), 0101 mathematics, Routing (electronic design automation), Software, Routing, Mathematics
Abstract

Major advances were recently obtained in the exact solution of vehicle routing problems (VRPs). Sophisticated branch-cut-and-price (BCP) algorithms for some of the most classical VRP variants now solve many instances with up to a few hundreds of customers. However, adapting and reimplementing those successful algorithms for other variants can be a very demanding task. This work proposes a BCP solver for a generic model that encompasses a wide class of VRPs. It incorporates the key elements found in the best existing VRP algorithms: ng-path relaxation, rank-1 cuts with limited memory, path enumeration, and rounded capacity cuts; all generalized through the new concepts of “packing set” and “elementarity set”. The concepts are also used to derive a branching rule based on accumulated resource consumption and to generalize the Ryan and Foster branching rule. Extensive experiments on several variants show that the generic solver has an excellent overall performance, in many problems being better than the best specific algorithms. Even some non-VRPs, like bin packing, vector packing and generalized assignment, can be modeled and effectively solved.

Published
2020
Full Text
View/download PDF

3. Deciding feasibility of a booking in the European gas market on a cycle is in P for the case of passive networks

Author

Johannes Thürauf, Fränk Plein, Martine Labbé, Martin Schmidt, Integrated Optimization with Complex Structure (INOCS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université libre de Bruxelles (ULB)-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), Département d'Informatique [Bruxelles] (ULB), Faculté des Sciences [Bruxelles] (ULB), Université libre de Bruxelles (ULB)-Université libre de Bruxelles (ULB), Trier University, Friedrich-Alexander Universität Erlangen-Nürnberg (FAU), and Martine Labbé has been partially supported by the Fonds de la Recherche Scientifique - FNRS under Grant no PDR T0098.18. Fränk Plein thanks the Fonds de la Recherche Scientifique - FNRS for his Aspirant fellowship supporting the research for this publication. He also thanks the Deutsche Forschungsgemeinschaft for their support within the project Z01 in CRC TRR 154. This research has been performed as part of the Energie Campus Nürnberg and is supported by funding of the Bavarian State Government. The third and fourth author also thank the DFG for their support within projects A05, B07, and B08 in CRC TRR 154. Finally, we want to thank Lars Schewe for many fruitful discussions on the topic of this paper.

Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Gas networks, Mathematical optimization, Computational complexity theory, Computer Networks and Communications, Computer science, Dimension (graph theory), 0211 other engineering and technologies, System of polynomial equations, Modèles mathématiques d'aide à la décision, 02 engineering and technology, Cycle, Optimisation de réseaux, Informatique mathématique, 0502 economics and business, Real algebraic geometry, Time complexity, European entry-exit market, 050210 logistics & transportation, computational complexity, 021103 operations research, cycle, 05 social sciences, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Maximization, potential-based flows, Potential-based flows, Computational complexity, Nonlinear system, Bookings, Flow (mathematics), bookings, Hardware and Architecture, 90B10, 90C30, 90C35, 90C90, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], gas networks, Software, Information Systems
Abstract

We show that the feasibility of a booking in the European entry-exit gas market can be decided in polynomial time on single-cycle networks that are passive, i.e. do not contain controllable elements. The feasibility of a booking can be characterized by solving polynomially many nonlinear potential-based flow models for computing so-called potential-difference maximizing load flow scenarios. We thus analyze the structure of these models and exploit both the cyclic graph structure as well as specific properties of potential-based flows. This enables us to solve the decision variant of the nonlinear potential-difference maximization by reducing it to a system of polynomials of constant dimension that is independent of the cycle's size. This system of fixed dimension can be handled with tools from real algebraic geometry to derive a polynomial-time algorithm. The characterization in terms of potential-difference maximizing load flow scenarios then leads to a polynomial-time algorithm for deciding the feasibility of a booking. Our theoretical results extend the existing knowledge about the complexity of deciding the feasibility of bookings from trees to single-cycle networks., SCOPUS: ar.j, info:eu-repo/semantics/published

Published
2021
Full Text
View/download PDF

4. Bayesian optimization using deep Gaussian processes with applications to aerospace system design

Author

Nouredine Melab, El-Ghazali Talbi, Mathieu Balesdent, Loïc Brevault, Ali Hebbal, DTIS, ONERA, Université Paris Saclay [Palaiseau], ONERA-Université Paris-Saclay, Optimisation de grande taille et calcul large échelle (BONUS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-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), 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), and This work is co-funded by ONERA-The French Aerospace Lab and Université de Lille, in the context of a joint PhD thesis. Discussions with Hugh Salimbeni and Zhenwen Dai were very helpful for this work, special thanks to them. The Experiments presented in this paper were carried out using the Grid’5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr).

Subjects
Mathematical optimization, 021103 operations research, Control and Optimization, Optimization problem, Covariance function, Computer science, Mechanical Engineering, Bayesian optimization, 0211 other engineering and technologies, Aerospace Engineering, Context (language use), 02 engineering and technology, symbols.namesake, Test case, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], symbols, Systems design, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], 021108 energy, Electrical and Electronic Engineering, Representation (mathematics), Gaussian process, ComputingMilieux_MISCELLANEOUS, Software, Civil and Structural Engineering
Abstract

Bayesian Optimization using Gaussian Processes is a popular approach to deal with optimization involving expensive black-box functions. However, because of the assumption on the stationarity of the covariance function defined in classic Gaussian Processes, this method may not be adapted for non-stationary functions involved in the optimization problem. To overcome this issue, Deep Gaussian Processes can be used as surrogate models instead of classic Gaussian Processes. This modeling technique increases the power of representation to capture the non-stationarity by considering a functional composition of stationary Gaussian Processes, providing a multiple layer structure. This paper investigates the application of Deep Gaussian Processes within Bayesian Optimization context. The specificities of this optimization method are discussed and highlighted with academic test cases. The performance of Bayesian Optimization with Deep Gaussian Processes is assessed on analytical test cases and aerospace design optimization problems and compared to the state-of-the-art stationary and non-stationary Bayesian Optimization approaches.

Published
2020
Full Text
View/download PDF

5. Production-based pollution versus deforestation: optimal policy with state-independent and-dependent environmental absorption efficiency restoration process

Author

Marc Leandri, Eugene Khmelnitsky, Fouad El Ouardighi, ESSEC Business School [Cergy-Pontoise], Tel Aviv University [Tel Aviv], Centre d'études sur la mondialisation, les conflits, les territoires et les vulnérabilités (Cemotev), Université de Versailles Saint-Quentin-en-Yvelines (UVSQ), Tel Aviv University, TAU, and The authors acknowledge helpful comments from one anonymous referee. This research was supported by ESSEC Business School (France) and Tel Aviv University (Israel). The first author dedicates this paper to the memory of Mohamed El Houari, a wonderful mentor and friend.

Subjects
Pollution, Natural resource economics, Process (engineering), media_common.quotation_subject, 0211 other engineering and technologies, General Decision Sciences, Social Welfare, 02 engineering and technology, Management Science and Operations Research, History dependence, Deforestation, 11. Sustainability, Restoration process, Production (economics), 10. No inequality, Environmental absorption efficiency, media_common, 021103 operations research, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], 15. Life on land, 13. Climate action, Sustainability, Environmental science, Optimal pollution, Absorption efficiency
Abstract

International audience; An important yet largely unexamined issue is how the interaction between deforestation and pollution affects economic and environmental sustainability.This article seeks to bridge the gap by introducing a dynamic model of pollution accumulation where polluting emissions can be mitigated and the absorption efficiency of pollution sinks can be restored. We assume that emissions are due to a production activity, and we include deforestation both as an additional source of emissions and as a cause of the exhaustion of environmental absorption efficiency. To account for the fact that the switching of natural sinks to a pollution source can be either possible, and in such a case even reversible, or impossible, we consider that restoration efforts can be either independent from or dependent on environmental absorption efficiency, i.e., state-independent versus state-dependent restoration efforts. We determine (i) whether production or deforestation is the most detrimental from environmental and social welfare perspectives, and (ii) how state-dependent restoration process affects pollution accumulation and deforestation policies and the related environmental and social welfare consequences.

Published
2020
Full Text
View/download PDF

6. An iterative dynamic programming approach for the temporal knapsack problem

Author

Boris Detienne, Gaël Guillot, François Clautiaux, Reformulations based algorithms for Combinatorial Optimization (Realopt), 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é de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-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)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), This work was funded by Investments for the future Program IdEx Bordeaux, Cluster of ExcellenceSySNum.Experiments presented in this paper were carried out using the PLAFRIM experimental testbed,being developed under the Inria PlaFRIM development action with support from Bordeaux INP, LABRIand IMB and other entities: Conseil R ́egional d’Aquitaine, Universit ́e de Bordeaux, CNRS and ANR inaccordance to the programme d’investissements d’Avenir (see https://www.plafrim.fr/), Plafrim, RealOpt, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-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)-Institut de Mathématiques de Bordeaux (IMB), 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é Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, 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-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-Institut de Mathématiques de Bordeaux (IMB), and 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)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest

Subjects
Mathematical optimization, Information Systems and Management, General Computer Science, Computer science, Generalization, Temporal knapsack, 0211 other engineering and technologies, 02 engineering and technology, Management Science and Operations Research, Industrial and Manufacturing Engineering, Set (abstract data type), symbols.namesake, Lagrangian Relaxation, 0502 economics and business, 050210 logistics & transportation, 021103 operations research, 05 social sciences, Exact algorithm, Successive Sublimation Dynamic Programming method, Exponential function, Dynamic programming, Lagrangian relaxation, Knapsack problem, Modeling and Simulation, symbols, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
Abstract

International audience; In this paper, we address the temporal knapsack problem (TKP). In this generalization of the classical knapsack problem, selected items enter and leave the knapsack at fixed dates. We solve the TKP with a dynamic program of exponential size, which is solved using a method called Successive Sublimation Dynamic Programming (SSDP). This method starts by relaxing a set of constraints from the initial problem, and iteratively reintroduces them when needed. We show that a direct application of SSDP to the temporal knapsack problem does not lead to an effective method, and that several improvements are needed to compete with the best results from the literature.

Published
2021
Full Text
View/download PDF

7. Solving Bin Packing Problems Using VRPSolver Models

Author

Ruslan Sadykov, Eduardo Uchoa, Artur Alves Pessoa, Universidade Federal Fluminense [Rio de Janeiro] (UFF), Reformulations based algorithms for Combinatorial Optimization (Realopt), 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é de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-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)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Experiments presented in this paper were carried out using the PlaFRIM (Federative Platform for Research in Computer Science and Mathematics), created under the Inria PlaFRIM development action with support from Bordeaux INP, LABRI and IMB and other entities: Conseil Régional d’Aquitaine, Université de Bordeaux, CNRS and ANR in accordance to the 'Programme d’Investissements d’Avenir'. The research was partially supported by the following grants: CNPq 313601/2018-6, Faperj E-26/202.887/2017, and CAPES PrInt UFF n° 88881., Plafrim, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-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)-Institut de Mathématiques de Bordeaux (IMB), and 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é Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest

Subjects
Mathematical optimization, 021103 operations research, Bin packing problem, Computer science, 0211 other engineering and technologies, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Solver, 01 natural sciences, Variable (computer science), 010201 computation theory & mathematics, Vehicle routing problem, Column generation, Heuristics, Integer programming, Smoothing
Abstract

International audience; We propose branch-cut-and-price algorithms for the classic bin packing problem and also for the following related problems: vector packing, variable sized bin packing and variable sized bin packing with optional items. The algorithms are defined as models for VRPSolver, a generic solver for vehicle routing problems. In that way, a simple parameterization enables the use of several branch-cut-and-price advanced elements: automatic stabilization by smoothing, limited-memory rank-1 cuts, enumeration, hierarchical strong branching and limited discrepancy search diving heuristics. As an original theoretical contribution, we prove that the branching over accumulated resource consumption (Gélinas et al. 1995), that does not increase the difficulty of the pricing subproblem, is sufficient for those bin packing models. Extensive computational results on instances from the literature show that the VRPSolver models have a performance that is very robust over all those problems, being often superior to the existing exact algorithms on the hardest instances. Several instances could be solved to optimality for the first time.

Published
2021
Full Text
View/download PDF

8. Method and Framework for Security Risks Analysis Guided by Safety Criteria

Author

Guillaume Mockly, Gabriel Pedroza, Laboratoire d'Intégration des Systèmes et des Technologies (LIST), Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA), Université Paris-Saclay, Trialog [Paris], Part of the work presented in this paper was conducted in the scope of the project ModSécAéro partially funded by thre French RAPID programme. RAPID (régime d’appui à l’innovation duale). https://www.defense.gouv.fr/aid/deposez-vos-projets/subventions/rapid, and Laboratoire d'Intégration des Systèmes et des Technologies (LIST (CEA))

Subjects
021103 operations research, Computer science, [INFO.INFO-CE]Computer Science [cs]/Computational Engineering, Finance, and Science [cs.CE], 0211 other engineering and technologies, [INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE], 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-IA]Computer Science [cs]/Computer Aided Engineering, Reuse, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, 01 natural sciences, Risk analysis (engineering), 010201 computation theory & mathematics, Control system, Path (graph theory), Safety criteria, State (computer science), Model-driven architecture, Architecture, computer, ComputingMilieux_MISCELLANEOUS, computer.programming_language, Unified Process, Security, Risks, methodology, safety
Abstract

As previously discussed [13], the challenges to achieve a consistent intertwining between safety and security are rather diverse and complex. Recent advances in safety and security suggest that risks analyses provide guidance for achieving a comprehensive alignment. However, for many domains, like in aeronautics, security is rather a recent concern whereas aircraft development has been mostly guided by safety criteria for several decades. The referred disparity along with the fact that security is, in many respects, a discipline still in evolution, imposes restrictions for specifying and applying methods to conduct safety and security co-engineering as a unified process. In this paper, we present the progress in the development of a model-based method, a framework and a tool useful to conduct a security risks analysis guided by safety criteria and goals. Among others, the approach relies on know-how found in the state of the art, in standards like ED202, ED203 (EUROCAE)1, as well as in open knowledge bases like CAPEC and CWE (MITRE)2. These sources are integrated which allows the instantiation of patterns of attacks, vulnerabilities, and architectures, which are crucial elements to semi-automate the analysis. A rule-based algorithm for exploring potential attack paths across an architecture is proposed and implemented. The approach is finally demonstrated by analyzing a combined attack-failure path in a Flight Control System which can undermine the safety of a modern aircraft. The framework and tool support seek safety-security by design and aim to facilitate the reuse of case studies and to settle a basis for repeatability and results comparison.

Published
2020
Full Text
View/download PDF

9. Privacy-Preserving Personalized Revenue Management

Author

Yanzhe Lei, Ruslan Momot, Sentao Miao, Ecole des Hautes Etudes Commerciales (HEC Paris), HEC Research Paper Series, and Haldemann, Antoine

Subjects
History, Polymers and Plastics, Operations research, Computer science, revenue management, JEL: M - Business Administration and Business Economics • Marketing • Accounting • Personnel Economics/M.M2 - Business Economics/M.M2.M20 - General, Industry standard, 0211 other engineering and technologies, 02 engineering and technology, privacy, Industrial and Manufacturing Engineering, JEL: M - Business Administration and Business Economics • Marketing • Accounting • Personnel Economics/M.M3 - Marketing and Advertising/M.M3.M31 - Marketing, personalized pricing, Order (exchange), 0502 economics and business, Revenue, Differential privacy, 050207 economics, Business and International Management, Set (psychology), JEL: C - Mathematical and Quantitative Methods/C.C0 - General/C.C0.C02 - Mathematical Methods, 021103 operations research, Revenue management, JEL: L - Industrial Organization/L.L5 - Regulation and Industrial Policy/L.L5.L51 - Economics of Regulation, 05 social sciences, JEL: C - Mathematical and Quantitative Methods/C.C1 - Econometric and Statistical Methods and Methodology: General/C.C1.C13 - Estimation: General, JEL: M - Business Administration and Business Economics • Marketing • Accounting • Personnel Economics/M.M3 - Marketing and Advertising/M.M3.M37 - Advertising, JEL: C - Mathematical and Quantitative Methods/C.C4 - Econometric and Statistical Methods: Special Topics/C.C4.C44 - Operations Research • Statistical Decision Theory, JEL: A - General Economics and Teaching/A.A1 - General Economics/A.A1.A10 - General, Privacy preserving, data-driven decision making, JEL: D - Microeconomics/D.D2 - Production and Organizations/D.D2.D21 - Firm Behavior: Theory, JEL: D - Microeconomics/D.D1 - Household Behavior and Family Economics/D.D1.D18 - Consumer Protection, Consumer privacy, JEL: A - General Economics and Teaching/A.A1 - General Economics/A.A1.A12 - Relation of Economics to Other Disciplines, [SHS.GESTION]Humanities and Social Sciences/Business administration, JEL: C - Mathematical and Quantitative Methods/C.C1 - Econometric and Statistical Methods and Methodology: General/C.C1.C18 - Methodological Issues: General, [SHS.GESTION] Humanities and Social Sciences/Business administration, JEL: M - Business Administration and Business Economics • Marketing • Accounting • Personnel Economics/M.M1 - Business Administration/M.M1.M15 - IT Management, JEL: D - Microeconomics/D.D1 - Household Behavior and Family Economics/D.D1.D11 - Consumer Economics: Theory
Abstract

This paper examines how data-driven personalized decisions can be made while preserving consumer privacy. Our setting is one in which the firm chooses a personalized price based on each new customer's vector of individual features; the true set of individual demand-generating parameters is unknown to the firm and so must be estimated from historical data. We extend this classical framework of personalized pricing by requiring also that the firm's pricing policy preserve consumer privacy, or (formally) that it be differentially private -- an industry standard for privacy preservation. The two settings we consider are theoretically and practically relevant: central and local models of differential privacy, which differ in the strength of the privacy guarantees they provide. For both models, we develop privacy-preserving personalized pricing algorithms and derive the theoretical bounds on their performance as measured by the firm's revenue. Our analyses suggest that, if the firm possesses a sufficient amount of historical data, then it can achieve central differential privacy at a cost of the same order as the "classical" loss in revenue due to estimation error. Comparing the two models, we conclude that local differentially private personalized pricing yields better privacy guarantees but leads to much greater revenue loss by the firm. We confirm our theoretical findings in a series of numerical experiments based on synthetically generated and real-world On-line Auto Lending (CPRM-12-001) data sets. Finally, we also apply our theoretical framework to the setting of personalized assortment optimization.

Published
2020

10. Adaptive Grids for the Estimation of Dynamic Models

Author

Ole Wilms, Gregor Reich, Ecole des Hautes Etudes Commerciales (HEC Paris), HEC Paris Research Paper Series, Research Group: Finance, and Department of Finance

Subjects
History, Mathematical optimization, Polymers and Plastics, Computer science, Economics, Econometrics and Finance (miscellaneous), 0211 other engineering and technologies, Structure (category theory), mathematical programming with equilibrium constraints, Equioscillation, 02 engineering and technology, Industrial and Manufacturing Engineering, JEL: C - Mathematical and Quantitative Methods/C.C6 - Mathematical Methods • Programming Models • Mathematical and Simulation Modeling/C.C6.C63 - Computational Techniques • Simulation Modeling, Dynamic discrete choice models, Bellman equation, 0502 economics and business, 050207 economics, Business and International Management, r-adaptive grid refinement, Balanced Errors, computer.programming_language, Marketing, 021103 operations research, equi-oscillation, 05 social sciences, Grid, Adaptive Grids, Dynamic models, numerical dynamic programming, Feature (computer vision), [SHS.GESTION]Humanities and Social Sciences/Business administration, Node (circuits), computer, JEL: C - Mathematical and Quantitative Methods/C.C2 - Single Equation Models • Single Variables/C.C2.C25 - Discrete Regression and Qualitative Choice Models • Discrete Regressors • Proportions • Probabilities, Interpolation, Rust (programming language)
Abstract

This paper develops a method to flexibly adapt interpolation grids of value function approximations in the estimation of dynamic models using either NFXP (Rust, Econometrica: Journal of the Econom etric Society, 55, 999– 1 033, 1987) or MPEC (Su & Judd, Econometrica: Journal of the Econometric Society, 80, 2213–2230, 2012). Since MPEC requires the grid structure for the value function approximation to be hard-coded into the constraints, one cannot apply iterative node insertion for grid refinement; for NFXP, grid adaption by (iteratively) inserting new grid nodes will generally lead to discontinuous likelihood functions. Therefore, we show how to continuously adapt the grid by moving the nodes, a technique referred to as r-adaption. We demonstrate how to obtain optimal grids based on the balanced error principle, and implement this approach by including additional constraints to the likelihood maximization problem. The method is applied to two models: (i) the bus engine replacement model (Rust, 1987), modified to feature a continuous mileage state, and (ii) to a dynamic model of content consumption using original data from one of the world’s leading user-generated content networks in the domain of music.

Published
2020

11. Climate Change Assessments: Confidence, Probability, and Decision

Author

Richard Bradley, Brian Hill, Casey Helgeson, Haldemann, Antoine, Department of Archaeology, University of Reading (UOR), and HEC Paris Research Paper Series

Subjects
History, 021103 operations research, 010504 meteorology & atmospheric sciences, Management science, Perspective (graphical), 0211 other engineering and technologies, Climate change, Vroom–Yetton decision model, B Philosophy (General), 02 engineering and technology, 01 natural sciences, Philosophy, History and Philosophy of Science, [SHS.GESTION]Humanities and Social Sciences/Business administration, [SHS.GESTION] Humanities and Social Sciences/Business administration, Psychology, 0105 earth and related environmental sciences
Abstract

The Intergovernmental Panel on Climate Change has developed a novel framework for assessing and communicating uncertainty in the findings published in its periodic assessment reports. But how should these uncertainty assessments inform decisions? We take a formal decision-making perspective to investigate how scientific input formulated in the IPCC’s novel framework might inform decisions in a principled way through a normative decision model.

Published
2017
Full Text
View/download PDF

12. Linear Search by a Pair of Distinct-Speed Robots

Author

Tomasz Kociumaka, Jurek Czyzowicz, David Ilcinkas, Leszek Gąsieniec, Ralf Klasing, Dominik Pająk, Evangelos Bampas, School of of Electrical and Computer Engineering [Athens] (School of E.C.E), National Technical University of Athens [Athens] (NTUA), Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), Department of Computer Science [Liverpool], University of Liverpool, 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), University of Warsaw (UW), Institute of informatics [Wrocław], See paper for details., ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), ANR-13-JS02-0002,MACARON,Bouger et Calculer: Agents, Robots et Réseaux(2013), ANR-16-CE40-0023,DESCARTES,Abstraction modulaire pour le calcul distribué(2016), ANR-10-IDEX-0003,IDEX BORDEAUX,Initiative d'excellence de l'Université de Bordeaux(2010), Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory, Pajak, Dominik S, Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-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), Institute of Informatics [Warsaw], Faculty of Mathematics, Informatics, and Mechanics [Warsaw] (MIMUW), University of Warsaw (UW)-University of Warsaw (UW), and Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU)

Subjects
Engineering, General Computer Science, Computer science, different speeds, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0211 other engineering and technologies, 0102 computer and information sciences, 02 engineering and technology, Bang-bang robot, linear search, 01 natural sciences, Article, Computer Science::Robotics, Position (vector), mobile robots, 0202 electrical engineering, electronic engineering, information engineering, Cartesian coordinate robot, Point (geometry), Computer vision, [INFO]Computer Science [cs], Online algorithm, Simulation, Linear search, 021103 operations research, business.industry, Applied Mathematics, Mobile robot, Computer Science Applications, 010201 computation theory & mathematics, group search, Moment (physics), Line (geometry), Robot, 020201 artificial intelligence & image processing, Artificial intelligence, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business
Abstract

Two mobile robots are initially placed at the same point on an infinite line. Each robot may move on the line in either direction not exceeding its maximal speed. The robots need to find a stationary target placed at an unknown location on the line. The search is completed when both robots arrive at the target point. The target is discovered at the moment when either robot arrives at its position. The robot knowing the placement of the target may communicate it to the other robot. We look for the algorithm with the shortest possible search time (i.e. the worst-case time at which both robots meet at the target) measured as a function of the target distance from the origin (i.e. the time required to travel directly from the starting point to the target at unit velocity). We consider two standard models of communication between the robots, namely wireless communication and communication by meeting. In the case of communication by meeting, a robot learns about the target while sharing the same location with a robot possessing this knowledge. We propose here an optimal search strategy for two robots including the respective lower bound argument, for the full spectrum of their maximal speeds. This extends the main result of Chrobak et al. (in: Italiano, Margaria-Steffen, Pokorný, Quisquater, Wattenhofer (eds) Current trends in theory and practice of computer science, SOFSEM, 2015) referring to the exact complexity of the problem for the case when the speed of the slower robot is at least one third of the faster one. In the wireless communication model, a message sent by one robot is instantly received by the other robot, regardless of their current positions on the line. For this model, we design a strategy which is optimal whenever the faster robot is at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sqrt{17}+4\approx 8.123$$\end{document}17+4≈8.123 times faster than the slower one. We also prove that otherwise the wireless communication offers no advantage over communication by meeting.

Published
2019
Full Text
View/download PDF

13. Multi-objective inventory routing problem : A stochastic model to consider profit, service level and green criteria

Author

Armand Baboli, Mohammad Rahimi, Yacine Rekik, emlyon business school, Décision et Information pour les Systèmes de Production (DISP), 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)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université Lumière - Lyon 2 (UL2), The authors gratefully acknowledge the scientific and financial support of the Région Rhône-Alpes, France (ARC7), for the research reported in this paper., and business school, emlyon

Subjects
0209 industrial biotechnology, Operations research, Stochastic modelling, 0211 other engineering and technologies, Transportation, 02 engineering and technology, Fuzzy logic, Profit (economics), 020901 industrial engineering & automation, Economics, Operations management, Inventory Routing Problem, Business and International Management, [SHS.ECO] Humanities and Social Sciences/Economics and Finance, Civil and Structural Engineering, 021103 operations research, Supply chain management, Green supply chain, Perishable product, Level of service, Service level, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [SHS.ECO]Humanities and Social Sciences/Economics and Finance, Stochastic programming, Multi-objective mathematical model, Inventory theory, [SHS.GESTION]Humanities and Social Sciences/Business administration, [SHS.GESTION] Humanities and Social Sciences/Business administration
Abstract

International audience; The Inventory Routing Problem has been mainly studied in recent decades under an economic performance perspective. In this paper, we develop a multi-objective mathematical framework for the IRP to link: (i) the economic performance, (ii) the achieved server level in terms of shortage and delivery delays and (iii) the environmental footprint. The framework developed addresses the uncertainty by considering fuzzy distributions for certain problem inputs, such as the demand and the transportation costs. We show the negative impact on the economic performance when service level targets are exogenously chosen without coordination with the logistics components (inventory and distribution). (C) 2017 Elsevier Ltd. All rights reserved.

Published
2017
Full Text
View/download PDF

14. An Efficient Approach for Multi-tenant Elastic Business Processes Management in Cloud Computing Environment

Author

François Charoy, Guillaume Rosinosky, Samir Youcef, Bonitasoft, Web Scale Trustworthy Collaborative Service Systems (COAST), 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 Networks, Systems and Services (LORIA - NSS), 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), CIFRE Bonitasoft, 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), 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), and The authors would like to thank Gurobi for the usage of their optimizer, and Amazon Web Services for the EC2 instances credits (this paper is supported by an AWS in Education Research Grant award).

Subjects
Computer science, Business process, 0211 other engineering and technologies, Cloud computing, Multi-tenancy, [INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE], 02 engineering and technology, [INFO.INFO-SI]Computer Science [cs]/Social and Information Networks [cs.SI], Utility computing, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, ACM: C.: Computer Systems Organization/C.2: COMPUTER-COMMUNICATION NETWORKS/C.2.4: Distributed Systems/C.2.4.1: Distributed applications, Elasticity (economics), Multitenancy, 021103 operations research, Management science, business.industry, Bi-criteria optimization, Quality of service, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, Elasticity, [INFO.INFO-PF]Computer Science [cs]/Performance [cs.PF], BPM, Risk analysis (engineering), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, Cloud
Abstract

International audience; Even though the proven benefits of cloud computing paradigm, it must face a serious problem that can compromise its commercial success. It concerns the lack of efficient approach for using optimally the available resources. For this, several approaches have been proposed. However,they suffer from several shortcomings. For instance, often only one objective is taken into account expressing all operations in terms of cost. Furthermore, business processes should be insured with elasticity and multitenancy mechanism while adjusting the available resources to the dynamic load distribution. The proposed approach aims to optimize two conflicting objectives, namely the number of migrated tenants and the cost incurred using a set of resources. It allows to take into account the multi-tenancy property and the Cloud computing elasticity, and is efficient as shown by an extensive experimentation based on real data from Bonita BPM customers.

Published
2016
Full Text
View/download PDF

15. How many oblivious robots can explore a line

Author

Nicola Santoro, David Ilcinkas, Andrzej Pelc, Paola Flocchini, School of Information Technology and Engineering [Ottawa] (SITE), University of Ottawa [Ottawa], 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), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), School of Computer Science [Ottawa], Carleton University, See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest

Subjects
Theoretical computer science, Computer science, Distributed computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0211 other engineering and technologies, 0102 computer and information sciences, 02 engineering and technology, exploration, 01 natural sciences, Theoretical Computer Science, distributed computing, oblivious, mobile robots, Impossibility, asynchronous, 021103 operations research, Mobile robot, Computer Science Applications, 010201 computation theory & mathematics, Asynchronous communication, Signal Processing, Robot, line, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Line (text file), Information Systems
Abstract

International audience; We consider the problem of exploring an anonymous line by a team of k identical, oblivious, asynchronous deterministic mobile robots that can view the environment but cannot communicate. We completely characterize sizes of teams of robots capable of exploring a n-node line. For k= 5, or k=4 and n is odd. For all values of k for which exploration is possible, we give an exploration algorithm. For all others, we prove an impossibility result.

Published
2011
Full Text
View/download PDF

16. A benchmark of kriging-based infill criteria for noisy optimization

Author

Tobias Wagner, David Ginsbourger, Victor Picheny, Unité de Mathématiques et Informatique Appliquées de Toulouse (MIAT INRA), Institut National de la Recherche Agronomique (INRA), Technische Universität Dortmund [Dortmund] (TU), University of Bern, Deutsche Forschungsgemeinschaft (DFG) [SFB/TR TRR 30] Funding Text : The contributions of Tobias Wagner to this paper are based on investigations of the project D5 of the Collaborative Research Center SFB/TR TRR 30, which is kindly supported by the Deutsche Forschungsgemeinschaft (DFG)., and Picheny, Victor

Subjects
Mathematical optimization, Control and Optimization, Covariance function, 0211 other engineering and technologies, 02 engineering and technology, Metamodeling, symbols.namesake, 510 Mathematics, DESIGN, Kriging, Homoscedasticity, 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], [MATH]Mathematics [math], Gaussian process, GLOBAL OPTIMIZATION, Mathematics, EGO, 021103 operations research, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], Covariance, Computer Graphics and Computer-Aided Design, Computer Science Applications, COMPUTER EXPERIMENTS, Control and Systems Engineering, Gaussian noise, SIMULATION, symbols, 020201 artificial intelligence & image processing, Engineering design process, Noise, Software
Abstract

International audience; Responses of many real-world problems can only be evaluated perturbed by noise. In order to make an efficient optimization of these problems possible, intelligent optimization strategies successfully coping with noisy evaluations are required. In this article, a comprehensive review of existing kriging-based methods for the optimization of noisy functions is provided. In summary, ten methods for choosing the sequential samples are described using a unified formalism. They are compared on analytical benchmark problems, whereby the usual assumption of homoscedastic Gaussian noise made in the underlying models is meet. Different problem configurations (noise level, maximum number of observations, initial number of observations) and setups (covariance functions, budget, initial sample size) are considered. It is found that the choices of the initial sample size and the covariance function are not critical. The choice of the method, however, can result in significant differences in the performance. In particular, the three most intuitive criteria are found as poor alternatives. Although no criterion is found consistently more efficient than the others, two specialized methods appear more robust on average.

Published
2013
Full Text
View/download PDF

17. Asynchronous deterministic rendezvous in bounded terrains

Author

Arnaud Labourel, Andrzej Pelc, David Ilcinkas, Jurek Czyzowicz, Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), 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), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'informatique Fondamentale de Marseille - UMR 6166 (LIF), Université de la Méditerranée - Aix-Marseille 2-Université de Provence - Aix-Marseille 1-Centre National de la Recherche Scientifique (CNRS), See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest

Subjects
Computational Geometry (cs.CG), FOS: Computer and information sciences, Mathematical optimization, General Computer Science, Computer science, 0211 other engineering and technologies, Terrain, ComputerApplications_COMPUTERSINOTHERSYSTEMS, 0102 computer and information sciences, 02 engineering and technology, Computer Science::Computational Geometry, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, ComputingMethodologies_ARTIFICIALINTELLIGENCE, Theoretical Computer Science, Computer Science::Robotics, 010104 statistics & probability, mobile agent, Compass, Computer Science - Data Structures and Algorithms, rendezvous, Data Structures and Algorithms (cs.DS), 0101 mathematics, obstacle, 021103 operations research, Rendezvous, deterministic, polygon, 010201 computation theory & mathematics, Asynchronous communication, Bounded function, Obstacle, Polygon, A priori and a posteriori, Robot, Computer Science - Computational Geometry, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Computer Science(all)
Abstract

Two mobile agents (robots) have to meet in an a priori unknown bounded terrain modeled as a polygon, possibly with polygonal obstacles. Agents are modeled as points, and each of them is equipped with a compass. Compasses of agents may be incoherent. Agents construct their routes, but the actual walk of each agent is decided by the adversary: the movement of the agent can be at arbitrary speed, the agent may sometimes stop or go back and forth, as long as the walk of the agent in each segment of its route is continuous, does not leave it and covers all of it. We consider several scenarios, depending on three factors: (1) obstacles in the terrain are present, or not, (2) compasses of both agents agree, or not, (3) agents have or do not have a map of the terrain with their positions marked. The cost of a rendezvous algorithm is the worst-case sum of lengths of the agents' trajectories until their meeting. For each scenario we design a deterministic rendezvous algorithm and analyze its cost. We also prove lower bounds on the cost of any deterministic rendezvous algorithm in each case. For all scenarios these bounds are tight.

Published
2011
Full Text
View/download PDF

18. A Chance-Constrained Model & Cutting Planes for Fixed Broadband Wireless Networks

Author

Grit Claßen, Arie M. C. A. Koster, David Coudert, Napoleão Nepomuceno, Lehrstuhl II für Mathematik, Rheinisch-Westfälische Technische Hochschule Aachen (RWTH), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 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 (... - 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), Institut for Matematik og Datalogi (IMADA), Syddansk Universitet, This paper results from a research cooperation which was promoted by the PROCOPE program, a bilateral program funded by the German Academic Exchange Service with funds of the BMBF and by the French Ministry of Foreign Affairs. Additionally, this work has been supported by ANR DIMAGREEN and ECOSCELLS, the PATHFINDER project, Région PACA, and SME 3ROAM as well as the excellence initiative of the German federal and state governments and by the UMIC Research Centre at RWTH Aachen University. The for, Rheinisch-Westfälische Technische Hochschule Aachen University (RWTH), Université Nice Sophia Antipolis (1965 - 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 (1965 - 2019) (UNS)

Subjects
Mathematical optimization, 021103 operations research, Linear programming, Computer science, Separation (aeronautics), 0211 other engineering and technologies, 020206 networking & telecommunications, Polytope, 02 engineering and technology, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Wireless broadband, 0202 electrical engineering, electronic engineering, information engineering, Integer programming, Communication channel, Integer (computer science)
Abstract

International audience; In this paper, we propose a chance-constrained mathematical program for fixed broadband wireless networks under unreliable channel conditions. The model is reformulated as integer linear program and valid inequalities are derived for the corresponding polytope. Computational results show that by an exact separation approach the optimality gap is closed by 42% on average.; Dans cet article, nous proposons une modélisation en programme mathématique de type "chance-constrained" de réseaux de collecte à faisceaux hertziens avec conditions de transmissions non fiables. Le modèle est reformulé sous forme de programme linéaire en nombres entiers. Des inégalités valides sont générées à partir du polytope correspondant. Les résultats numériques montrent que l'approche par séparation exacte fourni un écart à l'optimal de 42% en moyenne.

Published
2011
Full Text
View/download PDF

19. Almost Optimal Asynchronous Rendezvous in Infinite Multidimensional Grids

Author

Jurek Czyzowicz, Evangelos Bampas, Leszek Gąsieniec, David Ilcinkas, Arnaud Labourel, Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), Department of Computer Science [Liverpool], University of Liverpool, 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), See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Discrete mathematics, Mathematical optimization, 021103 operations research, Euclidean space, Dimension (graph theory), 0211 other engineering and technologies, Rendezvous, 0102 computer and information sciences, 02 engineering and technology, Grid, 01 natural sciences, Upper and lower bounds, law.invention, Computer Science::Multiagent Systems, 010201 computation theory & mathematics, law, Position (vector), rendezvous, Cartesian coordinate system, mobile agents, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Rendezvous problem, Mathematics
Abstract

International audience; Two anonymous mobile agents (robots) moving in an asynchronous manner have to meet in an infinite grid of dimension $\dime > 0$, starting from two arbitrary positions at distance at most $d$. Since the problem is clearly infeasible in such general setting, we assume that the grid is embedded in a $\dime$-dimensional Euclidean space and that each agent knows the Cartesian coordinates of its own initial position (but not the one of the other agent). We design an algorithm permitting the agents to meet after traversing a trajectory of length $O(d^\dime{\rm polylog\ }d)$. This bound for the case of {\sc 2d}~-grids subsumes the main result of \cite{CCGL}. The algorithm is almost optimal, since the $\Omega(d^\dime)$ lower bound is straightforward. Further, we apply our rendezvous method to the following network design problem. The ports of the $\dime$-dimensional grid have to be set such that two anonymous agents starting at distance at most $d$ from each other will always meet, moving in an asynchronous manner, after traversing a $O(d^\dime{\rm polylog\ }d)$ length trajectory. We can also apply our method to a version of the geometric rendezvous problem. Two anonymous agents move asynchronously in the $\dime$-dimensional Euclidean space. The agents have the radii of visibility of $r_1$ and $r_2$, respectively. Each agent knows only its own initial position and its own radius of visibility. The agents meet when one agent is visible to the other one. We propose an algorithm designing the trajectory of each agent, so that they always meet after traveling a total distance of $O((\frac{d}{r})^\dime {\rm polylog}(\frac{d}{r}))$, where $r = \min(r_1, r_2)$ and for $r\geq 1$.

Published
2010
Full Text
View/download PDF

20. A Solution to a Problem of D. Lau: Complete Classification of Intervals in the Lattice of Partial Boolean Clones

Author

Karsten Schölzel, Miguel Couceiro, Lucien Haddad, Tamás Waldhauser, Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Knowledge representation, reasonning (ORPAILLEUR), 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 Natural Language Processing & Knowledge Discovery (LORIA - NLPKD), 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), Royal Military College of Canada (RMCC), Royal Military College of Canada, Mathematics Research Unit, University of Luxembourg [Luxembourg], Bolyai Institute [Szeged], University of Szeged [Szeged], Université du Luxembourg (Uni.lu), and The authors thank the anonymous referees for their valuable comments on the previous version of this paper. L. Haddad is supported by Academic Research Program of RMC. K. Sch¨olzel is supported by the internal research project MRDO2 of the University of Luxembourg. T. Waldhauser acknowledges that the present project is supported by the Hungarian National Foundation for Scientific Research under grants no. K83219 and K104251. The present project is supported by the European Union and co-funded by the European Social Fund under the project 'Telemedicine-focused research activities on the field of Mathematics, Informatics and Medical sciences' of project number 'TAMOP-4.2.2.A-11/1/KONV-2012-0073'.

Subjects
Discrete mathematics, 021103 operations research, Parity function, Two-element Boolean algebra, 010102 general mathematics, 0211 other engineering and technologies, 02 engineering and technology, Boolean algebras canonically defined, Complete Boolean algebra, 01 natural sciences, Combinatorics, Boolean domain, Maximum satisfiability problem, Free Boolean algebra, Boolean expression, [INFO]Computer Science [cs], 0101 mathematics, [MATH]Mathematics [math], Mathematics
Abstract

International audience; The following natural problem, first considered by D. Lau, has been tackled by several authors recently: Let C be a total clone on 2 := {0, 1}. Describe the interval I(C) of all partial clones on 2 whose total component is C. We establish some results in this direction and combine them with previous ones to show the following dichotomy result: For every total clone C on 2, the set I(C) is either finite or of continuum cardinality. 1. Preliminaries Let k ≥ 2 be an integer and let k be a k-element set. Without loss of generality we assume that k := {0,. .. , k − 1}. For a positive integer n, an n-ary partial function on k is a map f : dom (f) → k where dom (f) is a subset of k n , called the domain of f. Let Par (n) (k) denote the set of all n-ary partial functions on k and let Par(k) := n≥1

Full Text
View/download PDF