LIX, École Polytechnique
Groupe Algorithmes et Optimisation: Publications




1  Journal Papers

  1. S. Kucherenko, P. Belotti, L. Liberti, and N. Maculan. New formulations for the kissing number problem. Discrete Applied Mathematics, (accepted).

  2. Marek Chrobak, Christoph Dürr, Wojciech Jawor, Lukasz Kowalik, and Maciej Kurowski. A note on scheduling equal-length jobs to maximize throughput. Journal of Scheduling, to appear.

  3. L. Liberti, E. Amaldi, N. Maculan, and F. Maffioli. Mathematical models and a constructive heuristic for finding minimum fundamental cycle bases. Yugoslav Journal of Operations Research, 15(1), 2005.

  4. L. Liberti and S. Kucherenko. Comparison of deterministic and stochastic approaches to global optimization. International Transactions in Operations Research, 12:263–285, 2005.

  5. L. Liberti. Linearity embedded in nonconvex programs. Journal of Global Optimization, 33(2):157–196, 2005.

  6. Ph. Baptiste and C. Le Pape. Scheduling a single machine to minimize a regular objective function under setup constraints. Discrete Optimization 2, 2:83–99, 2005.

  7. N. Hermann and P. Lescanne. Est-ce que p = np ? Les Dossiers de La Recherche, 20:64–68, août-octobre 2005.

  8. A. Durand, M. Hermann, and P. G. Kolaitis. Subtractive reductions and complete problems for counting complexity classes. Theoretical Computer Science, 340(3):496–513, 2005.

  9. Huy Tran Dac and Ph. Baptiste. Airspace sectorization with constraints. To appear in RAIRO Operations Research, ., 2005.

  10. L. Liberti. Reduction constraints for the global optimization of NLPs. International Transactions in Operations Research, 11(1):34–41, 2004.

  11. L. Liberti. Reformulation and convex relaxation techniques for global optimization. 4OR, 2:255–258, 2004.

  12. Ph. Baptiste and S. Demassey. Tight LP bounds for resource constrained project scheduling. OR Spectrum, 26:251–262, 2004.

  13. Ph. Baptiste, Peter Brucker, Sigrid Knust, and Vadim G. Timkovsky. Ten notes on equal-processing-time scheduling. 4OR: Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 2:111–127, 2004.

  14. Ph. Baptiste and V. Timkovsky. Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time. Mathematical Methods of Operations Research (ZOR), 60(1):145–153, 2004.

  15. Ph. Baptiste, Chrobak, C. Durr, Jawor, and Vakhania. Preemptive scheduling of equal-length jobs to maximize weighted throughput. Operations Research Letters, 32(3):258–264, 2004.

  16. G. Gottlob, M. Hermann, and M. Rusinowitch. 2nd International Workshop on Complexity in Automated Deduction (CiAD). Theory of Computings Systems, 37(6), 2004.

  17. J. Carlier Ph. Baptiste and A. Jouglet. A branch-and-bound procedure to minimize total tardiness on one machine with arbitrary release dates. European Journal of Operational research, 158:595–608, 2004.

  18. L. Liberti and C. C. Pantelides. Convex envelopes of monomials of odd degree. Journal of Global Optimization, 25:157–168, 2003.

  19. E. Amaldi, L. Liberti, N. Maculan, and F. Maffioli. Local search for the minimum fundamental cycle basis problem. Workshop on Real-life Applications of Metaheuristics, December 2003.

  20. Ph. Baptiste. On minimizing the weighted number of late jobs in unit execution time open-shops. European Journal of Operational Research, 149:344–354, 2003.

  21. B. Schieber Ph. Baptiste. A note on scheduling tall/small multiprocessor tasks with unit processing time to minimize maximum tardiness. Journal of Scheduling, 6(4):395–404, 2003.

  22. Ph. Baptiste. A note on scheduling multiprocessor tasks with identical processing times. Computers and Operations Research, 30, 2003.

  23. Ph. Baptiste, Laurent Peridy, and Eric Pinson. A branch and bound to mininimze the number of late jobs on a single machine with release time constraints. European Journal of Operational Research, 144(1):1–11, 2003.

  24. A. Durand, M. Hermann, and L. Juban. On the complexity of recognizing the Hilbert basis of a linear Diophantine system. Theoretical Computer Science, 270(1-2):625–642, 2002.

  25. E. Néron and J. Gupta Ph. Baptiste. Solving hybrid flow shop problem using energetic reasoning and global operations. Omega, 29:501–511, 2001.

  26. Ph. Baptiste and V. G. Timkovsky. On preemption redundancy in scheduling unit processing time jobs on two parallel machines. Operations Research Letters, 28:205–212, 2001.

  27. Ph. Baptiste and A. Jouglet. On minimizing total tardiness in a serial batching problem. RAIRO Operations Research, 35:107–115, 2001.

