Author: "CEDRIC. Optimisation Combinatoire (CEDRIC - OC)" - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"CEDRIC. Optimisation Combinatoire (CEDRIC - OC)"' showing total 182 results

Start Over Author "CEDRIC. Optimisation Combinatoire (CEDRIC - OC)"

182 results on '"CEDRIC. Optimisation Combinatoire (CEDRIC - OC)"'

1. Managing a multi battery energy storage system of a telecommunications company in order to reduce the total energy cost

Author: Silva, Isaias Faria, Bentz, Cédric, Bouhtou, Mustapha, Chardy, Matthieu, Kedad-Sidhoum, Safia, Conservatoire National des Arts et Métiers [CNAM] (CNAM), Orange Labs [Chatillon], Orange Labs, Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), HESAM Université (HESAM), HESAM Université (HESAM)-HESAM Université (HESAM), FARIA, Isaias, CEDRIC. Optimisation Combinatoire (CEDRIC - OC), HESAM Université (HESAM)-HESAM Université (HESAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), Orange Labs [Issy les Moulineaux], France Télécom, and Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)
Subjects: [SHS.INFO]Humanities and Social Sciences/Library and information sciences, heuristic, mixed-integer program, Multi battery energy storage system, demand-response mechanism, optimization, 7. Clean energy, [SHS.INFO] Humanities and Social Sciences/Library and information sciences
Abstract: International audience; The use of batteries as a backup in case of power outages is a common practice adopted by telecommunications companies that need to keep their services always active. Besides, those batteries can also be used for other purposes such as participating in the energy market in order to reduce the electricity bill, as long as the safety usage rules are respected. In this context, batteries can be used when the energy costs more and recharged when the energy costs less, which is known as the demand-response mechanism. Our focus in this work is to optimize the use of batteries installed for backup to participate in the demand-response mechanism, in order to reduce the total energy cost for the company. We formally state the related optimization problem and propose two solving approaches to address it: a mixed-integer program and a heuristic to solve large instances. Simulations based on real data of a French telecommunications operator prove the relevance of using batteries to reduce the energy cost for the company by participating in the demandresponse mechanism. The proposed heuristic proves to be economically relevant and computationally efficient, being a good alternative to a mixed-integer program for large-scale problems.
Published: 2022
Full Text: View/download PDF

2. Compact MILP formulations for the $p$-center problem

Author: Sourour Elloumi, Zacharie Alès, Unité de Mathématiques Appliquées ( UMA ), École Nationale Supérieure de Techniques Avancées ( Univ. Paris-Saclay, ENSTA ParisTech ), Centre d'Etude et De Recherche en Informatique du Cnam ( CEDRIC ), Conservatoire National des Arts et Métiers [CNAM] ( CNAM ), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), Optimisation et commande (OC), Unité de Mathématiques Appliquées (UMA), École Nationale Supérieure de Techniques Avancées (ENSTA Paris)-École Nationale Supérieure de Techniques Avancées (ENSTA Paris), Jon Lee, Giovanni Rinaldi, A. Ridha Mahjoub, Ales, Zacharie, and École Nationale Supérieure de Techniques Avancées (ENSTA Paris)
Subjects: Discrete mathematics, 021103 operations research, p-center, equivalent formulations, 0211 other engineering and technologies, discrete location, 02 engineering and technology, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Optimization and Control (math.OC), [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], 0202 electrical engineering, electronic engineering, information engineering, FOS: Mathematics, 020201 artificial intelligence & image processing, Center (algebra and category theory), Cover (algebra), Integer programming, integer programming, Mathematics - Optimization and Control, ComputingMilieux_MISCELLANEOUS, Mathematics, Integer (computer science), [ INFO.INFO-RO ] Computer Science [cs]/Operations Research [cs.RO]
Abstract: The p-center problem consists in selecting p centers among M to cover N clients, such that the maximal distance between a client and its closest selected center is minimized. For this problem we propose two new and compact integer formulations. Our first formulation is an improvement of a previous formulation. It significantly decreases the number of constraints while preserving the optimal value of the linear relaxation. Our second formulation contains less variables and constraints but it has a weaker linear relaxation bound. We besides introduce an algorithm which enables us to compute strong bounds and significantly reduce the size of our formulations. Finally, the efficiency of the algorithm and the proposed formulations are compared in terms of quality of the linear relaxation and computation time over instances from OR-Library., Lecture Notes in Computer Science 2018
Published: 2023
Full Text: View/download PDF

3. A Stochastic Dual Dynamic Integer Programming for the Uncapacitated Lot-Sizing Problem with Uncertain Demand and Costs

Author: Quezada, Franco, Gicquel, Céline, Kedad-Sidhoum, Safia, Recherche Opérationnelle (RO), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Recherche en Informatique (LRI), CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), and Gicquel, Céline
Subjects: [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract: International audience; We study the uncapacitated lot-sizing problem with uncertain demand and costs. We consider a multi-stage decision process and rely on a scenario tree to represent the uncertainty. We propose to solve this stochastic combinatorial optimization problem thanks to a new extension of the stochastic dual dynamic integer programming algorithm. Our results show that this approach can provide good quality solutions in a reasonable time for large-size instances.
Published: 2021
Full Text: View/download PDF

4. A partial decomposition approach for solving the stochastic uncapacitated lot-sizing problem

Author: Quezada, Franco, Gicquel, Céline, Kedad-Sidhoum, Safia, Industrial Engineering Department (DIIND-USACH), Universidad de Chile = University of Chile [Santiago] (UCHILE), Réseaux & Optimisation Combinatoire et Stochastique (ROCS), Laboratoire Interdisciplinaire des Sciences du Numérique (LISN), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Science des Données (SDD), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), and HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)
Subjects: [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract: International audience
Published: 2022

5. A partial decomposition approach to solve the stochastic uncapacitated lot-sizing problem

Author: Quezada, Franco, Gicquel, Céline, Kedad-Sidhoum, Safia, Industrial Engineering Department (DIIND-USACH), Universidad de Chile = University of Chile [Santiago] (UCHILE), Réseaux & Optimisation Combinatoire et Stochastique (ROCS), Laboratoire Interdisciplinaire des Sciences du Numérique (LISN), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Science des Données (SDD), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), and HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)
Subjects: [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract: International audience
Published: 2022

6. Mixing convex-optimization bounds for maximum-entropy sampling

Author: Zhongzhu Chen, Amélie Lambert, Jon Lee, Marcia Fampa, University of Michigan [Ann Arbor], University of Michigan System, Universidade Federal do Rio de Janeiro (UFRJ), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), and Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)
Subjects: 90C27, General Mathematics, 0211 other engineering and technologies, 02 engineering and technology, FOS: Mathematics, 90C51, 0202 electrical engineering, electronic engineering, information engineering, Applied mathematics, [MATH]Mathematics [math], Mathematics - Optimization and Control, Spatial analysis, Mixing (physics), Mathematics, maximum-entropy sampling, 021103 operations research, Covariance matrix, Principle of maximum entropy, Numerical analysis, Sampling (statistics), convex optimization Mathematics Subject Classification (2000) 90C25, Exact solutions in general relativity, Optimization and Control (math.OC), Convex optimization, 62K99, 020201 artificial intelligence & image processing, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], 90C25, 90C27, 90C51, 62K99, 62H11, 62H11, Software
Abstract: International audience; The maximum-entropy sampling problem is a fundamental and challenging combinatorial-optimization problem, with application in spatial statistics. It asks to find a maximum-determinant order-$s$ principal submatrix of an order-$n$ covariance matrix. Exact solution methods for this NP-hard problem are based on a branch-and-bound framework. Many of the known upper bounds for the optimal value are based on convex optimization. We present a methodology for "mixing" these bounds to achieve better bounds.
Published: 2021
Full Text: View/download PDF

7. A stochastic dual dynamic integer programming based approach for remanufacturing planning under uncertainty

Author: Franco Quezada, Céline Gicquel, Safia Kedad-Sidhoum, Universidad de Chile = University of Chile [Santiago] (UCHILE), Réseaux & Optimisation Combinatoire et Stochastique (ROCS), Laboratoire Interdisciplinaire des Sciences du Numérique (LISN), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Science des Données (SDD), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM), and This research was partially supported by Dicyt project 062217QV, Vicerrectoría de Investigación, Desarrollo e Innovación, Universidad de Santiago de Chile.
Subjects: Multi-stage stochastic integer programming, Strategy and Management, Lot-sizing, [INFO]Computer Science [cs], Production planning, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Management Science and Operations Research, Stochastic dual dynamic programming, Remanufacturing, Industrial and Manufacturing Engineering
Abstract: International audience; We seek to optimize the production planning of a three-echelon remanufacturing system under uncertain input data. We consider a multi-stage stochastic integer programming approach and use scenario trees to represent the uncertain information structure. We introduce a new dynamic programming formulation that relies on a partial nested decomposition of the scenario tree. We then propose a new approximate stochastic dual dynamic integer programming algorithm based on this partial decomposition. Our numerical results show that the proposed solution approach is able to provide near-optimal solutions for large-size instances with a reasonable computational effort.
Published: 2022
Full Text: View/download PDF

