IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v191y2008i3p705-735.html
   My bibliography  Save this article

Combining VNS with constraint programming for solving anytime optimization problems

Author

Listed:
  • Loudni, Samir
  • Boizumault, Patrice

Abstract

This paper presents an hybrid search method for solving on-line optimization problems that are modelled using the vcsp Valued Constraint Satisfaction Problems framework. To each constraint is associated a valuation representing the "cost to pay" when this constraint will be violated by a solution. Our method (VNS/LDS+CP) uses principles of VNS (Variable Neighborhood Search) and combines a partial tree search (Limited Discrepancy Search) with Constraint Propagation in order to compute local optima. Experiments on the CELAR benchmarks demonstrate significant improvements on other competing methods: LNS/CP/GR [Lobjois, L., Lemaitre, M., Verfaillie, G., 2000. Large neighbourhood search using constraint propagation and greedy reconstruction for valued csp resolution. In: Proceedings of the ECAI2000 Workshop on Modelling and Solving Problems with Constraints], another hybrid method using vcsps, and two standard versions of Simulated-Annealing [Li, Y.H., 1997. Directed annealing search in constraint satisfaction and optimization. Ph.D. thesis, Imperial College of Science, Department of Computing]: Quick and Medium. Moreover, VNS/LDS+CP clearly satisfies the key properties of anytime algorithms. Finally, VNS/LDS+CP has been successfully applied to a real-life on-line resource allocation problem in computer networks.

Suggested Citation

  • Loudni, Samir & Boizumault, Patrice, 2008. "Combining VNS with constraint programming for solving anytime optimization problems," European Journal of Operational Research, Elsevier, vol. 191(3), pages 705-735, December.
    • Handle: RePEc:eee:ejores:v:191:y:2008:i:3:p:705-735
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(07)00127-0
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. David Applegate & William Cook, 1991. "A Computational Study of the Job-Shop Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 3(2), pages 149-156, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Dubois-Lacoste, Jérémie & López-Ibáñez, Manuel & Stützle, Thomas, 2015. "Anytime Pareto local search," European Journal of Operational Research, Elsevier, vol. 243(2), pages 369-385.
    2. López-Ibáñez, Manuel & Stützle, Thomas, 2014. "Automatically improving the anytime behaviour of optimisation algorithms," European Journal of Operational Research, Elsevier, vol. 235(3), pages 569-582.
    3. Alexandre D. Jesus & Luís Paquete & Arnaud Liefooghe, 2021. "A model of anytime algorithm performance for bi-objective optimization," Journal of Global Optimization, Springer, vol. 79(2), pages 329-350, February.
    4. Pierre Hansen & Nenad Mladenović & José Moreno Pérez, 2010. "Variable neighbourhood search: methods and applications," Annals of Operations Research, Springer, vol. 175(1), pages 367-407, March.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Sels, Veronique & Craeymeersch, Kjeld & Vanhoucke, Mario, 2011. "A hybrid single and dual population search procedure for the job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 215(3), pages 512-523, December.
    2. Goodchild, Anne V. & Daganzo, Carlos F., 2005. "Crane Double Cycling in Container Ports: Affect on Ship Dwell Time," Institute of Transportation Studies, Research Reports, Working Papers, Proceedings qt9qp7p7jq, Institute of Transportation Studies, UC Berkeley.
    3. Vipul Jain & Ignacio E. Grossmann, 2001. "Algorithms for Hybrid MILP/CP Models for a Class of Optimization Problems," INFORMS Journal on Computing, INFORMS, vol. 13(4), pages 258-276, November.
    4. Rego, César & Duarte, Renato, 2009. "A filter-and-fan approach to the job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 194(3), pages 650-662, May.
    5. Sakawa, Masatoshi & Kubota, Ryo, 2000. "Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy duedate through genetic algorithms," European Journal of Operational Research, Elsevier, vol. 120(2), pages 393-407, January.
    6. Michael Pinedo & Marcos Singer, 1999. "A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(1), pages 1-17, February.
    7. El-Bouri, A. & Azizi, N. & Zolfaghari, S., 2007. "A comparative study of a new heuristic based on adaptive memory programming and simulated annealing: The case of job shop scheduling," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1894-1910, March.
    8. Bahman Naderi & Rubén Ruiz & Vahid Roshanaei, 2023. "Mixed-Integer Programming vs. Constraint Programming for Shop Scheduling Problems: New Results and Outlook," INFORMS Journal on Computing, INFORMS, vol. 35(4), pages 817-843, July.
    9. F. Guerriero, 2008. "Hybrid Rollout Approaches for the Job Shop Scheduling Problem," Journal of Optimization Theory and Applications, Springer, vol. 139(2), pages 419-438, November.
    10. Zapfel, G. & Wasner, M., 2000. "A heuristic solution concept for a generalized machine sequencing problem with an application to radiator manufacturing," International Journal of Production Economics, Elsevier, vol. 68(2), pages 199-213, November.
    11. Pisut Pongchairerks, 2019. "A Two-Level Metaheuristic Algorithm for the Job-Shop Scheduling Problem," Complexity, Hindawi, vol. 2019, pages 1-11, March.
    12. Francis Sourd & Wim Nuijten, 2000. "Multiple-Machine Lower Bounds for Shop-Scheduling Problems," INFORMS Journal on Computing, INFORMS, vol. 12(4), pages 341-352, November.
    13. Thomalla, Christoph S., 2001. "Job shop scheduling with alternative process plans," International Journal of Production Economics, Elsevier, vol. 74(1-3), pages 125-134, December.
    14. Yabo Luo, 2017. "Nested optimization method combining complex method and ant colony optimization to solve JSSP with complex associated processes," Journal of Intelligent Manufacturing, Springer, vol. 28(8), pages 1801-1815, December.
    15. Müller, David & Müller, Marcus G. & Kress, Dominik & Pesch, Erwin, 2022. "An algorithm selection approach for the flexible job shop scheduling problem: Choosing constraint programming solvers through machine learning," European Journal of Operational Research, Elsevier, vol. 302(3), pages 874-891.
    16. Ivens, Philip & Lambrecht, Marc, 1996. "Extending the shifting bottleneck procedure to real-life applications," European Journal of Operational Research, Elsevier, vol. 90(2), pages 252-268, April.
    17. Blazewicz, Jacek & Domschke, Wolfgang & Pesch, Erwin, 1996. "The job shop scheduling problem: Conventional and new solution techniques," European Journal of Operational Research, Elsevier, vol. 93(1), pages 1-33, August.
    18. El-Ghazali Talbi, 2016. "Combining metaheuristics with mathematical programming, constraint programming and machine learning," Annals of Operations Research, Springer, vol. 240(1), pages 171-215, May.
    19. Demirkol, Ebru & Mehta, Sanjay & Uzsoy, Reha, 1998. "Benchmarks for shop scheduling problems," European Journal of Operational Research, Elsevier, vol. 109(1), pages 137-141, August.
    20. Edward Rothberg, 2007. "An Evolutionary Algorithm for Polishing Mixed Integer Programming Solutions," INFORMS Journal on Computing, INFORMS, vol. 19(4), pages 534-541, November.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:191:y:2008:i:3:p:705-735. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.