Search

Showing total 10 results
Start Over Topic mathematical optimization Language undetermined
10 results

1. 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

2. 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

3. 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

4. A general global-local modelling framework for the deterministic optimisation of composite structures

Author

Marco Picchi Scardaoni, Marco Montemurro, Institut de Mécanique et d'Ingénierie de Bordeaux (I2M), École Nationale Supérieure d'Arts et Métiers (ENSAM), Arts et Métiers Sciences et Technologies, HESAM Université (HESAM)-HESAM Université (HESAM)-Arts et Métiers Sciences et Technologies, HESAM Université (HESAM)-HESAM Université (HESAM)-Institut Polytechnique de Bordeaux-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-Institut National de la Recherche Agronomique (INRA), University of Pisa - Università di Pisa, and This paper presents part of the activities carried out within the research project PARSIFAL ('PrandtlPlane ARchitecture for the Sustainable Improvement of Future AirpLanes'), which has been funded by the European Union under the Horizon 2020 Research and Innovation Program (Grant Agreement n.723149)

Subjects
Mathematical optimization, Control and Optimization, Cantilever, Local modelling approach, Computer science, 0211 other engineering and technologies, 02 engineering and technology, Marsaglia polar method, Design strategy, [SPI.MECA.SOLID]Engineering Sciences [physics]/Mechanics [physics.med-ph]/Solid mechanics [physics.class-ph], 01 natural sciences, Polar method, 021105 building & construction, Mécanique: Mécanique des structures [Sciences de l'ingénieur], 0101 mathematics, Anisotropy, Composites, Buckling, Deterministic optimisation, Global/local modelling approach, Deterministic Optimisation, Mécanique: Mécanique des solides [Sciences de l'ingénieur], Global, Optimisation et contrôle [Mathématique], Computer Graphics and Computer-Aided Design, Computer Science Applications, Design for manufacturability, 010101 applied mathematics, [SPI.MECA.STRU]Engineering Sciences [physics]/Mechanics [physics.med-ph]/Structural mechanics [physics.class-ph], Control and Systems Engineering, Macroscopic scale, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Engineering design process, Software
Abstract

International audience; This work deals with the multi-scale optimisation of composite structures by adopting a general global-local (GL) modelling strategy to assess the structure responses at different scales. The GL modelling approach is integrated into the multi-scale two-level optimisation strategy (MS2LOS) for composite structures. The resulting design strategy is, thus, called GL-MS2LOS and aims at proposing a very general formulation of the design problem, without introducing simplifying hypotheses on the laminate stack and by considering, as design variables, the full set of geometric and mechanical parameters defining the behaviour of the composite structure at each pertinent scale. By employing a GL modelling approach, most of the limitations of well-established design strategies, based on analytical or semi-empirical models, are overcome. The GL-MS2LOS makes use of the polar formalism to describe the anisotropy of the composite at the macroscopic scale (where it is modelled as an equivalent homogeneous anisotropic plate). In this work, deterministic algorithms are exploited during the solution search phase. The challenge, when dealing with such a design problem, is to develop a suitable formulation and dedicated operators, to link global and local models physical responses and their gradients. Closed-form expressions of structural responses gradients are rigorously derived by taking into account for the coupling effects when passing from global to local models. The effectiveness of the GL-MS2LOS is proven on a meaningful benchmark: the least-weight design of a cantilever wing subject to different design requirements. Constraints include maximum allowable displacements, maximum allowable strains, blending, manufacturability requirements and buckling factor.; This work deals with the multi-scale optimisation of composite structures by adopting a general global-local (GL) modelling strategy to assess the structure responses at different scales. The GL modelling approach is integrated into the multi-scale two-level optimisation strategy (MS2LOS) for composite structures. The resulting design strategy is, thus, called GL-MS2LOS and aims at proposing a very general formulation of the design problem, without introducing simplifying hypotheses on the laminate stack and by considering, as design variables, the full set of geometric and mechanical parameters defining the behaviour of the composite structure at each pertinent scale. By employing a GL modelling approach, most of the limitations of well-established design strategies, based on analytical or semi-empirical models, are overcome. The GL-MS2LOS makes use of the polar formalism to describe the anisotropy of the composite at the macroscopic scale (where it is modelled as an equivalent homogeneous anisotropic plate). In this work, deterministic algorithms are exploited during the solution search phase. The challenge, when dealing with such a design problem, is to develop a suitable formulation and dedicated operators, to link global and local models physical responses and their gradients. Closed-form expressions of structural responses gradients are rigorously derived by taking into account for the coupling effects when passing from global to local models. The effectiveness of the GL-MS2LOS is proven on a meaningful benchmark: the least-weight design of a cantilever wing subject to different design requirements. Constraints include maximum allowable displacements, maximum allowable strains, blending, manufacturability requirements and buckling factor.

Published
2020

5. Efficiency of Correlation in a Bottleneck Game

Author

Marco Scarsini, Thomas J Rivera, Tristan Tomala, Orange Labs, Groupement de Recherche et d'Etudes en Gestion à HEC (GREGH), Ecole des Hautes Etudes Commerciales (HEC Paris)-Centre National de la Recherche Scientifique (CNRS), and HEC Paris Research Paper Series