8. An efficient Benders decomposition for the p-median problem

Author: Cristian Duran-Mateluna, Zacharie Alès, Sourour Elloumi, Sciencesconf.org, CCSD, Optimisation et commande (OC), Unité de Mathématiques Appliquées (UMA), École Nationale Supérieure de Techniques Avancées (ENSTA Paris)-École Nationale Supérieure de Techniques Avancées (ENSTA Paris), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), Laboratory for the Development of Sustainable Production Systems (LDSPS), Department of Industrial Engineering, University of Santiago of Chile-University of Santiago of Chile, and Universidad de Santiago de Chile [Santiago] (USACH)
Subjects: median problem, [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], polynomial separation algorithm, Benders decomposition, discrete location, MILP formulation, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Optimization and Control (math.OC), p-median problem, FOS: Mathematics, Computer Science::Symbolic Computation, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Computer Science::Data Structures and Algorithms, Mathematics - Optimization and Control
Abstract: The p-median problem is a classic discrete location problem with several applications. It aims to open p sites while minimizing the sum of the distances of each client to its nearest open site. We study a Benders decomposition of the most efficient formulation in the literature. We prove that the Benders cuts can be separated by a polynomial time algorithm. The Benders decomposition also leads to a new compact formulation for the p-median problem. We implement a branch-and-Benders-cut approach that outperforms state-of-the-art methods on benchmark instances by an order of magnitude.
Published: 2022

9. Combining polyhedral approaches and stochastic dual dynamic integer programming for solving the uncapacitated lot-sizing problem under uncertainty

Author: Franco Quezada, Céline Gicquel, Safia Kedad-Sidhoum, Universidad de Santiago de Chile [Santiago] (USACH), Recherche Opérationnelle (RO), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Réseaux & Optimisation Combinatoire et Stochastique (ROCS), Laboratoire Interdisciplinaire des Sciences du Numérique (LISN), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Science des Données (SDD), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM), Laboratoire de Recherche en Informatique (LRI), CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), and Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)
Subjects: 0209 industrial biotechnology, 021103 operations research, 0211 other engineering and technologies, General Engineering, Stochastic dual dynamic integer programming, 02 engineering and technology, Stochastic lot-sizing, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Multi-stage stochastic programming, Valid inequalities, Node aggregation, 020901 industrial engineering & automation, [INFO]Computer Science [cs], Partial decomposition
Abstract: We study the uncapacitated lot-sizing problem with uncertain demand and costs. The problem is modeled as a multistage stochastic mixed-integer linear program in which the evolution of the uncertain parameters is represented by a scenario tree. To solve this problem, we propose a new extension of the stochastic dual dynamic integer programming algorithm (SDDiP). This extension aims at being more computationally efficient in the management of the expected cost-to-go functions involved in the model, in particular by reducing their number and by exploiting the current knowledge on the polyhedral structure of the stochastic uncapacitated lot-sizing problem. The algorithm is based on a partial decomposition of the problem into a set of stochastic subproblems, each one involving a subset of nodes forming a subtree of the initial scenario tree. We then introduce a cutting plane–generation procedure that iteratively strengthens the linear relaxation of these subproblems and enables the generation of an additional strengthened Benders’ cut, which improves the convergence of the method. We carry out extensive computational experiments on randomly generated large-size instances. Our numerical results show that the proposed algorithm significantly outperforms the SDDiP algorithm at providing good-quality solutions within the computation time limit. Summary of Contribution: This paper investigates a combinatorial optimization problem called the uncapacitated lot-sizing problem. This problem has been widely studied in the operations research literature as it appears as a core subproblem in many industrial production planning problems. We consider a stochastic extension in which the input parameters are subject to uncertainty and model the resulting stochastic optimization problem as a multistage stochastic integer program. To solve this stochastic problem, we propose a novel extension of the recently published stochastic dual dynamic integer programming (SDDiP) algorithm. The proposed extension relies on two main ideas: the use of a partial decomposition of the scenario tree and the exploitation of existing knowledge on the polyhedral structure of the stochastic uncapacitated lot-sizing problem. We provide the results of extensive computational experiments carried out on large-size randomly generated instances. These results show that the proposed extended algorithm significantly outperforms the SDDiP at providing good-quality solutions for the stochastic uncapacitated lot-sizing problem. Although the paper focuses on a basic lot-sizing problem, the proposed algorithmic framework may be useful to solve more complex practical production planning problems.
Published: 2022
Full Text: View/download PDF

10. A solution robustness approach applied to network optimization problems

Author: Alès, Zacharie, Elloumi, Sourour, CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), Optimisation et commande (OC), Unité de Mathématiques Appliquées (UMA), and École Nationale Supérieure de Techniques Avancées (ENSTA Paris)-École Nationale Supérieure de Techniques Avancées (ENSTA Paris)
Subjects: Optimization and Control (math.OC), [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Mathematics - Optimization and Control
Abstract: Solution robustness focuses on structural similarities between the nominal solution and the scenario solutions. Most other robust optimization approaches focus on the quality robustness and only evaluate the relevance of their solutions through the objective function value. However, it can be more important to optimize the solution robustness and, once the uncertainty is revealed, find an alternative scenario solution $x^s$ which is as similar as possible to the nominal solution $x^{nom}$. This for example occurs when the robust solution is implemented on a regular basis or when the uncertainty is revealed late. We call this distance between $x^{nom}$ and $x^s$ the solution cost. We consider the proactive problem which minimizes the average solution cost over a discrete set of scenarios while ensuring the optimality of the nominal objective of $x^{nom}$. We show for two different solution distances $d_{val}$ and $d_{struct}$ that the proactive problem is NP-hard for both the integer min-cost flow problem with uncertain arc demands and for the integer max-flow problem with uncertain arc capacities. For these two problems, we prove that once the uncertainty is revealed, even identifying a reactive solution $x^r$ with a minimal distance to a given solution $x^{nom}$ is NP-hard for $d_{struct}$, and that it is polynomial for $d_{val}$. We highlight the benefits of solution robustness in a case study on a railroad planning problem. First, we compare our proactive approach to the anchored and the $k$-distance approaches. Then, we show the efficiency of the proactive solution over reactive solutions. Finally, we illustrate the solution cost reduction when relaxing the optimality constraint on the nominal objective of the proactive solution $x^{nom}$.
Published: 2021

11. New valid inequalities for a multi-echelon multi-item lot-sizing problem with returns and lost sales

Author: Céline Gicquel, Franco Quezada, Safia Kedad-Sidhoum, Recherche Opérationnelle (RO), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Réseaux & Optimisation Combinatoire et Stochastique (ROCS), Laboratoire Interdisciplinaire des Sciences du Numérique (LISN), CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Science des Données (SDD), CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Science des Données (SDD), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Conservatoire National des Arts et Métiers [CNAM] (CNAM), HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), and HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)
Subjects: Structure (mathematical logic), Mathematical optimization, 021103 operations research, Inequality, Linear programming, Mixed-integer linear programming, Computer science, media_common.quotation_subject, 0211 other engineering and technologies, 02 engineering and technology, Production planning, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Solver, Sizing, Valid inequalities, 03 medical and health sciences, 0302 clinical medicine, Work (electrical), 030221 ophthalmology & optometry, Lot-sizing, Remanufacturing, media_common
Abstract: International audience; This work studies a multi-echelon multi-item lot-sizing problem with remanufacturing and lost sales. The problem is formulated as a mixed-integer linear program. A new family of valid inequalities taking advantage of the problem structure is introduced and used in a customized branch-and-cut algorithm. The provided numerical results show that the proposed algorithm outperforms both the generic branch-andcut algorithm embedded in a standard-alone mathematical solver and a previously published customized branch-and-cut algorithm.
Published: 2021
Full Text: View/download PDF

12. Lower and upper bounds for scheduling energy-consuming tasks with storage resources and piecewise linear costs

