Search

Showing total 12 results
Start Over Topic mathematical optimization Publication Year Range Last 10 years
12 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. Stability of optimal traffic plans in the irrigation problem

Author

Antoine Prouff, Antonio De Rosa, Andrea Marchese, Maria Colombo, Paul Pegon, Ecole Polytechnique Fédérale de Lausanne (EPFL), Courant Institute of Mathematical Sciences [New York] (CIMS), New York University [New York] (NYU), NYU System (NYU)-NYU System (NYU), Department of mathematics/Dipartimento di Matematica [Univ. Trento], Università degli Studi di Trento (UNITN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Ecole Normale Supérieure Paris-Saclay (ENS Paris Saclay), Maria Colombo was partially supported by the Swiss National Science Foundation grant 200021_182565. Antonio De Rosa has been supported by the NSF DMS Grant No. 1906451. Andrea Marchese acknowledges partial support from GNAMPA-INdAM., Department of Mathematics [College Park], University of Maryland [College Park], University of Maryland System-University of Maryland System, Bocconi Institute for Data Science and Analytics (BIDSA), Bocconi University [Milan, Italy], Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, M. C. was partially supported by the Swiss National Science Foundation grant 200021_182565. A. D. R. has been supported by the NSF DMS Grant No. 1906451 and the NSF DMS Grant No. 2112311. A. M. acknowledges partial support from GNAMPA-INdAM. A.P. was supported by the Fondation Mathématiques Jacques Hadamard. P.P and A.P. both acknowledge EPFL for hosting them during the semester this paper was prepared., Inria de Paris, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE)

Subjects
BRANCHED TRANSPORT, Mathematical optimization, Irrigation, TRAFFIC PLANS, [MATH.MATH-CA]Mathematics [math]/Classical Analysis and ODEs [math.CA], 01 natural sciences, Stability (probability), symbols.namesake, Mathematics - Analysis of PDEs, Classical Analysis and ODEs (math.CA), FOS: Mathematics, Computer Science::Networking and Internet Architecture, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], Discrete Mathematics and Combinatorics, Limit (mathematics), 0101 mathematics, Mathematics - Optimization and Control, Mathematics, TRANSPORTATION NETWORK, BRANCHED TRANSPORT, IRRIGATION PROBLEM, TRAFFIC PLANS, STABILITY, STABILITY, IRRIGATION PROBLEM, Applied Mathematics, TRANSPORTATION NETWORK, 010102 general mathematics, Eulerian path, Flow network, 010101 applied mathematics, Optimization and Control (math.OC), Mathematics - Classical Analysis and ODEs, symbols, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Analysis, Lagrangian, Analysis of PDEs (math.AP)
Abstract

We prove the stability of optimal traffic plans in branched transport. In particular, we show that any limit of optimal traffic plans is optimal as well. This result goes beyond the Eulerian stability proved in [7], extending it to the Lagrangian framework.

Published
2022

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

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

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

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

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

9. Bounding Fixed Points of Set-Based Bellman Operator and Nash Equilibria of Stochastic Games

Author

Li, Sarah H. Q., Assalé, Adjé, Garoche, Pierre-Loïc, Açıkmeşe, Behçet, University of Washington [Seattle], Université de Perpignan Via Domitia (UPVD), Ecole Nationale de l'Aviation Civile (ENAC), This work has been partially supported by Feanicses project, France ANR-17-CE25-0018 and NSF, USA CNS-1736582. The material in this paper was presented at the 21st IFAC World Congress (IFAC 2020), July 12–17, 2020, Berlin, Germany., and ANR-17-CE25-0018,FEANICSES,Analyses formelles et exhaustives de systèmes embarqués de contrôle à base de calculs intensifs(2017)

Subjects
FOS: Computer and information sciences, 0209 industrial biotechnology, Mathematical optimization, Computer Science::Computer Science and Game Theory, Computer science, MathematicsofComputing_NUMERICALANALYSIS, 02 engineering and technology, Interval (mathematics), Fixed point, learning in games, decision making and autonomy, symbols.namesake, 020901 industrial engineering & automation, Operator (computer programming), [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Computer Science - Computer Science and Game Theory, Bellman equation, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-SY]Computer Science [cs]/Systems and Control [cs.SY], FOS: Mathematics, stochastic control, multi-agent systems, Electrical and Electronic Engineering, Mathematics - Optimization and Control, Stochastic control, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], 020208 electrical & electronic engineering, Stochastic game, Control and Systems Engineering, Nash equilibrium, learning theory, Optimization and Control (math.OC), symbols, Markov decision process, Computer Science and Game Theory (cs.GT)
Abstract