Subjects
TheoryofComputation_MISCELLANEOUS, price of anarchy, Computer Science::Computer Science and Game Theory, Correlated equilibrium, Mathematical optimization, Computer science, price of correlated stability, Nash equilibrium, price of stability, Bottleneck, correlated equilibrium, Task (project management), symbols.namesake, Discrete time and continuous time, symbols, Price of anarchy, [SHS.GESTION]Humanities and Social Sciences/Business administration, Train, efficiency of equilibria, Price of stability
Abstract

We consider a model of bottleneck congestion in discrete time with a penalty cost for being late. This model can be applied to several situations where agents need to use a capacitated facility in order to complete a task before a hard deadline. A possible example is a situation where commuters use a train service to go from home to office in the early morning. Trains run at regular intervals, take always the same time to cover their itinerary, and have a fixed capacity. Commuters must reach their office in time. This is a hard constraint whose violation involves a heavy penalty. Conditionally on meeting the deadline, commuters want to take the train as late as possible. With the intent of considering strategic choices of departure, we model this situation as a game and we show that it does not have pure Nash equilibria. Then we characterize the best and worst mixed Nash equilibria, and show that they are both inefficient with respect to the social optimum. We then show that there exists a correlated equilibrium that approximates the social optimum when the penalty for missing the deadline is sufficiently large.

Published
2018

6. Derandomizing random walks in undirected graphs using locally fair exploration strategies

Author

Ralf Klasing, Adrian Kosowski, Colin Cooper, David Ilcinkas, Department of Computer Science (DCS), King‘s College London, 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), Combinatoire et Algorithmique, 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), 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), Department of Algorithms and Systems Modelling [ETI GUT] (Gdansk University of Technology), Faculty of Electronics, Telecommunications and Informatics [GUT Gdańsk] (ETI), Gdańsk University of Technology (GUT)-Gdańsk University of Technology (GUT), ANR-05-MMSA-0006,ALPAGE,ALgorithmique des Plates-formes A Grande Echelle(2005), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, 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), 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
Mathematical optimization, Computer Networks and Communications, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Comparability graph, Random walk, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, law.invention, Theoretical Computer Science, Combinatorics, Indifference graph, Graph exploration, law, Graph power, Line graph, Random regular graph, 0202 electrical engineering, electronic engineering, information engineering, Pancyclic graph, Mathematics, Discrete mathematics, Block graph, graph exploration : Propp machine, Directed graph, Feedback arc set, Computational Theory and Mathematics, 010201 computation theory & mathematics, Hardware and Architecture, Robbins' theorem, Graph (abstract data type), 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

International audience; We consider the problem of exploring an anonymous undirected graph using an oblivious robot. The studied exploration strategies are designed so that the next edge in the robot's walk is chosen using only local information, and so that some local equity (fairness) criterion is satisfied for the adjacent undirected edges. Such strategies can be seen as an attempt to derandomize random walks, and are natural counterparts for undirected graphs of the rotor-router model for symmetric directed graphs. The first of the studied strategies, known as Oldest-First (OF), always chooses the neighboring edge for which the most time has elapsed since its last traversal. Unlike in the case of symmetric directed graphs, we show that such a strategy in some cases leads to exponential cover time. We then consider another strategy called Least-Used-First (LUF) which always uses adjacent edges which have been traversed the smallest number of times. We show that any Least-Used-First exploration covers a graph G=(V,E) of diameter diam within time O(diam|E|), and in the long run traverses all edges of G with the same frequency.

Published
2011

7. The cost of monotonicity in distributed graph searching

Author

Nicolas Nisse, David Soguet, David Ilcinkas, Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Additional supports from the project 'Fragile' of the ACI Sécurité Informatique, and from the project 'Grand Large' of INRIA., Eduardo Tovar, Philippas Tsigas, Hacène Fouchal, 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), 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), 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), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, 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
Monotonicity, Mathematical optimization, Theoretical computer science, Computer Networks and Communications, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 050801 communication & media studies, 0102 computer and information sciences, 02 engineering and technology, Strength of a graph, Biconnected graph, 01 natural sciences, Theoretical Computer Science, law.invention, 0508 media and communications, Graph power, law, Line graph, 0202 electrical engineering, electronic engineering, information engineering, Graph property, Complement graph, Graph searching, Distance-hereditary graph, Mobile agent, Discrete mathematics, 020203 distributed computing, 05 social sciences, Voltage graph, Directed graph, Butterfly graph, Competitive ratio, Graph bandwidth, Computational Theory and Mathematics, 010201 computation theory & mathematics, Hardware and Architecture, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Null graph, Graph factorization, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