Author: Sandra Ulrich Ngueveu, Christian Artigues, Nabil Absi, Safia Kedad-Sidhoum, Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Département Sciences de la Fabrication et Logistique (SFL-ENSMSE), École des Mines de Saint-Étienne (Mines Saint-Étienne MSE), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-CMP-GC, Conservatoire National des Arts et Métiers [CNAM] (CNAM), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM), Université de Toulouse (UT), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), and HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], 0209 industrial biotechnology, Control and Optimization, column generation, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Computer Networks and Communications, 020209 energy, piecewise linear costs, storage resources, lot sizing, 02 engineering and technology, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Management Science and Operations Research, mixed integer programming, 020901 industrial engineering & automation, Energy-aware scheduling, Artificial Intelligence, matheuristic, 0202 electrical engineering, electronic engineering, information engineering, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Software, Information Systems
Abstract: This paper considers the problem of scheduling a set of time-and energy-constrained preemptive tasks on a discrete time horizon. At each time period, the total energy required by the tasks that are in process can be provided by two energy sources: a reversible one and a non-reversible one. The non-reversible energy source can provide an unlimited amount of energy for a given period but at the expense of a time-dependent piecewise linear cost. The reversible energy source is a storage resource. The goal is to schedule each task preemptively inside its time window and to dispatch the required energy to the sources at each time period, while satisfying the reversible source capacity constraints and minimizing the total cost. We propose a mixed integer linear program of pseudo-polynomial size to solve this NP-hard problem. Acknowledging the limits of this model for problem instances of modest size, we propose an iterative decomposition matheuristic to compute an upper bound. The method relies on an efficient branch-and-price method or on a local search procedure to solve the scheduling problem without storage. The energy source allocation problem for a fixed schedule can in turn be solved efficiently by dynamic programming as a particular lot-sizing problem. We also propose a lower bound obtained by solving the linear programming relaxation of a new extended formulation by column generation. Experimental results show the quality of the bounds compared to the ones obtained using mixed integer linear program. Keywords Energy-aware scheduling piecewise linear costs storage resources matheuristic column generation lot sizing mixed integer programming MSC 90B05 MSC 90B30 MSC 90C39 MSC 90C59
Published: 2021
Full Text: View/download PDF

13. Minimal graphs for hamiltonian extension

Author: Christophe Picouleau, CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), and Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)
Subjects: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], hamiltonian path, 2-factor, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Hamiltonian path, Graph, Combinatorics, symbols.namesake, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, symbols, hamiltonian cycle, Mathematics - Combinatorics, [INFO]Computer Science [cs], Combinatorics (math.CO), Mathematics
Abstract: International audience; For every $n\ge 3$ we determine the minimum number of edges of graph with $n$ vertices such that for any non edge $xy$ there exits a hamiltonian cycle containing $xy$.
Published: 2020
Full Text: View/download PDF

14. Projective Cutting-Planes

Author: Daniel Cosmin Porumbel, CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), and Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)
Subjects: 021103 operations research, 0211 other engineering and technologies, Polytope, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], 010103 numerical & computational mathematics, 02 engineering and technology, Stride length, 01 natural sciences, Theoretical Computer Science, Combinatorics, Projection (mathematics), Column generation, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Software, Interior point method, Mathematics
Abstract: Given a polytope $\mathcal P$, an interior point ${x}\in\mathcal P$, and a direction ${d}\in\mathbb{R}^n$, the projection of ${x}$ along ${d}$ asks to find the maximum step length $t^*$ such that $...
Published: 2020
Full Text: View/download PDF

15. New valid inequalities for a multi-item multi-echelon lot-sizing problem with returns and lost sales

Author: Quezada, Franco, Gicquel, Céline, Kedad-Sidhoum, Safia, Recherche Opérationnelle (RO), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Réseaux & Optimisation Combinatoire et Stochastique (ROCS), Laboratoire Interdisciplinaire des Sciences du Numérique (LISN), CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Science des Données (SDD), CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Science des Données (SDD), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM), and Gicquel, Céline
Subjects: [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 2021

16. Capacitated lot-sizing problem with inventory constraints within periods

Author: Stéphane Dauzère-Pérès, Issam Mazhoud, Mehdi Charles, Safia Kedad-Sidhoum, Département Sciences de la Fabrication et Logistique (SFL-ENSMSE), École des Mines de Saint-Étienne (Mines Saint-Étienne MSE), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-CMP-GC, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), Centre Microélectronique de Provence - Site Georges Charpak (CMP-GC) (CMP-ENSMSE), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM), and DecisionBrain S.A.S.
Subjects: Lost sales, Operations research, business.industry, Computer science, Production (economics), [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], business, Computer-aided software engineering, Automation, Sizing
Abstract: This paper first motivates the need to consider the dynamic evolution of the inventory within periods when solving the capacitated lot-sizing problem with lost sales, setup times and inventory bounds. Two models are introduced to characterize and bound the minimum and maximum inventory levels within each period under specific assumptions on the production and the demand shapes. Computational experiments are carried out to compare these models and emphasize the need for better inventory modeling in lot-sizing problems.
Published: 2021
Full Text: View/download PDF

17. Multi-objective optimization for VM placement in homogeneous and heterogeneous cloud service provider data centers

Author: Taoufik Aguili, Zacharie Ales, Rym Regaieg, Mohamed Koubaa, National Engineering School of Tunis = Ecole Nationale d'Ingénieurs de Tunis [University of Tunis El Manar] (ENIT), University of Tunis El Manar, CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), Optimisation et commande (OC), Unité de Mathématiques Appliquées (UMA), and École Nationale Supérieure de Techniques Avancées (ENSTA Paris)-École Nationale Supérieure de Techniques Avancées (ENSTA Paris)
Subjects: Mathematical optimization, Linear programming, Computer science, 02 engineering and technology, computer.software_genre, Multi-objective optimization, Theoretical Computer Science, Reduction (complexity), Set (abstract data type), Resource (project management), [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], 0202 electrical engineering, electronic engineering, information engineering, ComputingMilieux_MISCELLANEOUS, Numerical Analysis, business.industry, 020206 networking & telecommunications, Computer Science Applications, Computational Mathematics, Computational Theory and Mathematics, Virtual machine, 020201 artificial intelligence & image processing, Data center, business, computer, Software, Integer (computer science)
Abstract: We address the virtual machine placement problem that arises in Cloud Service Providers data centers. We purpose, a Multi-Objective Integer Linear Programming model which aims at optimizing simultaneously the number of hosted virtual machines, the resource wastage and the number of active physical machines (PM) in order to minimize power consumption. This new combination of objectives enables to maximize the client satisfaction rate with minimizing the data center (DC) operational costs. We modelize this problem with a multi-objective integer linear program and solve it through two different methods. The first method computes a unique solution for a given preference order over the objectives whereas the second computes a set of non-dominated solutions. Both methods are compared through extensive simulation scenarios. We consider two DC architectures: homogeneous DCs (i.e., a DC with PMs having the same amount of resources) and heterogeneous DCs. We study the impact of each DC configuration on the performances of the solutions. We show that the second method leads to solutions with a reduction of up to 30% over the number of used PMs and that the heterogeneous DCs outperforms the homogeneous one across all objectives.
Published: 2021
Full Text: View/download PDF

18. A tight compact quadratically constrained convex relaxation of the Optimal Power Flow problem

Author: Lambert, Amélie, CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), and Lambert, Amélie
Subjects: [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], [MATH] Mathematics [math], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [MATH]Mathematics [math], Mathematics - Optimization and Control
Abstract: preprint; In this paper, we consider the optimal power flow (OPF) problem which consists in determining the power production at each bus of an electric network by minimizing the production cost. Our contribution is an exact solution algorithm for the OPF problem. It consits in a spatial branch-and-bound algorithm based on a compact quadratically constrained convex relaxation. This compact relaxation is computed by solving the rank relaxation once at the beginning of the algorithm. The key point of this approach is that the lower bound at the root node of the branch-and-bound tree is equal to the rank relaxation value, but is obtained by solving a quadratic convex problem which is much faster than solving a SDP. To construct this compact relaxation, we add only O(n) variables that model the squares of the initial variables, where n is the number of buses in the power system. The relations between the initial and auxiliary variables are therefore non-convex. By relaxing them in our relaxation, we have only O(n) equalities to force by the branch-and-bound algorithm to prove global optimality. Our first experiments show that our new algorithm Compact OPF (COPF) performs better than the methods of the literature we compare it with
Published: 2021

19. Characterization of the degree sequences of (quasi) regular uniform hypergraphs

Author: Frosini, A., Picouleau, Christophe, Rinaldi, S., Università degli Studi di Firenze = University of Florence [Firenze] (UNIFI), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), and Università degli Studi di Siena = University of Siena (UNISI)
Subjects: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Mathematics - Combinatorics, [INFO]Computer Science [cs], Combinatorics (math.CO), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract: International audience; In hypergraph theory, determining a characterization of the degree sequence $d=(d_1,d_2,\ldots,d_n)$ where $d_1\ge d_2\ge\ldots,d_n$ are positive integers, of an $h$-uniform simple hypergraph $\cal H$, and deciding the complexity status of the reconstruction of $\cal H$ from $d$, are two challenging open problems. They can be formulated in the context of discrete tomography: asks whether there is a matrix $A$ with positive projection vectors $H=(h,h,\ldots,h)$ and $V=(d_1,d_2,\ldots,d_n)$ with distinct rows. In this paper we consider the two subcases where the vector $V$ is an homogeneous vector, and where $V$ is almost homogeneous, i.e., $d_1-d_n=1$. We give a simple characterization for these two subcases, and we show how to solve the related reconstruction problems in polynomial time. To reach our goal, we use the concepts of Lyndon words and necklaces of fixed density, and we apply some already known algorithms for their efficient generation.
Published: 2021
Full Text: View/download PDF