2  Books

  1. L. Liberti. Introduction to Global Optimization. SMP, Lima, 2004.

  2. Ph. Baptiste, E. Néron, and F. Sourd. Modèles et algorithmes en ordonnancement. Exercice et problèmes corrigés (18 auteurs). Ellipses, 2004.

  3. L. Liberti and N. Maculan, editors. Global Optimization: from Theory to Implementation. Springer, Berlin, (to appear february 2006).

3  Book Chapters

  1. A. Jouglet, Ph. Baptiste, and J. Carlier. HandBook of Scheduling: Algorithms, Models and Performance Analysis, chapter Branch-and-Bound Algorithms for Total Weighted Tardiness. CRC Press, 2004.

  2. Ph. Baptiste and P. Brucker. HandBook of Scheduling: Algorithms, Models and Performance Analysis, chapter Scheduling Equal Processing Time Jobs. CRC Press, 2004.

  3. C. Lavor, L. Liberti, and N. Maculan. Computational experience with the molecular distance geometry problem. In J. Pintér, editor, Global Optimization: Scientific and Engineering Case Studies. Springer, Berlin, (to appear february 2006).

  4. L. Liberti. Writing global optimization software. In L. Liberti and N. Maculan, editors, Global Optimization: from Theory to Implementation, pages 211–262. Springer, Berlin, (to appear february 2006).

4  Proceedings Volumes

  1. L. Liberti and F. Maffioli, editors. CTW04 Workshop on Graphs and Combinatorial Optimization, volume 17 of Electronic Notes in Discrete Mathematics, Amsterdam, 2004. Elsevier.

