Search

Your search keyword '"CEDRIC. Optimisation Combinatoire (CEDRIC - OC)"' showing total 43 results
Start Over Author "CEDRIC. Optimisation Combinatoire (CEDRIC - OC)" Language undetermined
43 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. 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 Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (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

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

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

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

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

7. 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 Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (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

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

9. 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 Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (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

10. 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 Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (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

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

12. 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 Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (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

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

14. Semidefinite programming relaxations through quadratic reformulation for box-constrained polynomial optimization problems

Author

Sourour Elloumi, Arnaud Lazare, Amélie Lambert, 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), 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
Semidefinite programming, 0209 industrial biotechnology, Polynomial, Quadratically constrained quadratic program, 021103 operations research, Degree (graph theory), Dimension (graph theory), MathematicsofComputing_NUMERICALANALYSIS, 0211 other engineering and technologies, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], 02 engineering and technology, 020901 industrial engineering & automation, Quadratic equation, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, Applied mathematics, Quadratic programming, Relaxation (approximation), Mathematics
Abstract

International audience; In this paper we introduce new semidefinite programming relaxations to box-constrained polynomial optimization programs (P). For this, we first reformu-late (P) into a quadratic program. More precisely, we recursively reduce the degree of (P) to two by substituting the product of two variables by a new one. We obtain a quadratically constrained quadratic program. We build a first immediate SDP relaxation in the dimension of the total number of variables. We then strengthen the SDP relaxation by use of valid constraints that follow from the quadratization. We finally show the tightness of our relaxations through several experiments on box polynomial instances.

Published
2019
Full Text
View/download PDF

15. Iterated Local Search and Column Generation to solve Arc-Routing as a permutation set-covering problem

Author

Daniel Cosmin Porumbel, Hamid Allaoui, Tiente Hsu, Gilles Goncalves, 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 Génie Informatique et d'Automatique de l'Artois (LGI2A), and Université d'Artois (UA)

Subjects
050210 logistics & transportation, 021103 operations research, Information Systems and Management, General Computer Science, Iterated local search, 05 social sciences, 0211 other engineering and technologies, Duality (optimization), Set cover problem, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], 02 engineering and technology, Management Science and Operations Research, Data structure, Industrial and Manufacturing Engineering, Dynamic programming, Permutation, Modeling and Simulation, 0502 economics and business, Column generation, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Arc routing, Algorithm, ComputingMilieux_MISCELLANEOUS, Mathematics
Abstract

We propose a method that combines Column Generation (CG) and Iterated Local Search (ILS) to solve the Capacitated Arc-Routing Problem (CARP). One of the goals is to integrate into the ILS (some of) the duality information that underpins the CG paradigm. The CARP is expressed in a space of permutations and sub-permutations (sequences, routes) of the set of required edges. For this, the ILS uses an exact decoder that maps any permutation s to a list of sequences (routes) of minimum cost servicing all edges in the order s(1), s(2), s(3), etc. This permutation space is explored both by an ILS process and a CG process that run in parallel and that communicate by exchanging sequences. The first use of the CG paradigm in ILS is the following: all sequences discovered by CG are sent to the ILS process that can inject them into the current ILS solution. The second application of CG in ILS is a “CG improver” operator that acts on the current ILS solution, so as to (try to) improve it by running several CG iterations. The first half of the paper describes the method in a general framework based on sequences, permutations and set covering. The second part is devoted to more specialized Arc-Routing techniques. For instance, the CG convergence could be accelerated by factors of tens or even hundreds by exploiting two ideas in the Dynamic Programming (DP) pricing: (i) avoid as much as possible to traverse edges without service, and (ii) record only non-dominated DP states using a fast-access data structure mixing an array and a red-black tree. Regarding the ILS, we show that the permutation-level search can be substantially improved if the exact decoder is reinforced by a deterministic post-decoder acting on explicit routes. The general results are competitive (reducing the best-known gap of five instances) and certain ideas could be potentially useful for other set-covering or permutation problems.

Published
2017
Full Text
View/download PDF

16. On graceful difference labelings of disjoint unions of circuits

Author

Alain Hertz, Christophe Picouleau, Groupe d’études et de recherche en analyse des décisions (GERAD), École Polytechnique de Montréal (EPM)-McGill University = Université McGill [Montréal, Canada]-HEC Montréal (HEC Montréal)-Université du Québec à Montréal = University of Québec in Montréal (UQAM), 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
Vertex (graph theory), Conjecture, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Graceful labelings, Directed graph, Disjoint sets, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], directed graphs, Combinatorics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Bijection, FOS: Mathematics, Mathematics - Combinatorics, [INFO]Computer Science [cs], Combinatorics (math.CO), disjoint unions of circuits, Mathematics, Electronic circuit
Abstract

A graceful difference labeling (gdl for short) of a directed graph G with vertex set V is a bijection f between V and {1,...,|V|} such that, when each arc uv is assigned the difference label f(v)-f(u), the resulting arc labels are distinct. We conjecture that all disjoint unions of circuits have a gdl, except in two particular cases. We prove partial results which support this conjecture., Comment: 21 pages,15 figures, 9 tables

Published
2019
Full Text
View/download PDF

17. Novel Approach Towards Global Optimality of Optimal Power Flow Using Quadratic Convex Optimization

Author

Hadrien Godard, Amélie Lambert, Jean Maeght, Manuel Ruiz, Sourour Elloumi, Réseau de Transport d'Electricité [Paris] (RTE), 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), and 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, 020209 energy, MathematicsofComputing_NUMERICALANALYSIS, 0211 other engineering and technologies, 02 engineering and technology, Upper and lower bounds, Computational Engineering, Finance, and Science (cs.CE), Computer Science - Robotics, Quadratic equation, Computer Science::Systems and Control, 0202 electrical engineering, electronic engineering, information engineering, FOS: Mathematics, Quadratic programming, Computer Science - Computational Engineering, Finance, and Science, Mathematics - Optimization and Control, Mathematics, Quadratically constrained quadratic program, 021103 operations research, [SPI.NRJ]Engineering Sciences [physics]/Electric power, [INFO.INFO-CE]Computer Science [cs]/Computational Engineering, Finance, and Science [cs.CE], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Constraint (information theory), Optimization and Control (math.OC), Convex optimization, Node (circuits), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Relaxation (approximation), Robotics (cs.RO)
Abstract

International audience; Optimal Power Flow (OPF) can be modeled as a non-convex Quadratically Constrained Quadratic Program (QCQP). Our purpose is to solve OPF to global optimality. To this end, we specialize the Mixed-Integer Quadratic Convex Reformulation method (MIQCR) to (OPF). This is a method in two steps. First, a Semi-Definite Programming (SDP) relaxation of (OPF) is solved. Then the optimal dual variables of this relaxation are used to reformulate OPF into an equivalent new quadratic program, where all the non-convexity is moved to one additional constraint. In the second step, this reformulation is solved within a branch-and-bound algorithm, where at each node a quadratic and convex relaxation of the reformulated problem, obtained by relaxing the non-convex added constraint, is solved. The key point of our approach is that the lower bound at the root node of the branch-and-bound tree is equal to the SDP relaxation value. We test this method on several OPF cases, from two-bus networks to more-than-a-thousand-buses networks from the MAT-POWER repository. Our first results are very encouraging.

Published
2019
Full Text
View/download PDF

18. Solving unconstrained 0-1 polynomial programs through quadratic convex reformulation

Author

Sourour Elloumi, Arnaud Lazare, Amélie Lambert, Unité de Mathématiques Appliquées (UMA), É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), Optimisation et commande (OC), and École Nationale Supérieure de Techniques Avancées (ENSTA Paris)-École Nationale Supérieure de Techniques Avancées (ENSTA Paris)