20. Dominance inequalities for scheduling around an unrestrictive common due date

Author: Anne-Elisabeth Falq, Safia Kedad-Sidhoum, Pierre Fouilhoux, Recherche Opérationnelle (RO), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), and Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)
Subjects: FOS: Computer and information sciences, Mathematical optimization, Information Systems and Management, General Computer Science, Discrete Mathematics (cs.DM), Computer science, Tardiness, 0211 other engineering and technologies, Scheduling (production processes), Context (language use), 02 engineering and technology, Management Science and Operations Research, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Industrial and Manufacturing Engineering, 0502 economics and business, FOS: Mathematics, [INFO]Computer Science [cs], scheduling, Integer programming, integer programming, Mathematics - Optimization and Control, 050210 logistics & transportation, 021103 operations research, Job shop scheduling, Heuristic, 05 social sciences, dominance properties, common due date, Solver, Linear inequality, Optimization and Control (math.OC), Modeling and Simulation, Computer Science - Discrete Mathematics
Abstract: The problem considered in this work consists in scheduling a set of tasks on a single machine, around an unrestrictive common due date to minimize the weighted sum of earliness and tardiness. This problem can be formulated as a compact mixed integer program (MIP). In this article, we focus on neighborhood-based dominance properties, where the neighborhood is associated to insert and swap operations. We derive from these properties a local search procedure providing a very good heuristic solution. The main contribution of this work stands in an exact solving context: we derive constraints eliminating the non locally optimal solutions with respect to the insert and swap operations. We propose linear inequalities translating these constraints to strengthen the MIP compact formulation. These inequalities, called dominance inequalities, are different from standard reinforcement inequalities. We provide a numerical analysis which shows that adding these inequalities significantly reduces the computation time required for solving the scheduling problem using a standard solver., 30 pages, 7 figures and 4 tables
Published: 2021

21. Mixed integer formulations using natural variables for single machine scheduling around a common due date

Author: Pierre Fouilhoux, Anne-Elisabeth Falq, Safia Kedad-Sidhoum, Recherche Opérationnelle (RO), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), and Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)
Subjects: FOS: Computer and information sciences, Mathematical optimization, Single-machine scheduling, Discrete Mathematics (cs.DM), Applied Mathematics, Tardiness, 0211 other engineering and technologies, 021107 urban & regional planning, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Scheduling (computing), Due date, 010201 computation theory & mathematics, Computer Science - Data Structures and Algorithms, Discrete Mathematics and Combinatorics, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs], Extreme point, Integer programming, Computer Science - Discrete Mathematics, Separation problem, Mathematics
Abstract: While almost all existing works which optimally solve just-in-time scheduling problems propose dedicated algorithmic approaches, we propose in this work mixed integer formulations. We consider a single machine scheduling problem that aims at minimizing the weighted sum of earliness tardiness penalties around a common due-date. Using natural variables, we provide one compact formulation for the unrestrictive case and, for the general case, a non-compact formulation based on non-overlapping inequalities. We show that the separation problem related to the latter formulation is solved polynomially. In this formulation, solutions are only encoded by extreme points. We establish a theoretical framework to show the validity of such a formulation using non-overlapping inequalities, which could be used for other scheduling problems. A Branch-and-Cut algorithm together with an experimental analysis are proposed to assess the practical relevance of this mixed integer programming based methods., Comment: 32 pages, 10 figures
Published: 2021
Full Text: View/download PDF

22. Designing Protected Area Networks: A Mathematical Programming Approach

Author: Billionnet, Alain, Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), and Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)
Subjects: Optimization, Mathematical programming, Conservation, Biodiversity, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Environment, [SDE.BE]Environmental Sciences/Biodiversity and Ecology, Protected areas
Abstract: International audience; There is a broad consensus in considering that the loss of biodiversity is accelerating which is due, for example, to the destruction of habitats, overexploitation of wild species and climate change. Many countries have pledged at various international conferences to take swift measures to halt this loss of biodiversity. Among these measures, the creation of protected areas – which also contribute to food and water security, the fight against climate change and people’ health and well-being – plays a decisive role, although it is not sufficient on its own.In this book, we review classic and original problems associated with the optimal design of a network of protected areas, focusing on the modelling and practical solution of these problems. We show how to approach these optimisation problems within a unified framework, that of mathematical programming, a branch of mathematics that focuses on finding good solutions to a problem from a huge number of possible solutions. We describe efficient and often innovative modellings of these problems.Several strategies are also proposed to take into account the inevitable uncertainty concerning the ecological benefits that can be expected from protected areas. These strategies are based on the classical notions of probability and robustness.This book aims to help all those, from students to decision-makers, who are confronted with the establishment of a network of protected areas to identify the most effective solutions, taking into account ecological objectives, various constraints and limited resources.In order to facilitate the reading of this book, most of the problems addressed and the approaches proposed to solve them are illustrated by fully processed examples, and an appendix presents in some detail the basic mathematical concepts related to its content.
Published: 2021
Full Text: View/download PDF

23. The complexity of the bondage problem in planar graphs

Author: Bouquet, Valentin, Bouquet, Valentin, CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), and CEDRIC. Réseaux et Objets Connectés (CEDRIC - ROC)
Subjects: [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], FOS: Computer and information sciences, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Discrete Mathematics (cs.DM), [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], FOS: Mathematics, Mathematics - Combinatorics, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Combinatorics (math.CO), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Computer Science - Discrete Mathematics
Abstract: A set $S\subseteq V(G)$ of a graph $G$ is a dominating set if each vertex has a neighbor in $S$ or belongs to $S$. Let $\gamma(G)$ be the cardinality of a minimum dominating set in $G$. The bondage number $b(G)$ of a graph $G$ is the smallest cardinality of a set of edges $A\subseteq E(G)$, such that $\gamma(G-A)=\gamma(G)+1$. The $d$-Bondage is the problem of deciding, given a graph $G$ and an integer $d\geq 1$, if $b(G)\leq d$. This problem is known to be $\mathsf{NP}$-hard even for bipartite graphs and $d=1$. In this paper, we show that $1$-Bondage is $\mathsf{NP}$-hard, even for the class of $3$-regular planar graphs, the class of subcubic claw-free graphs, and the class of bipartite planar graphs of maximum degree $3$, with girth $k$, for any fixed $k\geq 3$. On the positive side, for any planar graph $G$ of girth at least $8$, we show that we can find, in polynomial time, a set of three edges $A$ such that $\gamma(G-A)>\gamma(G)$. Last, we exposed some classes of graphs for which Dominating Set can be solved in polynomial time, and where $d$-Bondage can also be solved in polynomial time, for any fixed $d\geq 1$., Comment: 24 pages, 8 figures
Published: 2021
Full Text: View/download PDF

24. A Partial Nested Decomposition Approach for Remanufacturing Planning Under Uncertainty

Author: Safia Kedad-Sidhoum, Céline Gicquel, Franco Quezada, Recherche Opérationnelle (RO), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Réseaux & Optimisation Combinatoire et Stochastique (ROCS), Laboratoire Interdisciplinaire des Sciences du Numérique (LISN), CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Science des Données (SDD), CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Science des Données (SDD), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM), Alexandre Dolgui, Alain Bernard, David Lemoine, Gregor von Cieminski, David Romero, TC5, and WG 5,7
Subjects: Mathematical optimization, 021103 operations research, Computer science, Information structure, 0211 other engineering and technologies, Stochastic lot-sizing, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], 010103 numerical & computational mathematics, 02 engineering and technology, Extension (predicate logic), Stochastic dual dynamic programming, Multistage stochastic integer programming, 01 natural sciences, Dual (category theory), Dynamic programming, Production planning, Decomposition (computer science), [INFO]Computer Science [cs], 0101 mathematics, Remanufacturing, Integer programming
Abstract: International audience; We seek to optimize the production planning of a three-echelon remanufacturing system under uncertain input data. We consider a multi-stage stochastic integer programming approach and use scenario trees to represent the uncertain information structure. We introduce a new dynamic programming formulation that relies on a partial nested decomposition of the scenario tree. We then propose a new extension of the recently published stochastic dual dynamic integer programming algorithm based on this partial decomposition. Our numerical results show that the proposed solution approach is able to provide near-optimal solutions for large-size instances with a reasonable computational effort.
Published: 2021
Full Text: View/download PDF

25. Wind farm cable layout optimization with constraints of load flow and robustness