5  Conference Papers

  1. L. Liberti, N. Maculan, and S. Kucherenko. The kissing number problem: a new result from global optimization. pages 203–207.

  2. E. Amaldi, L. Liberti, N. Maculan, and F. Maffioli. Efficient edge-swapping heuristics for finding minimum fundamental cycle bases. pages 14–29.

  3. E. Amaldi, L. Liberti, N. Maculan, and F. Maffioli. The minimum fundamental cycle basis problem: a new heuristic based on edge swaps. pages 315–317.

  4. Wojciech Jawor, Marek Chrobak, and Christoph Dürr. Competitive analysis of scheduling algorithms for aggregated links. In Proceedings of Latin American Theoretical INformatics (LATIN), page to appear, 2006.

  5. Ph. Baptiste E. Winter. On scheduling a multifunction radar. Paris, France, March 2006. In press.

  6. L. Liberti and M. Drazic. Variable neighbourhood search for the global optimization of constrained NLPs. In Proceedings of GO Workshop, Almeria, Spain, 2005.

  7. E. Winter, Ph. Baptiste, L. Lupinski, and E. Chamouard. Modélisation des problèmes dordonnancement de tâches sur des radars embarqués. In Sixième congrès de la société Française de Recherche Opérationnelle et Aide à la Décision, 2005.

  8. C. Lavor, L. Liberti, and N. Maculan. Grover's algorithm applied to the molecular distance geometry problem. In Proc. of VII Brazilian Congress of Neural Networks, Natal, Brazil, 2005.

  9. L. Liberti, C. Lavor, and N. Maculan. Double VNS for the molecular distance geometry problem. In Proc. of Mini Euro Conference on Variable Neighbourhood Search, Tenerife, Spain, 2005.

  10. D. Savourey, A. Jouglet, and Ph. Baptiste. Règles de dominance pour l'ordonnancement de jobs avec dates de disponibilité sur machines parallèles. In Sixième congrès de la société Française de Recherche Opérationnelle et Aide à la Décision, 2005.

  11. C. Le Pape and Ph. Baptiste. Scheduling a single machine to minimize a regular objective function under setup constraints. In 2nd Multidisciplinary International Conference on Scheduling : Theory and Applications, 2005.

  12. Ph. Baptiste and P. Brucker. Scheduling equal processing time jobs on parallel machines: A survey. In Troisieme Conference Internationale en Informatique Recherche, Innovation & Vision du Futur, Can Tho, Vietnam, 2005.

  13. E. Chamouard E. Winter, Ph. Baptiste, L. Lupinski. Modélisation des problèmes d'ordonnancement de tâches sur des radars embarqués. In Actes de la conference ROADEF 2005, Tours, France, February 2005.

  14. Ph. Baptiste, M. Chrobak, C. Durr, and F. Sourd. Preemptive multi-machine scheduling of equal length jobs to minimize the average flow time. In Models and Algorithms for Planning and Scheduling Problems, Siena, Italy, 2005.

  15. Ph. Baptiste, F. Della Croce, A. Grosso, and V. TKindt. On some compact integer programming formulations of machine scheduling problems. In Sixième congrès de la société Française de Recherche Opérationnelle et Aide à la Décision, 2005.

  16. K. Artiouchine, Ph. Baptiste, and J. Mattioli. Le problème des N-rois : un modèle des systèmes dynamiques. In Sixième congrès de la société Française de Recherche Opérationnelle et Aide à la Décision, 2005.

  17. K. Artiouchine and Ph. Baptiste. Inter-distance constraint: An extension of the all-different constraint for scheduling equal length jobs. In Proc. of the 11th International Conference, CP (Principles and Practice of Constraint Programming), volume 3709 of Lecture Notes in Computer Science, Sitges, Spain, 2005.

  18. C. Gwiggner, Ph. Baptiste, and V. Duong. Conditions et lois : une analyse des données du trafic aérien. In Sixième congrès de la société Française de Recherche Opérationnelle et Aide à la Décision, 2005.

  19. Ph. Baptiste E. Winter, L. Lupinski, E. Chamouard. Optimisation de la gestion des poursuites radar. In Actes des Journée COGIS sur les Nouvelles Formes d'onde en Imagerie Localisation et Communication, Paris, France, March 2005.

  20. D. Savourey, A. Jouglet, Ph. Baptiste, and J. Carlier. Méthode tabou pour minimiser le retard total pondéré sur une machine avec dates de disponibilité. In MOSIM ., 2004.

  21. Ph. Baptiste and Peter Brucker. Scheduling parallel machines to minimize total completion time and total number of late jobs. In Proceedings of the Proc. of the 9th International Workshop on Project Management and Scheduling, 2004.

  22. K. Artiouchine, Ph. Baptiste, and C. Dürr. Runway scheduling with holding loop. In The Second International Workshop DOM Discrete Optimization Methods in Production and Logistics, Omsk - Irkutsk, Russia, 2004.

  23. Ph. Baptiste and Francis Sourd. Lower bounds for the earliness-tardiness scheduling problem on parallel machines. In Proceedings of the Proc. of the 9th International Workshop on Project Management and Scheduling, 2004.

  24. S. Demassey, Ph. Baptiste C. Artigues , and Ph. Michelon. Lagrangean relaxation-based lower bounds for the RCPSP. In Proceedings of the Proc. of the 9th International Workshop on Project Management and Scheduling, 2004.

  25. A. Gil, M. Hermann, G. Salzer, and B. Zanuttini. Efficient algorithms for constraint description problems over finite totally ordered domains. In D. Basin and M. Rusinowitch, editors, Proceedings 2nd International Joint Conference on Automated Reasoning (IJCAR'04). Cork (Ireland), volume 3097 of Lecture Notes in Computer Science, pages 244–258. Springer-Verlag, July 2004.

  26. M. Bauland, P. Chapdelaine, N. Creignou, M. Hermann, and H. Vollmer. An algebraic approach to the complexity of generalized conjunctive queries. In H. H. Hoos and D. G. Mitchell, editors, Proceedings 7th International Conference on Theory and Applications of Satisfiability Testing, (SAT 2004), Vancouver (British Columbia, Canada), volume 3542 of Lecture Notes in Computer Science, pages 30–45. Springer-Verlag, May 2004.

  27. D. Savourey, A. Jouglet, Ph. Baptiste, and Jacques Carlier. A tabu search method to minimize total (weighted) tardiness on one machine with release dates. In Proc. of the 9th International Workshop on Project Management and Scheduling, 2004.

  28. A. Jouglet, Ph. Baptiste, and J. Carlier. The one machine total cost scheduling problem with release dates. In 1st Multidisciplinary International Conference on Scheduling : Theory and Applications, Nottingham, UK., 2003.

  29. Ph. Baptiste and M. Sviridenko. Structural properties of preemptive parallel machine schedules. In Proc. of the Sixth Workshop on Models and Algorithms for Planning and Scheduling Problems, 2003.

  30. Ph. Baptiste and Huy Tran Dac. Sectorisation dynamique de l'espace aérien européen. In Cinquième congrès de la société Française de Recherche Opérationnelle et Aide à la Décision, 2003.

  31. Huy Tran Dac and Ph. Baptiste. Optimized sectorization of airspace with constraints. In 5th Air Traffic Management R&D Seminar, Budapest, 2003.

  32. A. Durand and M. Hermann. The inference problem for propositional circumscription of affine formulas is coNP-complete. In H. Alt and M. Habib, editors, Proceedings 20th Symposium on Theoretical Aspects of Computer Science (STACS 2003), Berlin (Germany), volume 2607 of Lecture Notes in Computer Science, pages 451–462. Springer-Verlag, February 2003.

  33. A. Jouglet, Ph. Baptiste, J. Carlier, and D. Savourey. Dominance based heuristics to minimize a total cost on one machine. In 1st Multidisciplinary International Conference on Scheduling : Theory and Applications, Nottingham, UK., 2003.

  34. Ph. Baptiste and B. Schieber. Scheduling tall/small multiprocessor tasks with unit processing time to minimize maximum tardiness. In Proc. of the 8th International Workshop on Project Management and Scheduling, Valencia, Spain, 2002.

  35. Ph. Baptiste. On preemption redundancy. In Conférence italienne de RO (AIR0 02), , LAquila., 2002.

  36. A. Jouglet and Ph. Baptiste. General techniques to minimize total (weighted) tardiness and total (weighted) flow time on one machine. In INFORMS, San Jose, USA, 2002.

  37. A. Jouglet, Ph. Baptiste, and J. Carlier. Exact procedures for single machine total cost scheduling. In IEEE International Conference on Systems, Man and Cybernetics, Hammamet, Tunisia, 2002.

  38. Ph. Baptiste, J. Carlier, and E. Néron. Bornes et ajustements pour le problème de gestion de projet à contraintes de ressource. In Quatrième congrès de la société Française de Recherche Opérationnelle et Aide à la Décision, 2002.

  39. H. Tran-Dac and Ph. Baptiste. A CP approach for dynamic airspace reconfiguration. In Proc. of the 21st Digital Avionics Systems Conference, Irvine, California, 2002.

  40. A. Jouglet, Ph. Baptiste, and J. Carlier. A branch and bound procedure to minimize total tardiness or total completion time on one machine with different release date. In 8th International Workshop on Project Management and Scheduling, Valencia, Spain, 2002.

  41. Ph. Baptiste. Preemptive scheduling of identical machines. In Fifth Workshop on Models and Algorithms for Planning and Scheduling Problems, 2001.

  42. Ph. Baptiste and V. Timkovsky. On preemption redundancy in scheduling unit processing time jobs on two parallel machines. In International Workshop on Scheduling and Telecommunications (IWST), San Francisco, California, USA, 2001.

  43. A. Jouglet, Ph. Baptiste, and J. Carlier. Minimizing total tardiness on one machine with release dates 1 |ri |ΣTi. In Fifth Workshop on Models and Algorithms for Planning and Scheduling Problems, 2001.

  44. Ph. Baptiste, J. Carlier, and A. Jouglet. Minimiser la somme des retards sur une machine avec dates de disponibilité. In 3eme Conférence Francophone de MOdélisation et SIMulation, 2001.

  45. A. Jouglet, Ph. Baptiste, and Wim Nuijten. Une méthode arborescente pour un problème d'ordonnancement bicritère sur machines parallèles : P|ri|fh(Σwi Ui,Tmax). In Troisième congrès de la société Française de Recherche Opérationnelle et Aide à la Décision, 2000.

  46. A. Jouglet and Ph. Baptiste. Minimizing total tardiness on one machine with release dates. In International Symposium on Math. Prog., Atlanta, 2000.

  47. Ph. Baptiste. Batching identical jobs. In INFORMS National Meeting San-Antonio, also presented at a "Dagstuhl Seminar"., 2000.

  48. Ph. Baptiste and Wim Nuijten. A constraint-based approach to minimize total weighted flow time. In International Symposium on Math. Prog., Atlanta, 2000.

  49. Ph. Baptiste. Ordonnancement de tâches de durées égales. In Deuxième congrès de la société Française de Recherche Opérationnelle et Aide à la Décision, 1999.

  50. Ph. Baptiste and Wim Nuijten. Incorporating new scheduling criteria in constraint-based tools. In INFORMS National Meeting Philadelphia, 1999.

  51. Ph. Baptiste and C. Le Pape. Constraint propagation techniques for cumulative scheduling. In Proc. of the Workshop on Integration of AI and OR techniques in Constraint Programming for Combinatorial Optimization Problems, Ferrare, Italie, 1999.

  52. Ph. Baptiste, L. Péridy, and E. Pinson. An exact procedure for minimizing the number of late jobs on a single machine. In INFORMS National Meeting Cincinnati, Ohio, 1999.

  53. Ph. Baptiste, Y. Caseau, T. Kökény, C. Le Pape, and R. Rodoek. Creating and evaluating hybrid algorithms for inventory management problems. In Journées Nationales sur la Résolution Pratique de Problèmes NP Complets, 1998.

  54. C. Le Pape and Ph. Baptiste. Constraint-based scheduling: A theoretical comparison of resource constraint propagation rules. In Proc. of the Workshop on non-binary constraints, ECAI, 1998.

  55. Ph. Baptiste, J. Carlier, C. Le Pape, and E. Néron. Specialized techniques for solving highly cumulative and highly disjunctive resource constrained project scheduling problems. In Première conférence de la Société Française de Recherche Opérationnelle, 1997.

  56. Ph. Baptiste. A branch and bound procedure for the preemptive job-shop scheduling problem. In Dagstuhl Seminar 97/29, Dagstuhl, 1997.

  57. Ph. Baptiste and C. Le Pape. A constraint-based branch and bound algorithm for preemptive job-shop scheduling. In Proc. of the International Workshop on Production Planning and Control, 1996.

6  Technical Reports

  1. C. Lavor, L. Liberti, N. Maculan, and M. A. Chaer Nascimento. Solving a quantum chemistry problem with deterministic global optimization. Technical Report 1175, www.optimization-online.org, 2005.

  2. T. Davidovic, L. Liberti, N. Maculan, and N. Mladenovic. Mathematical programming-based approach to scheduling of communicating tasks. Technical Report G-2004-99, Cahiers du GERAD, December 2004.

  3. L. Liberti. Automatic reformulation of bilinear MINLPs. Technical Report 2004.24, DEI, Politecnico di Milano, July 2004.
This document was translated from LATEX by HEVEA.