Subjects
FOS: Computer and information sciences, Polynomial, Control and Optimization, Discrete Mathematics (cs.DM), 0211 other engineering and technologies, 02 engineering and technology, Management Science and Operations Research, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Quadratic equation, Computer Science - Data Structures and Algorithms, Applied mathematics, Global optimiza-tion, Semidefinite programming, Data Structures and Algorithms (cs.DS), Quadratic programming, Global optimization, Mathematics, Quadratic convex reformulation, 021103 operations research, Applied Mathematics, Semi-definite programming, Quadratic function, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Solver, Computer Science Applications, Relaxation (approximation), Unconstrained binary polynomial programming, Experiments, Computer Science - Discrete Mathematics
Abstract

International audience; We propose a solution approach for the problem (P) of minimizing an unconstrained binary polynomial optimization problem. We call this method PQCR (Polynomial Quadratic Convex Reformulation). The resolution is based on a 3-phase method. The first phase consists in reformulating (P) into a quadratic program (QP). For this, we recursively reduce the degree of (P) to two, by use of the standard substitution of the product of two variables by a new one. We then obtain a linearly constrained binary program. In the second phase, we rewrite the quadratic objective function into an equivalent and parametrized quadratic function using the equality x 2 i = x i and new valid quadratic equalities. Then, we focus on finding the best parameters to get a quadratic convex program which continuous relaxation's optimal value is maximized. For this, we build a semidefinite relaxation (SDP) of (QP). Then, we prove that the standard linearization inequalities, used for the quadratization step, are redundant in (SDP) in presence of the new quadratic equalities. Next, we deduce our optimal parameters from the dual optimal solution of (SDP). The third phase consists in solving (QP *), the optimal reformulated problem, with a standard solver. In particular, at each node of the branch-and-bound, the solver computes the optimal value of a continuous quadratic convex program. We present computational results on instances of the image restoration problem and of the low autocorrelation binary sequence problem. We compare PQCR with other convexification methods, and with the general solver Baron 17.4.1 [39]. We observe that most of the considered instances can be solved with our approach combined with the use of Cplex [24].

Published
2019
Full Text
View/download PDF

19. Exact quadratic convex reformulations of mixed-integer quadratically constrained problems

Author

Sourour Elloumi, Amélie Lambert, Alain Billionnet, 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), 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), 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
Quadratic growth, Quadratically constrained quadratic program, Mathematical optimization, 021103 operations research, General Mathematics, 0211 other engineering and technologies, branch-and-bound algorithm, Integer quadratic programming, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], 010103 numerical & computational mathematics, 02 engineering and technology, Quadratic function, semidefinite programming, Isotropic quadratic form, 01 natural sciences, Convex optimization, Second-order cone programming, Binary quadratic form, Quadratic programming, 0101 mathematics, Software, Equivalent convex reformulation, Mathematics
Abstract