International audience; Blin {\it et al.} (2006) proposed a distributed protocol that enables the smallest number of searchers to clear any unknown asynchronous graph in a decentralized manner. {\it Unknown} means that the searchers are provided no {\it a priori} information about the graph. However, the strategy that is actually performed lacks of an important property, namely the monotonicity. That is, the clear part of the graph may decrease at some steps of the execution of the protocol. Actually, the protocol of Blin {\it et al.} is executed in exponential time. Nisse and Soguet (2007) proved that, in order to ensure the smallest number of searchers to clear any $n$-node graph in a monotone way, it is necessary and sufficient to provide $\Theta(n \log n)$ bits of information to the searchers by putting short labels on the nodes of the graph. This paper deals with the smallest number of searchers that are necessary and sufficient to monotoneously clear any graph in a decentralized manner, when the searchers have no a priori information about the graph. The distributed graph searching problem considers a team of searchers that is aiming at clearing any connected contaminated graph. The clearing of the graph is required to be {\it connected}, i.e., the clear part of the graph must remain permanently connected, and {\it monotone}, i.e., the clear part of the graph only grows. The {\it search number} $\mcs(G)$ of a graph $G$ is the smallest number of searchers necessary to clear $G$ in a monotone connected way in centralized settings. We prove that any distributed protocol aiming at clearing any unknown n-node graph in a monotone connected way, in decentralized settings, has {\it competitive ratio} $\Theta(\frac{n}{\log n})$. That is, we prove that, for any distributed protocol $\cal P$, there exists a constant $c$ such that for any sufficiently large $n$, there exists a $n$-node graph $G$ such that $\cal P$ requires at least $c\frac{n}{\log n}\, \mcs(G)$ searchers to clear $G$. Moreover, we propose a distributed protocol that allows $O(\frac{n}{\log n})\, \mcs(G)$ searchers to clear any unknown asynchronous $n$-node graph $G$ in a monotone connected way.

Published
2009

8. Approximate Implementation in Markovian Environments

Author

Ludovic Renou, Tristan Tomala, University of Essex, Groupement de Recherche et d'Etudes en Gestion à HEC (GREGH), Ecole des Hautes Etudes Commerciales (HEC Paris)-Centre National de la Recherche Scientifique (CNRS), and HEC Paris Research Paper Series

Subjects
jel:C70, High probability, Economics and Econometrics, Mechanism design, Computer Science::Computer Science and Game Theory, Mathematical optimization, Markov Process, Computer science, Existential quantification, Markov process, Function (mathematics), Set (abstract data type), undetectability, symbols.namesake, Monopolistic competition, JEL: C - Mathematical and Quantitative Methods/C.C7 - Game Theory and Bargaining Theory, efficiency, symbols, [SHS.GESTION]Humanities and Social Sciences/Business administration, implementation, Mathematical economics, Private information retrieval, Social choice theory, Mathematics
Abstract

This paper considers dynamic implementation problems with evolving private information (according to Markov processes). A social choice function is approximately implementable if there exists a dynamic mechanism such that the social choice function is implemented by an arbitrary large number of times with arbitrary high probability in every communication equilibrium. We show that if a social choice function is strictly efficient in the set of social choice functions that satisfy an undetectable condition, then it is approximately implementable. We revisit the classical monopolistic screening problem and show that the monopolist can extract the full surplus in almost all periods with arbitrary high probability.

Published
2013

9. Markov games with frequent actions and incomplete information

Author

Pierre Cardaliaguet, Catherine Rainer, Nicolas Vieille, Dinah Rosenberg, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL-Centre National de la Recherche Scientifique (CNRS), Laboratoire de mathématiques de Brest (LM), Université de Brest (UBO)-Institut Brestois du Numérique et des Mathématiques (IBNM), Université de Brest (UBO)-Centre National de la Recherche Scientifique (CNRS), Groupement de Recherche et d'Etudes en Gestion à HEC (GREGH), Ecole des Hautes Etudes Commerciales (HEC Paris)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), and HEC Paris Research Paper Series

Subjects
Mathematical optimization, Computer Science::Computer Science and Game Theory, Optimization problem, MathematicsofComputing_NUMERICALANALYSIS, jel:C00, Markov model, 01 natural sciences, Bayesian game, Markov games, Complete information, zero-sum games, 91A05, 91A15, 60J10, 0502 economics and business, incomplete information, FOS: Mathematics, 0101 mathematics, Mathematics - Optimization and Control, 050205 econometrics, Mathematics, Markov chain, Variable-order Markov model, 010102 general mathematics, 05 social sciences, Stochastic game, ComputingMilieux_PERSONALCOMPUTING, TheoryofComputation_GENERAL, stochastic, zero sum, Hamilton-Jacobi equation, repeated games, Optimization and Control (math.OC), Balance equation, [SHS.GESTION]Humanities and Social Sciences/Business administration, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Hamilton-Jacobi equations
Abstract

We study a two-player, zero-sum, stochastic game with incomplete information on one side in which the players are allowed to play more and more frequently. The informed player observes the realization of a Markov chain on which the payoffs depend, while the non-informed player only observes his opponent's actions. We show the existence of a limit value as the time span between two consecutive stages vanishes; this value is characterized through an auxiliary optimization problem and as the solution of an Hamilton-Jacobi equation.

Published
2013
Full Text
View/download PDF

10. 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