Author: Bentz, Cédric, Costa, Marie-Christine, Poirion, Pierre-Louis, Ridremont, Thomas, Zakour, Camille, CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), Optimisation et commande (OC), Unité de Mathématiques Appliquées (UMA), École Nationale Supérieure de Techniques Avancées (ENSTA Paris)-École Nationale Supérieure de Techniques Avancées (ENSTA Paris), RIKEN - Institute of Physical and Chemical Research [Japon] (RIKEN), Artelys France, EDF (EDF), PGMO, and Costa, Marie-Christine
Subjects: [SDE] Environmental Sciences, [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], Bilevel Optimization, [SDE]Environmental Sciences, Operational Research, Robust Optimization, Renewable Energy, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract: International audience; We consider an offshore wind farm defined by the location of the wind turbines and the amount of energy supplied per turbine, as well as the location of the central station responsible for redistributing the collected energy to users on the power grid. Knowing the power injected at each node, the capacities, susceptance and costs of the cables that can be used, the goal is to determine the least expensive cabling to route the energy supplied by the wind turbines to the central station. This cabling must respect the capacity constraints on the cables as well as the electrical constraints of Load Flow defined at each node of the network. In a second step, we look for a cabling that is also robust in case of failure of a cable, the notion of robustness being seen here as the protection again the worst case of failure. This work was carried out in collaboration with EDF Energies renouvelables. We give a mathematical model of the problem taking into account all the constraints of capacity, connectivity, load flow, cable types and incompatibility between edges, in the form of a mixed integer quadratic program that can be linearized and solved using a MIP solver. We then propose two mathematical models for the robust problem, formulation inspired by the previous one and a bi-level program where the second level is a max min program. Finally we present the results of our tests which provide solutions for real data up to about 50 nodes, before concluding.
Published: 2020

26. Valid inequalities and global solution algorithm for Quadratically Constrained Quadratic Programs

Author: Lambert, Amélie, CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), and Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)
Subjects: [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [MATH]Mathematics [math], Mathematics - Optimization and Control
Abstract: We consider the exact solution of problem $(QP)$ that consists in minimizing a quadratic function subject to quadratic constraints. Starting from the classical convex relaxation that uses the McCormick's envelopes, we introduce 12 inequalities that are derived from the ranges of the variables of $(QP)$. We prove that these general Triangle inequalities cut feasible solutions of the McCormick's envelopes. We then show how we can compute a convex relaxation $(P^*)$ which optimal value equals to the "Shor's plus RLT plus Triangle" semi-definite relaxation of $(QP)$ that includes the new inequalities. We also propose a heuristic for solving this huge semi-definite program that serves as a separation algorithm. We then solve $(QP)$ to global optimality with a branch-and-bound based on $(P^*)$. Moreover, as the new inequalities involved the lower and upper bounds on the original variables of $(QP)$, their use in a branch-and-bound framework accelerates the whole process. We show on the unitbox instances that our method outperforms the compared solvers., Comment: preprint
Published: 2020

27. The complexity of the Perfect Matching-Cut problem

Author: Bouquet, Valentin, Picouleau, Christophe, Bouquet, Valentin, CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), CEDRIC. Réseaux et Objets Connectés (CEDRIC - ROC), and Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)
Subjects: [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Mathematics::Combinatorics, Computer Science::Discrete Mathematics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], FOS: Mathematics, Mathematics - Combinatorics, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Combinatorics (math.CO), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract: Perfect Matching-Cut is the problem of deciding whether a graph has a perfect matching that is an edge cut. We show that this problem is $NP$-complete for planar graphs with maximum degree four, for planar graphs with girth five, for bipartite five-regular graphs, for graphs of diameter three and for bipartite graphs of diameter four. We show that there exist polynomial time algorithms for the following classes of graphs: claw-free, $P_5$-free, diameter two, bipartite with diameter three, quadrangulated and graphs with bounded tree-width.
Published: 2020

28. Complexity and algorithms for constant diameter augmentation problems

Author: Christophe Picouleau, Eun Jung Kim, Jérôme Monnot, Martin Milanič, Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL), University of Primorska, CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Discrete mathematics, General Computer Science, Computational complexity theory, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Polynomial algorithm, Theoretical Computer Science, 010201 computation theory & mathematics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Mathematics - Combinatorics, Graph (abstract data type), 020201 artificial intelligence & image processing, [INFO]Computer Science [cs], Combinatorics (math.CO), [MATH]Mathematics [math], NP-complete, Constant (mathematics), Distance, Mathematics
Abstract: International audience; We study the following problem: for given integers $d,k$ and graph $G$, can we obtain a graph with diameter $d$ via at most $k$ edge deletions ? We determine the computational complexity of this and related problems for different values of $d$.
Published: 2020
Full Text: View/download PDF

29. The K‐partitioning problem: Formulations and branch‐and‐cut

Author: Zacharie Alès, Arnaud Knippel, CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), Optimisation et commande (OC), Unité de Mathématiques Appliquées (UMA), École Nationale Supérieure de Techniques Avancées (ENSTA Paris)-École Nationale Supérieure de Techniques Avancées (ENSTA Paris), Laboratoire de Mathématiques de l'INSA de Rouen Normandie (LMI), Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), and Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)
Subjects: 050210 logistics & transportation, 021103 operations research, Computer Networks and Communications, 05 social sciences, 0211 other engineering and technologies, Complete graph, Graph partition, Polytope, 02 engineering and technology, Set (abstract data type), Combinatorics, Hardware and Architecture, 0502 economics and business, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Combinatorial optimization, Relaxation (approximation), Branch and cut, Integer programming, Software, ComputingMilieux_MISCELLANEOUS, Information Systems, Mathematics
Abstract: The K-partitioning problem consists in partitioning the nodes of a complete graph G = (V, E) with weights on the edges in exactly K clusters such that the sum of the weights of the edges inside the clusters is minimized. For this problem, we propose two node-cluster formulations adapted from the literature on similar problems as well as two edge-representative formulations. We introduced the first edge-representative formulation in a previous work [4] while the second is obtained by adding an additional set of edge variables. We compare the structure of the polytopes of the two edge-representative formulations and identify a new family of facet-defining inequalities. The quality of the linear relaxation and the resolution times of the four formulations are compared on various data sets. We provide bounds on the relaxation values of the node-cluster formulations which may account for their low performances. Finally, we propose a branch-and-cut strategy, based on the edge-representative formulations, which performs even better.
Published: 2020
Full Text: View/download PDF

30. Distance-guided local search

Author: Daniel Cosmin Porumbel, Jin-Kao Hao, CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), Laboratoire d'Etudes et de Recherche en Informatique d'Angers (LERIA), Université d'Angers (UA), Institut Universitaire de France (IUF), and Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.)
Subjects: 021103 operations research, Control and Optimization, Computer Networks and Communications, business.industry, Computer science, 0211 other engineering and technologies, Process (computing), Structure (category theory), 02 engineering and technology, Management Science and Operations Research, Artificial Intelligence, Path (graph theory), 0202 electrical engineering, electronic engineering, information engineering, Trajectory, 020201 artificial intelligence & image processing, Local search (optimization), Guided Local Search, SPHERES, [INFO]Computer Science [cs], business, Priority queue, Algorithm, Software, ComputingMilieux_MISCELLANEOUS, Information Systems
Abstract: We present several techniques that use distances between candidate solutions to achieve intensification in Local Search (LS) algorithms. An important drawback of classical LS is that after visiting a very high-quality solution the search process can “forget about it” and continue towards very different areas. We propose a method that works on top of a given LS to equip it with a form of memory so as to record the highest-quality visited areas (spheres). More exactly, this new method uses distances between candidate solutions to perform a coarse–grained recording of the LS trajectory, i.e., it records a number of discovered spheres. The (centers of the) spheres are kept sorted in a priority queue in which new centers are continually inserted as in insertion-sort algorithms. After thoroughly investigating a sphere, the proposed method resumes the search from the first best sphere center in the priority queue. The resulting LS trajectory is no longer a continuous path, but a tree-like structure, with closed branches (already investigated spheres) and open branches (as-yet-unexplored spheres). We also explore several other techniques relying on distances, e.g., in Section 2.3, we show how to use distance information to prevent the search from looping indefinitely on large (quasi-)plateaus. Experiments on three problems based on different encodings (partitions, vectors and permutations) confirm the intensification potential of the proposed ideas.
Published: 2020
Full Text: View/download PDF

31. Reinforcement Learning for Variable Selection in a Branch and Bound Algorithm