International audience; We propose a solution approach for the general problem (QP) of minimizing a quadratic function of bounded integer variables subject to a set of quadratic constraints. The resolution is based on the reformulation of the original problem (QP) into an equivalent quadratic problem whose continuous relaxation is convex, so that it can be effectively solved by a branch-and-bound algorithm based on quadratic convex relaxation. We concentrate our efforts on finding a reformulation such that the continuous relaxation bound of the reformulated problem is as tight as possible. Furthermore, we extend our method to the case of mixed-integer quadratic problems with the following restriction: all quadratic sub-functions of purely continuous variables are already convex. Finally, we illustrate the different results of the article by small examples and we present some computational experiments on pure-integer and mixed-integer instances of (QP). Most of the considered instances with up to 53 variables can be solved by our approach combined with the use of Cplex.

Published
2015
Full Text
View/download PDF

20. An FPT algorithm in polynomial space for the Directed Steiner Tree problem with Limited number of Diffusing nodes

Author

Marc-Antoine Weisser, Cédric Bentz, Dimitri Watel, Dominique Barth, Supélec Sciences des Systèmes (E3S), Ecole Supérieure d'Electricité - SUPELEC (FRANCE), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-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), Parallélisme, Réseaux, Systèmes, Modélisation (PRISM), and Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Centre National de la Recherche Scientifique (CNRS)

Subjects
0211 other engineering and technologies, Parameterized complexity, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Steiner tree problem, Theoretical Computer Science, Combinatorics, symbols.namesake, [INFO]Computer Science [cs], ComputingMilieux_MISCELLANEOUS, Mathematics, Discrete mathematics, Circuit switching, 021103 operations research, Multicast, Directed graph, Computer Science Applications, Tree (data structure), Exact algorithm, 010201 computation theory & mathematics, Signal Processing, symbols, Routing (electronic design automation), Algorithm, Information Systems
Abstract

Given a directed graph with n nodes, a root r, a set X of k nodes called terminals and non-negative weights ω over the arcs, the Directed Steiner Tree problem (DST) asks for a directed tree T * of minimum cost ω ( T * ) rooted at r and spanning X.If this problem has several applications in multicast routing in packet switching networks, the modeling is no longer adapted in networks based upon the circuit switching principle, in which some nodes, called non-diffusing nodes, are not able to duplicate packets. We study a generalization of DST, called Directed Steiner Tree with Limited number of Diffusing nodes (DSTLD), able to model the multicast routing in a network containing at most d diffusing nodes.We provide an FPT exact algorithm running in time O ( t d ? d k ? n ? ( d + k ) ) and in polynomial space for DSTLD, where t d is the number of unordered rooted trees with d unlabelled nodes. Thereby, we also provide the first exact algorithm running in polynomial space and in FPT time with respect to k which returns an optimal solution for DST instead of the optimal cost only. We model a Directed Steiner Tree problem in optical networks.We propose an algorithm for this problem building an optimal solution.This gives an algorithm for the classical Directed Steiner problem in graphs.The algorithm runs in polynomial space and in FPT time in the number of terminals.

Published
2015
Full Text
View/download PDF

21. Blockers for the Stability Number and the Chromatic Number

Author

Christophe Picouleau, Cédric Bentz, Bernard Ries, Cristina Bazgan, Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), 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 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], Dense graph, split graph, graphe biparti, Comparability graph, Theoretical Computer Science, law.invention, Combinatorics, Pathwidth, chromatic number, law, nombre de stabilité, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, threshold graph, Line graph, Discrete Mathematics and Combinatorics, [INFO]Computer Science [cs], Cograph, Split graph, blocker, Pancyclic graph, graphique du seuil, Mathematics, Discrete mathematics, stability number, graphe de Split, Threshold graph, nombre chromatique, bipartite graph, Triangle-free graph, Bloqueur, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

International audience; Given an undirected graph G = (V,E) and two positive integers k and d, we are interested in finding a set of edges (resp. non-edges) of size at most k to delete (resp. to add) in such a way that the chromatic number (resp. stability number) in the resulting graph will decrease by at least d compared to the original graph. We investigate these two problems in various classes of graphs (split graphs, threshold graphs, (complement of) bipartite graphs) and determine their computational complexity. In some of the polynomial-time solvable cases, we also give a structural description of a solution.

Published
2013
Full Text
View/download PDF

22. A Recourse Approach for the Capacitated Vehicle Routing Problem with Evidential Demands

Author

Frédéric Pichon, Daniel Cosmin Porumbel, David Mercier, Nathalie Helal, Eric Lefevre, Mercier, David, 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
[INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], Difficult problem, Mathematical optimization, 021103 operations research, [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], Computer science, Computation, 0211 other engineering and technologies, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], 02 engineering and technology, Extension (predicate logic), Belief function, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], Stochastic programming with recourse, Vehicle routing problem, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Metaheuristic
Abstract

International audience; The capacitated vehicle routing problem with stochastic demands can be modelled using either the chance-constrained approach or the recourse approach. In previous works, we extended the former approach to address the case where uncertainty on customer demands is represented by belief functions, that is where customers have so-called evidential demands. In this paper, we propose an extension of the recourse approach for this latter case. We also provide a technique that makes computations tractable for realistic situations. The feasibility of our approach is then shown by solving instances of this difficult problem using a metaheuristic algorithm.