Motivated by uncertain parameters encountered in Markov decision processes (MDPs) and stochastic games, we study the effect of parameter uncertainty on Bellman operator-based algorithms under a set-based framework. Specifically, we first consider a family of MDPs where the cost parameters are in a given compact set; we then define a Bellman operator acting on a set of value functions to produce a new set of value functions as the output under all possible variations in the cost parameter. We prove the existence of a fixed point of this set-based Bellman operator by showing that it is contractive on a complete metric space, and explore its relationship with the corresponding family of MDPs and stochastic games. Additionally, we show that given interval set bounded cost parameters, we can form exact bounds on the set of optimal value functions. Finally, we utilize our results to bound the value function trajectory of a player in a stochastic game., 15 pages, 4 figures

Published
2020

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

11. Maximum Distortion Attacks in Electricity Grids

Author

H. Vincent Poor, Oliver Kosut, Inaki Esnaola, Samir M. Perlaza, University of Sheffield [Sheffield], Software and Cognitive radio for telecommunications (SOCRATE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CITI Centre of Innovation in Telecommunications and Integration of services (CITI), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA), Princeton University, Arizona State University [Tempe] (ASU), This work was supported in part by the European Commission under Individual Fellowship Marie Skłodowska-CurieAction (CYBERNETS) under Grant 659316, and in part by the U.S. National Science Foundation under Grant CMMI-1435778 and Grant ECCS-1549881. Paper no. TSG-01065-2015., European Project: 659316,H2020 Pilier Excellent Science,H2020-MSCA-IF-2014,CYBERNETS(2015), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), and Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon

Subjects
game theory, State variable, Mathematical optimization, Data-injection attacks, General Computer Science, Exploit, MMSE estimation, 020209 energy, [MATH.MATH-IT]Mathematics [math]/Information Theory [math.IT], 020206 networking & telecommunications, 02 engineering and technology, symbols.namesake, Cardinality, de-centralized attacks, [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, Nash equilibrium, Distortion, 0202 electrical engineering, electronic engineering, information engineering, symbols, Potential game, Game theory, Gaussian process, Mathematics, Computer Science::Cryptography and Security
Abstract

International audience; Multiple attacker data injection attack construction in electricity grids with minimum-mean-square-error state estimation is studied for centralized and decentralized scenarios. A performance analysis of the trade-off between the maximum distortion that an attack can introduce and the probability of the attack being detected by the network operator is considered. In this setting, optimal centralized attack construction strategies are studied. The decentralized case is examined in a game-theoretic setting. A novel utility function is proposed to model this trade-off and it is shown that the resulting game is a potential game. The existence and cardinality of the corresponding set of Nash Equilibria (NEs) of the game is analyzed. Interestingly, the attackers can exploit the correlation among the state variables to facilitate the attack construction. It is shown that attackers can agree on a data injection vector construction that achieves the best trade-off between distortion and detection probability by sharing only a limited number of bits offlline. For the particular case of two attackers, numerical results based on IEEE test systems are presented.

Published
2016

12. Comparisons of Ambiguous Experiments

Author

Ludovic Renou, Fabien Gensbittel, Tristan Tomala, Haldemann, Antoine, Groupe de recherche en économie mathématique et quantitative (GREMAQ), Centre National de la Recherche Scientifique (CNRS)-École des hautes études en sciences sociales (EHESS)-Institut National de la Recherche Agronomique (INRA)-Université Toulouse 1 Capitole (UT1), 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), HEC Research Paper Series, and Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées

Subjects
Mathematical optimization, media_common.quotation_subject, 05 social sciences, Ambiguity, experiments, Decision maker, Minimax, value of information, Value of information, maximin, Set (abstract data type), multiple priors, Joint probability distribution, 0502 economics and business, JEL: C - Mathematical and Quantitative Methods/C.C7 - Game Theory and Bargaining Theory/C.C7.C72 - Noncooperative Games, [SHS.GESTION]Humanities and Social Sciences/Business administration, Point (geometry), rectangularity, 050207 economics, [SHS.GESTION] Humanities and Social Sciences/Business administration, 050205 econometrics, media_common, Mathematics
Abstract

An ambiguous statistical experiment is a set of joint probability distributions over states and signals. This note compares ambiguous experiments from the point of view of an ambiguity averse decision maker and extends the Blackwell (1951, 1953) ordering to this setting.

Published
2015