Author: Marc Etheve, Zacharie Alès, Côme Bissuel, Olivier Juan, Safia Kedad-Sidhoum, EDF (EDF), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), and École Nationale Supérieure de Techniques Avancées (ENSTA Paris)
Subjects: 0301 basic medicine, Mathematical optimization, 021103 operations research, Artificial neural network, Branch and bound, Computer science, 0211 other engineering and technologies, Feature selection, 02 engineering and technology, Solver, 03 medical and health sciences, 030104 developmental biology, Bellman equation, Leverage (statistics), Reinforcement learning, [INFO]Computer Science [cs], Heuristics, ComputingMilieux_MISCELLANEOUS
Abstract: Mixed integer linear programs are commonly solved by Branch and Bound algorithms. A key factor of the efficiency of the most successful commercial solvers is their fine-tuned heuristics. In this paper, we leverage patterns in real-world instances to learn from scratch a new branching strategy optimised for a given problem and compare it with a commercial solver. We propose FMSTS, a novel Reinforcement Learning approach specifically designed for this task. The strength of our method lies in the consistency between a local value function and a global metric of interest. In addition, we provide insights for adapting known RL techniques to the Branch and Bound setting, and present a new neural network architecture inspired from the literature. To our knowledge, it is the first time Reinforcement Learning has been used to fully optimise the branching strategy. Computational experiments show that our method is appropriate and able to generalise well to new instances.
Published: 2020
Full Text: View/download PDF

32. Battery Energy Management of a Telecommunications Company to Participate in the Curtailment Market and Reduce the Total Energy Cost

Author: Cédric Bentz, Safia Kedad-Sidhoum, Matthieu Chardy, Mustapha Bouhtou, Isaias Faria Silva, Orange Labs [Chatillon], Orange Labs, CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), and Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)
Subjects: 021103 operations research, business.industry, 020209 energy, 0211 other engineering and technologies, Context (language use), [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], 02 engineering and technology, Energy consumption, Grid, [SPI]Engineering Sciences [physics], Work (electrical), Backup, 0202 electrical engineering, electronic engineering, information engineering, Production (economics), Business, Electricity, Telecommunications, Operating expense, ComputingMilieux_MISCELLANEOUS
Abstract: The use of batteries as a backup in case of power outages is frequent in telecommunications companies that need to keep their services always active. Also, these batteries can be used when the energy costs more, to reduce the electricity bill, as long as the safety usage rules are respected. A new context of use is to participate in the curtailment market, which is a key financial lever for the transmission grid to balance energy demand and offer. The company would use its batteries if called upon to reduce its energy consumption when the power demand is greater than a country's production, receiving a reward in exchange. Our focus in this work is to optimize over time the use of batteries installed for backup in case of power outages to participate in the curtailment market and also to reduce the energy OPEX for the company. We formally state the related optimization problem and propose a mixed-integer program to address it. Such a model is investigated with tests based on real data of a telecommunications operator in France. Simulation results prove the efficiency of our solving approach and the relevance of using batteries to participate in the curtailment market and also to reduce the energy cost for the company.
Published: 2020
Full Text: View/download PDF

33. La R.O. pour préserver la biodiversité

Author: Billionnet, Alain, Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), and Billionnet, Alain
Subjects: [SDE.BE] Environmental Sciences/Biodiversity and Ecology, [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], Diversité phylogénétique, Optimisation mathématique, Aires protégées, Conservation, Biodiversité, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [SDE.BE]Environmental Sciences/Biodiversity and Ecology
Abstract: Exemple d’utilisation de la programmation mathématique comme outil d’aide à la décision dans le domaine de la préservation de la biodiversité; National audience; L’érosion de la biodiversité est de plus en plus rapide et sa préservation est devenue un enjeu majeur. De nombreux pays se sont engagés à prendre des mesures rapides pour enrayer cette érosion. Parmi ces mesures, la création de sites - ou aires - protégés joue un rôle décisif. Nous illustrons dans cet article l’aide que la recherche opérationnelle peut apporter à la sélection d’un ensemble de sites à protéger de façon à maximiser la biodiversité associée à ces sites.
Published: 2020

34. Minimal graphs for 2-factor extension

Author: Marie-Christine Costa, Christophe Picouleau, D. de Werra, CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), and Ecole Polytechnique Fédérale de Lausanne (EPFL)
Subjects: reliability, Applied Mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0211 other engineering and technologies, 021107 urban & regional planning, 0102 computer and information sciences, 02 engineering and technology, Extension (predicate logic), 2-factor, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Combinatorics, Cardinality, Integer, minimum expandable graph, 010201 computation theory & mathematics, Simple (abstract algebra), [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Discrete Mathematics and Combinatorics, [INFO]Computer Science [cs], Undirected graph, ComputingMilieux_MISCELLANEOUS, Mathematics
Abstract: Let G = ( V , E ) be a simple loopless finite undirected graph. We say that G is (2-factor) expandable if for any non-edge u v , G + u v has a 2-factor F that contains u v . We are interested in the following: Given a positive integer n = | V | , what is the minimum cardinality of E such that there exists G = ( V , E ) which is 2-factor expandable? This minimum number is denoted by E x p 2 ( n ) . We give an explicit formula for E x p 2 ( n ) and provide 2-factor expandable graphs of minimum size E x p 2 ( n ) .
Published: 2020
Full Text: View/download PDF

35. Coordination of a two-level supply chain with contracts

Author: Safia Kedad-Sidhoum, Siao-Leu Phouratsamay, Fanny Pascual, 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), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), Recherche Opérationnelle (RO), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université 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, Conservatoire National des Arts et Métiers [CNAM] (CNAM), HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), and HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)
Subjects: 021103 operations research, Supply chain management, media_common.quotation_subject, Supply chain, 0211 other engineering and technologies, Holding cost, Screening game, 02 engineering and technology, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], 010501 environmental sciences, Management Science and Operations Research, Trusted third party, Payment, Discount points, 01 natural sciences, Theoretical Computer Science, Management Information Systems, Microeconomics, Computational Theory and Mathematics, Business, Market power, 0105 earth and related environmental sciences, media_common
Abstract: International audience; We consider the coordination of planning decisions of a single product in a supply chain composed of one supplier and one retailer, by using contracts. We assume that the retailer has the market power: he can impose his optimal replenishment plan to the supplier. Our aim is to minimize the supplier’s cost without increasing the retailer’s cost. To this end, the supplier (or a trusted third party) proposes to the retailer a contract, which is made of a replenishment plan and a side payment. This side payment compensates the increase of cost of the retailer due to the fact that the proposed replenishment plan may have a cost larger than the retailer’s optimal replenishment plan. We evaluate how much the supplier can gain by using contracts under several scenarios which depend on the side payment coverage. From a theoretical point of view, in all the scenarios, contracts may decrease the cost of the supplier by an arbitrarily large factor. We perfom experiments which measures the gain that can be obtained in practice on various instances types. If side payments are allowed, experiments show that the use of contracts decreases significantly the cost of the supplier, and that side payments on the holding costs are sufficient. We show that if there is no side payment, or if there is no constraint on the side payment, then the problem can be solved in polynomial time. On the contrary, if the side payment is limited to the holding costs of the retailer, then the problem is NP-hard. We extend this study to the case where the information is asymmetric (the supplier—or the trusted third entity—does not know all the costs of the retailer): in this case, the situation is modelled by a screening game.
Published: 2020
Full Text: View/download PDF

36. A multi-stage stochastic integer programming approach for a multi-echelon lot-sizing problem with returns and lost sales

Author: Céline Gicquel, Franco Quezada, Safia Kedad-Sidhoum, Dong Quan Vu, Recherche Opérationnelle (RO), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Recherche en Informatique (LRI), CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), and Nokia Bell Labs [Paris-Saclay]
Subjects: 0209 industrial biotechnology, Mathematical optimization, Optimization problem, General Computer Science, Linear programming, Inequality, Computer science, Heuristic (computer science), media_common.quotation_subject, 0211 other engineering and technologies, multi-stage stochastic integer programming, 02 engineering and technology, Management Science and Operations Research, valid inequalities, Set (abstract data type), 020901 industrial engineering & automation, scenario tree, [INFO]Computer Science [cs], branch-and-cut algorithm, Remanufacturing, media_common, 021103 operations research, lost sales, Heuristic, Stochastic lot-sizing, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Solver, Resolution (logic), Tree (data structure), Modeling and Simulation, remanufacturing system, Deterministic system
Abstract: International audience; We consider an uncapacitated multi-item multi-echelon lot-sizing problem within a remanufacturing system involving three production echelons: disassembly, refurbishing and reassembly. We seek to plan the production activities on this system over a multi-period horizon. We consider a stochastic environment, in which the input data of the optimization problem are subject to uncertainty. We propose a multi-stage stochastic integer programming approach relying on scenario trees to represent the uncertain information structure and develop a branch-and-cut algorithm in order to solve the resulting mixed-integer linear program to optimality. This algorithm relies on a new set of tree inequalities obtained by combining valid inequalities previously known for each individual scenario of the scenario tree. These inequalities are used within a cutting-plane generation procedure based on a heuristic resolution of the corresponding separation problem. Computational experiments carried out on randomly generated instances show that the proposed branch-and-cut algorithm performs well as compared to the use of a stand-alone mathematical solver. Finally, rolling horizon simulations are carried out to assess the practical performance of the multi-stage stochastic planning model with respect to a deterministic model and a two-stage stochastic planning model.
Published: 2020
Full Text: View/download PDF