Published
2017
Full Text
View/download PDF

23. A Branch and Bound algorithm for general mixed-integer quadratic programs based on quadratic convex relaxation

Author

Amélie Lambert, Alain Billionnet, Sourour Elloumi, 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), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), 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-CC]Computer Science [cs]/Computational Complexity [cs.CC], Control and Optimization, 0211 other engineering and technologies, 010103 numerical & computational mathematics, 02 engineering and technology, 01 natural sciences, Combinatorics, Quadratic equation, Integer, Branch and Bound, Discrete Mathematics and Combinatorics, [INFO]Computer Science [cs], Quadratic programming, 0101 mathematics, Global optimization, Mathematics, Discrete mathematics, Branche et lié aux, 021103 operations research, Branch and bound, Applied Mathematics, General mixed-integer quadratic programming, experiments, expériences, Quadratic function, Solver, relaxation convexe quadratique, Computer Science Applications, Générale mixte-entier quadratique, Computational Theory and Mathematics, quadratic convex relaxation, Relaxation (approximation)
Abstract

Let $$(MQP)$$ be a general mixed-integer quadratic program that consists of minimizing a quadratic function $$f(x) = x^TQx +c^Tx$$ subject to linear constraints. Our approach to solve $$(MQP)$$ is first to consider an equivalent general mixed-integer quadratic problem. This equivalent problem has additional variables $$y_{ij}$$ , additional quadratic constraints $$y_{ij}=x_ix_j$$ , a convex objective function, and a set of valid inequalities. Contrarily to the reformulation proposed in Billionnet et al. (Math Program 131(1):381---401, 2012), the equivalent problem cannot be directly solved by a standard solver. Here, we propose a new Branch and Bound process based on the relaxation of the non-convex constraints $$y_{ij}=x_ix_j$$ to solve $$(MQP)$$ . Computational experiences are carried out on pure- and mixed-integer quadratic instances. The results show that the solution time of most of the considered instances with up to 60 variables is improved by our Branch and Bound algorithm in comparison with the approach of Billionnet et al. (2012) and with the general mixed-integer nonlinear solver BARON (Sahinidis and Tawarmalani, Global optimization of mixed-integer nonlinear programs, user's manual, 2010).

Published
2012
Full Text
View/download PDF

24. Minimum decomposition into convex binary matrices

Author

Christophe Picouleau, Fethi Jarray, 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), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), 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
Discrete mathematics, Applied Mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], LU decomposition, Intensity Modulated Radiation Therapy, law.invention, QR decomposition, Matrix decomposition, Combinatorics, Integer matrix, Matrix (mathematics), law, Singular value decomposition, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Discrete Mathematics and Combinatorics, Logical matrix, [INFO]Computer Science [cs], Convex polyomino, ComputingMilieux_MISCELLANEOUS, Cholesky decomposition, Mathematics, NP-complete
Abstract

Motivated by Intensity Modulated Radiation Therapy, we consider the problem of the minimum decomposition of an integer matrix into hv-convex matrices with time and cardinality objectives. We study the special case where the matrix to decompose is a binary matrix (in this case, time decomposition and cardinality decomposition are the same). We prove that the decomposition into two hv-convex matrices or into two hv-convex polyominoes is polynomially solvable. For the decomposition into three hv-convex matrices the problem becomes NP-complete.

Published
2012
Full Text
View/download PDF

25. Disjoint paths in sparse graphs

Author

Cédric Bentz, 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-CC]Computer Science [cs]/Computational Complexity [cs.CC], Discrete mathematics, Applied Mathematics, Approximation algorithm, Planar graphs, Circuit rank, Computer Science::Computational Complexity, Polynomial-time solvability, Tree (graph theory), Approximation algorithms, Planar graph, Treewidth, Combinatorics, symbols.namesake, Indifference graph, Computer Science::Discrete Mathematics, Chordal graph, Bounded function, Bounded tree-width, symbols, Discrete Mathematics and Combinatorics, [INFO]Computer Science [cs], Disjoint paths, Computer Science::Data Structures and Algorithms, Mathematics
Abstract

We generalize all the results obtained for maximum integer multiflow and minimum multicut problems in trees by Garg, Vazirani and Yannakakis [N. Garg, V.V. Vazirani, M. Yannakakis, Primal-dual approximation algorithms for integral flow and multicut in trees, Algorithmica 18 (1997) 3–20] to graphs with a fixed cyclomatic number, while this cannot be achieved for other classical generalizations of trees. We also introduce thek-edge-outerplanar graphs, a class of planar graphs with arbitrary (but bounded) tree-width that generalizes the cacti, and show that the integrality gap of the maximum edge-disjoint paths problem is bounded in these graphs.

Published
2009
Full Text
View/download PDF

26. A simple algorithm for multicuts in planar graphs with outer terminals

Author

Cédric Bentz, 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-CC]Computer Science [cs]/Computational Complexity [cs.CC], Discrete mathematics, Applied Mathematics, Minimum weight, Planar graphs, Graph, Planar graph, Combinatorics, symbols.namesake, Bounded function, symbols, Discrete Mathematics and Combinatorics, [INFO]Computer Science [cs], Multicuts, Graph algorithms, Time complexity, SIMPLE algorithm, MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics
Abstract

