×

zbMATH — the first resource for mathematics

LocalSolver 1.x: A black-box local-search solver for 0-1 programming. (English) Zbl 1231.90318
Summary: This paper introduces LocalSolver 1.x, a black-box local-search solver for general 0-1 programming. This software allows OR practitioners to focus on the modeling of the problem using a simple formalism, and then to defer its actual resolution to a solver based on efficient and reliable local-search techniques. Started in 2007, the goal of the LocalSolver project is to offer a model-and-run approach to combinatorial optimization problems which are out of reach of existing black-box tree-search solvers (integer or constraint programming). Having outlined the modeling formalism and the main technical features behind LocalSolver, its effectiveness is demonstrated through an extensive computational study. The version 1.1 of LocalSolver can be freely downloaded at http://www.localsolver.com and used for educational, research, or commercial purposes.

MSC:
90C27 Combinatorial optimization
90C10 Integer programming
90C90 Applications of mathematical programming
90B90 Case-oriented studies in operations research
90-04 Software, source code, etc. for problems pertaining to operations research and mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aarts E, Lenstra J (1997) Local search in combinatorial optimization. In: Aarts E, Lenstra J (eds) Local search in combinatorial optimization, wiley-interscience series in discrete mathematics and optimization. Wiley, Chichester · Zbl 0869.00019
[2] Benoist T, Bourreau E (2008) Fast global filtering for eternity II. Constraint Program Lett 3: 35–50
[3] Benoist T, Estellon B, Gardi F, Jeanjean A (2009a) High-performance local search for solving inventory routing problems. In: Stützle T, Birattari M, Hoos H (eds) Proceedings of SLS 2009, the 2nd international workshop on engineering stochastic local search algorithms, Springer, Lecture Notes in Computer Science, vol 5752, pp 105–109
[4] Benoist T, Jeanjean A, Molin P (2009b) Minimum formwork stock problem on residential buildings construction sites. 4OR-Q J Oper Res 7: 275–288 · Zbl 1176.90372 · doi:10.1007/s10288-008-0092-6
[5] Cahon S, Melab N, Talbi EG (2004) ParadisEO: a framework for the reusable design of parallel and distributed metaheuristics. J Heuristics 10(3): 357–380 · doi:10.1023/B:HEUR.0000026900.92269.ec
[6] Caseau Y, Laburthe F, Silverstein G (1999) A meta-heuristic factory for vehicle routing problems. In: Proceedings of CP 1999, Springer, Lecture Notes in Computer Science, vol 1713, pp 144–158
[7] Comet Tutorial (2010) Comet 2.1 Tutorial. Dynadec Decision Technologies Inc., Providence, RI, 581 pages, http://www.dynadec.com
[8] Di Gaspero L, Schaerf A (2003) EasyLocal++: an object-oriented framework for flexible design of local search algorithms. Softw Pract Exp 33(8): 733–765 · Zbl 01963260 · doi:10.1002/spe.524
[9] Dotú I, Van Hentenryck P (1999) Scheduling social golfers locally. In: Proceedings of CPAIOR 2005, Springer, Lecture Notes in Computer Science, vol 3524, pp 155–167 · Zbl 1133.90336
[10] Estellon B, Gardi F, Nouioua K (2006) Large neighborhood improvements for solving car sequencing problems. RAIRO Oper Res 40(4): 355–379 · Zbl 1151.90523 · doi:10.1051/ro:2007003
[11] Estellon B, Gardi F, Nouioua K (2008) Two local search approaches for solving real-life car sequencing problems. Eur J Oper Res 191(3): 928–944 · Zbl 1156.90361 · doi:10.1016/j.ejor.2007.04.043
[12] Estellon B, Gardi F, Nouioua K (2009) High-performance local search for task scheduling with human resource allocation. In: Proceedings of SLS 2009, Springer, Lecture Notes in Computer Science, vol 5752, pp 1–15
[13] Hnich B, Miguel I, Gent I, Walsh T (2009) CSPLib: a problem library for constraints. http://www.csplib.org
[14] Michel L, Van Hentenryck P (2000) Localizer. Constraints 5(1/2): 43–84 · Zbl 0988.90015 · doi:10.1023/A:1009818401322
[15] Perron L, Shaw P (2004) Combining forces to solve the car sequencing problem. In: Proceedings of CPAIOR 2004, Springer, Lecture Notes in Computer Science, vol 3011, pp 225–239 · Zbl 1094.68651
[16] Perron L, Shaw P, Furnon V (2004) Propagation guided large neighborhood search. In: Proceedings of CP 2004, Springer, Lecture Notes in Computer Science, vol 3258, pp 468–481 · Zbl 1152.68572
[17] Prandtstetter M, Raidl G (2008) An integer linear programming approach and a hybrid variable neighborhood search for the car sequencing problem. Eur J Oper Res 191(3): 1004–1022 · Zbl 1156.90321 · doi:10.1016/j.ejor.2007.04.044
[18] Rego C, Glover F (2002) Local search and metaheuristics. In: Gutin G, Punnen A (eds) The traveling salesman problem and its variations. Kluwer Academic Publishers, Dordrecht, pp 105–109
[19] Schaus P, Deville Y (2008) Hybridation de la programmation par contraintes et d’un voisinage à très grande taille pour Eternity II. In: Proceedings of JFPC 2008, pp 115–122
[20] Schaus P, Hentenryck PV, Monette JN, Coffrin C, Michel L, Deville Y (2011) Solving steel mill slab problems with constraint-based techniques: CP, LNS, CBLS, to appear in Constraints
[21] Selman B, Kautz H, Cohen B (1996) Local search strategies for satisfiability testing. In: Johnson D, Trick M (eds) Cliques, coloring, and satisfiability: 2nd DIMACS implementation challenge, DIMACS series in discrete mathematics and theoretical computer science, vol 26. AMS, Providence
[22] Van Hentenryck P, Michel L (2005) Constraint-based local search. The MIT Press, Boston · Zbl 1153.90582
[23] Van Hentenryck P, Michel L (2007) Synthesis of constraint-based local search algorithms from high-level models. In: Proceedings of AAAI 2007, pp 273–279
[24] Van Hentenryck P, Michel L (2008) The steel mill slab design problem revisited. In: Proceedings of CPAIOR 2008, Lecture Notes in Computer Science, vol 5015, pp 377–381
[25] Vasquez M, Hao JK (2001) A ”logic-constrained” knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite. Comput Optim Appl 20(2): 137–157 · Zbl 0983.90082 · doi:10.1023/A:1011203002719
[26] Voudouris C, Dorne R, Lesaint D, Liret A (2001) iOpt: a software toolkit for heuristic search methods. In: Proceedings of CP 2001, Lecture Notes in Computer Science, vol 2239, pp 716–730 · Zbl 1067.68681
[27] Walser J, Iyer R, Venkatasubramanyan N (1998) An integer local search method with application to capacitated production planning. In: Proceedings of AAAI 1998, pp 373–379
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.