IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v184y2011i1p121-13510.1007-s10479-010-0715-0.html
   My bibliography  Save this article

Using local search to speed up filtering algorithms for some NP-hard constraints

Author

Listed:
  • Philippe Galinier
  • Alain Hertz
  • Sandrine Paroz
  • Gilles Pesant

Abstract

This paper proposes to use local search inside filtering algorithms of combinatorial structures for which achieving a desired level of consistency is too computationally expensive. Local search quickly provides supports for many variable-value pairs, thus reducing the effort required to check and potentially filter the rest of them. The idea is demonstrated on the SomeDifferent constraint, a graph coloring substructure. An experimental evaluation confirms its significant computational gain in many cases. Copyright Springer Science+Business Media, LLC 2011

Suggested Citation

  • Philippe Galinier & Alain Hertz & Sandrine Paroz & Gilles Pesant, 2011. "Using local search to speed up filtering algorithms for some NP-hard constraints," Annals of Operations Research, Springer, vol. 184(1), pages 121-135, April.
    • Handle: RePEc:spr:annopr:v:184:y:2011:i:1:p:121-135:10.1007/s10479-010-0715-0
    DOI: 10.1007/s10479-010-0715-0
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-010-0715-0
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-010-0715-0?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    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. Michel Gendreau & Alain Hertz & Gilbert Laporte, 1994. "A Tabu Search Heuristic for the Vehicle Routing Problem," Management Science, INFORMS, vol. 40(10), pages 1276-1290, October.
    Full references (including those not matched with items on IDEAS)

    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. Jozefowiez, Nicolas & Semet, Frédéric & Talbi, El-Ghazali, 2009. "An evolutionary algorithm for the vehicle routing problem with route balancing," European Journal of Operational Research, Elsevier, vol. 195(3), pages 761-769, June.
    2. Schmid, Verena & Doerner, Karl F. & Laporte, Gilbert, 2013. "Rich routing problems arising in supply chain management," European Journal of Operational Research, Elsevier, vol. 224(3), pages 435-448.
    3. Moreira, Mayron César O. & Costa, Alysson M., 2013. "Hybrid heuristics for planning job rotation schedules in assembly lines with heterogeneous workers," International Journal of Production Economics, Elsevier, vol. 141(2), pages 552-560.
    4. Sahar Validi & Arijit Bhattacharya & P. J. Byrne, 2020. "Sustainable distribution system design: a two-phase DoE-guided meta-heuristic solution approach for a three-echelon bi-objective AHP-integrated location-routing model," Annals of Operations Research, Springer, vol. 290(1), pages 191-222, July.
    5. C Schumacher & P R Chandler & M Pachter & L S Pachter, 2007. "Optimization of air vehicles operations using mixed-integer linear programming," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(4), pages 516-527, April.
    6. Nair, D.J. & Grzybowska, H. & Fu, Y. & Dixit, V.V., 2018. "Scheduling and routing models for food rescue and delivery operations," Socio-Economic Planning Sciences, Elsevier, vol. 63(C), pages 18-32.
    7. Aringhieri, Roberto & Cordone, Roberto & Grosso, Andrea, 2015. "Construction and improvement algorithms for dispersion problems," European Journal of Operational Research, Elsevier, vol. 242(1), pages 21-33.
    8. César Rego, 1998. "A Subpath Ejection Method for the Vehicle Routing Problem," Management Science, INFORMS, vol. 44(10), pages 1447-1459, October.
    9. Tino Henke & M. Grazia Speranza & Gerhard Wäscher, 2014. "The Multi-Compartment Vehicle Routing Problem with Flexible Compartment Sizes," FEMM Working Papers 140006, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    10. Atieh Madani & Rajan Batta & Mark Karwan, 2021. "The balancing traveling salesman problem: application to warehouse order picking," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(2), pages 442-469, July.
    11. Barbara De Rosa & Gennaro Improta & Gianpaolo Ghiani & Roberto Musmanno, 2002. "The Arc Routing and Scheduling Problem with Transshipment," Transportation Science, INFORMS, vol. 36(3), pages 301-313, August.
    12. R. Baldacci & E. Hadjiconstantinou & A. Mingozzi, 2004. "An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation," Operations Research, INFORMS, vol. 52(5), pages 723-738, October.
    13. Müller, Juliane, 2010. "Approximative solutions to the bicriterion Vehicle Routing Problem with Time Windows," European Journal of Operational Research, Elsevier, vol. 202(1), pages 223-231, April.
    14. Yin, Yunqiang & Li, Dongwei & Wang, Dujuan & Ignatius, Joshua & Cheng, T.C.E. & Wang, Sutong, 2023. "A branch-and-price-and-cut algorithm for the truck-based drone delivery routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1125-1144.
    15. Nourelfath, Mustapha & Châtelet, Eric & Nahas, Nabil, 2012. "Joint redundancy and imperfect preventive maintenance optimization for series–parallel multi-state degraded systems," Reliability Engineering and System Safety, Elsevier, vol. 103(C), pages 51-60.
    16. Z Fu & R Eglese & L Y O Li, 2008. "A unified tabu search algorithm for vehicle routing problems with soft time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(5), pages 663-673, May.
    17. Angelelli, Enrico & Grazia Speranza, Maria, 2002. "The periodic vehicle routing problem with intermediate facilities," European Journal of Operational Research, Elsevier, vol. 137(2), pages 233-247, March.
    18. Simon Emde, 2017. "Scheduling the replenishment of just-in-time supermarkets in assembly plants," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(1), pages 321-345, January.
    19. Baldacci, R. & Dell'Amico, M., 2010. "Heuristic algorithms for the multi-depot ring-star problem," European Journal of Operational Research, Elsevier, vol. 203(1), pages 270-281, May.
    20. Olli Bräysy & Michel Gendreau, 2002. "Tabu Search heuristics for the Vehicle Routing Problem with Time Windows," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 10(2), pages 211-237, December.

    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:spr:annopr:v:184:y:2011:i:1:p:121-135:10.1007/s10479-010-0715-0. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.