Given an edge-weighted graph G and a list of source–sink pairs of terminal vertices of G, the minimum multicut problem consists in selecting a minimum weight set of edges of G whose removal leaves no path from the ith source to the ith sink, for each i. Few tractable special cases are known for this problem. In this paper, we give a simple polynomial-time algorithm solving it in undirected planar graphs where (I) all the terminals lie on the outer face and (II) there is a bounded number of terminals.

Published
2009
Full Text
View/download PDF

27. On the complexity of the multicut problem in bounded tree-width graphs and digraphs

Author

Cédric Bentz, 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-CC]Computer Science [cs]/Computational Complexity [cs.CC], Discrete mathematics, Vertex (graph theory), Applied Mathematics, Minimum weight, Digraph, Directed graph, Directed acyclic graph, Graph, Combinatorics, Treewidth, Bounded function, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, Discrete Mathematics and Combinatorics, [INFO]Computer Science [cs], Computer Science::Data Structures and Algorithms, Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

Given an edge- or vertex-weighted graph or digraph and a list of source-sink pairs, the minimum multicut problem consists in selecting a minimum weight set of edges or vertices whose removal leaves no path from each source to the corresponding sink. This is a classical NP-hard problem, and we show that the edge version becomes tractable in bounded tree-width graphs if the number of source-sink pairs is fixed, but remains NP-hard in directed acyclic graphs and APX-hard in bounded tree-width and bounded degree unweighted digraphs. The vertex version, although tractable in trees, is proved to be NP-hard in unweighted cacti of bounded degree and bounded path-width.

Published
2008
Full Text
View/download PDF

28. Comparison of Quadratic Convex Reformulations to Solve the Quadratic Assignment Problem

Author

Amélie Lambert, Sourour Elloumi, 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), 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), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), 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
Semidefinite programming, Quadratically constrained quadratic program, 021103 operations research, Quadratic assignment problem, 0211 other engineering and technologies, 010103 numerical & computational mathematics, 02 engineering and technology, Quadratic function, 01 natural sciences, Quadratic equation, Convex optimization, Applied mathematics, [INFO]Computer Science [cs], Relaxation (approximation), Quadratic programming, [MATH]Mathematics [math], 0101 mathematics, Experiments, Convex quadratic programming, Mathematics
Abstract

International audience; We consider the (QAP) that consists in minimizing a quadratic function subject to assignment constraints where the variables are binary. In this paper, we build two families of equivalent quadratic convex formulations of (QAP). The continuous relaxation of each equivalent formulation is then a convex problem and can be used within a B&B. In this work, we focus on finding the “best” equivalent formulation within each family, and we prove that it can be computed using semidefinite programming. Finally, we get two convex formulations of (QAP) that differ from their sizes and from the tightness of their continuous relaxation bound. We present computational experiments that prove the practical usefulness of using quadratic convex formulation to solve instances of (QAP) of medium sizes.

Published
2016
Full Text
View/download PDF

29. Exact and approximate resolution of integral multiflow and multicut problems: algorithms and complexity

Author

Cédric Bentz, 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-CC]Computer Science [cs]/Computational Complexity [cs.CC], Discrete mathematics, Optimization problem, Graph theory, Management Science and Operations Research, Resolution (logic), 1-planar graph, Theoretical Computer Science, Management Information Systems, Planar graph, Combinatorics, symbols.namesake, Computational Theory and Mathematics, Bounded function, symbols, Integral graph, Combinatorial optimization, [INFO]Computer Science [cs], Mathematics
Abstract

This is a summary of the author’s PhD thesis supervised by Marie- Christine Costa and Frederic Roupin and defended on 20 November 2006 at the Conservatoire National des Arts et Metiers in Paris (France). The thesis is written in French and is available upon request from the author. This work deals with two well-known optimization problems from graph theory: the maximum integral multiflow and the minimum multicut problems. The main contributions of this thesis concern the polynomial-time solvability and the approximation of these two problems (and of some of their variants) in classical classes of graphs: bounded tree-width graphs, planar graphs and grids, digraphs, etc.

Published
2007
Full Text
View/download PDF

30. Reconstruction of domino tiling from its two orthogonal projections

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
General Computer Science, Open problem, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Domino tiling, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Type (model theory), 01 natural sciences, Polynomial algorithm, Polynomial-time algorithm, Theoretical Computer Science, Combinatorics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], Rectangle, Time complexity, ComputingMilieux_MISCELLANEOUS, Mathematics, Discrete mathematics, Reconstruction problem, Mathematics::Combinatorics, Mathematics::History and Overview, Orthographic projection, Nonlinear Sciences::Cellular Automata and Lattice Gases, NP-completeness, Transformation (function), 010201 computation theory & mathematics, 020201 artificial intelligence & image processing, Computer Science(all)
Abstract

We are interested in the reconstruction of a domino tiling of a rectangle from its two orthogonal projections. We give polynomial algorithms for some subproblems when all the dominoes are of the same type and prove NP-completeness results when there are three types of dominoes. When two types of dominoes are allowed, we give a polynomial-time transformation from a well-known open problem.

Published
2001
Full Text
View/download PDF

31. A polynomial-time algorithm for planar multicuts with few source-sink pairs

Author