37. On Minimum Dominating Sets in cubic and (claw,H)-free graphs

Author: Bouquet, Valentin, Delbot, François, Picouleau, Christophe, Rovedakis, Stephane, CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), CEDRIC. Réseaux et Objets Connectés (CEDRIC - ROC), Recherche Opérationnelle (RO), LIP6, and Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)
Subjects: FOS: Computer and information sciences, claw-free graphs, NP- complete, Discrete Mathematics (cs.DM), [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], FOS: Mathematics, Mathematics - Combinatorics, cubic graphs, Combinatorics (math.CO), Minimum Dominating Set, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Computer Science - Discrete Mathematics
Abstract: Given a graph $G=(V,E)$, $S\subseteq V$ is a dominating set if every $v\in V\setminus S$ is adjacent to an element of $S$. The Minimum Dominating Set problem asks for a dominating set with minimum cardinality. It is well known that its decision version is $NP$-complete even when $G$ is a claw-free graph. We give a complexity dichotomy for the Minimum Dominating Set problem for the class of $(claw, H)$-free graphs when $H$ has at most six vertices. In an intermediate step we show that the Minimum Dominating Set problem is $NP$-complete for cubic graphs.
Published: 2020

38. Adaptive network flow with $k$-Arc Destruction

Author: Ridremont, Thomas, Watel, Dimitri, Poirion, Pierre-Louis, Picouleau, Christophe, CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), Méthodes et modèles pour les réseaux (METHODES-SAMOVAR), Services répartis, Architectures, MOdélisation, Validation, Administration des Réseaux (SAMOVAR), Institut Mines-Télécom [Paris] (IMT)-Télécom SudParis (TSP)-Institut Mines-Télécom [Paris] (IMT)-Télécom SudParis (TSP), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE), and HUAWEI Technologies France (HUAWEI)
Subjects: FOS: Computer and information sciences, Maximum flow, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Complexity, Linear program, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Adaptive flow, Computer Science - Data Structures and Algorithms, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs], Combinatorics (math.CO)
Abstract: When a flow is not allowed to be reoriented the Maximum Residual Flow Problem with $k$-Arc Destruction is known to be $NP$-hard for $k=2$. We show that when a flow is allowed to be adaptive the problem becomes polynomial for every fixed $k$.
Published: 2020

39. Single-machine common due date total earliness/tardiness scheduling with machine unavailability

Author: Safia Kedad-Sidhoum, Halil Şen, Kerem Bülbül, Sabanci University [Istanbul], CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), Recherche Opérationnelle (RO), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), 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), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM), 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, Machine scheduling, Maintenance, Computer science, T055.4-60.8 Industrial engineering. Management engineering, Tardiness, 0211 other engineering and technologies, Time horizon, Semi-resumable, 0102 computer and information sciences, 02 engineering and technology, NP−complete, Management Science and Operations Research, Dynamic programming, 01 natural sciences, Machine unavailability, Scheduling (computing), Common due date, Unrestrictive, Due date, Artificial Intelligence, [INFO]Computer Science [cs], 021103 operations research, Supply chain management, General Engineering, Earliness/tardiness, 010201 computation theory & mathematics, Non-resumable, Single-machine, Unavailability, T57.6-57.97 Operations research. Systems analysis, Software, Resumable
Abstract: Research on non-regular performance measures is at best scarce in the deterministic machine scheduling literature with machine unavailability constraints. Moreover, almost all existing works in this area assume either that processing on jobs interrupted by an interval of machine unavailability may be resumed without any additional setup/processing or that all prior processing is lost. In this work, we intend to partially fill these gaps by studying the problem of scheduling a single machine so as to minimize the total deviation of the job completion times from an unrestrictive common due date when one or several fixed intervals of unavailability are present in the planning horizon. We also put serious effort into investigating models with semi-resumable jobs so that processing on a job interrupted by an interval of machine unavailability may later be resumed at the expense of some extra processing time. The conventional assumptions regarding resumability are also taken into account. Several interesting cases are identified and explored, depending on the resumability scheme and the location of the interval of machine unavailability with respect to the common due date. The focus of analysis is on structural properties and drawing the boundary between polynomially solvable and $$\mathcal {NP}$$ -complete cases. Pseudo-polynomial dynamic programming algorithms are devised for $$\mathcal {NP}$$ -complete variants in the ordinary sense.
Published: 2018
Full Text: View/download PDF

40. The Unit-capacity Constrained Permutation Problem

Author: Pierre Fouilhoux, Pascale Bendotti, Safia Kedad-Sidhoum, EDF R&D (EDF R&D), EDF (EDF), Recherche Opérationnelle (RO), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), and Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)
Subjects: Sequence, Polynomial, 021103 operations research, Information Systems and Management, General Computer Science, Computer science, Constraint (computer-aided design), 0211 other engineering and technologies, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], 0102 computer and information sciences, 02 engineering and technology, Management Science and Operations Research, Type (model theory), 01 natural sciences, Industrial and Manufacturing Engineering, Set (abstract data type), Dynamic programming, Permutation, 010201 computation theory & mathematics, Modeling and Simulation, [INFO]Computer Science [cs], Algorithm, ComputingMilieux_MISCELLANEOUS
Abstract: The Unit-capacity Constrained Permutation Problem (UCPP) is to find a sequence of moves for pieces over a set of locations. From a given location, a piece can be moved towards a location with a unit-capacity constraint, i.e. the latter location must be free of its original piece. Each piece has a specific type and at the end every location must contain a piece of a required type. A piece must be handled using a specific tool incurring a setup cost whenever a tool changeover is required. The aim of the UCPP is finding a sequence of moves with a minimum total setup cost. This problem arises in the Nuclear power plant Fuel Renewal Problem (NFRP) where locations correspond to fuel assemblies and pieces to fuel assembly inserts. We first show that the UCPP is NP-hard. We exhibit some symmetry and dominance properties and propose a dynamic programming algorithm. Using this algorithm, we prove that the UCPP is polynomial when two tools and two types are considered. Experimental results showing the efficiency of the algorithm for some instances coming from the NFRP are presented.
Published: 2018
Full Text: View/download PDF

41. The capacitated vehicle routing problem with evidential demands

Author: Eric Lefevre, Nathalie Helal, Daniel Cosmin Porumbel, Frédéric Pichon, David Mercier, Laboratoire de Génie Informatique et d'Automatique de l'Artois (LGI2A), Université d'Artois (UA), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), and Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)
Subjects: Mathematical optimization, Expected cost, Computer science, Applied Mathematics, Theory of evidence, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], 02 engineering and technology, Function (mathematics), Extension (predicate logic), Chance constrained programming, Belief function, Stochastic programming, Theoretical Computer Science, Stochastic programming with recourse, Data set, 03 medical and health sciences, 0302 clinical medicine, Artificial Intelligence, Vehicle routing problem, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, 030212 general & internal medicine, Metaheuristic, Software
Abstract: International audience; We propose to represent uncertainty on customer demands in the Capacitated Vehicle Routing Problem (CVRP) using the theory of evidence. To tackle this problem, we extend classical stochastic programming modelling approaches. Specifically, we propose two models for this problem. The first model is an extension of the chance-constrained programming approach, which imposes certain minimum bounds on the belief and plausibility that the sum of the demands on each route respects the vehicle capacity. The second model extends the stochas-tic programming with recourse approach: for each route, it represents by a belief function the uncertainty on its recourses, i.e., corrective actions performed when the vehicle capacity is exceeded, and defines the cost of a route as its classical cost (without recourse) plus the worst expected cost of its recourses. We solve the proposed models using a metaheuristic algorithm and present experimental results on instances adapted from a well-known CVRP data set.
Published: 2018
Full Text: View/download PDF

42. A Family of Scheduling Algorithms for Hybrid Parallel Platforms

