| Malapert A and Nattaf M (2021), "Minimizing Flow Time on a Single Machine with Job Families and Setup Times", In Project Management and Scheduling (PMS2021)., April, 2021. |
BibTeX:
@inproceedings{malapert.nattaf-21,
author = {Arnaud Malapert and Margaux Nattaf},
title = {Minimizing Flow Time on a Single Machine with Job Families and Setup Times},
booktitle = {Project Management and Scheduling (PMS2021)},
year = {2021},
url = {https://hal.archives-ouvertes.fr/hal-02530703}
}
|
| Dersarkissian SB and Malapert A (2020), "Flexibilité et Portabilité pour Embarrassingly Parallel Search", In 21ème Conférence ROADEF., EasyChair Preprint no. 2815. Montpellier, France, February, 2020. |
BibTeX:
@inproceedings{dersarkissian.malapert-20,
author = {Samvel Balassanian Dersarkissian and Arnaud Malapert},
title = {Flexibilité et Portabilité pour Embarrassingly Parallel Search},
booktitle = {21ème Conférence ROADEF},
year = {2020}
}
|
| Nattaf M and Malapert A (2020), "Filtering Rules for Flow Time Minimization in a Parallel Machine Scheduling Problem", In Principles and Practice of Constraint Programming. Cham , pp. 462-477. Springer International Publishing. |
| Abstract: This paper studies the scheduling of jobs of different families on parallel machines with qualification constraints. Originating from semi-conductor manufacturing, this constraint imposes a time threshold between the execution of two jobs of the same family. Otherwise, the machine becomes disqualified for this family. The goal is to minimize both the flow time and the number of disqualifications. Recently, an efficient constraint programming model has been proposed. However, when priority is given to the flow time objective, the efficiency of the model can be improved. |
BibTeX:
@inproceedings{nattaf.malapert-20,
author = {Nattaf, Margaux and Malapert, Arnaud},
editor = {Simonis, Helmut},
title = {Filtering Rules for Flow Time Minimization in a Parallel Machine Scheduling Problem},
booktitle = {Principles and Practice of Constraint Programming},
publisher = {Springer International Publishing},
year = {2020},
pages = {462--477}
}
|
| Vlk M, Novak A, Hanzalek Z and Malapert A (2020), "Non-overlapping Sequence-Dependent Setup Scheduling with Dedicated Tasks", In Operations Research and Enterprise Systems. Cham , pp. 23-46. Springer International Publishing. |
| Abstract: The paper deals with a parallel machines scheduling problem with dedicated tasks with sequence-dependent setup times that are subject to the non-overlapping constraint. This problem emerges in the productions where only one machine setter is available on the shop floor. We consider that setups are performed by a single person who cannot serve more than one machine at the same moment, i.e., the setups must not overlap in time. We show that the problem remains $$backslashmathcal NP$$-hard under the fixed sequence of tasks on each machine. To solve the problem, we propose an Integer Linear Programming formulation, five Constraint Programming models, and a hybrid heuristic algorithm LOFAS that leverages the strength of Integer Linear Programming for the Traveling Salesperson Problem (TSP) and the efficiency of Constraint Programming at sequencing problems minimizing makespan. Furthermore, we investigate the impact of the TSP solution quality on the overall objective value. The results show that LOFAS with a heuristic TSP solver achieves on average 10.5% worse objective values but it scales up to 5000 tasks with 5 machines. |
BibTeX:
@inproceedings{vlk.ea-20,
author = {Vlk, Marek and Novak, Antonin and Hanzalek, Zdenek and Malapert, Arnaud},
editor = {Parlier, Greg H. and Liberatore, Federico and Demange, Marc},
title = {Non-overlapping Sequence-Dependent Setup Scheduling with Dedicated Tasks},
booktitle = {Operations Research and Enterprise Systems},
publisher = {Springer International Publishing},
year = {2020},
pages = {23--46}
}
|
| Idrissi AK, Malapert A and Jolin R (2019), "Flight Radius Algorithms", In Proceedings of the 8th International Conference on Operations Research and Enterprise Systems, ICORES 2019, Prague, Czech Republic, February 19-21, 2019. , pp. 370-377. SciTePress. |
| Abstract: In this article, we present the flight radius problem (FRP) on the condensed flight network. The problem is derived from a decision tool for airline managers to analyze and simulate a new market. It concerns the network design and visualization when allocating a new flight. The flight radius problem consists in finding routes passing through a specific flight that represent business opportunities, for instance, regarding time and cost criteria. It is formulated as finding a maximal subgraph of nodes belonging to routes satisfying a regret constraint. This constraint is defined as a function of the optimal values of the time, distance, and cost criteria. We propose to compare four algorithms: two algorithms that decompose the FRP in shortest path problems (SPP) and solved them in parallel using either the Dijkstra or Bellman algorithm; the third algorithm extends the Dijkstra algorithm to avoid useless computations; the fourth algorithm extends the Bellman algorithm to compute all shortest paths for all criteria at once. These four algorithms perform parallel computation when it is possible. The experimental evaluation demonstrates that the best algorithm is the third one that meets the real-time constraints of the targeted industrial application. |
BibTeX:
@inproceedings{idrissi.ea-19,
author = {Assia Kamal Idrissi and Arnaud Malapert and Rémi Jolin},
editor = {Greg H. Parlier and Federico Liberatore and Marc Demange},
title = {Flight Radius Algorithms},
booktitle = {Proceedings of the 8th International Conference on Operations Research and Enterprise Systems, ICORES 2019, Prague, Czech Republic, February 19-21, 2019},
publisher = {SciTePress},
year = {2019},
pages = {370--377},
url = {https://doi.org/10.5220/0007388503700377},
doi = {10.5220/0007388503700377}
}
|
| Malapert A and Nattaf M (2019), "A New CP-Approach for a Parallel Machine Scheduling Problem with Time Constraints on Machine Qualifications", In Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 16th International Conference, CPAIOR 2019, Thessaloniki, Greece, June 4-7, 2019, Proceedings. Vol. 11494, pp. 426-442. Springer. |
| Abstract: This paper considers the scheduling of job families on parallel machines with time constraints on machine qualifications. In this problem, each job belongs to a family and a family can only be executed on a subset of qualified machines. In addition, machines can lose their qualifications during the schedule. Indeed, if no job of a family is scheduled on a machine during a given amount of time, the machine loses its qualification for this family. The goal is to minimize the sum of job completion times, i.e. the flow time, while maximizing the number of qualifications at the end of the schedule. The paper presents a new Constraint Programming (CP) model taking more advantages of the CP feature to model machine disqualifications. This model is compared with two existing models: an Integer Linear Programming (ILP) model and a Constraint Programming model. The experiments show that the new CP model outperforms the other model when the priority is given to the number of disqualifications objective. Furthermore, it is competitive with the other model when the flow time objective is prioritized. |
BibTeX:
@inproceedings{malapert.nattaf-19,
author = {Arnaud Malapert and Margaux Nattaf},
editor = {Louis-Martin Rousseau and Kostas Stergiou},
title = {A New CP-Approach for a Parallel Machine Scheduling Problem with Time Constraints on Machine Qualifications},
booktitle = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 16th International Conference, CPAIOR 2019, Thessaloniki, Greece, June 4-7, 2019, Proceedings},
publisher = {Springer},
year = {2019},
volume = {11494},
pages = {426--442},
url = {https://doi.org/10.1007/978-3-030-19212-9_28},
doi = {10.1007/978-3-030-19212-9\_28}
}
|
| Régin J-C and Malapert A (2018), "Parallel Constraint Programming", In Handbook of Parallel Constraint Reasoning. Cham , pp. 337-379. Springer International Publishing. |
| Abstract: Constraint programming (CP) is an efficient technique for solving combinatorial optimization problems. In CP a problem is defined over variables that take values in domains and constraints which restrict the allowed combination of values. CP uses for each constraint an algorithm that removes values of variables that are inconsistent with the constraint. These algorithms are called while a domain is modified. Then, a search algorithm such as a backtracking or branch-and-bound algorithm is called to find solutions. Several methods have been proposed to combine CP with parallelism. In this chapter, we present some of them: parallelization of the propagator, parallel propagation, search splitting, also called work-stealing, problem decomposition, also called embarrassingly parallel search (EPS), and portfolio approaches. We detail the two giving the best performances in practice: the work-stealing approach and embarrassingly parallel search. We give some experiments supporting this claim on a single multi-core machine, on a data center and on the cloud. |
BibTeX:
@inbook{regin.malapert-18,
author = {Régin, Jean-Charles and Malapert, Arnaud},
editor = {Hamadi, Youssef and Sais, Lakhdar},
title = {Parallel Constraint Programming},
booktitle = {Handbook of Parallel Constraint Reasoning},
publisher = {Springer International Publishing},
year = {2018},
pages = {337--379},
url = {https://doi.org/10.1007/978-3-319-63516-3_9},
doi = {10.1007/978-3-319-63516-3_9}
}
|
| Idrissi AK, Malapert A and Jolin R (2017), "The route network development based on QSI models", In Doctoral Program of the International Conference on Operations Research and Enterprise Systems (ICORES 2017)., February, 2017. , pp. 3-11. |
BibTeX:
@inproceedings{idrissi.ea-17,
author = {Assia Kamal Idrissi and Arnaud Malapert and Rémi Jolin},
title = {The route network development based on QSI models},
booktitle = {Doctoral Program of the International Conference on Operations Research and Enterprise Systems (ICORES 2017)},
year = {2017},
pages = {3--11},
url = {https://hal.archives-ouvertes.fr/hal-01514375}
}
|
| Julia S, Malapert A and Provillard J (2017), "A Synergic Approach to the Minimal Uncompletable Words Problem", Journal of Automata, Languages and Combinatorics. Vol. 22(4), pp. 271-286. |
| Abstract: A finite language X over an alphabet § is complete if any word in * is a factor of a word in X^*. A word which is not a factor of X^* is said uncompletable. Among them, some are minimal as all their proper factors belong to Fact(X^*). The problem is to find bounds on the length of the shortest minimal uncompletable words depending on k, the maximal length of words in X. Though Restivo's conjecture stating an upper bound in 2k^2 was already contradicted twice, the problem of the existence of a quadratic upper bound is still open. Our approach is original and synergic. We start by characterizing minimal uncompletable words. An efficient in practice algorithm is given that speeds up the search of such words. Finally, a genetic algorithm using a SAT-solver allows us to obtain new results for the first values of k. |
BibTeX:
@article{julia.ea-17,
author = {Sandrine Julia and Arnaud Malapert and Julien Provillard},
title = {A Synergic Approach to the Minimal Uncompletable Words Problem},
journal = {Journal of Automata, Languages and Combinatorics},
year = {2017},
volume = {22},
number = {4},
pages = {271--286},
url = {https://doi.org/10.25596/jalc-2017-271},
doi = {10.25596/jalc-2017-271}
}
|
| Malapert A and Kuusinen J-M (2017), "Estimation of elevator passenger traffic based on the most likely elevator trip origin-destination matrices", Building Services Engineering Research and Technology., April, 2017. Vol. 38(5), pp. 563-579. |
| Abstract: We present a constraint programming formulation for the elevator trip origin-destination matrix estimation problem using a lexicographic bi-criteria optimization method where least squares minimization is applied to the measured counts and the minimum information or the maximum entropy approach to the whole matrix. An elevator trip consists of successive stops in one direction of travel with passengers inside the elevator. It can be defined as a directed network, where the nodes correspond to the stops on the trip and the arcs to the possible origins and destinations of the passengers. The goal is to estimate the most likely counts of passengers for the origin-destination pairs of every elevator trip occurring in a building that are consistent with the measured boarding and alighting counts and any prior information about the trip matrix. These counts are used to make passenger traffic forecasts which, in turn, are used in elevator dispatching to reduce uncertainties related to future passengers and therefore to improve passenger service level. Artificial test data was obtained by simulations of lunch hour traffic in a typical multi-story office building. This resulted in complex problem instances that enable robust performance and quality testing. The results show that the proposed approach outperforms previous alternatives in terms of quality, and can take an advantage of prior information. In addition, the proposed approach satisfies real time elevator group control requirements for estimating elevator trip origin-destination matrices.Practical application: The elevator trip origin-destination matrix estimation problem is important since it makes it possible to obtain complete information and statistics about the elevator passenger traffic. The statistics can be used to model future passengers which, when taken into account in the elevator group control, helps to improve passenger service level. Simulation experiments show that most of the problems occurring in reality can be solved within a reasonable time considering a real application, and the solving algorithms are relatively easy to implement using available constraint programming tools. Hence, this work is undoubtedly of interest to the building and elevator industry. |
BibTeX:
@article{malapert.kuusinen-17,
author = {Arnaud Malapert and Juha-Matti Kuusinen},
title = {Estimation of elevator passenger traffic based on the most likely elevator trip origin-destination matrices},
journal = {Building Services Engineering Research and Technology},
year = {2017},
volume = {38},
number = {5},
pages = {563--579},
url = {http://dx.doi.org/10.1177/0143624417707875},
doi = {10.1177/0143624417707875}
}
|
| Malapert A, Régin J-C and Rezgui M (2016), "Embarrassingly Parallel Search in Constraint Programming", J. Artif. Intell. Res. (JAIR)., November, 2016. Vol. 57, pp. 421 - 464. |
| Abstract: We introduce an Embarrassingly Parallel Search (EPS) method for solving constraint problems in parallel, and we show that this method matches or even outperforms state-of-the-art algorithms on a number of problems using various computing infrastructures. EPS is a simple method in which a master decomposes the problem into many disjoint subproblems which are then solved independently by workers. Our approach has three advantages: it is an efficient method; it involves almost no communication or synchronization between workers; and its implementation is made easy because the master and the workers rely on an underlying constraint solver, but does not require to modify it. This paper describes the method, and its applications to various constraint problems (satisfaction, enumeration, optimization). We show that our method can be adapted to different underlying solvers (Gecode, Choco2, OR-tools) on different computing infrastructures (multi-core, data centers, cloud computing). The experiments cover unsatisfiable, enumeration and optimization problems, but do not cover first solution search because it makes the results hard to analyze. The same variability can be observed for optimization problems, but at a lesser extent because the optimality proof is required. EPS offers good average performance, and matches or outperforms other available parallel implementations of Gecode as well as some solvers portfolios. Moreover, we perform an in-depth analysis of the various factors that make this approach efficient as well as the anomalies that can occur. Last, we show that the decomposition is a key component for efficiency and load balancing. |
BibTeX:
@article{malapert.ea-16,
author = {Malapert, Arnaud and Régin, Jean-Charles and Rezgui, Mohamed},
title = {Embarrassingly Parallel Search in Constraint Programming},
journal = {J. Artif. Intell. Res. (JAIR)},
year = {2016},
volume = {57},
pages = {421 -- 464},
url = {http://jair.org/papers/paper5247.html},
doi = {10.1613/jair.5247}
}
|
| Boussemart F, Lecoutre C, Malapert A and Piette C (2015), "About Benchmarking and Competitions of Solvers in Constraint Programming", In Workshop on the International Planning Competition. |
BibTeX:
@inproceedings{boussemart.ea-15,
author = {Frédéric Boussemart and Christophe Lecoutre and Arnaud Malapert and Cédric Piette},
title = {About Benchmarking and Competitions of Solvers in Constraint Programming},
booktitle = {Workshop on the International Planning Competition},
year = {2015}
}
|
| Kuusinen J-M and Malapert A (2014), "The Effect of Randomization on Constraint Based Estimation of Elevator Trip Origin-Destination Matrices", In Lift Symposium.. Thesis at: INRIA. Northampton, England, September, 2014. |
| Abstract: We present a constraint programming formulation for the elevator trip origin-destination matrix estimation problem, and study different deterministic and randomized algorithms to solve the problem. An elevator trip consists of successive stops in one direction of travel with passengers inside the elevator. It can be defined as a directed network, where the nodes correspond to the stops on the trip, and the arcs to the possible origins and destinations of the passengers. The goal is to estimate the count of passengers for the origin-destination pairs of every elevator trip occurring in a building. These counts can be used to make passenger traffic forecasts which, in turn, can be used in elevator dispatching to reduce uncertainties related to future passengers. The results show that randomized search improves the quality of estimation results. In addition, the proposed approach satisfies real time elevator group control requirements for estimating elevator trip origin-destination matrices. |
BibTeX:
@inproceedings{kuusinen.malapert-14,
author = {Kuusinen, Juha-Matti and Malapert, Arnaud},
title = {The Effect of Randomization on Constraint Based Estimation of Elevator Trip Origin-Destination Matrices},
booktitle = {Lift Symposium},
school = {INRIA},
year = {2014},
url = {http://www.liftsymposium.org/}
}
|
| Malapert A and Lecoutre C (2014), "À propos de la bibliothèque de modèles XCSP", In 10èmes Journées Francophones de Programmation par Contraintes. Angers, France, June, 2014. |
| Abstract: Les bibliothé·ues de modèles (modées et instances) sont couramment utilisées pour évaluer les solveurs et les algorithmes en programmation par contraintes. Elles sont d'un intérêt certain pour l'expérimentation : vaste corpus de modèles, comparaison et reproductibilité. Toutefois, ces bibliothèques doivent être régulièement examinées avec attention pour évaluer la pérennité de leur intérét. Dans cet article, nous discutons de la classification des modèles, sous l'angle de la comparaison de solveurs. Ces réflexions sont étayées par les résultats d'un portfolio de solveurs utilisant les solveurs Choco2 et AbsCon sur la bibliothèque XCSP 2.1. |
BibTeX:
@inproceedings{malapert.lecoutre-14,
author = {Arnaud Malapert and Christophe Lecoutre},
title = {À propos de la bibliothèque de modèles XCSP},
booktitle = {10èmes Journées Francophones de Programmation par Contraintes},
year = {2014}
}
|
| Régin J-C, Rezgui M and Malapert A (2014), "Improvement of the Embarrassingly Parallel Search for Data Centers", In Principles and Practice of Constraint Programming: 20th International Conference, CP 2014, Lyon, France, September 8-12, 2014. Proceedings. Cham Vol. 8656, pp. 622-635. Springer International Publishing. |
| Abstract: We propose an adaptation of the Embarrassingly Parallel Search (EPS) method for data centers. EPS is a simple but efficient method for parallel solving of CSPs. EPS decomposes the problem in many distinct subproblems which are then solved independently by workers. EPS performed well on multi-cores machines (40), but some issues arise when using more cores in a datacenter. Here, we identify the decomposition as the cause of the degradation and propose a parallel decomposition to address this issue. Thanks to it, EPS gives almost linear speedup and outperforms work stealing by orders of magnitude using the Gecode solver. |
BibTeX:
@incollection{regin.ea-14,
author = {Régin, Jean-Charles and Rezgui, Mohamed and Malapert, Arnaud},
editor = {O'Sullivan, Barry},
title = {Improvement of the Embarrassingly Parallel Search for Data Centers},
booktitle = {Principles and Practice of Constraint Programming: 20th International Conference, CP 2014, Lyon, France, September 8-12, 2014. Proceedings},
publisher = {Springer International Publishing},
year = {2014},
volume = {8656},
pages = {622-635},
url = {http://dx.doi.org/10.1007/978-3-319-10428-7_45},
doi = {10.1007/978-3-319-10428-7_45}
}
|
| Rezgui M, Régin J-C and Malapert A (2014), "Using Cloud Computing for Solving Constraint Programming Problems", In First Workshop on Cloud Computing and Optimization, a conference workshop of CP 2014. Lyon, France, September, 2014. |
| Abstract: We propose to use cloud computing for solving constraint programing problems in parallel. We used the Embarrassingly Parallel Search (EPS) method in conjunction with Microsoft Azure, the cloud computing platform and infrastructure, created by Microsoft. EPS decomposes the problem in many distinct subproblems which are then solved independently by workers. EPS has three advantages: it is an efficient method, it is simple to deploy and it involves almost no communication between workers. Thus, EPS is particularly well-suited method for being used on cloud infrastructure. Experimental results show ratio of gain equivalent to those obtained for a parallel machine or a data center showing the strength of EPS while using in conjunction with a cloud infrastructure. We also compute the number of cores in a cloud infrastructure requires to improve the resolution by a factor of k and we discuss about the price to pay for solving a given problem in a certain amount of time. |
BibTeX:
@inproceedings{rezgui.ea-14,
author = {Rezgui, Mohamed and Régin, Jean-Charles and Malapert, Arnaud},
title = {Using Cloud Computing for Solving Constraint Programming Problems},
booktitle = {First Workshop on Cloud Computing and Optimization, a conference workshop of CP 2014},
year = {2014}
}
|
| Rezgui M, Régin J-C and Malapert A (2014), "Adaptation de la méthode Embarrassingly Parallel Search pour un centre de calcul", In 10èmes Journées Francophones de Programmation par Contraintes. Angers, France, June, 2014. [BibTeX] |
BibTeX:
@inproceedings{rezgui.ea-14b,
author = {Rezgui, Mohamed and Régin, Jean-Charles and Malapert, Arnaud},
title = {Adaptation de la méthode Embarrassingly Parallel Search pour un centre de calcul},
booktitle = {10èmes Journées Francophones de Programmation par Contraintes},
year = {2014}
}
|
| Malapert A, Régin J-C and Parpaillon J (2013), "The Package Server Location Problem", In International Conference on Operations Research and Enterprise Systems (ICORES)., February, 2013. , pp. 193 - 204. SCITEPRESS. |
| Abstract: In this paper, we introduce a new multi-objective optimization problem derived from a real-world application: the package server location problem. A number of package servers are to be located at nodes of a network. Demand for these package servers is located at each node, and a subset of nodes are to be chosen to locate one or more package servers. Each client is statically associated to a package server. The objective is to minimize the number of package servers while maximizing the efficiency and the reliability of the broadcast of packages to clients. These objectives are contradictory: the broadcast becomes more efficient as the number of servers increases. This problem is analyzed as a multi-objective optimization problem and a mathematical formulation is proposed. In addition, the criteria combination can be specified via a small dedicated language. Results for exact multi-objective solution approaches based on mixed integer linear programming are reported. |
BibTeX:
@inproceedings{malapert.ea-13,
author = {Arnaud Malapert and Jean-Charles Régin and Jean Parpaillon},
editor = {Begoña Vitoriano and Fernando Valente},
title = {The Package Server Location Problem},
booktitle = {International Conference on Operations Research and Enterprise Systems (ICORES)},
publisher = {SCITEPRESS},
year = {2013},
pages = {193 -- 204},
note = {ISBN: 978-989-8565-40-2},
url = {http://www.icores.org},
doi = {10.5220/0004282501930204}
}
|
| Malapert A, Cambazard H, Guéret C, Jussien N, Langevin A and Rousseau L-M (2013), "An Optimal Constraint Programming Approach to the Open-Shop Problem", In International Conference on Automated Planning and Scheduling., June 10--14, 2013. AAAI. |
| Abstract: This is a summary of the journal article (Malapert et al. 2012) published by Journal on Computing entitled "An Optimal Constraint Programming Approach to the Open-Shop Problem". The article presents an optimal constraint programming approach for the Open-Shop scheduling problem, which integrates recent constraint propagation and branching techniques with new upper bound heuristics. Randomized restart policies combined with nogood recording allow to search diversification and learning from restarts. his approach is compared with the best-known metaheuristics and exact algorithms, and shows better results on a wide range of benchmark instances. |
BibTeX:
@inproceedings{malapert.ea-13b,
author = {Arnaud Malapert and Hadrien Cambazard and Christelle Guéret and Narendra Jussien and André Langevin and Louis-Martin Rousseau},
editor = {Daniel Borrajo and Subbarao Kambhampati and Angelo Oddi and Simone Fratini},
title = {An Optimal Constraint Programming Approach to the Open-Shop Problem},
booktitle = {International Conference on Automated Planning and Scheduling},
publisher = {AAAI},
year = {2013}
}
|
| Régin J-C, Rezgui M and Malapert A (2013), "Embarrassingly Parallel Search", In Principles and Practice of Constraint Programming: 19th International Conference, CP 2013, Uppsala, Sweden, September 16-20, 2013. Proceedings. Vol. 8124, pp. 596-610. Springer Berlin Heidelberg. |
| Abstract: We propose the Embarrassingly Parallel Search, a simple and efficient method for solving constraint programming problems in parallel. We split the initial problem into a huge number of independent subproblems and solve them with available workers, for instance cores of machines. The decomposition into subproblems is computed by selecting a subset of variables and by enumerating the combinations of values of these variables that are not detected inconsistent by the propagation mechanism of a CP Solver. The experiments on satisfaction problems and optimization problems suggest that generating between thirty and one hundred subproblems per worker leads to a good scalability. We show that our method is quite competitive with the work stealing approach and able to solve some classical problems at the maximum capacity of the multi-core machines. Thanks to it, a user can parallelize the resolution of its problem without modifying the solver or writing any parallel source code and can easily replay the resolution of a problem. |
BibTeX:
@incollection{regin.ea-13,
author = {Régin, Jean-Charles and Rezgui, Mohamed and Malapert, Arnaud},
editor = {Schulte, Christian},
title = {Embarrassingly Parallel Search},
booktitle = {Principles and Practice of Constraint Programming: 19th International Conference, CP 2013, Uppsala, Sweden, September 16-20, 2013. Proceedings},
publisher = {Springer Berlin Heidelberg},
year = {2013},
volume = {8124},
pages = {596-610},
url = {http://dx.doi.org/10.1007/978-3-642-40627-0_45},
doi = {10.1007/978-3-642-40627-0_45}
}
|
| Malapert A, Cambazard H, Guéret C, Jussien N, Langevin A and Rousseau L-M (2012), "An Optimal Constraint Programming Approach to the Open-Shop Problem", INFORMS Journal on Computing. Vol. 24(2), pp. 228-244. |
| Abstract: This paper presents an optimal constraint programming approach for the open-shop scheduling problem, which integrates recent constraint propagation and branching techniques with new upper bound heuristics. Randomized restart policies combined with nogood recording allow us to search diversification and learning from restarts. This approach is compared with the best-known metaheuristics and exact algorithms, and it shows better results on a wide range of benchmark instances. |
BibTeX:
@article{malapert.ea-12,
author = {Arnaud Malapert and Hadrien Cambazard and Christelle Guéret and Narendra Jussien and André Langevin and Louis-Martin Rousseau},
title = {An Optimal Constraint Programming Approach to the Open-Shop Problem},
journal = {INFORMS Journal on Computing},
year = {2012},
volume = {24},
number = {2},
pages = {228--244},
url = {http://joc.journal.informs.org/content/24/2/228.abstract},
doi = {10.1287/ijoc.1100.0446}
}
|
| Malapert A, Guéret C and Rousseau L-M (2012), "A Constraint Programming Approach for a Batch Processing Problem with Non-identical Job Sizes", European Journal of Operational Research. Vol. 221(3), pp. 533 - 545. |
| Abstract: This paper presents a constraint programming approach for a batch processing machine on which a finite number of jobs of non-identical sizes must be scheduled. A parallel batch processing machine can process several jobs simultaneously and the objective is to minimize the maximal lateness. The constraint programming formulation proposed relies on the decomposition of the problem into finding an assignment of the jobs to the batches, and then minimizing the lateness of the batches on a single machine. This formulation is enhanced by a new optimization constraint which is based on a relaxed problem and applies cost-based domain filtering techniques. Experimental results demonstrate the efficiency of cost-based domain filtering techniques. Comparisons to other exact approaches clearly show the benefits of the proposed approach: it can optimally solve problems that are one order of magnitude greater than those solved by a mathematical formulation or by a branch-and-price. |
BibTeX:
@article{malapert.ea-12a,
author = {Arnaud Malapert and Christelle Guéret and Louis-Martin Rousseau},
title = {A Constraint Programming Approach for a Batch Processing Problem with Non-identical Job Sizes},
journal = {European Journal of Operational Research},
year = {2012},
volume = {221},
number = {3},
pages = {533 - 545},
url = {http://www.sciencedirect.com/science/article/pii/S0377221712002846},
doi = {10.1016/j.ejor.2012.04.008}
}
|
| Malapert A, Demassey S and Régin J-C (2012), "Beyond Cmax: an optimization-oriented framework for constraint-based scheduling". Thesis at: INRIA., April, 2012. (ISRN I3S/RR-2012-07-FR) |
| Abstract: This paper presents a framework taking advantage of both the flexibility of constraint programming and the efficiency of operations research algorithms for solving scheduling problems under various objectives and constraints. Built upon a constraint programming engine, the framework allows the use of scheduling global constraints, and it offers, in addition, a modular and simplified way to perform optimality reasoning based on well-known scheduling relaxations. We present a first instantiation on the single machine problem with release dates and lateness minimization. Beyond the simplicity of use, the ptimizationoriented framework appears to be, from the experiments, effective for dealing with such a pure problem even without any ad-hoc heuristics. |
BibTeX:
@techreport{malapert.ea-12e,
author = {Malapert, Arnaud and Demassey, Sophie and Régin, Jean-Charles},
title = {Beyond Cmax: an optimization-oriented framework for constraint-based scheduling},
school = {INRIA},
year = {2012},
number = {ISRN I3S/RR-2012-07-FR},
url = {http://hal.archives-ouvertes.fr/hal-00976994}
}
|
| Malapert A and Régin J-C (2012), "Propagation de contraintes arithmétiques", In 8èmes Journées Francophones de Programmation par Contraintes. Toulouse, France, May, 2012. , pp. 202-205. |
| Abstract: We consider the resolution by constraint programming of large problems, i.e. involving millions of constraints, which mainly imply arithmetic constraints, like shortest path problems or other related problems. We show that a simple constraint programming model is not competitive with dedicated algorithms (or dedicated constraints). This mainly comes from the propagation mechanism, i.e. the ordering along which the constraints are revised. Thus, we propose a modification of this propagation mechanism integrating the main ideas of the dedicated algorithms. We give some experiments for the shortest path problem and more general problems which confirms the robustness of our approach. Last, we give some results showing that only a few variables are considered more than once during a propagation step. |
BibTeX:
@inproceedings{malapert.regin-12,
author = {Arnaud Malapert and Jean-Charles Régin},
title = {Propagation de contraintes arithmétiques},
booktitle = {8èmes Journées Francophones de Programmation par Contraintes},
year = {2012},
pages = {202--205}
}
|
| Malapert A and Régin J-C (2012), "A note on arithmetic constraint propagation". Thesis at: Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Equipe CEP , Université Nice Sophia Antipolis - UNS., April, 2012. (I3S/RR-2012-03-FR) |
| Abstract: We consider the resolution by constraint programming of large problems, i.e. involving millions of constraints, which mainly imply arithmetic constraints, like shortest path problems or other related problems. We show that a simple constraint programming model is not competitive with dedicated algorithms (or dedicated constraints). This mainly comes from the propagation mechanism, i.e. the ordering along which the constraints are revised. Thus, we propose a modification of this propagation mechanism integrating the main ideas of the dedicated algorithms. We give some experiments for the shortest path problem and more general problems which confirms the robustness of our approach. Last, we give some results showing that only a few variables are considered more than once during a propagation step. |
BibTeX:
@techreport{malapert.regin-12b,
author = {Malapert, Arnaud and Régin, Jean-Charles},
title = {A note on arithmetic constraint propagation},
school = {Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Equipe CEP , Université Nice Sophia Antipolis - UNS},
year = {2012},
number = {I3S/RR-2012-03-FR},
url = {http://hal.archives-ouvertes.fr/hal-00690317}
}
|
| Malapert A (2012), "Shop and batch scheduling with constraints", A Quarterly Journal of Operations Research (4OR). Vol. 10(4), pp. 397-398. Springer Berlin / Heidelberg. |
BibTeX:
@article{malapert-12,
author = {Malapert, Arnaud},
title = {Shop and batch scheduling with constraints},
journal = {A Quarterly Journal of Operations Research (4OR)},
publisher = {Springer Berlin / Heidelberg},
year = {2012},
volume = {10},
number = {4},
pages = {397--398},
url = {http://dx.doi.org/10.1007/s10288-011-0196-2},
doi = {10.1007/s10288-011-0196-2}
}
|
| Rezgui M, Régin J-C and Malapert A (2012), "Recherche basée sur la substituabilité: une stratégie de recherche efficace pour énumérer toutes les solutions", In 8èmes Journées Francophones de Programmation par Contraintes. Toulouse, France, May, 2012. , pp. 282-287. |
| Abstract: Nous introduisons une nouvelle stratégie de recherche pour énumérer toutes les solutions d'un problème de satisfaction de contraintes. L'idée principale de cette stratégie consiste á énumérer des solutions génériques á partir desquelles toutes les solutions peuvent é»re efficacement calculées. Les solutions génériques contiennent des valeurs qui sont substituables á toutes les autres. Notre stratégie provoque l'apparition des valeurs substituables. Ainsi, á la différence d'une stratégie de recherche classique, notre méthode économise du temps en générant seulement quelques solutions génériques. Nous montrons expérimentalement que notre approche donne des résultats intéressants sur des problèmes ayant un grand nombre de solutions. |
BibTeX:
@inproceedings{rezgui.ea-12b,
author = {Mohamed Rezgui and Jean-Charles Régin and and Arnaud Malapert},
title = {Recherche basée sur la substituabilité: une stratégie de recherche efficace pour énumérer toutes les solutions},
booktitle = {8èmes Journées Francophones de Programmation par Contraintes},
year = {2012},
pages = {282--287}
}
|
| Malapert A, Guéret C and Rousseau L-M (2011), "A Constraint Programming Approach for a Batch Processing Problem with Non-identical Job Sizes". Thesis at: École des Mines de Nantes. Nantes, France, June, 2011. (11/6/AUTO) |
| Abstract: This paper presents a constraint programming approach for a batch processing machine on which a finite number of jobs of non-identical sizes must be scheduled. A batch processing machine can process several jobs simultaneously and the objective is to minimize the maximal lateness. The constraint programming formulation proposed relies on the decomposition of the problem into finding an assignment of the jobs to the batches, and then minimizing the lateness of the batches on a single machine. This formulation is enhanced by a new optimization constraint which is based on a relaxed problem and applies cost-based domain filtering techniques. Experimental results demonstrate the efficiency of cost-based domain filtering techniques. Comparisons to other exact approaches clearly show the benefits of the proposed approach: our optimization constraint can optimally solve problems that are one order of magnitude greater than those solved by a mathematical formulation or by a branch-and-price. |
BibTeX:
@techreport{malapert.ea-11,
author = {Arnaud Malapert and Christelle Guéret and Louis-Martin Rousseau},
title = {A Constraint Programming Approach for a Batch Processing Problem with Non-identical Job Sizes},
school = {École des Mines de Nantes},
year = {2011},
number = {11/6/AUTO}
}
|
| Malapert A, Guéret C and Rousseau L-M (2011), "A Constraint Programming Approach for a Batch Processing Problem with Non-identical Job Sizes", In Late Breaking Abstracts of the 8th International Conference on Integration of Artificial Intelligence and Operations Research techniques in Constraint Programming (CPAIOR 2011)., May, 2011. , pp. 23-26. |
BibTeX:
@inproceedings{malapert.ea-11b,
author = {Arnaud Malapert and Christelle Guéret and Louis-Martin Rousseau},
title = {A Constraint Programming Approach for a Batch Processing Problem with Non-identical Job Sizes},
booktitle = {Late Breaking Abstracts of the 8th International Conference on Integration of Artificial Intelligence and Operations Research techniques in Constraint Programming (CPAIOR 2011)},
year = {2011},
pages = {23-26}
}
|
| Malapert A, Guéret C and Rousseau L-M (2011), "A Constraint Programming Approach for a Batch Processing Problem with Non-identical Job Sizes", {INFORMS} 2011 Annual Meeting, Charlotte, USA. November, 2011. |
BibTeX:
@misc{malapert.ea-11c,
author = {Arnaud Malapert and Christelle Guéret and Louis-Martin Rousseau},
title = {A Constraint Programming Approach for a Batch Processing Problem with Non-identical Job Sizes},
howpublished = {{INFORMS} 2011 Annual Meeting, Charlotte, USA},
year = {2011},
url = {http://meetings2.informs.org/charlotte2011/}
}
|
| Malapert A (2011), "Techniques d'ordonnancement d'atelier et de fournées basées sur la programmation par contraintes". Thesis at: Université de Nantes., September, 2011. |
| Abstract: Résoudre un problème d'ordonnancement consiste à organiser un ensemble de tâches, c'est-à-dire déterminer leurs dates de début et de fin et leur attribuer des ressources en respectant certaines contraintes. Dans cette thèse, nous proposons de nouvelles approches exactes basées sur la programmation par contraintes pour deux classes de problèmes d'ordonnancement NP-difficiles validées expérimentalement par l'implémentation d'un ensemble de nouvelles fonctionnalités dans le solveur de contraintes choco. \ Dans un problème d'atelier, n lots sont constitués chacun de m tâches à exécuter sur m machines distinctes. Chaque machine ne peut exécuter qu'une tâche à la fois. La nature des contraintes liant les tâches d'un mï¾ï½ªme lot peut varier (séquencement global ou par lot, pas de séquencement). Le critère d'optimalité étudié est la minimisation du délai total. Nous proposons d'abord une étude et une classification des différents modèles et algorithmes de résolution. Ensuite, nous introduisons une nouvelle approche flexible pour ces problèmes classiques. \ Une machine à traitement par fournées peut traiter plusieurs tâches en une seule opération, une fournée. Les dates de début et de fin des tâches d'une mï¾ï½ªme fournée sont identiques. Le problème étudié consiste à minimiser le retard algébrique maximal de n tâches de différentes tailles sur une machine de capacité b. Conjointement, la somme des tailles des tâches d'une fournée ne doit pas excéder la capacité b. Nous proposons, dans ce contexte, un modèle basé sur une décomposition du problème. Nous définissons ensuite une nouvelle contrainte pour l'optimisation basée sur une relaxation du problème qui améliore sa résolution. |
BibTeX:
@phdthesis{malapert-11,
author = {Arnaud Malapert},
title = {Techniques d'ordonnancement d'atelier et de fournées basées sur la programmation par contraintes},
school = {Université de Nantes},
year = {2011}
}
|
| Badr AM, Malapert A and Brown KN (2010), "Modelling a Maintenance Scheduling Problem with Alternative Resources", In The 9th International Workshop on Constraint Modelling and Reformulation (ModRef10). St. Andrews, Scotland, September, 2010. |
| Abstract: Effective management of maintenance in buildings can have a significant impact on the total life cycle costs and on the building energy use. Nevertheless, the building maintenance scheduling problem has been infrequently studied. In this paper, we present constraint-based scheduling models for the building maintenance scheduling problem, where each activity has a set of alternative resources. We consider two different models, one using basic constraints, and the other using our new and modifed global constraints, which handle alternative disjunctive resources for each activity to allow propagation before activities are assigned to resources. We evaluate these models on randomly generated problems and show that while the basic model is faster on smaller problems, the global constraint model scales better. |
BibTeX:
@inproceedings{badr.ea-10,
author = {Aliaa M. Badr and Arnaud Malapert and Kenneth N. Brown},
title = {Modelling a Maintenance Scheduling Problem with Alternative Resources},
booktitle = {The 9th International Workshop on Constraint Modelling and Reformulation (ModRef10)},
year = {2010},
url = {http://www.it.uu.se/research/group/astra/ModRef10/}
}
|
| Grimes D, Hebrard E and Malapert A (2009), "Closing the Open Shop: Contradicting Conventional Wisdom", In Proceedings of the 15th International Conference on Principles and Practice of Constraint Programming (CP 2009)., September, 2009. Vol. 5372, pp. 400-408. Springer. |
| Abstract: This paper describes a new approach for solving disjunctive temporal problems such as the open shop and job shop scheduling domains. Much previous research in systematic search approaches for these problems has focused on developing problem specific constraint propagators and ordering heuristics. Indeed, the common belief is that many of these problems are too difficult to solve without such domain specific models. We introduce a simple constraint model that combines a generic adaptive heuristic with naive propagation, and show that it often outperforms state-of-the-art solvers for both open shop and job shop problems. |
BibTeX:
@inproceedings{grimes.ea-09,
author = {Diarmuid Grimes and Emmanuel Hebrard and Arnaud Malapert},
editor = {Ian P. Gent},
title = {Closing the Open Shop: Contradicting Conventional Wisdom},
booktitle = {Proceedings of the 15th International Conference on Principles and Practice of Constraint Programming (CP 2009)},
publisher = {Springer},
year = {2009},
volume = {5372},
pages = {400--408},
url = {http://www.springerlink.com/content/185388818586r18h/},
doi = {10.1007/978-3-642-04244-7_33}
}
|
| Malapert A, Cambazard H, Guéret C, Jussien N, Langevin A and Rousseau L-M (2009), "An Optimal Constraint Programming Approach to the Open-Shop Problem". Thesis at: Centre Inter-universitaire de Recherche sur les Réseaux d'Entreprise, la Logistique et le Transport. Montréal, Canada (CIRRELT-2009-25) |
| Abstract: This paper presents an optimal constraint programming approach for the Open-Shop problem, which integrates recent constraint propagation and branching techniques with new upper bound heuristics for the Open-Shop problem. Randomized restart policies combined with nogood recording allow to search diversification and learning from restarts. This approach closed all remaining problems of the Brucker et al. and Guéret and Prins benchmarks with cpu times that are orders of magnitude lower than the best known metaheuristics. |
BibTeX:
@techreport{malapert.ea-09,
author = {Arnaud Malapert and Hadrien Cambazard and Christelle Guéret and Narendra Jussien and André Langevin and Louis-Martin Rousseau},
title = {An Optimal Constraint Programming Approach to the Open-Shop Problem},
school = {Centre Inter-universitaire de Recherche sur les Réseaux d'Entreprise, la Logistique et le Transport},
year = {2009},
number = {CIRRELT-2009-25}
}
|
| Malapert A, Guéret C, Jussien N, Langevin A and Rousseau L-M (2008), "Two-dimensional Pickup and Delivery Routing Problem with Loading Constraints", In First CPAIOR Workshop on Bin Packing and Placement Constraints (BPPC'08). Paris, France, May, 2008. |
| Abstract: In this paper, a special case of the vehicle routing problem in which the demands consist in a set of rectangular two-dimensional weighted items is considered. The vehicles have a two-dimensional loading surface and a maximum weight capacity. These problems have a routing and a packing component. A framework to handle the loading of a vehicle is proposed. A Constraint Programming loading model based on a scheduling approach is developed. It is also shown that the non-overlapping rectangle constraint can be extended to handle a practical constraint called sequential loading constraint. |
BibTeX:
@inproceedings{malapert.ea-08,
author = {Arnaud Malapert and Christelle Guéret and Narendra Jussien and André Langevin and Louis-Martin Rousseau},
title = {Two-dimensional Pickup and Delivery Routing Problem with Loading Constraints},
booktitle = {First CPAIOR Workshop on Bin Packing and Placement Constraints (BPPC'08)},
year = {2008},
url = {http://contraintes.inria.fr/CPAIOR08/BPPC.html}
}
|
| Malapert A (2006), "Optimisation de tournées de véhicules pour l'exploitation de Réseau Telecom". Thesis at: Université Pierre et Marie Curie (Paris VI) & France Telecom R&D (CORE/M2V/AOC). Issy-les-Moulineaux, France, September, 2006. |
BibTeX:
@mastersthesis{malapert-06,
author = {Arnaud Malapert},
title = {Optimisation de tournées de véhicules pour l'exploitation de Réseau Telecom},
school = {Université Pierre et Marie Curie (Paris VI) & France Telecom R&D (CORE/M2V/AOC)},
year = {2006},
note = {Sous la supervision de Safia Kedad Sidhoum (LIP6), Cédric Chamayou et Matthieu Chardy (France Telecom)}
}
|
Computer Science
My other websites