Cédric Bentz, 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-CC]Computer Science [cs]/Computational Complexity [cs.CC], Source sink, Discrete mathematics, FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Longest path problem, Planar graph, Combinatorics, Indifference graph, symbols.namesake, Planar, Chordal graph, Computer Science - Data Structures and Algorithms, symbols, [INFO]Computer Science [cs], Data Structures and Algorithms (cs.DS), Sink (computing), Time complexity, Algorithm, Mathematics, Computer Science - Discrete Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

Given an edge-weighted undirected graph and a list of k source-sink pairs of vertices, the well-known minimum multicut problem consists in selecting a minimum-weight set of edges whose removal leaves no path between every source and its corresponding sink. We give the first polynomial-time algorithm to solve this problem in planar graphs, when k is fixed. Previously, this problem was known to remain NP-hard in general graphs with fixed k, and in trees with arbitrary k; the most noticeable tractable case known so far was in planar graphs with fixed k and sources and sinks lying on the outer face., Comment: 11 pages, 1 figure

Published
2012
Full Text
View/download PDF

32. Scaling the Level of Difficulty in Single Player Video Games

Author

Stéphane Natkin, Guillaume Levieux, Maria-Virginia Aponte, 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 - Interactivité pour Lire et Jouer (CEDRIC - ILJ)

Subjects
Game mechanics, Game art design, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], Sequential game, Multimedia, Game Design, Property (programming), Computer science, ComputingMilieux_PERSONALCOMPUTING, Jeux vidéo, computer.software_genre, Difficulté, Turns, rounds and time-keeping systems in games, Game design, Video Games, [INFO]Computer Science [cs], [INFO.INFO-HC]Computer Science [cs]/Human-Computer Interaction [cs.HC], Video game design, Difficulty, Video game, computer
Abstract

In this this paper, we discuss the interest and the need to evaluate the difficulty of single player video games. We first show the importance of difficulty, drawing from semiotics to explain the link between tension-resolution cycles, and challenge with the player's enjoyment. Then, we report related work on automatic gameplay analysis. We show through a simple experimentation that automatic video game analysis is both practicable and can lead to interesting results. We argue that automatic analysis tools are limited if they do not consider difficulty from the player point of view. The last section provides a player and Game Design oriented definition of the challenge and difficulty notions in games. As a consequence we derive the property that must fulfill a measurable definition of difficulty.; Dans cet article, nous présentons l'intérêt et la nécessité d'une évaluation de la difficulté des jeux vidéo. Nous montrons tout d'abord l'importance de la difficulté, en questionnant le liens entre les cycles de tensions - résolution proposés en sémiotique, le niveau de challenge et le plaisir du joueur. Ensuite, nous rapportons un ensemble de travaux sur l'analyse automatique de gameplay. Nous montrons, au travers d'une expérimentation, que l'analyse automatique de gameplay est tout autant réalisable que capable de fournir des résultats pertinents. Nous insistons sur le fait qu'un outil d'analyse automatique de jeu gagne à considérer la difficulté du point de vue du joueur. La dernière section propose une définition de la difficulté orientée game design et centrée sur le joueur. Nous proposons en ensemble de propriétés qui permette de définir la difficulté d'un jeu comme un élément mesurable.

Published
2009
Full Text
View/download PDF

33. Linear Reformulations of Integer Quadratic Programs

Author

Alain Billionnet, Sourour Elloumi, Amélie Lambert, 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), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), 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
Discrete mathematics, Quadratically constrained quadratic program, Expériences, Integer programming, quadratic programming, linear reformulations, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Quadratic function, nouvelles formulations linéaires, Quadratic residue, Quadratic equation, Applied mathematics, Second-order cone programming, Binary quadratic form, Quadratic field, Quadratic programming, Programmation en nombres entiers, Experiments, programmation quadratique, Mathematics
Abstract

Let (QP) be an integer quadratic program that consists in minimizing a quadratic function subject to linear constraints. In this paper, we present several linearizations of (QP). Many linearization methods for the quadratic 0-1 programs are known. A natural approach when considering (QP) is to reformulate it into a quadratic 0-1 program. However, this method, that we denote BBL(Binary Binary Linearization), leads to a quadratic program with a large number of variables and constraints. Our new approach, BIL(Binary Integer Linearization), consists in reformulating (QP) into a particular quadratic integer program where each quadratic term is the product of an integer variable by a 0-1 variable. The obtained integer linear program is significantly smaller than in the BBL approach.Each reformulation leads to an integer linear program that we improve by adding valid inequalities. Finally, we get 4 different programs that we compare from the computational point of view.

Published
2008
Full Text
View/download PDF

34. Addendum to 'Bicolored Matchings in Some Classes of Graphs'

Author

Christophe Picouleau, D. de Werra, Bernard Ries, Marie-Christine Costa, CEDRIC. Réseaux et Objets Connectés (CEDRIC - ROC), 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), Ecole Polytechnique Fédérale de Lausanne (EPFL), and CEDRIC. Optimisation Combinatoire (CEDRIC - OC)

Subjects
Combinatorics, Discrete mathematics, Web of science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Discrete Mathematics and Combinatorics, Addendum, [INFO]Computer Science [cs], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], ComputingMilieux_MISCELLANEOUS, Theoretical Computer Science, Mathematics
Abstract

Reference ROSE-ARTICLE-2008-008doi:10.1007/s00373-008-0771-2View record in Web of Science Record created on 2008-06-12, modified on 2016-08-08

Published
2008
Full Text
View/download PDF

35. Reformulation Quadratique Convexe Pour l'Optimisation des Flux de Puissance

Author

Hadrien Godard, sourour elloumi, Amélie Lambert, Jean Maeght, Manuel Ruiz, 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), Réseau de Transport d'Electricité [Paris] (RTE), and Lambert, Amélie

Subjects
[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract

International audience; Mots-clés : Optimisation des flux de puissance, Reformulation quadratique, Programmation quadratique, Programmation semi-définie. Un réseau électrique est constitué d'un ensemble de noeuds reliés par des lignes. L'effet Joule rend non conservatif le transport de l'électricité des noeuds de production aux noeuds de consommation à travers les lignes. L'optimisation des flux de puissance, en anglais Optimal Power Flow (OPF), consiste à déterminer un état du réseau (tension et injections aux noeuds, transits sur les lignes) permettant de satisfaire la demande aux noeuds tout en mi-nimisant un certain critére. Dans ce travail une nouvelle approche permettant de résoudre à l'optimum global l'OPF est introduite. Cette approche consiste à construire une reformulation quadratique [1] de l'OPF en utilisant une relaxation issue de l'état de l'art [4]. 1 Formulation de l'OPF et relaxation semi-définie positive L'OPF s'exprime comme un problème hermitien [5] dont les variables v ∈ C n sont les tensions aux n noeuds du réseau électrique. Il est possible de plonger v dans R 2n en introduisant les variables réelles x tel que x t = [ v t +v t 2 ; v t −v t 2i ] qui représentent les parties réelles et imaginaires des tensions. L'OPF se modélise alors comme un programme quadratique non convexe en variables réelles, avec ∀k ∈ {0,. .. , m}, A k ∈ M 2n (R) : (OP F) min x∈R 2n f 0 (x) = x t A 0 x s.t. f k (x) = x t A k x ≤ a k k = 1,. .. , m En introduisant la matrice variable Y = xx t , (OP F) se reformule ainsi : (RSDP)        min Y ∈M2n(R) A 0 , Y s.t. A k , Y ≤ a k k = 1,. .. , m Y 0, rg(Y) = 1 Une relaxation semi définie positive convexe (RSDP), appelée relaxation du rang, s'obtient en éliminant la contrainte non convexe rg(Y) = 1. 2 Algorithme de résolution de l'OPF Pour résoudre (OP F), nous en construisons dans un premier temps une reformulation qua-dratique à partir de la résolution de (RSDP). Dans un second temps nous résolvons cette reformulation dans un algorithme de branch-and-bound ayant comme borne à la racine la va-leur de (RSDP) qui est de bonne qualité pour le problème de l'OPF [3].

36. Solving Optimal Power Flow through reformulation

Author

Sourour Elloumi, Hadien Godard, Amelie Lambert, Jean Maeght, Manuel Ruiz, ELLOUMI, Sourour, Optimisation et commande ( OC ), Unité de Mathématiques Appliquées ( UMA ), École Nationale Supérieure de Techniques Avancées ( Univ. Paris-Saclay, ENSTA ParisTech ) -É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 ), École Nationale Supérieure de Techniques Avancées ( Univ. Paris-Saclay, ENSTA ParisTech ), Réseau de Transport d'Electricité-RTE, 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), 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), École Nationale Supérieure de Techniques Avancées (ENSTA Paris), Réseau de Transport d'Electricité [Paris] (RTE), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), 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-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI], [ INFO.INFO-NI ] Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], ComputingMilieux_MISCELLANEOUS, [ INFO.INFO-RO ] Computer Science [cs]/Operations Research [cs.RO]
Abstract

International audience

37. Reducing the Adaptation Costs of a Rolling Stock Schedule with Adaptive Solution: the Case of Demand Changes

Author

Rémi Lucas, Zacharie Alès, François Ramond, sourour elloumi, Ales, Zacharie, 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), SNCF : Innovation & Recherche, SNCF, 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
[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], Discrete Optimization, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Adaptive Solution, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Rolling Stock
Abstract

International audience; In railway scheduling, a nominal traffic schedule is established well in advance for the main resources: train-paths, rolling stock and crew. However, it has to be adapted each time a change in the input data occurs. In this paper, we focus on the costs in the adaptation phase. We introduce the concept of adaptive nominal solution which minimizes adaptation costs with respect to a given set of potential changes. We illustrate this framework with the rolling stock scheduling problem with scenarios corresponding to increasing demand in terms of rolling stock units. We define adaptation costs for a rolling stock schedule and propose two MILPs. The first one adapts, at minimal cost, an existing rolling stock schedule with respect to a given scenario. The second MILP considers a set of given scenarios and computes an adaptive nominal rolling stock schedule together with an adapted solution to each scenario, again while minimizing adaptation costs. We illustrate our models with computational experiments on realistic SNCF instances.

38. Convex reformulations of Integer Quadratically Constrained Problems

Author

Alain Billionnet, Sourour Elloumi, Amelie Lambert, 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), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), 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, Laboratoire

Subjects
Reformulation linéaire, [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], Expériences, General integer programming, MathematicsofComputing_NUMERICALANALYSIS, Semi-definite programming, Reformulation convexe quadratique, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Quadratique contraint programmation, Programmation semi-définie, Linear reformulation, Quadratically constrained programming, Programmation en nombres entiers générales, Experiments, Quadratic convex reformulation
Abstract

We consider a general integer program (QQP) where both the objective function and the constraints are quadratic. We show that the quadratic convex reformulation approach can be extended to that case. This approach consists in designing a program, equivalent to QQP, with a quadratic convex objective function and linear or quadratic convex constraints. The resulting program is then solved by a standard solver. We start by dealing with the objective function. For this, we solve a semi-definite program from which we deduce a reformulation of (QQP) as an equivalent problem (P) having a convex quadratic objective function. We then handle the quadratic constraints of (P). We propose and compare linear and quadratic convex reformulations of these constraints. Finally, we give some numerical results comparing our different approaches.

39. Convex reformulations of mixed-integer quadratically constrained programs

Author

Alain Billionnet, Sourour Elloumi, Amelie Lambert, CEDRIC, Laboratoire, 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), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), 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
Programmation quadratique, [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], Quadratic Programming, Programmation semi-définie, Programmation mixte, Semidefinite programming, Mixed-integer programming, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract

We present a solution approach for the general problem (QP) of minimizing a quadratic function of integer variables subject to a set of quadratic constraints. The resolution is divided into two phases. The ?rst phase is to reformulate the initial problem as an equivalent quadratic problem which continuous relaxation is convex; the second phase is to solve the reformulated problem by a branch and bound algorithm. We further extend these results to the mixed-integer case. Finally, we present some computational experiments on pure-integer and mixed-integer instances of (QP ).

40. Reformulation convexe des programmes quadratiques entiers : un algorithme de Branch and Bound fondé sur la structure du problème reformulé

Author

Alain Billionnet, Sourour Elloumi, Amelie Lambert, 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), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), 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, Laboratoire

Subjects
[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], reformulation convexe, Branch and Bound, convex reformulation, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], programmation quadratique entière, integer quadratic programming
Abstract

International audience; programmation quadratique entière, reformulation convexe, Branch and Bound

41. The Single-Item Green Lot-Sizing Problem with Fixed Carbon Emissions

Author

Christophe Rapine, Safia Kedad-Sidhoum, Nabil Absi, Bernard Penz, Stéphane Dauzère-Pérès, 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)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Recherche Opérationnelle (RO), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP ), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), 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]), Laboratoire de Génie Industriel, de Production et de Maintenance (LGIPM), Université de Lorraine (UL), Penz, Bernard, Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes (LIMOS), SIGMA Clermont (SIGMA Clermont)-Université d'Auvergne - Clermont-Ferrand I (UdA)-Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Blaise Pascal - Clermont-Ferrand 2 (UBP), 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 pour les Systèmes de Production (G-SCOP_ROSP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Kedad-Sidhoum, Safia, Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Université d'Auvergne - Clermont-Ferrand I (UdA)-SIGMA Clermont (SIGMA Clermont)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-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), 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
0209 industrial biotechnology, Mathematical optimization, Information Systems and Management, General Computer Science, [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], Astrophysics::High Energy Astrophysical Phenomena, 0211 other engineering and technologies, chemistry.chemical_element, Time horizon, 02 engineering and technology, [INFO] Computer Science [cs], Management Science and Operations Research, 7. Clean energy, Industrial and Manufacturing Engineering, 020901 industrial engineering & automation, [INFO]Computer Science [cs], Limit (mathematics), Time complexity, ComputingMilieux_MISCELLANEOUS, Astrophysics::Galaxy Astrophysics, Mathematics, 021103 operations research, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Sizing, Dynamic programming, Constraint (information theory), chemistry, Modeling and Simulation, Greenhouse gas, Carbon
Abstract

International audience; We consider in this paper a single-item lot sizing problem with a periodic carbon emission constraint. In each period, the carbon emission constraint defines an upper limit on the average emission per product. Different modes are available, each one is characterized by its own cost and carbon emission parameters. The problem consists in selecting the modes used in each period such that no carbon emission constraint is violated, and the cost of satisfying all the demands on a given time horizon is minimized. This problem has been introduced in Absi et al. (2013), and has been shown polynomially solvable when only unit carbon emissions are considered. In this paper, we extend the analysis for this constraint to the realistic case of a fixed carbon emission associated with each mode, in addition to its unit carbon emission. We establish that this generalization renders the problem NP-hard. Several dominant properties are presented, and two dynamic programming algorithms are proposed. We also establish that the problem can be solved in polynomial time for a fixed number of modes when carbon emission parameters are stationary.

Full Text
View/download PDF

42. The Impact of Quadratization in Convexification-Based Resolution of Polynomial Binary Optimization

Author

Amelie Lambert, Sourour Elloumi, Arnaud Lazare, Elisabeth Rodriguez-Heck, 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), 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
[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

43. Optimisation du maillage électrique du parc éoliennes off-shore – projet Stationis

Author

Egor Gladkikh, Amelie Lambert, Alain Faye, Dimitri Watel, Marie-Christine Costa, 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), École Nationale Supérieure de Techniques Avancées (ENSTA Paris), CEDRIC. Optimisation Combinatoire (CEDRIC - OC), 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), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE), 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), and Lambert, Amélie

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

Catalog

Books, media, physical & digital resources
See catalog results