Author: Grégory Mounié, Denis Trystram, Florence Monna, Safia Kedad-Sidhoum, Recherche Opérationnelle (RO), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), Data Aware Large Scale Computing (DATAMOVE ), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), and HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)
Subjects: Computer science, Approximation algorithm, 0102 computer and information sciences, 02 engineering and technology, Parallel computing, 01 natural sciences, Fair-share scheduling, Scheduling (computing), General purpose, 010201 computation theory & mathematics, 020204 information systems, Two-level scheduling, 0202 electrical engineering, electronic engineering, information engineering, Computer Science (miscellaneous), [INFO]Computer Science [cs], General-purpose computing on graphics processing units, Graphics, ComputingMilieux_MISCELLANEOUS
Abstract: More and more parallel computing platforms are built upon hybrid architectures combining multi-core processors (CPUs) and hardware accelerators like General Purpose Graphics Processing Units (GPGPUs). We present in this paper a new method for scheduling efficiently parallel applications with [Formula: see text] CPUs and [Formula: see text] GPGPUs, where each task of the application can be processed either on an usual core (CPU) or on a GPGPU. We consider the problem of scheduling [Formula: see text] independent tasks with the objective to minimize the time for completing the whole application (makespan). This problem is NP-hard, thus, we present two families of approximation algorithms that can achieve approximation ratios of [Formula: see text] or [Formula: see text] for any integer [Formula: see text] when only one GPGPU is considered, and [Formula: see text] or [Formula: see text] for [Formula: see text] GPGPUs, where [Formula: see text] is an arbitrary small value which corresponds to the target accuracy of a binary search. The proposed method is based on a dual approximation scheme that uses a dynamic programming algorithm. The associated computational costs are for the first (resp. second) family in [Formula: see text] (resp. [Formula: see text]) per step of dual approximation. The greater the value of parameter [Formula: see text], the better the approximation, but the more expensive the computational cost. Finally, we propose a relaxed version of the algorithm which achieves a running time in [Formula: see text] with a constant approximation bound of [Formula: see text]. This last result is compared to the state-of-the-art algorithm HEFT. The proposed solving method is the first general purpose algorithm for scheduling on hybrid machines with a theoretical performance guarantee that can be used for practical purposes.
Published: 2018
Full Text: View/download PDF

43. Prize-collecting set multicovering with submodular pricing

Author: Daniel Cosmin Porumbel, CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), and Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)
Subjects: 021103 operations research, Linear programming, Strategy and Management, 0211 other engineering and technologies, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], 02 engineering and technology, Management Science and Operations Research, Computer Science Applications, Dual (category theory), Submodular set function, Combinatorics, Combinatorial auction, Set (abstract data type), Management of Technology and Innovation, 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], 020201 artificial intelligence & image processing, Column generation, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Sensitivity (control systems), [MATH]Mathematics [math], Business and International Management, Time complexity, Mathematics
Abstract: International audience; We consider a ground set E and a submodular function f : 2 E → R acting on it. We first propose a Set Multi-Covering problem in which the value (price) of any S ⊆ E is f (S). We show that the Linear Program (LP) of this problem can be directly solved by applying a Submodular Function Minimization (SFM) algorithm on the dual LP. However, the main results of this study concern Prize-Collecting Multi-Covering With Submodular Pricing, i.e., a more general and more difficult Multi-Covering problem in which elements can be left uncovered by paying a penalty. We formulate it as a large-scale LP (with 2 |E| variables representing all subsets of E) that could be tackled by Column Generation (CG), see [18] for a CG algorithm for Set-Covering problems with submodular pricing. However, we do not solve this large-scale LP by CG, but we solve it in polynomial time by exploiting its integrality properties. More exactly, after appropriate restructuring, the dual LP can be transformed into an LP that has been thoroughly studied (as a primal) in the SFM theory. Solving this LP reduces to optimizing a strong map of O(n) submodular functions. For this, we use the Fleischer-Iwata framework [6] that optimizes all these O(n) functions within the same asymptotic running time as solving a single SFM, i.e., in O(n 7 γ + n 8), where n = |E| and γ is the complexity of one submodular evaluation. Besides solving the problem, the proposed approach can be useful to: (1) simultaneously find the best solution of up to O(n 5) functions under strong map relations in O(n 8 γ + n 9) time, (2) perform sensitivity analysis in very short time (even at no extra cost), (3) reveal combinatorial insight into the primal-dual optimal solutions. We present several potential applications along the paper, from production planning to combinatorial auctions.
Published: 2017
Full Text: View/download PDF

44. Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth

Author: Cédric Bentz, Pierre Le Bodic, CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), and Monash University [Melbourne]
Subjects: General Computer Science, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Theoretical Computer Science, Combinatorics, Treewidth, 010201 computation theory & mathematics, Bounded function, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, [INFO]Computer Science [cs], ComputingMilieux_MISCELLANEOUS, Mathematics
Abstract: In the Multicut problem, the input consists of a graph and a set of pairs of terminal vertices that have to be disconnected by the removal of a set of edges with minimum total weight. The Partial Multicut problem generalizes Multicut by only requiring a given number of pairs of terminals to be disconnected by the removal of edges. It has been shown that Multicut remains APX-hard if the treewidth t w ( G ) of its input graph G is bounded, but that it is FPT w.r.t. t w ( G + H ) , where H is the demand graph, whose vertices are the terminals and whose edges are the pairs of terminals. We prove that this also holds for Partial Multicut . Furthermore, it has been proved that Multicut also becomes polynomial-time solvable if t w ( G ) is bounded and H is complete (this is the Multiterminal Cut problem). We extend this result in two directions, by proving that Multicut remains polynomial-time solvable if t w ( G + H ¯ ) is bounded, and that this remains true for Partial Multicut . Finally, we show that if we further generalize the problem to allow non-unitary profits for pairs of terminals, then the problem is weakly NP-hard and has an FPTAS if t w ( G + H ) is bounded, and becomes APX-hard if t w ( G + H ¯ ) is bounded.
Published: 2020
Full Text: View/download PDF

45. Optimisation robuste du câblage d'un parc éolien sous contraintes de load flow

Author: Bentz, Cédric, Costa, Marie-Christine, Poirion, Pierre-Louis, Ridremont, Thomas, Zakhour, Camille, CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), École Nationale Supérieure de Techniques Avancées (ENSTA Paris), RIKEN Center for Advanced Intelligence Project [Tokyo] (RIKEN AIP), RIKEN - Institute of Physical and Chemical Research [Japon] (RIKEN), Artelys France, EDF (EDF), and Costa, Marie-Christine
Subjects: Mots-clés : Optimisation discrète, [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], parc éolien, câblage, Load flow, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], robustesse, ComputingMilieux_MISCELLANEOUS, réseau
Abstract: International audience
Published: 2020

46. Linear inequalities for neighborhood based dominance properties for the common due-date scheduling problem

Author: Falq, Anne-Elisabeth, Fouilhoux, Pierre, Kedad-Sidhoum, Safia, Recherche Opérationnelle (RO), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), and Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)
Subjects: dominance properties, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], ComputingMilieux_MISCELLANEOUS, just-in-time scheduling, integer linear programming
Abstract: National audience
Published: 2020

47. Optimizing Battery Usage for a Telecommunications Company with Energy Curtailment Incentives

Author: Silva, Isaias Faria, Bentz, Cédric, Bouhtou, Mustapha, Chardy, Matthieu, Kedad-Sidhoum, Safia, Orange Labs [Chatillon], Orange Labs, CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), and FARIA, Isaias
Subjects: [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 2020

48. The Minimum Dominating Set problem is polynomial for (claw, P8)-free graphs

Author: Bouquet, Valentin, Picouleau, Christophe, CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), and CEDRIC. Réseaux et Objets Connectés (CEDRIC - ROC)
Subjects: Mathematics::Combinatorics, polynomial time, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Computer Science::Computational Complexity, Minimum Dominating Set, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], claw-free graph, P k -free graph, Computer Science::Discrete Mathematics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Mathematics - Combinatorics, [INFO]Computer Science [cs], Combinatorics (math.CO), Pk -free graph, Computer Science::Data Structures and Algorithms
Abstract: We prove that the Minimum Dominating Set problem is polynomial for the class of (claw, P8)-free graphs.
Published: 2020

49. Partition of graphs with maximum degree ratio

Author: Bouquet, Valentin, Delbot, Fran��ois, Picouleau, Christophe, Picouleau, Christophe, CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), Recherche Opérationnelle (RO), LIP6, and Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)
Subjects: [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Mathematics - Combinatorics, [INFO]Computer Science [cs], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Combinatorics (math.CO), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO] Computer Science [cs], MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: Given a graph $G$ and a non trivial partition $(V_1,V_2)$ of its vertex-set, the satisfaction of a vertex $v\in V_i$ is the ratio between the size of it's closed neighborhood in $V_i$ and the size of its closed neighborhood in $G$. The worst ratio over all the vertices defines the quality of the partition. We define $q(G)$ the degree ratio of a graph as the maximum of the worst ratio over all the non trivial partitions. We give bounds and exact values of $q(G)$ for some classes of graphs. We also show some complexity results for the associated optimization or decision problems.
Published: 2020

50. Stochastic lot-sizing problem with remanufacturing: a dual dynamic decomposition approach

Author: Quezada, Franco, Gicquel, Céline, Kedad-Sidhoum, Safia, Recherche Opérationnelle (RO), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), Laboratoire de Recherche en Informatique (LRI), CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), and Kedad-Sidhoum, Safia
Subjects: [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], [INFO]Computer Science [cs], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [INFO] Computer Science [cs], ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 2019

Catalog

Books, media, physical & digital resources

See catalog results

Searchworks

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

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Journal

Database

Publisher

182 results on '"CEDRIC. Optimisation Combinatoire (CEDRIC - OC)"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources